(2) Katsotaan, mitä tapahtuu, kun modulina on 21 eli kahden alkuluvun tulo: Huomataan ensin, että 3:lla tai 7:llä jaolliset luvut ovat sikäli kehnoja, että ne "jakavat nollan" eli ne voivat olla toisena tekijänä kertolaskussa, jonka tulos on 0 eli jaollinen 21:llä. Tutkitaan siis vain lukuja, joissa ei ole tekijänä 3:a eikä 7:ä, eli sellaisia joiden syt 21:n kanssa on 1. Näitä osoittautuu olevan 12, joka on = (7-1)(3-1) eli Eulerin phi-funktio arvolla 21. (Kyseiset luvut muodostavat multiplikatiivisen ryhmän modulo 21. Edellä laskettiin sellaisessa modulo 7. Phi arvolla alkuluku p on p-1.)
Lasketaan toiset potenssit, toteamalla etukäteen että x:llä ja sen vastaluvulla eli (21-x):llä on sama neliö. Katsotaan, minkä verran luvuilla on neliöjuuria. Yritetään generointia potenssiin korottamalla. Osoittautuu että viimeistään 6. potenssi on aina 1 (ja usein jo 2. tai 3.; erityisesti generaattoria ei siis ole eli ryhmä ei ole syklinen. Silti aina myös Phi's eli 12. potenssi on 1.)
Mitäpä sitten, jos joku tunteekin p:n ja q:n (ja p,q=3 mod 4)? Tällöin hän voi käyttää tehokkaita algoritmeja x:n neliöjuurten laskemiseen modulo p ja modulo q ja nämä juuret yhdistämällä hän saa selville neljä ehdokasta x:ksi. Jos x:ään on koodattu jokin viesti, jossa on mukana hieman redundanssia (esim luonnollista kieltä tai tarkistussumma), niin viesti ratkeaa.
Jos p ja q ovat riittävän suuria alkulukuja, niiden tuloa n on erittäin vaikea jakaa tekijöihin, joten valittuaan p:n ja q:n satunnaisesti käyttäjä voi huoletta paljastaa n:n ja antaa toisten lähettää "neliö"viestejä hänelle. Kukaan muu ei niitä saa auki. Tämä on julkisen avaimen kryptografiaa ja luonnosteltu systeemi kantaa Rabinin nimeä (vuodelta 1979). Tämän systeemin murtaminen on yhtäpitävää luvun n tekijöihinjakamisen kanssa, seikka jota ei ole voitu todistaa seuraavaksi esiteltävästä RSA:sta.
Yleisesti salausavain (edellä "n") voi siis olla kaikkien saatavilla eli se on julkinen avain. Purkamiseen tarvitaan tietenkin jokin salausavaimesta riippuva tieto, ns. salainen avain (tässä "p ja q"). Se, että nämä ovat erilaiset, antaa aiheen kutsua julkisen avaimen systeemejä myös epäsymmetrisiksi kryptosysteemeiksi. Joissain tapauksissa, kuten edellä, algoritmikin on hyvin erilainen eri suuntiin. Sitä, että julkisen avaimen laatija tietää mitä sen takana on (tässä siis tekijöihinjako), sanotaan salaluukuksi (trapdoor). Kaikissa julkisen avaimen systeemeissä on jokin vastaava rakenne. Julkisella avaimella salatun viestin murtajalla on edessään jokin vaikealta näyttävä ongelma, joka ei ole lainkaan hankala, jos vain tuntee salaluukun.
Tässä (p-1)(q-1) = Phi(n) = Eulerin phi-funktio arvolla n (myös
"Euler's totient function"). Yleisesti, siis muunkinlaisilla n:n arvoilla, pätee
xPhi(n) = 1 mod n, jos syt(x,n)=1. Seuraava lasku osoittaa miksi RSA
toimii. Merkitään siinä F = Phi(n). Tällöin ed=1+vF, missä v on jokin vakio.
Tätähän tarkoittaa se että ed = 1 mod F. Nyt (xe mod
n)d mod n = (xe)d mod n = xed mod n =
x1+vF mod n = x1(xF)v mod n =
x*1v mod n = x mod n.
Oleellista RSA:n turvallisuuden kannalta on, että luvuista e ja n ei
voi käytännössä laskea salaista eksponenttia d. Periaatteessa tämä kävisi
jakamalla n ensin tekijöihin p ja q ja ratkaisemalla sitten d kuten
laatijakin on tehnyt. Riittäisi tietenkin tuntea tulo (p-1)*(q-1). Ovathan e ja d
toistensa käänteislukuja modulo juuri tämän luku.
Eksponenttilasku on hidas operaatio, vaikka julkiselle eksponentille e olisikin valittu usein käytetty arvo 3. Tämän vuoksi RSA:ta ei kannata käyttää pitkien viestien salaamiseen. Sama koskee tosin muitakin julkisen avaimen systeemejä - kaikki ovat hitaampia kuin symmetrinen salaus.
Kannattaakin muodostaa ns. digitaalinen kirjekuori. Valitaan satunnainen symmetrisen salausalgoritmin avain k ja salataan viesti sen avulla. Salataan sitten k käyttäen vastaanottajan julkista RSA-avainta. Lähetetään nämä salatekstit vastaanottajalle yhdessä asianmukaisten otsikkotietojen kanssa, joilla tyypillisesti yksilöidään käytetyt algoritmit ja se mitä julkista avainta on käytetty. Näin vastaanottaja tietää mitä viestin osille pitää tehdä. Tällaista menettelyä käytetään osana jotain protokollaa esim. PGP:ssä ja SET:ssä, joista kummastakin lisää myöhemmin.
RSA:n kehittivät ja sittemmin patentoivat Rivest, Shamir ja Adleman. Alkuperäinen artikkeli vuodelta 1978 on "A method for obtaining digital signatures and public key cryptosystems".
Epäsymmetrisillä kryptosysteemeillä voidaan saada aikaan todellisia digitaalisia allekirjoituksia. Perusidea on, että allekirjoittaja A luo epäsymmetrisen avainparin (V,S) ja sitoo julkisesti avaimen julkisen osan V (=verifiointiavain) omaan identiteettiinsä ja käyttää salaista osaa S (=signeerausavain) dokumenttien allekirjoittamiseen. Kuka tahansa B voi vakuuttua allekirjoituksen aitoudesta, koska vain A on voinut laatia ne: vain A tuntee S:n ja vain S:llä allekirjoitetun dokumentin voi verifioida V:llä. Lisäksi A:n julkinen sitoutuminen V:hen saa aikaan sen, ettei hän voi kiistää S:llä allekirjoitettuja dokumentteja - paitsi yrittämällä väittää, että hänen avaimensa on paljastunut. Periaatteessahan mistä tahansa julkisesta avaimesta voi laskea vastaavan salaisen avaimen. Yksilöitä ja avaimia toisiinsa sitovien järjestelmien täytyy tämän vuoksi olla varuillaan, ettei kukaan yritä ottaa käyttöön helposti murrettavaa julkista avainta, jolloin myöhemmin esitettävälle murtumisväitteelle olisi ikäänkuin jälkikäteen löydettävissä selityskin.
RSA soveltuu epäsymmetrisistä systeemeistä sikäli luontevimmin allekirjoitukseen, että julkisen ja salaisen eksponentin roolit ovat matemaattisessa mielessä symmetriset (vrt. eo. laskelma, kyse on kommutatiivuudesta). Allekirjoitusta varten avaimia vain käytetään toisessa järjestyksesä kuin salauksessa. Dokumentin m allekirjoitus s muodostetaan salaisella eksponentilla d laskemalla s=md mod n. Kun m ja s lähetetään yhdessä, kuka tahansa, joka tuntee vastaavan julkisen avaimen e, voi verifioida eli todentaa, että m = se mod n.
Se mitä edellä sanottiin symmetrisellä algoritmilla salattavan viestin redundanssin merkityksestä todentamiselle, pätee toki epäsymmetristen systeemien allekirjoitukseen. Koska RSA:n tapauksessa pelkästä potenssista s=md mod n saa selville koko m:n, ei m:ää tarvitsisi välttämättä liittää mukaan. Toisaalta, kuten on jo todettu, RSA:n eksponenttilasku on hidas operaatio, minkä vuoksi yleensä vain viestin tiivistelmä allekirjoitetaan. Lähetys on siis: m, (H(m))d mod n, missä H on hash-funktio.
Harjoitus: Miksi luotettu osapuoli on sitä luotettavampi mitä vähemmän se luottaa sinuun? Keksi esimerkkejä.
Tärkeä ominaisuus tietoturvaprotokollissa on, että osapuolet voivat protokollan päätyttyä vakuuttua siitä, että tavoite tuli saavutetuksi ja havaita mikäli näin ei käynyt. Tätä varten voidaan tarvita luotettua kolmatta osapuolta. Sellainen voi kuulua osaksi protokollaa joko välittäjänä tai siten että jossain vaiheessa ollaan siihen yhteydessä (esim. sertifioija), tai sitten kolmannen osapuolen roolina on jälkikäteen tarvittaessa kaivaa esiin mahdolliset väärinkäytökset.
Kryptoprotokollien suunnittelussa pätee, varmaan paremmin kuin missään muussa, että jos jokin voi mennä pieleen niin se menee. Tämä johtuu siitä, ettei riitä, että protokolla suoriutuu tehtävästään kaikki tunnetut hyökkäykset välttäen. Sen pitäisi välttää kaikki mahdolliset hyökkäykset. Toisin kuin ohjelmistoissa ja tekniikassa yleensä, käyttäjien ei voida olettaa edes aikovan toimia sääntöjen mukaisesti. Vaikka tämän kurssin perusteella ei suunnitellakaan uusia protokollia, on hyvä tuntea kaksi tärkeintä suunnittelussa huomioitavaa periaatetta:
Monet erikoisiin tavoitteisiin esim. sähköisessä kaupankäynnissä tähtäävät kryptoprotokollat ovat varsin monimutkaisia ja niissä sovelletaan usein sellaisia aliprotokollia, jotka irrallaan tuntuvat kummallisilta. Tällaisia ovat mm.
Yksilöinnin tärkeimpiä sovelluksia on pääsyn valvonta. Sisäänpääsy tuo sitten tyypillisesti mukanaan oikeutuksen käyttää resursseja sen mukaan, millainen auktorisointi yksilölle on erikseen määritelty. Oikeuksien määrittely on keskeinen tietoturvallisuuteen vaikuttava tekijä ja se on tullut esille aiemmin, samoinkuin salasanoihin perustuva autentikointi. Katsotaan seuraavaksi vahvempia autentikointimenetelmiä, jotka perustuvat johonkin tiedettyyn.
Yleistys: edes isäntä ei tiedä salaisuutta, mutta voi silti
vakuuttua, että vieras tietää! Tällaista sanotaan nollatietotodistukseksi,
ja esimerkkinä siitä on Feige-Fiat-Shamir-protokolla. Merkitään:
Y = vieras joka pitää Yksilöidä
T = isäntä, joka haluaa Todentaa Y:n henkilöllisyyden
Esitellään protokollan idea olettaen vain jokin yksisuuntainen funktio f, jolle pätee ns. morfismiominaisuus f(x*y)=f(x)*f(y).
Protokollan tavoitteena on vakuuttaa T siitä, että Y tietää salaisen lukunsa s, jonka Y on valinnut ja laskenut siitä julkisen avaimensa v = f(s). Jotta ei T eikä salakuuntelija saisi tietää s:ää, Y ei koskaan lähetä T:lle itse s:ää vaan tulon u=r*s, missä r on satunnaisluku, josta Y on protokollan alussa kertonut T:lle arvon f(r). Koska T ei tiedä s:ää eikä r:ää, niiden tulon näyttää T:stä satunnaiselta eikä sellaisenaan riitäkään vielä vakuuttamaan T:tä: Jotta Y ei voisi lähettää "r*s":nä mitä tahansa, T pyytääkin Y:ltä satunnaisesti joko r:n tai s*r:n.
Oletetaan, että T saa vastaukseksi luvun u. Jos pitäisi olla "u=r", T laskee f:n arvolla r ja vertaa. Jos pitäisi olla "u=s*r": T tarkistaa, onko f(u)= f(r)*v.
Todennäköisyys, että Y, joka ei tunne s:ää, läpäisee tarkastuksen on enintään 1/2. Ainoa, mitä Y voi tehdä, on yrittää ennakoida jompaakumpaa pyyntöä ensimmäisessä viestissään. Jos Y uskoisi etukäteen, että häneltä tullaan kysymään r*s:ää, hän lähettäisikin protokollan alussa f(r):n sijasta arvon f(z)/v, missä z on satunnainen. Haasteeseen "anna r*s" hän vastaisi sitten z, joka olisi verifioijan mielestä oikein.
Toistamalla protokollaa riittävän monta kertaa saadaan onnistuneen huijauksen todennäköisyys riittävän pieneksi vakuuttamaan T siitä, että Y tietää s:n: tekemällä m kierrosta saadaan huijauksen todennäköisyydeksi 1/2m.
Yksisuuntainen funktio, jolla on tarvittava (morfismi-)ominaisuus on neliöinti modulo n, missä n=p*q ja osapuolet Y ja T eivät tunne (suuria alkuluku)tekijöitä p ja q. Y saisi tuntea ne, jos n olisi Y:n oma, mutta yleisesti tarvitaan luotettu välittäjä, joka valitsee luvut p ja q ja julkaisee niiden tulon n. Osapuoli Y valitsee satunaisluvun s ja rekisteröi julkiseksi avaimekseen luvun v=s2 mod n.
Tästä protokollasta voidaan todistaa, että T ei saa sen kautta mitään sellaista tietoa, mitä sillä ei ole ennestään (esim. käytännössä laskettavissa v:n ja n:n perusteella).