Kryptografia: teoria¶
Tässä materiaalissa kryptografian opiskeluun on tarkoitettu pääluku Sovellettu kryptografia. Lähteenä käytetyssä CyBOK 1.1-kirjassa on enimmäkseen samojen asioiden teoreettinen käsittely tässä kohden (luku 10), mutta tähän kurssimateriaaliin sitä ei ole tuotu lainkaan. Sen sijaan tässä on vain hieman yleistä selitystä ja motivointia sekä esimerkki yhdenlaiseksi johdannoksi, josta todennäköisesti on hyötyä. Toisaalta opiskelijan kannattaa tutustua myös lähdeteokseen, kun hän jatkaa myöhemmille kursseille, joita Tampereen yliopistossa on useita nimenomaan kryptologian alalla.
Kryptografian teoriassa korostuu matematiikka ja turvallisuuden mallintaminen abstraktin hyökkääjän ominaisuuksien kautta. Mallintaminen edellyttää niin ikään matemaattista osaamista, koska siinä käsitellään todennäköisyyksiä, käytetään logiikkaa, ja päädytään usein varsin mutkikkaan oloisiin merkintöihin. Kun on nähnyt muutamia tällaisia esityksiä, esim. turvallisuuden todistuksia, voi huomata, että merkinnöissä ja todennäköisyyslausekkeissa on runsaasti säännönmukaisuutta, joka helpottaa oppimista jatkossa.
Kryptografisten algoritmien matematiikka edellyttää algebrallisen struktuurin käsitteen ymmärtämistä. Kokonaisluvut operaatioiden +, − ja × kera on jo struktuuri, mutta ensi vaiheessa tämä pitää muokata sellaiseksi, jossa on myös jakolasku määritelty kaikkien alkioiden välillä (joskaan nollalla ei voi eikä saa edelleenkään jakaa). Tätä varten rajoitutaan kokonaislukuihin 0, 1, 2, …, p−1, missä p on alkuluku. Nämä ovat modulaarisia kokonaislukuja, joiden välillä voi tehdä +, −, × ja ÷. Muut paitsi ÷ menevät “tavalliseen tapaan”, kunhan lopputuloksesta otetaan jakojäännös modulo p, toisin sanoen lisätään p tai −p niin monta kertaa, että tullaan välille 0,…,p−1 .
Jos esimerkiksi p=11, niin 5+6=0, 4−7=8, 3×5=4 ja 10×10=1. Viimeksi mainittu tarkoittaa sitä, että 10 on itsensä käänteisluku modulo 11. Vastaava pätee aina q-1:lle, kun q on alkuluku: (q-1)×(q-1) = q2- 2q + 1 = 0-0+1 = 1 modulo q.
Operaatiota ÷ varten tarvitaan uusi algoritmi, mutta samahan koski jakolaskua aikoinaan peruskoulussakin. Tässä eteenpäin päästään käänteisluvun kautta. Kun p on tosiaan alkuluku, niin luvun a käänteisluvun a-1 voi laskea potenssina ap-2 modulo p. Kokeile laskimella 109 mod 11. Eukleideen algoritmi on suurille luvuille paljon nopeampi.
Edellä olevaa esimerkkiä soveltaen huomataan, että modulo 11 pätee 4÷5=3, 1÷10=10 ja 2÷10 = 2×10=9. Tässä on käsillä struktuuri nimeltä äärellinen kunta (finite field). Niitä on kryptologiassa muitakin kuin luvuista koostuvia. (Ne koostuvat vektoreista, joiden alkiot ovat polynomin kertoimia, mutta ei mennä näihin nyt vaan tiettyihin lukupareihin).
Toinen askel kryptomatematiikassa johtaa struktuureihin, jotka koostuvat modulaaristen kokonaislukujen pareista. Niidenkin välille määritellään laskuoperaatiot + ja − sekä skalaarilla (kokonaisluvulla) kertominen. Tämä olisi muuten kuin koulusta tuttua analyyttista geometriaa, mutta uusi askel on rajoittaa nuo (x,y)-pisteet sellaisiksi, että ne toteuttavat yhtälön y2 = x3+1 (tai vastaavan, jossa aina y on toiseen ja x kolmanteen potenssiin). Osoittautuu, että kahden pisteen välinen operaatio tuottaa uuden pisteen, joka toteuttaa saman yhtälön (kunhan yksi piste kuvitellaan äärettömyyksiin). Pisteet muodostavat algebrallisen struktuurin nimeltä elliptinen käyrä. Sellaisetkin ovat äärellisiä, vaikka kryptografiassa käytettävät sisältävätkin enemmän pisteitä kuin maailmankaikkeus tiettävästi atomeja. Suuret luvut ja lukujoukot ovat kryptologiassa tarpeen, jotta läpikäyvä etsintä ei onnistuisi. Kvanttikryptolla on käytössään toisenlaisia keinoja ja toisenlaista matematiikkaa. Sekään ei ole ylivaikeaa, mikäli on uskominen kanadalaisen yliopiston lukiolaisille pitämän kvanttikesäkurssin (QSYS) taustamateriaalia (tilaa se rohkeasti!).
Käsitellään tämän luvun lopuksi yksi esimerkki, joka täydentää sovelletun kryptografian luvussa olevaa esitystä. Kuvassa on kryptografinen protokolla eli viestinvaihto osapuolten Alice ja Bob välillä. Se tuottaa heille, eli A:lle ja B:lle (vrt. myös symbolien alaindeksit), yhteisen symmetrisen avaimen K siten, että kumpikin voi olla varma siitä, kenen kanssa on sen muodostanut. Tämän protokollan nimi on Station-to-station ja se on perustapaus autentikoidusta avaintenvaihdosta. Tässä tavoitteena on lähinnä avata kryptografisissa esityksissä käytettyjä merkintöjä. Ei ole syytä huolestua, vaikka kuvan jäljessä oleva selitys ei niitä täysin avaisi. Tulevathan kryptaus ja allekirjoituskin opiskeltaviksi vasta tuonnempana.
Kuvan keskeltä näet, että A ja B lähettävät toisilleen yhteensä kolme viestiä, joista B:n viesti A:lle sisältää kaksi tietoalkiota (niiden välissä on pilkku). Muu osuus on laskennan kuvausta. Pisin rivi kummallakin osapuolella on allekirjoituksen verifiointia, jossa yhtäsuuruusmerkin yläpuolinen ? tarkoittaa kysymystä, onnistuiko eli päteekö yhtäsuuruus. Kaavioon ei ole merkitty, että A lopettaisi, jos verifiointi ei onnistuisi. Tämä on tyypillistä protokollien esitykselle. Toteutuksessa tätä ei voi jättää huomiotta.
Etsi seuraavaksi molemmilta puolilta toiseksi pisin rivi ja vertaa äskeisiin. Huomaat että Sign-funktiosta tulee ulos σ:lla (sigmalla) merkitty allekirjoitus, joka vastakkaisella puolella syötetään Verify-funktioon. Kummallisella fontilla kirjoitetut sk ja pk tarkoittavat osapuolten (ks. alaindeksistä kumman) yksityistä ja julkista avainta (secret ja public key). Se, mitä allekirjoitetaan, ei ole aivan samanlaista (symmetristä) eri puolilla, sillä B:llä ei omassa vaiheessaan ole vielä yhtä paljon tietoja kuin A:lla, joka laskee allekirjoituksen myös B:n allekirjoituksesta σB. A on edeltävällä rivillä purkanut sen salatusta cB:stä avaimella K, jonka A on juuri saanut selville sitä edeltävällä rivillä. B sai sen tietää jo vähän aikaisemmin. Löytänet rivin, jossa tämä tapahtuu. B soveltaa avainta funktiossa EncK eli (en)kryptauksessa, kun taas A käyttää funktiota DecK eli dekryptaus. Jäljempänä tapahtuu toisinpäin, kun A lähettää allekirjoituksensa (σA) salattuna cA:ksi ja B purkaa sen verifiointia varten.
Allekirjoitusten verifiointi on tässä se osuus, joka varmistaa osapuolet oikeiksi. Selvitetään vielä, miten yhteinen avain K muodostuu. Alussa kumpikin generoi satunnaisen alkion (luvut a ja b) joukosta Z/Zq, joka on q:n alkion äärellinen kunta (toisinaan merkitään GF(q)). Seuraavilla riveillään kumpikin laskee kertolaskun, jossa P on yhteisesti tunnettu elliptisen käyrän piste—ja käyräkin tietysti on tunnettu, samoin kuin suuri alkuluku q. Luvut a ja b on kertolaskussa merkitty hakasulkeisiin korostamaan sitä, että tässä ne ovat tosiaan tavallisia kokonaislukuja, kun ne edellä ovat itse asiassa kunnan alkioita (ja kunta voisi olla mutkikkaampikin). Joka tapauksessa voit laskua seuraamalla huomata, että kumpikin laskee K:ksi saman alkion [a]·[b]·P. Se, että viestintää kuunnellut hyökkääjä ei saa K:ta selville, on protokollan tämän osuuden suuri oivallus jo 1970-luvulta. Katso lisää Sovelletun kryptografian alaluvusta Diffie-Hellman-Merklen avaintenvaihto.