tiistai 7. helmikuuta 2017

Salakirjoituksen lyhyt historia

Ihmiset tuntuvat tykkäävän salaisuuksista. Tällä kertaa en tarkoita sitä, minkäväriset villasukat paljastuvat joulupaketista tai arvuuttelua, kenen kanssa naapuri palasi pikkujouluista, vaan sellaisia juttuja kuin kauppasopimuksen ehdot tai tulevan hyökkäyksen ajankohta. Ilmeisesti näiden salassapysymisestä on jonkinlaista strategista hyötyä. (Kuten tietysti naapurinkin tapauksessa.)

Salakirjoitus on iloista matemaattista kissa ja hiiri -leikkiä: toinen osapuoli yrittää saada viestinsä salattua ja toinen purettua ne. Sivutuotteena syntyy uutta matematiikkaa ja tietokoneen kaltaisia työkaluja, joista on hyötyä esimerkiksi kissavideoiden katsomisessa täydellisen salattua yhteyttä pitkin.

Antiikkinen salaus

Tässä tekstissä ohitamme kaikki salaukset, jotka sotkevat kirjainten järjestyksen. Niitäkin on käytetty menestyksellä jo antiikin ajoista lähtien, mutta tämä tarina keskittyy menetelmiin, joissa kirjaimia vaihdetaan toisiksi.

Ihan yksinkertaisin salausmenetelmä, nykymittapuulla suorastaan alakoulutasoa, tunnetaan Julius Caesarin (100-44 eaa.) mukaan Caesar-salauksena. Jokaista kirjainta muutetaan tietyn monta kirjainta johonkin suuntaan, esimerkiksi niin että viestistä ABC tulee DEF. Edellinen esimerkki käytti kolmen kirjaimen eroa kuten klassinen Caesar-salauskin, mutta myös muut vaihtoehdot ovat mahdollisia — nykyään suosittu on 13, jolla englannin 26 aakkosen "salaaminen" ja purkaminen tapahtuvat samalla tavalla.

Tämä ei ole läheskään ensimmäinen salausmenetelmä, mutta merkittävä siksi, että se on hyvä esimerkki aakkosia korvaavasta salauksesta. Menetelmän voi yleistää niin, että selkokielisen ja salatun tekstin aakkosten välillä on mielivaltainen yksi yhteen -vastaavuus. Tällöin suomen kielen aakkosille voisi kehittää $29! \approx 10^{31}$ erilaista salausta. Täydellistä?

Ei alkuunkaan. Yksinkertainen aakkosten korvaaminen säilyttää sanojen sisäiset suhteet, kuten vaikkapa kirjainparit. Pahempana ongelmana myös kirjainten esiintymistiheys säilyy samana: jos Q on 11 % kirjaimista, se todennäköisesti vastaa A:ta tai I:tä.[1] Frekvenssianalyysi on tunnettu jo keskiajan arabimatemaatikoista alkaen.

Caesarille tämä ei kuitenkaan muodostanut ongelmaa hyvästä syystä. Useimmat viholliset eivät osanneet lukea, muunnetusta latinasta puhumattakaan.

Monta antiikkista salausta

Seuraava menetelmä perustuu yksinkertaisesti useampaan yhtäaikaiseen Caesar-salaukseen. Valitaan avainsana, vaikkapa ABEL. Tekstin ensimmäinen kirjain pysyy muuttumattomana, koska A on ensimmäinen aakkonen; seuraavaa kasvatetaan yhdellä, kolmatta neljällä ja sitä seuraavaa yhdellätoista. Sitten aloitetaan avainsana taas alusta.

Näinkin simppeli tapa riittää kumoamaan yksinkertaisen frekvenssianalyysin. Menetelmä kehitettiin ja kuvattiin 1500-luvulla, ja se pysyi pääosin murtamattomana pitkään — silloin tällöin sen lempinimikin oli "murtamaton salaus": le chiffre indéchiffrable.[2]

Valitettavasti nimi osoittautui 1800-luvun puolivälissä kehnoksi. Kun avaimen pituus tiedetään, frekvenssianalyysi toimii taas — kyseessähän on vain useampi vierekkäinen Caesar-salaus! Myös avaimen pituus selviää aika helposti: luonnollisessa kielessä on paljon yleisiä kirjainpareja. Osa niistä sattuu väistämättä samaan kohtaan toistettua avainta, joten myös salatusta tekstistä löytyy pareja. Niiden välisestä etäisyydestä voi päätellä avaimen pituuden.

Tässä menetelmässä on kuitenkin yksi käänne, jolla siitä saa todistettavasti täydellisen. Sitä ennen ei tosin voi olla mainitsematta Enigmaa.

