Veikko Siivola
Tietojenkäsittelytieteen laitos
Helsingin yliopisto
Seminaariesitelmä Salakirjoituksen historia
9. maaliskuuta 2000
Veikko.SiivolaPOISTA@iki.fi
Erilaisia salakirjoitusmenetelmiä on käytetty viestien salaamiseen jo muinaisen Egyptin ja Rooman ajoista asti. Hallitsijoiden lähetit ovat kuljettaneet viestejä, jotka on salattu, etteivät mahdolliset viholliset saisi niiden sisältöä selville. On myös käytetty erilaisia menetelmiä salaisen viestin olemassaolon kätkemiseen.
Salakirjoitusmenetelmät ovat vähitellen kehittyneet antiikin ajoista asti ja myöhemmin kehittyi kryptologia, joka tutkii salakirjoitusta. Tietokoneiden aikana salakirjoitusmenetelmät ja niiden tutkimus on kehittynyt huomattavasti ja salakirjoitusta käytetään monissa eri sovelluksissa.
Muinaisen Egyptin kulttuuri on vanhin, josta on olemassa tietoa salakirjoituksen käytöstä. Salakirjoitusmenetelmä oli epästandardien tavallisesta poikkeavien hieroglyfien käyttö kirjoituksessa. Myös Intiassa on tunnettu salakirjoitus. Yatsyajanan teoksessa Kama Sutra mainitaan salakirjoitus, joka on yksi 64 taidosta, joita naisen tulisi osata ja harjoitella. Muita taitoja tässä luettelossa ovat laulumusiikki ja kielelliset ja sanalliset ongelmat.
Latinan kielen sana crypta tulee kreikankielestä ja siitä on peräisin etuliite krypto, joka tarkoittaa salaista.
Steganografia tarkoittaa salaisen viestin olemassaolon kätkemistä. Historiassa tunnetaan jo antiikin ajoilta esimerkkejä steganografian käytöstä. Herodotos kertoi eräästä tapahtumasta persialaissotien ajalta. Sanoman kuljettamiseen käytettiin luotettavaa orjaa. Hänen päänsä ajeltiin paljaaksi ja sanoma tatuoitiin päänahkaan. Sen jälkeen tukan annettiin kasvaa ja orja lähti matkaan. Perillä hänen päänsä ajeltiin taas paljaaksi ja viesti voitiin lukea.
Spartalaiset olivat ensimmäisiä, jotka käyttivät salakirjoitusta sotilaallisiin tarkoituksiin. 400-luvulla ekr he keksivät laitteen skytale. Puisen sauvan ympärille kiedottiin papyrus- tai pergamenttinauhaa, johon viesti kirjoitettiin sauvan pituussuunnassa. Sen jälkeen nauha otettiin pois sauvan ympäriltä. Tämän jälkeen nauhassa näytti olevan jono merkityksettömiä kirjaimia. Viestin lukija tarvitsi samanpaksuisen sauvan, jonka ympärille hän kietoi nauhan. ja sitten hän saattoi lukea viestin sauvan pituussuuntaan. Jos sauva oli eripaksuinen, kirjaimet eivät asettuneet samoille kohdille kuin ne olivat viestin kirjoittajan sauvan ympärillä eikä viestistä saanut selvää.
Polybius keksi signalointimenetelmän, jota alettiin käyttää laajasti salakirjoitusmenetelmänä. Hän järjesti kirjaimet taulukkoon. Englannin kielen aakkoset voitaisiin merkitä Polybiuksen menetelmän mukaan seuraavasti taulukkoon, jossa i ja j on yhdistetty.[KAHN83-86]
1 2 3 4 5 1 a b c d e 2 f g h ij k 3 l m n o p 4 q r s t u 5 v w x y z
Kirjaimia alettiin merkitä niiden numerokoodeilla. e on 15 ja m on 32. Polybius ehdotti, että numeroita voitaisin viestittää vasemmassa ja oikeassa kädessä olevilla soihduilla pitkien matkojen etäisyydelle. Nykyajan salakirjoituksen tutkijat ovat löytäneet Polybiuksen nelöistä monia piirteitä, joita hyödynnetään nykyaikana kryptografiassa. Kirjaimet muutetaan numeroiksi, erilaisten merkkien lukumäärää voidaan vöhentää ja kirjain voidaan jakaa kahteen erilliseen osaan.
Gaius Julius Caesar on jättänyt nimensä kryptografian historiaan. Hänen keksimänsä korvausmenetelmä tunnetaan nimellä Caesar-salakirjoitus. Tässä menetelmässä jokainen kirjain korvattiin aakkostossa kolme kirjainta seuraavana olevalla merkillä. Caesarin meneltelmässä a korvataan kirjaimella D, b kirjaimella E, jne. Kirjain X korvataan kirjaimella A.
selväkieli abcdefghijklmnopqrstuvwxyz salakieli DEFGHIJKLMNOPQRSTUVWXYZABCSanoma Omnia Gallia est divisa in partes tres olisi salattuna RPQLD JDOOLD HVW GLYLVD LQ SDUWHV WUHV. Korvausaakkosto voi alkaa muullakin merkillä kuin kirjaimella D. Myös näitä korvausmenetelmiä kutsutaan nimellä Caesar-salakirjoitus.
Keskiajalla tiede kehittyi nopeimmin arabien keskuudessa ja Kryptologia sai siellä alkunsa. Arabit olivat ensimmäisiä, jotka keksivät ja merkitsivät muistiin kryptoanalyysissä käytettäviä menetelmiä. Vuonna 855 Abu Bakr Ahmad ben `Ali ben Wahshiyya an-Nabati julkaisi kirjoituksia salakoodeista, joita käytettiin enimmäkseen magiassa.
Kun hän keksi, miten salakirjoitusta voidaan yrittää purkaa, hän alkoi miettiä keinoja, miten salauksen purkua voidaan vaikeuttaa. Hän tutki erilaisia korvausmenetelmiä, transpositiota ja näkymättömiä musteita. Transpositiossa kirjainten järjestystä sanoissa muutetaan. Korvausmenetelmässä merkkejä korvataan toisilla jonkin säännön määrittelemällä tavalla.
Alberti valmisti kuparista kaksi ympyrälevyä, jotka ovat samalla akselilla. Levyjen ulkokehät on jaettu 24 osaan ja toinen levy on hiukan suurempi. Isomman levyn ulkokehällä on kirjaimia järjestyksessä ja myös neljä numeroa. Pienemmän levyn ulkokehällä on kirjaimia satunnaisesti valitussa järjestyksessä. Salattuja sanomia vaihtavilla henkilöillä on oltava saamnlaiset levyt ja on sovittava yhteisestä indeksikirjaimesta.
Olkoon indeksikirjain k. Kun viestin kirjoitus aloitetaan, kiekolle valitaan jokin alkuasento. Käännetään sisempi kiekko asentoon, jossa k on M-kirjaimen kohdalla. Sanoma aloitetaan isolla M-kirjaimella. Sen jälkeen sanomaan kirjoitetaan tekstiä siten, että ulkokehän kirjaimen tilalle kirjoitetaan pienemmän levyn kehällä vastaavassa kohdassa oleva kirjain. Kiekon asentoa muutetaan kolmen tai neljän sanan välein. Pienemmän kiekon uutta asentoa vastaava kirjain merkitään taas isolla uuden sanan alkuun. Tämä oli ensimmäinen moniaakkostoinen salakirjoitusmenetelmä.
Menetelmää kehitti edelleen saksalainen Trithemius, joka syntyi 2. helmikuuta vuonna 1462. Hän julkaisi ensimmäisen painetun kryptologian kirjan, jonka nimi on Polygraphiae.
Kirjassa Steganographia Trithemius selosti menetelmiä salaisten ja piilotettujen sanomien kirjoitusmenetelmiä. Pitkän miettimisen jälkeen hän oli tullut siihen johtopäätökseen, että on olemassa asioita, joita ei voi tietää. Kerrotaan, että vuonna 1499 eräs henki opetti unessa hänelle niitä ja hän merkitsi niitä muistiin tähän kirjaan. Sen parissa ensimmäisessä luvussa hän kertoo, miten salainen viesti voidaan piilottaa tekstiin siten, että vain tietyt kirjaimet sanoissa ovat merkityksellisiä ja muut merkityksettömiä. Tekstistä voidaan löytää näiden sääntöjen avulla sanoma jolla ei ole yhteyttä asiaan, jota teksti käsittelee. Piilotettu merkityksellinen sanoma voidaan löytää poimimalla vaikkapa tekstin joka toisesta sanasta joka toinen kirjain.
Vuonna 1518 julkaistussa kirjassa Polygraphiae Trithemius selosti salakirjoitusmenetelmiä, jotka perustuvat seuraavaan taulukkoon. Rivejä on yhtä monta kuin kirjaimia on aakkostossa.
abcdefghiklmnopqurstuxyzw bcdefghiklmnopqurstuxyzwa cdefghiklmnopqurstuxyzwab ... zwabcdefghiklmnopqurstuxy wabcdefghiklmnopqurstuxyzKukin rivi määrittelee Caesar-menetelmällä tapahtuvan korvauksen. Trithemius käytti taulua siten, että viestin ensimmäinen kirjain korvataan ensimmäisen rivin aakkosta vastaavan paikan kirjaimella, viestin toinen kirjain toisella rivillä olevalla merkille, jne. Kun Albertin menetelmässä korvaus vaihtui muutaman sanan välein, tässä se vaihtui joka kirjaimella. Selväkieli Hunc caveto virum muuttui salaviestiksi HXPF GFBMCZ FUEIB.
Giovan Batista Belaso kehitti edelleen korvausmenetelmiä. Sen sijaan, että korvausaakkostoa vaihdettiin taulun rivien mukaan käytettiin helposti muistettavaa avainta, joka oli jono sanoja.
Digrafisen salausmenetelmän keksi Giovanni Battista Porta [KAHN137-143], joka syntyi Napolissa vuonna 1535. Hän oli kiinnostunut luonnon mysteereistä ja alkoi tutkia luontoa ja sen ilmiöitä kokeellisin menetelmin. Porta kehitti näkymättömiä musteita, joiden reseptejä julkaistiin kirjan Magia Naturalis 16. osassa. Digrafisessa menetelmässä kaksi kirjainta korvataan uudella merkillä.
Vuonna 1563 Porta julkaisi 28-vuotiaana kryptologiaa käsittelevän kirjan De Furtivis Literarum Notis. Siinä hän selostaa antiikin salakirjoitusmenetelmiä, uudempia menetelmiä, kryptoanalyysia ja lingvistiikan erityispiirteitä, joita voidaan käyttää. Hän luokitteli salakirjoitusmenetelmät kolmeen ryhmään seuraavasti.
Babbagen kryptografiaa käsitteleviä töitä ei julkaistu eikä niillä ollut merkittävää asemaa kryptografian kehityksessä, mutta hänen keksimänsä ideat olivat hyvin edistyksellisiä. Eräässä julkaisemassaan esseessä hän kertoi, että salasanomien purkaminen oli eräs haastavimmista ja kiinnostavimmista taidoista.
Saksalaisilla oli Enigma laajassa käytössä toisen maailmansodan aikana. Liittoutuneet onnistuivat murtamaan Enigman Englannissa Bletchley Parkissa Alan Turingin ja monen muun eri alan asiantuntijan yhteistyönä. Vielä sodan jälkeen englantilaiset salasivat pitkään sen, että Enigma onnistuttiin murtamaan ja antoivat Enigma-laitteita brittiläisen kansainyhteisön maiden käyttöön antaen heidän ymmärtää, että ne ovat turvallisia. Englannin tiedustelupalvelu sai näin tilaisuuden kerätä tietoja.
Informaatioteoria tutkii kaikenlaiseen viestintään liittyviä matemaattisia lakeja. Sen käyttö on laajentunut puhelin- ja lennätinteknikasta monille muille tieteenaloille. Nykyään sitä käytetään myös psykologiassa, lingvistiikassa ja tilastotieteessä. Ihmisten välisessä kommunikaatiossa on runsaasti redunsanssia. Tietoa voitaisiin vähentää ilman, että sanoman ymmärrettävyys vaarantuu. Satunnaiset kirjoitusvirheet eivät useinkaan haittaa viestin ymmärrettävyyttä. Hyvä esimerkki redundanssista on kirjainpari qu englannin kielessä. Kirjaimen q perässä on aina u. Tekstissä esiintyvä redundanssi johtuu kieliopista ja sen asettamista säännöistä. Mielivaltaiset kirjainyhdistelmät eivät ole mahdollisia sanoissa. Kielioppi määrittelee myös säännöt, miten sanoja voidaan sijoittaa lauseisiin. Jotkut äänneyhdistelmät ovat ihmiselle helpompia lausua ja tunnistaa kuin toiset ja luonnolliset kielet suosivat niitä. Myös tämä lisää kielen redundanssia.
Jos sanoman salauksen jälkeen salakielisessä sanomassa on redundanssia jäljellä, se helpottaa huomattavasti kryptoanalyysiä. Yksinkertainen esimerkki tästä on Caesar-salakirjoitus. Jotta salakirjoitus olisi vaikea murtaa, hyvissä salausmenetelmissä redundanssi pyritään hävittämään mahdollisimman tehokkaasti.
DES [2],[DES] on kehitetty 1970-luvulla ja se on lyhenne sanoista Data Encryption Standard. NIST (National Institute of Standards and Technology) on vahvistanut sen standardiksi ja käytettäväksi muuhun kuin korkean tason turvallisuutta vaativiin sovelluksiin. DES on lohkosalaus, jossa lohkon pituus on 64 bittiä ja avaimen pituus 56 bittiä. Salaus ja purku tapahtuvat samalla algoritmilla. DES koostuu 16 kierroksesta, joissa tehdään muunnoksia ja permutaatioita. Nykyisin DES ei ole enää turvallinen. Se on mahdollista murtaa, jos on käytettävissä suuri määrä tietokonekapasiteettia.
Esimerkkejä muista symmetrisistä salausalgoritmeista ovat 3DES, IDEA ja Blowfish. [2] 3DES on tehollisesti 112-bittinen salaus, jossa ensin tehdään DES-salaus avaimella k1 ja purku avaimella k2. Sen jälkeen tehdään taas salaus avaimella k1.
RSA [2],[RSA] on eräs tunnetuimpia julkisen avaimen salausalgoritmeja. Se perustuu siihen, että suuria kokonaislukuja on hyvin vaikea jakaa alkutekijöihin. RSA:n kehittivät ja julkaisivat vuonna 1977 Ron Rivest, Adi Shamir ja Leonard Adleman. Algoritmi nimettiin suunnittelijoidensa mukaan. Vuosia kestänyt kryptoanalyysi ei ole todistanut algoritmia turvalliseksi, mutta ei ole myöskään löytänyt siitä heikkouksia.
Valitaan kaksi suurta alkulukua p ja q. n = pq. fi(n) = (p-1)*(q-1). Valitaan e, (1 < e < fi(n) ) siten, että gcd(e,fi(n)) = 1. gcd on suurin yhteinen jakaja. Lasketaan d = (1/e) mod fi(n). Julkinen avain on (e,n) ja yksityinen avain (d,n). Unohdetaan p,q ja fi(n).
RSA-algoritmia voidaan käyttää salakirjoitukseen ja digitaaliseen allekirjoitukseen. Algoritmia voidaan pitää turvallisena, jos avaimen pituus on vähintään 1024 bittiä. RSA on patentoitu USA:ssa ja sen patentti vanhenee 20. syyskuuta. 2000. Muita julkisen avaimen algoritmeja ovat Diffie-Hellman ja El Gamal.
Ennen julkisen avaimen salakirjoitusmenetelmien keksimistä salaukseen ja purkuun käytettiin samaa koodia. Jos n eri osapuolta haluaisi kommunikoida turvallisesti jonkun muun kanssa, tarvittaisiin n*(n-1)/2 salausavainta. Niiden hallinta on epäkäytännöllistä ja hankalaa.
Julkisen avaimen salausmenetelmät helpottivat tätä ongelmaa. Tarvitaan enää n avainparia. Kun Alice haluaa lähettää Bobille salatun viestin, hän salaa sen Bobin julkisella avaimella ja lähettää sen Bobille. Bob voi purkaa viestin omalla salaisella avaimellaan. Alice ja Bob ovat julkaisseet omat julkiset avaimet. Tässä on vielä sekin ongelma, miten voidaan varmistua, ettei Charlie tee avainparia ja julkaise Alicen nimissä julkista avainta. Alice ja Bob voivat tavata henkilökohtaisesti ja vaihtaa avaimia. Se ei aina ole mahdollista. Toinen ratkaisu on käyttää luotettua kolmatta osapuolta, joka varmentaa digitaalisella allekirjoituksellaan, että avain todella kuuluu sille henkilölle, joka sen omistaa. Tätä menetelmää käytetään esimerkiksi sähköisessä henkilökortissa, jonka avaimet varmentaa väestörekisterikeskus. PGP:ssa käyttäjät voivat päättää, kehen luottavat. Sen lisäksi, että avain voidaan varmentaa henkilökohtaisella tapaamisella tai puhelimella, käyttäjä voi päättää, luottaako johonkin kaveriisa ja pitää hänen allekirjoituksellaan varmentamaa avainta luotettavana.
Tietokoneiden tehon kasvaessa myös salakirjoitusmentelmiä pitää kehittää. Avainten pituuksia on kasvatettava ja uusia salausmenetelmiä joudutaan kehittämään, jos keksitään keinoja murtaa vanhoja salausmentelmiä Hyvän salakirjoituksen turvallisuus ei perustu siihen, että algoritmi on salainen vaan salaiseen avaimeen ja siihen, että salauksen murtaminen ei ole järkevässä ajassa mahdollista.
| Kryptografia (cryptography) | tiede, joka tutkii miten viestejä voidaan salata ja pitää ulkopuolisilta salassa. |
| Kryptoanalyysi (cryptoanalysis) | tutkii, miten salattuja viestejä voidaan purkaa tietämättä avainta |
| Kryptologia (cryptology) | matemaattinen tiede, joka tutkii salakirjoitusta |
| Steganografia (steganography) | menetelmä salatun sanoman kätkemiseksi, niin, että sen olemassaolo on salattu |
| selväkieli (cleartext) | alkuperäinen selväkielinen sanoma |
| salakieli (ciphertext) | salakirjoitettu sanoma |
| [KAHN1] |
The Codebreakers, David Kahn, The MacMillacn Company, New York, 1972 |
| [2] |
Applied Cryptography, Bruce Schneier, John Wiley & Sons, Inc. 1996 |
| [3] |
Time-Line of Cryptography < http://allen.comm.virginia.edu/dsc4y/ET/overview.htm#history>
|
| [4] |
About Enigma and Its Decryption < http://www.attlabs.att.co.uk/andyc/enigma/about_enigma.html>
|
| [DES] | National Bureau of Standards, NBS FIPS PUB 46. "Data Encryption Standard," National Bureau of Standards, U.S. Department of Commerse, Jan 1977 |
| [RSA] | R.J. Rivest, A. Shamir, and L.M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, v. 21, n. 2, Feb 1978, pp. 120-126. |
