Blaisen koodi Mystery Cache

Taistelu Pirkanmaan FTF-kuninkuudesta on käynyt kuumaksi. Geotiimit väijyvät ja salakuuntelevat toisiaan ja kätköntarkistajia.

On synkkä yö ja sinun vahtivuorosi Team GeoLokkien päämajassa radion äärellä. Vahvasta kahvista huolimatta olet jo puoliunessa vastaanottimen vierellä, kun yhtäkkiä kaiuttimesta kuuluu lupaava räsähdys ja pian alkaa tuttu morsekoodin piipitys.

Tiedätte, että kätköntarkistajat käyttävät Vigenèren autokey-salakirjoitusta. Geotiiminne koodarinörtti on tehnyt teille työkalun, jolla pystytte purkamaan koodia. Sitten vain hommiin ja selvittämään, missä kätkö sijaitsee!

• Viesti
• Purkutyökalu

(Jos nappasit morsekoodista alkuperäisen version ja saamasi koordinaatit ovat ihan oudot, laitapa viestiä niin kerron oikeat. Jos lataat morsekoodin vasta nyt, siitä tulee oikea tulos.)

Taustaa

Blaise de Vigenère oli ranskalainen diplomaatti 1500-luvulla. Vigenèren mukaan nimetty koodi on itse asiassa väärin nimetty: sen kehitti Giovanni Battista Bellaso. Mutta aloitetaanpa alusta!

Caesarin salakirjoitus

Caesar-salakirjoitus on klassinen salakirjoitus, jossa jokainen kirjain vaihdetaan aakkosissa kolme kirjainta myöhemmin olevaan kirjaimeen. A:sta tulee D, B:stä E ja niin edelleen.

Tällainen salakirjoitus on kuitenkin varsin helppo purkaa. Vaikka tarkoitettaisiin yleistystä, jossa ero voi olla kolmen kirjaimen sijasta mikä määrä kirjaimia tahansa, koodin purkaminen on sittenkin varsin yksinkertaista.

Kaikille geokätköilijöille tuttu Rot13-salaus, jolla vihjeet on koodattu, on muuten yksi erikoistapaus Caesarin salakirjoituksesta. Sen erikoisuus on siinä, että englannin 26-kirjaimisella aakkostolla koodaus on samalla purku, eli A on N ja N on A ja niin edelleen.

Polyalfabeettinen korvaus

Vigenèrelle virheellisesti nimetty koodi perustuu Caesarin salaukseen, mutta käyttää alkuperäisen viestin jokaiseen kirjaimeen eri koodausta. Sivun lopussa on esitetty taulukko, jota käytetään koodauksessa. Rivi katsotaan viestin kirjaimen mukaan ja sarake salausavaimen mukaan. Rivin ja sarakkeen kohtaamispaikasta löytyy sitten koodattu kirjain. Esimerkiksi jos viesti on "ostakaa makkaraa" ja salasana on "tapola", niin:

Viesti:   OSTAKAAMAKKARAA
Salasana: TAPOLATAPOLATAP
Tulos:    7S8OVATMPYWAAAP

Tällä tavalla sama kirjain koodautuu hieman eri tavoin ja toisaalta useista eri kirjaimista voi tulla sama kirjain. Tällä tavoin voidaan hukata alkuperäisen viestin kirjainten esiintymistiheyksiä – se on tavallinen tapa murtaa Caesar-koodauksia.

Lyhyt, toistuva avain aiheuttaa kuitenkin koodiin heikkouksia. 1863 Friedrich Kasiski julkaisi oman ratkaisunsa, jolla tällainen koodi ratkeaa melko helposti. Se edellyttää vain, että koodista löytyy toistuvia samanlaisia pätkiä: sellaisia syntyy, kun samalla pätkällä salasanaa on koodattu sama teksti. Näiden pätkien etäisyys toisistaan paljastaa avaimen pituuden ja loppu onkin sitten helppoa: kun avaimen pituus tiedetään, teksti voidaan jakaa erillisiksi Caesar-salauksiksi, jotka on helppo purkaa kirjainfrekvenssien perusteella. Ratkaisuun vaadittuja toistuvia pätkiä tulee melko helposti, jos koodattava teksti on pitkä ja avain on lyhyt.

Juokseva avain

Kasiskin testin pystyy torppaamaan käyttämällä juoksevaa avainta. Siinä avain on yhtä pitkä kuin koodattava teksti, eikä toistuvia pätkiä enää synny. Tässä menetelmässä on kuitenkin heikkoutensa, mikäli salasanateksti on luonnollista tekstiä – silloin siinä on tilastollista tietoa, jota voi hyödyntää.

