(Kryptoprimitiivit jatkuvat:)

Yksisuuntaiset funktiot

Yksisuuntaisella funktiolla tarkoitetaan yleensä sellaista injektiivistä funktiota f, jolle arvon x laskeminen arvosta f(x) on käytännössä mahdotonta. Arvon f(x) laskeminen x:stä ei saa olla vaikeaa. Esimerkkejä yksisuuntaisista funktioista:

• diskreetti logaritmi: f(x) = g^x mod p, missä p on alkuluku ja g on primitiivinen eli sellainen että g^x käy läpi kaikki luvut 1,...,p-1, kun x käy 0,...,p-2.
• neliö: f(x) = x² mod p*q   (oletus: luvut p ja q salaisia ja p,q=3 mod 4)
• RSA-funktio f(x) = x^e mod p*q   (oletus: luvut p ja q salaisia ja lukujen e ja (p-1)(q-1) syt = 1)
• osajoukkosumma (sub-set sum): n:n mittainen bittivektori x kuvataan skalaarituloksi x.A, missä vektorin A n alkiota ovat likimain tasan jakautuneet välille 1,..., 2ⁿ (x:n selvittäminen osajoukkosummasta x.A on ns. selkäreppuprobleema, knapsack problem)
• Harjoitus: Olkoon f(x,k) = tulos x:n salaamisesta DES:llä (tai jollain toisella, hyvällä salausalgoritmilla) käyttäen avainta k. Onko kyseessä yksisuuntainen funktio, jos f(x,k):ta ajatellaan
  x:n funktiona (k tunnettuna parametrina),
  k:n funktiona (x tunnettuna parametrina),
  x:n ja k:n funktiona? [HAC:329]
• Harjoitus: Olkoon f(x,k) kuten edellä. Miksi funktio g(x) = f(x,k) XOR x on yksisuuntainen? [HAC:328]

Tiivistefunktio, hash

Tiivistefunktiolta H edellytetään siis yksisuuntaisuutta: kun on annettu h, ei voida löytää x:ää jolle olisi H(x)=h. (Toinen nimitys: 'preimage resistance'; x on h:n 'preimage' eli "alkukuva"). Usein vaaditaan enemmän: vaikka etukäteen ei olisi annettu tiivistettä h ei saisi löytyä viestejä jotka "törmäävät" eli tiivistyvät samaksi h:ksi: Harjoitus: Toinen seuraavista ominaisuuksista on ns. heikko törmäyksen vastustuskyky, 'weak collision resistance', toinen puolestaan vahva. Kumpi on kumpi?

• Annettua x:ää kohti on mahdotonta löytää (eri) y:tä, jolle pätee H(y)=H(x). Tästä ominaisuudesta käytetään myös nimitystä 'second preimage resistance'.
• On mahdotonta löytää paria (x,y), jolle pätee H(x)=H(y). Tämä on joissain lähteissä pelkkä 'collision resistance'.

Tiivistealgoritmi voidaan varustaa myös avaimella, ts. tulos lasketaan viestistä ja (salaisesta) avaimesta pelkän viestin sijasta. Tällaisista käytetään termiä Message Authentication Code, MAC, koska niitä käytettäessä tavoitteena on osoittaa viestin eheyden lisäksi sen aitous. Törmäysten välttäminen ei näissä ole vastaavalla tavalla tärkeätä kuin avaimettomissa algoritmeissa (joita kutsutaan käyttönsä mukaan usein nimellä Manipulation Detection Code, MDC.). Sen sijaan MAC:ltä edellytetään sitä, ettei avainta k tuntematon voi laskea mitään paria (x, H(k,x)), vaikka tuntisikin useita pareja (y, H(k,y)).

Tiivistefunktiolta vaaditaan jossain määrin samantapaisia asioita kuin salausalgoritmilta: Jokainen viestin bitti vaikuttaa ja pieni muutos viestissä tuottaa suuren muutoksen tuloksessa. Niinpä joitakin salausalgoritmeja käytetään tiivistealgoritmien osina. Yksinkertaisimmillaan voisi tiivisteeksi ottaa CBC- tai CFB-moodissa käytetyn blokkikryptoalgoritmin viimeisen blokin. Kyseessä olisi MDC, jos avain on kaikkien tuntema, MAC jos se on salainen. Edellinen ei kuitenkaan ole järkevä. Jälkimmäistä, siis MAC:tä, käytetään, joskin yleensä erilaisin lisäyksin ja muunnoksin (moodina CBC). Mikäli salausalgoritmeja halutaan käyttää MDC:n luomiseen, se tehdään yleensä seuraavan yleisen rakenteen puitteissa.

