Sisällysluettelo

• 0. Johdanto
• 1. Dokumentissa käytetty aakkosto ja kieli
• 2. Caesarin menetelmä
  • 2.1 Tekstin salaaminen
  • 2.2 Salatun tekstin avaaminen
  • 2.3 Caesarin menetelmän murtaminen
  • 2.4 Harjoitustehtäviä
• 3. Vigenere'n menetelmä
  • 3.1 Tekstin salaaminen
  • 3.2 Salatun tekstin avaaminen
  • 3.3 Vigenere'n menetelmän murtaminen
  • 3.4 Harjoitustehtäviä
• 4. One-time-pad
• 5. XOR-salaus
• 6. Salaukset K1, K2 ja K3

0. Johdanto

Tässä dokumentissa esitellään pari klassista salaustekniikka (tällä hetkellä Caesar ja Vigenere) sekä paljastetaan kuinka helppoja ne ovat todellisuudessa purkaa. Nämä salaukset ovat siinä mielessä huonoja, että jos tunnetaan tarpeeksi salattua ja vastaavaa selväkielistä tekstiä, voidaan avain määrittää helposti näiden perusteella.

Kuitenkaan yleisessä tapauksessa ei ole tiedossa kuin salattu teksti sekä mahdollisesti algoritmi jolla teksti on salattu ja tarkoituksena on selvittää tekstin sisältö. Tässä keskitytäänkin nimenomaan salauksen murtamiseen tapauksessa, jossa on tiedossa vain salattu teksti ja algoritmi jolla teksti on salattu.

Dokumentin tarkoituksena ei ole opettaa kuinka murretaan esimerkiksi DES tai IDEA, vaan tässä keskitytään ainoastaan yksinkertaisiin salauksiin, joiden murtaminen kuitenkin perustuu samankaltaisiin tekniikoihin kuin parempien salausten murtaminenkin. Hyvää salausta ei pystytä murtamaan muuten kuin Brute-Force:lla eli kokeilemalla koko avainavaruus läpi.

1. Dokumentissa käytetty aakkosto ja kieli

Tässä dokumentissa aakkostossa käytetään alla olevaa 27-alkioista numeerista koodausta. Isot ja pienet kirjaimet käsitellään samoina kirjaimina ja mahdolliset muut merkit jätetään huomiotta.

        ' ' = 0    'F' = 6    'L' = 12   'R' = 18   'X' = 24
        'A' = 1    'G' = 7    'M' = 13   'S' = 19   'Y' = 25
        'B' = 2    'H' = 8    'N' = 14   'T' = 20   'Z' = 26
        'C' = 3    'I' = 9    'O' = 15   'U' = 21
        'D' = 4    'J' = 10   'P' = 16   'V' = 22
        'E' = 5    'K' = 11   'Q' = 17   'W' = 23

Osittain aakkostosta johtuen salattavien tekstien kielenä on englanti. Kaikki dokumentin menetelmät ovat toki pienin muutoksin yleistettävissä muihinkin kieliin.

2. Caesarin menetelmä

2.1 Salaaminen

Caesarin menetelmässä avain yhden merkin mittainen. Avain tulkitaan numeroarvona jonka verran jokaista kirjainta "siirretään" aakkosissa eteenpäin. Esimerkiksi jos avain on A=1, jokainen A korvataan B:llä, B korvataan C:llä jne. Ja ylimenevät kirjaimet menevät ympäri, esimerkiksi Z:sta tulee A. Jokainen kirjain siis lasketaan yhteen avaimen kanssa modulo 27.

Esimerkiksi jos koodataan merkkijono "THIS IS COOL" avaimella S=19:

Jossa siis:

2.2 Salauksen avaaminen

Salaus puretaan avaimen avulla analogisella tavalla, mutta nyt kutakin kirjainta siirretäänkin taaksepäin aakkosissa. Toisin sanoen avain vähennetään salatusta tekstistä modulo 27.

2.3 Caesarin menetelmän murtaminen

2.3.1 Välilyöntien etsiminen

Luonnollisin lähestymistapa Caesarin menetelmän murtamiseen voisi olla idea, että tutkitaan kaikki mahdolliset avaimet (27 kappaletta) ja tarkastellaan milloin teksti on järkevä. Tämä on muuten hyvä idea, mutta mistä tiedetään, että teksti on järkevä? Otetaan avuksi eräs englanninkielen (ja suomenkielen) ominaisuus:

Oletus: Tekstin yleisin merkki on välilyönti

Tämä pätee luonnollisesti vasta kun tekstiä on tarpeeksi, mutta tulee selvästi esille jo yhden lauseen tekstissä:

Kirjainten määrät:

Havaitaan, että W-kirjain (23) on selvästi yleisin salatussa tekstissä. Oletetaan sen olevan välilyönti (0):

