Johdanto kryptoanalyysiin¶

Voimme olettaa, että salatun tiedon sisältöä on yritetty selvittää yhtä kauan kuin tietoa on salattu.

Salaimen tuottaman informaation pitäisi muistuttaa sekä yksittäisten bittien että bittikuvioiden tasolla satunnaista kohinaa.

Yksi tapa tarkastella, onko salaimen tuottama informaatio satunnaista, on tutkia riittävän suurta määrää salaimen tuottamaa informaatiota. Silloin haluaisimme, että:

Todennäköisyys, että salaimen tuottama yksittäinen bitti on 0 on 0.5. Eli \(\mathcal{P}('0')=0.5\)
Samoin todennäköisyys, että salaimen tuottama bitti olla 1 on 0.5. Eli \(\mathcal{P}('1')=0.5\)

Edellisen lisäksi, salaimen tuottamien bittijonojen oletetaan olevan satunnaisia.

Jos salain tuottaa kaksi bittiä, se tuottaa yhtä suurella todennäköisyydellä minkä tahansa mahdollisen bittikuvion (00, 01, 10 ja 11). Jokaisen edellä mainitun bittikuvion esiintymisen todennäköisyys on \(\frac{1}{4}\) eli 0.25.
Samoin, jos salain tuottaa kolmen bitin informaatiota, on jokaisen bittijonon 000, 001, 010, 011, 100, 101, 110, 111 yhtä suuri. Kolme bittiä tuottavan salaimen todennäköisyys yksittäiselle bittikuvioille on \(\frac{1}{8}\) eli 0.125.
Vastaavasti tarkastellessa mitä tahansa salaimen tuottamaa informaatiota, jonka pituus on \(n\) bittiä, on jokaisen tällaisen bittijonon todennäköisyys \(\frac{1}{2^n}\).
Mikään bittikuvio ei toistu salaimen tuottamassa informaatiossa systemaattisesti millään tavalla tutkittuna.

Jos salaimen tuottama informaatio täyttää edellä mainitut oletukset, sen tuottaman informaation sanotaan olevan erottamatonta kohinasta (engl. indistinguishable IND). Jos etsit hakukoneilla eri analyysimenetelmiä, huomaat monessa kryptoanalyysin määrittelyssä käsitteitä kuten IND-CCA, IND-CPA.

Seuraavassa tehtävässä on väittämiä edelliseen tekstiin liittyen. Valitse oikeat vaihtoehdot.

Kysymys 1

Voit valita useita vaihtoehtoja. Jos salain tuottaa neljä bittiä, on:

Jokaisen salaimen tuottaman yksittäisen bitin todennäköisyys olla joko ’0’ tai ’1’ on yhtä suuri \(\frac{1}{2}\) eli 0.5.

Jokaisen salaimen tuottaman neljän bitin mittaisen bittijonon todennäköisyys on yhtä suuri \(\frac{1}{16}\) eli 0.0625.

Yleensä salaimen tuottamassa informaatiossa on enemmän nollia kuin ykkösiä.

Jos salain on tuottanut bittikuvion ’0101’, salain ei voi tuottaa seuraavaksi samaa bittijonoa.

Jos salain on tuottanut bittijonon ’0110’, tuottaa salain myös seuraavaksi bittikuvion ’0110’ todennäköisyydellä \(\frac{1}{16}\).

Salaimen yksittäisistä biteistä tai bittijonoista ei voi päätellä seuraavia tai aiemmin tuotettuja bittiä tai bittijonoja.

Kysymys 2

Erottamattomuus (engl. indistinguishable) tarkoittaa kryptografisten salaimien tapauksessa sitä, että:

Salaimen tuottamaa informaatiota on mahdoton erottaa informaatiosta, joka on tuotettu satunnaisesta kohinasta.

Mikään salain ei pysty tuottamaan aidosti kohinasta erottumatonta informaatiota.

Kurssin kryptoanalyysi¶

Kryptoanalyysissä yksi lähestymistapa on analysoida selväkieli-salakieli-pareja. Kryptoanalyysin helppous tai vaikeus riippuu siitä, millaisia mustan laatikon hyökkäystapoja voimme käyttää.

Opetusmoduulissa 2 esittelimme seuraavat hyökkäystavat:

COA (ciphertext only attack)-hyökkäystapaa käytetään silloin, kun käytössä on vain salakirjoitettua informaatiota.
KPA (Known-plaintext attack)-hyökkäystapaa käytetään silloin, kun on saatu kerättyä selväkieli-salakieli pareja, eli meillä on saman informaation selväkielinen ja salakielinen versio saatavilla.
CPA (Chosen-plaintext attack)-hyökkäystapaa käytetään silloin, kun pystytään tuottamaan salaimella selväkielestä salakieltä.
CCA (Chosen-ciphertext attack)-hyökkäystapaa käytetään silloin, kun CPA:n lisäksi pystymme purkamaan salakielen informaatiota selväkieliseksi.

Tällä kurssilla meillä on pääsy salaimeen, jota voimme käyttää täysin vapaasti. Tällöin voimme:

Enkoodata informaatiota eli muuttaa selväkielen valitsemallamme avaimella salakieleksi.
Dekoodata salakielen informatiota valitsemallamme avaimella selväkieleksi.

Tässä opetusmoduulissa opettelemme kryptoanalyysin toimintaa klassisella frekvenssianalyysi menetelmällä.

Esimerkeissä käytämme salattavana informaationa erilaisia tekstitiedostoja, koska frekvenssianalyysi on helppo visualisoida tekstimuotoisella informaatiolla. On hyvä muistaa, että edistyneitä tilastollisia analyysejä sekä koneoppimisen menetelmiä käytetään informaation analysointiin. Tällöin informaatio on usein binääri-tiedosto, eli tiedosto jossa informaatio on vain bitteinä, eikä sillä ole tekstimuotoista esitystapaa.

Aluksi opettelemme lukemaan histogrammeja
Toiseksi kokeilemme miten frekvenssianalyysiä voi käyttää klassisten salainten avaimien selvittämiseen. Analysoimme edellisessä opetusmoduulissa esiteltyjä klassisia salaimia.
Lopuksi perehdymme satunnaisuuteen ja mietimme, miksi sillä on oleellinen rooli tiedon salauksessa ja suojauksessa.