Yleinen yksisuuntaisen tiivistämisen periaate: käytetään "kutistusfunktiota" (compression function), jolle syötetään iteratiivisesti aiempi kutistustulos ja seuraava blokki viestistä. Alussa tarvitaan alustusvektori ja viestin täydennys blokin monikerran mittaiseksi (täydennystä voidaan tehdä myös blokkikohtaisesti). Useimmiten viestin loppuun liitetään sen pituus. Kutistusvaiheen jälkeen voidaan tehdä vielä jokin toisenlainen muunnos.

Tunnetuimmat tiivistealgoritmit kuuluvat MD4-perheeseen, jonka kehitystä (joka tapahtui 1990-luvun alkupuoliskolla) kuvaa seuraava kaavio:

MD4  --> MD5 ----->   SHA --> SHA-1
 | \___________
 |             \
ext-MD4	---->  RIPEMD   ------->    RIPEMD-160

Epäsymmetrinen kryptosysteemi

Lyhyesti sanottuna epäsymmetrinen kryptosysteemi on sellainen, jossa salausalgoritmi on yksisuuntainen funktio, vaikka avain tunnettaisiinkin ja silti on jokin yksinkertainen keino purkaa salateksti.

Salausavain voi siis olla kaikkien saatavilla eli se on julkinen avain. Purkamiseen tarvitaan tietenkin jokin salausavaimesta riippuva tieto, ns. salainen avain. Se, että nämä ovat erilaiset, antaa nimen epäsymmetrinen. Joissain tapauksissa algoritmikin on hyvin erilainen eri suuntiin.

Tunnetuimmassa julkisen avaimen systeemissä RSA:ssa algoritmi on symmetrinen ja vain avain on erilainen eri suuntiin. Jos lukupari (k,n) on asiaan kuuluva avain, niin x:n salaus/purku tapahtuu RSA:ssa laskemalla potenssi f_k(x) = x^k mod n. Vaikka moduli n on siis osa sekä julkista että salaista avainta, usein pelkkää eksponenttia k sanotaan avaimeksi. Systeemin laatija on laskenut n:n kahden valitsemansa ja salassa pitämänsä suuren alkuluvun p ja q tulona: n=p*q. Salainen eksponentti d ja julkinen eksponentti e (kuten niitä yleensä merkitään) suhtautuvat toisiinsa kaavan d*e=1 modulo (p-1)*(q-1) mukaisesti, josta laatija on alunperin laskenut d:n valittuaan ensin e:n.

Oleellista RSA:n turvallisuuden kannalta on siis, 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)).

Sitä että laatija tietää n:n tekijät, 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.

Muitakin julkisen avaimen kryptosysteemejä on. Mainitaan tässä esimerkin vuoksi yksi, Rabinin systeemi (vuodelta 1979):

• Avainparin generointi: Valitaan sellaiset suuret alkuluvut p ja q, että p-1 ja q-1 eivät ole neljällä jaollisia (ts. p ja q ovat kongruentteja 3:n kanssa modulo 4). Tulo n = p*q on julkinen avain ja luvut p ja q ovat salainen avain.
• Viesti M salataan korottamalla se toiseen modulo n.
• Salateksti C puretaan laskemalla siitä erikseen neliöjuuret modulo p ja q (2 kpl kumpiakin, lauseke on plusmiinus C^(p+1)/4 mod p) ja yhdistämällä nämä yhteensä neljäksi ratkaisuksi. Oikea selväteksti pitää päätellä esim. redundanssin perusteella.

Joihinkin erityistarkoituksiin kehitettyjä järjestelmiä tulee esille myöhemmin. Niillä voi suorittaa avainten vaihdon, allekirjoituksen tai tunnistuksen, mutta niitä ei voi käyttää viestin salaamiseen. RSA soveltuu useimpiin tarkoituksiin.

Perusprotokollat