Kokeillaan purkaa salattua tekstiä avaimella Key = 23, jolloin tulos on:

2.3.2 Histogrammin tutkiminen

Miksi ei voisi käyttää muidenkin kirjainten esiintymistiheyksiä hyväksi? Se onkin hieman yleispätevämpi ratkaisu salauksen murtamiseen:

Oletus: Samankielisten tekstien merkkihistogrammit ovat samankaltaisia

Merkkihistogrammi on siis yksinkertaisesti eri merkkien prosentuaaliset osuudet tekstissä, eli montako kirjainta esiintyy keskimäärin sadan kirjaimen joukossa. Englanninkielen merkkihistogrammi on likimäärin seuraavanlainen:

Välilyönti on siis yleisin merkki (1/5 kirjaimista), toiseksi yleisin on E (1/10 kirjaimista).

Nyt kuitenkaan avainta ei saada suoraan laskemalla salatun tekstin histogrammi ja päättelemällä siitä mikä on oikea avain "jotenkin helposti". Taktiikkana onkin tutkia kaikki mahdolliset avaimet (27 kpl) ja käyttää histogrammia avuksi päätettäessä mikä on oikea avain.

Ideana on kokeilla kutakin avainta, purkaa teksti tällä avaimella ja verrata syntynyttä histogrammia kielen luonnolliseen histogrammiin. Havaitaan seuraava hyödyllinen ominaisuus:

Oletus: Kaikista avaimista todellinen avain tuottaa histogrammin joka on lähimpänä kielen luonnollista histogrammia.

Tutkitaan jälleen aikaisemman esimerkin salatun tekstin histogrammia. Muutetaan samalla kirjainten osuudet prosenteiksi:

Lasketaan kullakin avaimella (0,1,2,3...) puretun tekstin histogrammin ja englanninkielen histogrammin etäisyyttä. Etäisyys lasketaan siten, että vähennetään kunkin kirjaimen frekvenssit (tiheydet) toisistaan, lasketaan tästä itseisarvo ja summataan kaikki yhteen (L¹-normi).

Saadaan seuraavanlaisia tuloksia:

Helposti on havaittavissa pienin etäisyys avaimen 23 (W-kirjain) kohdalla. Tämä siis toimi hyvin vaikka teksti oli näinkin lyhyt.

2.4 Harjoitustehtäviä

1. Ratkaise käytetty avain ja teksti etsimällä välilyönnit kun tiedetään, että teksti on englantia:

2. Ratkaise käytetty avain ja teksti tutkimalla histogrammia kun tiedetään, että teksti on englantia:

3. Vigenere'n menetelmä

3.1 Salaaminen

Edellä kuvattu Caesarin menetelmä on erikoistapaus Vigenere'n menetelmästä. Tässä menetelmässä avain on jokin kirjainyhdistelmä (vaikka ABC tai KJHSA), jota lasketaan toistuvasti salattavan tekstin kanssa yhteen modulo 27:

Esimerkiksi jos avain on ABC:

Jossa siis:

3.2 Salauksen avaaminen

Salauksen purkaminen tapahtuu samalla tavalla kuin salaaminenkin, mutta lisäämisen sijasta avainta vähennetään salatusta tekstistä modulo 27.

3.3 Vigenere'n menetelmän murtaminen

3.3.1 Tunnetunpituisen avaimen määrittäminen

Vigenere'n menetelmä voidaan murtaa samankaltaisilla keinoilla kuin Caesarin menetelmä. Seuraavasta tiedosta on hyötyä:

Oletus: Tekstin joka K:nnen merkin muodostama histogrammi on likimäärin sama kuin koko tekstin histogrammi

Tätä tietoa voidaan hyödyntää siten, että jos avaimen pituus on K, voidaan tällaista osahistogrammia tutkimalla löytää yksi avaimen osa. Luonnollisesti tätä varten pitää tietää avaimen pituus.

Esimerkiksi jos tiedetään, että avaimen pituus on 3 ja salattu teksti on seuraavanlainen:

Aloitetaan merkistä 0 ja lasketaan joka kolmannelle merkille saadun histogrammin ja englanninkielen histogrammin etäisyys. Etäisyys lasketaan samalla tavalla kuin Caesarin menetelmän murtamisessa eli summaamalla erotuksien itseisarvot.

Histogrammien erotus aloitettaessa ensimmäisestä merkistä (indeksi 0):

Selvästi histogrammien erotus on pienin avaimen 2 kohdalla. Arvataan siis, että ensimmäinen merkki avaimessa on B.

Vastaavasti saadaan histogrammeiksi aloitettaessa toisesta ja kolmannesta merkistä (indeksit 1 ja 2):

Selvästi havaitaan minimit avainten 1 (merkki A) ja 18 (merkki R) kohdalla. Päätellään siis, että koko avain on BAR ja kokeillaan avata tekstiä tällä avaimella:

3.3.2 Avaimen pituuden määrittäminen

Jotta pystyttäisiin laskemaan histogrammit joka K:nnelle merkille, jossa K on avaimen pituus, on luonnollisesti avaimen pituus tiedettävä. Yleisessä tapauksessa avaimen pituutta ei tiedetä, mutta onneksi se pystytään päättelemään salatun tekstin perusteella.

Tekstin index-of-coincidence lasketaan siten, että "shiftataan" tarkasteltavaa tekstiä N kirjainta sivulle. Tämän jälkeen asetataan alkuperäinen teksti ja shiftattu teksti allekkain ja lasketaan kuinka monta samaa merkkiä on kohdakkain.

Esimerkiksi:

Tälle tekstille olisi siis index-of-coincidence 4.7 % (shiftausmäärällä 3).

Oletus: Index-of-concidence ei ole riippuvainen siitä kuinka monta paikkaa tekstiä on shiftattu

Edellinen oletus pätee jos shiftaus on "monta" merkkiä eli esimerkiksi yhden merkin shiftaus laskee oikeastaan vain peräkkäisten samojen merkkien määrän.

Oletus: Englanninkielen IOC on huomattavasti suurempi kuin satunnaisen tekstin

Voidaan olettaa, että jos Vigenere'n menetelmällä salatulle tekstille lasketaan IOC siten, että shiftaus ei ole avaimen monikerta, tämä vastaa IOC:n mielessä satunnaista tekstiä. Avaimen pituus voidaankin määrittää laskemalla IOC:a eri shiftauksen määrillä ja tutkimalla minkä luvun monikertojen kohdalle osuu suurimmat arvot.

Tarkastellaan jälleen erästä Vigenere'n menetelmällä salattua tekstiä ja lasketaan sille index-of-coincidence eri shiftauksen määrillä. Salattu teksti on seuraava:

Shiftauksilla 1-10 saadaan seuraavanlaiset IOC:n arvot:

Kuvaajana arvot näyttävät seuraavalta:

Voidaan havaita selvät piikit kohdissa 3,6 ja 9. Tästä on pääteltävissä, että avaimen pituus on vasemmanpuoleisin näistä piikeistä eli 3. Itse avaimen murtaminen jätetään harjoitustehtäväksi.

Tämä salattu teksti myös paljastaa pienen heikkouden histogrammiin perustuvassa avaimen määrittämisessä. Nimittäin kun tekstiä on vähän, histogrammien erotus voi olla pienempi jossakin muussa kohdassa kuin todellisen avaimen kohdalla. Mutta jos tekstiä on paljon ei ongelmaa esiinny. Vihje tekstin ratkaisemiseen: Avaimen ensimmäinen merkki onkin H vaikka se vaikuttaa olevan M (tarkista!).

3.4 Harjoitustehtäviä

1. Ratkaise edellisessä esimerkissä oleva avain sekä alkuperäinen teksti (teksti on englantia).

2. Määritä avaimen pituus seuraavalle tekstille (teksti on englantia). Vihje: Etsi maksimi.

3. Määritä tehtävän 2 avain sekä alkuperäinen teksti.

4. One-time-pad

Tämä menetelmä on erikoistapaus Vigenere'n menetelmästä ja siinä avaimen pituus on sama kuin tekstin pituus. Selvästi voidaan havaita, että minkäänlaisen histogrammin laskeminen on mahdotonta. Oikeastaan on todistettu, että tällaista salausta ei voi murtaa millään tekniikalla, koska mahdollisia selväkielisiä tekstejä on saman verran kuin samanpituisia tekstejä koko kielessä. Toisin sanoen mistä tahansa salatusta tekstistä saadaan mikä tahansa selväkielinen teksti avainta vaihtamalla.

5. XOR-Salaus

Tämä salaus on sama kuin Vigenere'n salaus, mutta aakkoston koodauksena on ASCII-koodaus, eli aakkoston luvut ovat välillä 0-255. Lisäksi yhteenlaskun modulo 27 tilalla on XOR-operaatio selväkielen ja avaimen välillä. Purkaminen tapahtuu tekemällä XOR-operaatio salatun tekstin ja avaimen välillä jolloin saadaan jälleen selväkielinen teksti.

Tämän salauksen murtamiseen pätevät samat tekniikat kuin Vigenere'n salaukseenkin. Tästä huolimatta eräät ohjelmistovalmistajat ovat vielä muutamia vuosia sitten väittäneet tätä salausta lähes yhtä turvalliseksi kuin DES (Data Encryption Standard) kun avaimen pituus on vaikkapa (8*8 = 64 bittiä). Kuitenkin kuten esitellyistä tekniikoista voidaan havaita, avaimen pituus ei vaikuta kuin hyvin vähän salauksen turvallisuuteen (turvattomuuteen...).

6. Salaukset K1, K2 ja K3