Enigma-laite.

(Punishar/Wikimedia Commons. CC-BY-SA 4.0.)

Pulma, joka ratkaistiin

Enigma oli salakirjoituslaite, jota saksalaiset käyttivät toisessa maailmansodassa. Tarkkaan ottaen laitteita ei ollut yhtä, vaan siitä kehitettiin useita paranneltuja versioita, vaikka sitä pidettiinkin käytännössä murtamattomana. Tarinasta tekee hienon se, kuinka koodit murrettiin.

Enigma muistutti laitteena kirjoituskonetta, jossa näppäimen painaminen sytytti kirjainvalon. Näppäimestä sähkövirta kulki kirjaimia keskenään vaihtavan kytkinlevyn kautta pyöriviin rattaisiin, joista jokainen toteutti yksinkertaisen kirjaimenvaihtosalauksen. Koska rattaita oli useampi ja ne pyörivät eri nopeuksilla, salaus muuttui joka painalluksella. Kytkinlevyn asetuksilla, rattaiden valinnalla useamman joukosta ja alkuasentojen säätämisellä saatiin lukemattomia salausmahdollisuuksia. Se oli laitteena todella hieno ja lähes täydellinen. Lähes.

Valitettavasti ihmiset ovat huonoja valitsemaan satunnaisia alkuasetuksia, varsinkin jos säännöt kieltävät edellisten osittaisenkin uudelleenkäytön. Tämä heikensi satunnaisuutta ja avasi polun paljon vakavamman virheen hyväksikäytölle: Enigman rakenteesta johtuen kirjain salakirjoitettiin aina jonain toisena kirjaimena, ei ikinä itsenään.

Jos selväkielisen sanoman osasta oli hyvä arvaus — ja liittoutuneilla usein oli, luokkaa "ei raportoitavaa" tai "säähavainto kello" tai muuten kaapattu viesti — riitti kokeilla asetuksia, kunnes yksikään oletettu selväkielinen ja salattu kirjain eivät olleet samoja. Asetusten kokeilemiseen britit rakensivat bombeja — tehokkaita laitteita, jotka hoitivat kokeilun, ja jotka olivat eräänlaisia tietokoneen esivanhempia.

Sanotaan, että koodinmurto-operaatio Bletchley Parkissa lyhensi sotaa kahdella vuodella. Minusta hämmästyttävintä on, että britit ja heitä työssä edeltäneet puolalaiset pystyivät selvittämään koodien rakennetta usein edes näkemättä laitteita!

Oikeasti täydellinen salaus

Kaikki äskeiset salaukset purkesivat menetelmän heikkouksiin tai huonosti käsiteltyihin salausavaimiin. Kuitenkin osoittautuu, että toisena esitelty salaus on tietyissä olosuhteissa täysin mahdoton purkaa: avaimen on oltava täysin satunnainen, yhtä pitkä kuin viesti, eikä sitä saa käyttää toiste.

Nykyaikaiset salaukset noudattavat yhtä tärkeää suunnitteluperiaatetta: vastapuoli tietää järjestelmästä kaiken paitsi salausavaimen. Menetelmät, täysin julkisesti kuvatut ja tutkitut sellaiset, perustuvat tehokkaaseen lukuteoriaan, jonka avulla salattua tekstiä on käytännössä mahdotonta erottaa satunnaisesta. Ne eivät oikeastaan ole hirveän kaukana Enigmasta, ainoastaan kompleksisuus on paljon suurempi. Jäljelle jää vain yksi kysymys: miten siirtää salausavain turvallisesti aikana, jona viestijät voivat olla eri puolilla maailmaa?

Ensi kerralla: Nerokas temppu avaimen sopimiseen.


[1] Suomen yleiskielen kirjaintilastoja. (Kielikello 1/1991)
[2] Tätä lempinimeä käytettiin oikeastaan kahdelle salaukselle, joista molemmat tunnettiin myös Vigenère-salauksina, vaikka vain toisen keksi Vigèrene. Asioiden nimeäminen tuntuu olevan vaikeaa.

Niin ja hei: IÅARHIDIÅVIVÅAÅÄP ZJÖÖJÅ ÄDÖVVC ÄDÖR DAÅ ÖVHÖÅBPPGÅC KRÅC BVIGÅC HMKMÅCVC.

Ei kommentteja:

Lähetä kommentti

Kommentit ovat moderoituja — yritän hyväksyä kommenttisi mahdollisimman pian. Voit kirjoittaa kommenttiin LaTeX-koodia tai yksinkertaista HTML-merkintää: lue lisää Kommentointi-sivulta.