Tutustutaan perusprotokolliin kahdessa vaiheessa. Ensinnä tehdään salausalgoritmeista alkava aasinsiltojen kautta "johdateltu" ekskursio, joka päättyy (ensi kerralla) avaintenhallintaan. Sitä käsitellään melko kattavasti ja se toimiikin lähtökohtana toiselle vaiheelle, jossa tutkitaan mm., miten primitiiveistä voidaan panna kokoon protokollia erityisesti autentisointiin ja avainten hallintaan.

Tässä vaiheessa asetetaan tehtäväksi luoda järjestelmä, jolla kaksi osapuolta Aino ja Bertil voivat lähettää toisilleen viestejä siten, että kumpikin voi luottaa niiden yksityisyyteen ja aitouteen. Osapuolet Aino ja Bertil eli A ja B eivät välttämättä ole ihmisiä, vaan toinen, tai molemmat, voi olla esim. palvelin, sovellusohjelma, IP-tason salausmekanismi, käyttöjärjestelmän luotettu komponentti, tai toimikortti. Ilmeisin keino tavoitteeseen pääsemiseksi on viestin salaaminen.

Salaus

Mielenkiintoisemmaksi tässä yhteydessä salaus tulee, kun tutkitaan minkä tason olioita A ja B voivat olla tietoliikennejärjestelmässä.

1. Periaatteessa (ainakin) toinen osapuolista voisi olla ihminen, joka kirjoittaa avaimen ja viestin tietoliikennekanavasta irrallaan olevaan (akkukäyttöiseen) salauslaitteeseen, joka kryptaa sen. Sitten hän kirjoittaa salatekstin kanavaan.
2. Sovellusohjelma, esim. tekstinkäsittelyohjelma tai sähköpostieditori suorittaa salauksen. Yhtä hyvin jokin erillinen suodinohjelma voi tehdä tämän. Tuloksena on päästä-päähän-salaus.
3. Tieto menee salaamatta ensimmäiseen tietoliikenteen solmukohtaan (jonka oletetaan olevan niin lähellä että siihen voidaan luottaa, esim. oman koneen tietoliikenneohjelmisto). Tästä eteenpäin jokainen reitin varrella oleva (tietyn tasoinen) solmu salaa viestin (tai sen erillään liikkuvan osan) ja seuraava solmu purkaa salauksen ja salaa uudestaan eteenpäin. Jokaisella toisiinsa kytketyllä solmuparilla on siis yhteinen salainen avain. Kunkin solmun sisällä tieto on paljaana.

Avainten vaihto

Jos kommunikointi tapahtuu ylemmällä tasolla, fyysinen avaintenvaihto ei yleensä ole käytännöllistä. Julkisen avaimen kryptosysteemi tarjoaa seuraavan mahdollisuuden: A luo julkisen avaimen ja lähettää sen ja oman nimensä B:lle, joka luo symmetrisen avaimen K ja lähettää sen A:lle kryptattuna A:n julkisella avaimella. A saa K:n selville salaisella avaimellaan.
Tämä olisi kelpo avaintenvaihtoprotokolla, kunhan vastustajat eivät pystyisi muuhun kuin salakuunteluun. Harjoitus: Oletetaan, että C pystyy pysäyttämään viestit ja lähettämään omiansa toisten nimissä. Näytä miten C voi välittää ("releoida") A:n ja B:n välisen avaimenvaihdon siten, että saa selville K:n eikä A:lla ja B:llä ole tästä aavistustakaan. (Man-in-the-middle attack)

Harjoitus: Mitä kritiikin aihetta on seuraavassa avaintenvaihtoprotokollassa?

Kumpikin osapuolista A ja B generoi ensin kaksi riittävän pitkää satunnaista bittijonoa. Olkoot A:n jonot K_A ja R_A ja B:n jonot vastaavasti. Kumpikin osapuoli tekee sitten symmetrisesti operaatiot, jotka seuraavassa on kuvattu A:n näkökulmasta: A lähettää B:lle bittijonon S_A = K_A XOR R_A ja saa tältä vastauksena jonon T_A = S_A XOR K_B. Tämän jälkeen A muodostaa yhteisen avaimen K_AB ottamalla ne bitit jonosta K_A, joiden kohdalla jonossa R_A XOR T_A on nolla.