Mikäli salausavain on satunnaista silppua, saadaan erittäin vahva, teoriassa murtamaton salaus. Sen voima ei kuitenkaan ole enää salausmenetelmässä, vaan itse avaimessa. Tällaista menetelmää kutsutaan nimellä "one-time pad" eli kertakäyttökoodi, ja sen ongelmat liittyvät koodien tuottamiseen ja turvalliseen käyttöön: jos samaa koodia käytetään kaksi kertaa, turvallisuus kärsii.

Teoriassa tällainen koodaus on kuitenkin mahdoton murtaa: jokainen kirjain voi vastata mitä tahansa kirjainta, jolloin raa'alla voimalla on mahdoton kokeilla kaikkia vaihtoehtoja.

Autokey-koodi

Nyt, lopulta, pääsemme itse asiaan. Blaise de Vigenère keksi nokkelan keinon tuottaa pitkiä salausavaimia. Autokey-koodissa avain muodostuu viestistä itsestään!

Girolamo Cardano, italiainen renessanssimies (kardaaniakselin ja monen muun hienon asian keksijä), keksi tämän ensin, mutta ratkaisevalla vialla: Cardanon koodi ei sisältänyt mitään ylimääräistä salasanaa, vaan viesti koodattiin itsellään.

Muuten ihan kiva, mutta tällaista viestiä vastaanottajan on ihan yhtä vaikea purkaa kuin kenenkään muunkaan. Ei näin!

De Vigènere (ja Giovan Battista Bellaso) keksi autokey-koodiin olennaisen parannuksen: lisätään alkuun sovittu kirjain, josta salasana lähtee. Jos siis viesti on "ostakaa makkaraa" ja sovittu kirjain on "q", salasana olisi "qostakaamakkaraa".

Tätä on tietysti näppärä täydentää lisäämällä salasanan alkuun yhden kirjaimen sijasta hieman pidempi salasana. Ta-daa! Tällainen salaus tässäkin tehtävässä on käytössä.

Autokey-koodin purkaminen ja murtaminen

Jos salasanan tietää, on koodi helppo purkaa. Jos koodi on "46BTKKAMMKUKRRA" ja tiedämme salasanan olevan "Q", katsomme vain taulukosta rivin Q ja sieltä sarakkeen, jonka kohdalla tulos on 4. Se on sarake "O", jolloin viestin ensimmäinen kirjain on O. Se on myös avaimen seuraava kirjain, joten rivillä 6 on O-kirjain sarakkeessa S. Viesti on nyt "OS", ja avaimen seuraava kirjain on S. Kokeile harjoituksena purkaa viestiä pari kirjainta eteenpäin, niin ymmärrät, miten prosessi toimii.

Mutta entäs jos salasanaa ei tiedä? No, tässä salausmenetelmässä on pieni ongelma. Kun avaimena käytetään viestin tekstiä, avaimen sisältöä voi arvuutella. Englanninkielisessä tekstissä avaimessa esiintyy varmaankin sana "THE".

Vielä parempi tietysti on, jos on joku käsitys – kuten tämän tehtävän tapauksessa on – siitä, mitä viestissä on, jolloin voi arvuutella viestin mahdollisesti sisältämiä sanoja. Kokeilemalla avaimessa mahdollisesti esiintyviä sanoja jokaisessa mahdollisessa kohdassa viestiä voi saada avattua esiin pieniä pätkiä selkokielistä viestiä.

Kun tällaisia pätkiä löytyy, tietää, että ne esiintyvät myös avaimessa, ja niillä voi saada lisää viestiä avattua ja niin edelleen – ja ennen pitkää viesti on murrettu. Tutkailemalla viestinpätkien etäisyyttä toisistaan koodissa voi saada selvitettyä, miten pitkä käytetty avain on. Se taas antaa lisää aseita ratkaisuun.

Käytännössä kynällä ja paperilla tällainen purkutyö on hidasta ja vaivalloista, etenkin jos viesti on pitkä. Tietokoneella työ käy helposti, kun erilaisia vaihtoehtoja voi kokeilla nopeasti. On helppo uskoa, että aikoinaan tällaisen koodin murtaminen on ollut niin vaivalloista, että se tuntuu käytännössä mahdottomalta.

Koska haluan, että tämä haaste liittyy salakirjoituksen purkamiseen eikä ohjelmointiin, olen tasannut kenttää antamalla kaikkien käyttöön valmiin purkutyökalun.