Kuuluisin avaintenvaihtoprotokolla on nimeltään Diffie-Hellman. Se on myös kaikkien aikojen ensimmäinen julkisen avaimen algoritmi (vuodelta 1976). Julkisena avaimena siinä on moduli p (suuri alkuluku), ja kantaluku g, joka on primitiivinen juuri modulo p (eli sellainen että g^x käy läpi kaikki luvut 1,...,p-1, kun x käy 0,...,p-2). Luvut p ja g ovat siis julkisia eivätkä välttämättä mihinkään osapuoleen sidottuja. Oleellista on, että p ei ole mitään erityistä muotoa, jonka suhteen diskreetti logaritmi olisi tavallista helpompi.

Kun osapuolet A ja B haluavat generoida yhteisen avaimen kumpikin valitsee satunnaisen luvun; olkoon A:n luku x ja B:n luku y. Sitten A lähettää B:lle luvun g^x mod p ja B lähettää A:lle luvun g^y mod p. Yhteisenä avaimena A:lla ja B:llä on nyt luku (g^y)^x mod p = (g^x)^y mod p. Jotta joku muu saisi selville saman luvun, hänen pitäisi siis luvuista g^x ja g^y laskea luku g^xy. Tätä varten hyökkääjäkin tarvitsisi jomman kumman luvuista x ja y, eli hän joutuisi laskemaan diskreetin logaritmin modulo p luvusta g^x tai g^y.

Harjoitus: Luonnostele protokolla jossa A, B ja C sopivat keskenään DH-tyyppisesti avaimesta, joka on muotoa g^xyz mod p.

Harjoitus: Oletetaan, että DH-lähtötilanteen eli julkisen lukuparin (g,p) valinnan jälkeen ei ruvetakaan heti vaihtamaan avaimia tai lähettämään viestejä. Sen sijaan kukin osapuoli vain julkaisee oman lukunsa eli g potenssiin salainen satunnaisluku (mod p). Jos esimerkiksi A:n salainen luku oli x kuten edellä niin A:lla on nyt ikäänkuin julkinen avain (g,p,X), missä X = g^x mod p. Miten viesti M voidaan salata tällä avaimella ja lähettää A:lle - siis suoraan ilman avaintenvaihtoa? Tehdään kuitenkin kuten DH-avaimenvaihdossa: luodaan satunnaisluku k, joka toimii kuin B:n eksponentti y ja lähetetään salatekstin alkuosana g^k mod p. Jälkiosan pitäisi sitten riippua jotenkin viestistä M (ja varmaan X:stäkin) ja sen pitäisi aueta DH-tyyppisesti tietoon g^xk = (g^k)^x mod p pohjautuen (A:han tietää oman salaisen x:nsä). Millainen jälkiosa kelpaisi?

Ratkaisu on X^kM mod p ja tuloksena on ElGamalin julkisen avaimen systeemi (vuodelta 1984). Se tulee esille myöhemminkin allekirjoituksen yhteydessä. Oletuksena on, että salatekstiä satunnaistavalla luvulla k ei ole yhteisiä tekijöitä (p-1):n kanssa. Viestin M purkaminen salatekstistä eli lukuparista (a=g^k mod p,b=X^kM mod p) tapahtuu näin: M = b/a^x.

Perusmuodossaan DH-protokollan ongelma on siinä, etteivät A ja B oikeastaan tiedä, kenen kanssa he avaimia vaihtavat. Menettelyltä puuttuu siis autenttisuus (eikä ElGamalkaan sellaisenaan auta tässä). Yhtenä ratkaisuna voitaisiin ajatella allekirjoittaa viestit. Tarkastellaan tätä seuraavalla kerralla yhtenä allekirjoituksen sovelluksena. Myöhemmin otetaan esille muita avaimenvaihtoon sopivia menetelmiä, mm. sellaisia, joissa käytetään kolmatta osapuolta.

Artikkeli on varsin kevyt, joten aikaa pitäisi jäädä seuraavaan kotitehtävään: Etsi esim. www:stä jokin raportti kryptosysteemin murtamisesta, eli siitä että joku on saanut selville selvätekstin, salausavaimen, ennakoinut satunnaislukuja tai löytänyt törmäyksen tiivistefunktiosta. Kuinka työlästä murtaminen oli? Millaisessa yhteydessä tämä tapahtui (soveltuuko esim. luokittelu chosen cryptotext tms.? Oliko menetelmä yleinen eli voidaanko sitä sellaisenaan soveltaa uusiin yhteyksiin? Tehtävää ei mainittu tunnilla, joten sen tarkastaminen tapahtuu sitä mukaa kun ratkaisuja ilmenee.