You are here: TUTWiki>Tietoturva>Sisällysluettelo?>JulkisenAvaimenKryptografianIdea (revision 1)

Julkisen avimen kryptografian idea

Salakirjoituksen pitäisi merkitä muunnosta, jota ei voi kääntää ilman suunnatonta vaivaa, ellei tunne salaista avainta. Kryptologiassa käytetään myös sellaisia muunnoksia eli funktioita, joita on lähes mahdoton kääntää, vaikka funktiossa ei olisi mitään salaista. Tämä vastaa siis sitä (onnetonta tilannetta), että kryptotekstiä ei voi purkaa, vaikka avain tunnettaisiin ja tiedettäisiin, että on vain yksi selväteksti, josta kryptoteksti voi olla peräisin.

Tärkein esimerkki tällaisesta funktiosta on potenssiin korottaminen ja jakojäännöksen ottaminen hyvin suuren alkuluvun suhteen. Tämän funktion kääntäminen vaatisi logaritmin laskentaa, mikä ei diskreetissä eli (isojen) kokonaislukujen maailmassa onnistu missään kohtuullisessa ajassa. Tämä nimenomainen funktio tulee käyttöön avaintenvaihdossa ( Diffie-Hellman). Katsotaan tässä johdannossa toisenlaista potenssilaskun tilannetta, josta saadaan salaus- ja purkualgoritmi.

Olkoon luku n kahden suuren alkuluvun p ja q tulo, mutta p:tä ja q:ta ei tunneta. Jos korotetaan jokin luku x toiseen potenssiin ja lasketaan jakojäännös luvun n suhteen, niin lopputuloksesta y ja luvusta n ei saa x:ää selville millään kohtuullisella vaivalla (kun x:kin oli niin suuri, että x2 on suurempi kuin n).

Mitäpä sitten, jos joku tunteekin p:n ja q:n? Tällöin hän voi laskea erikseen x:n neliöjuuret p:n ja q:n suhteen, sillä alkulukujen suhteen on olemassa tehokkaita algoritmeja tähän tarkoitukseen. Tuloksia on kaksi kummankin alkuluvun suhteen ("plus ja miinus"). Yhdistelemällä saadaan neljä ehdokasta x:ksi. Jos x:ään on koodattu jokin viesti, jossa on mukana hieman redundanssia (esim. luonnollista kieltä tai tarkistussumma), niin viesti erottuu ratkaisujen joukosta. Lievä epäinjektiivisyys ("4-to-1") ei siis haittaa.

Yleisesti salausavain (edellä "n") voi siis olla kaikkien saatavilla eli se on julkinen avain. Purkamiseen tarvitaan jokin salausavaimesta riippuva tieto, ns. yksityinen, tai 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.

Monessa muussakin järjestelmässä, mm. RSA:ssa, salaluukkuna on julkisen avaimen n tekijöihinjako. Kun n on suuri, sen tekijöiden p ja q löytäminen on hyvin työlästä. Tähän tarvittavaa tietokoneaika riippuu paitsi n:n pituuden ja koneen tehosta myös algoritmista. Nopeimmilla algoritmeilla esim. 1024-bittisen n:n tekijöiden löytäminen kestäisi 107 vuotta koneessa, joka tekee miljoona operaatiota sekunnissa. (Silti monet suositukset esittivät jo vuonna 2007 suurempia n:n arvoja esim. 2048-bittisiä, jos tieto pitää turvata yli vuoden 2010!))

Siispä 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 esim. RSA:sta).

Edellä jo pariin otteeseen viitattu RSA on tunnetuin epäsymmetrinen kryptosysteemi, tekijöinä Rivest, Shamir ja Adleman, 1978. Salaus muistuttaa Rabinin systeemiä, koska se voisi olla esim. kolmanteen korottamista. Purkukin on vain yksi potenssiin korotus (ja mod n eli jakojäännöksen lasku n:n suhteen):

  • Selkotekstin x salaus kryptotekstiksi y: y = xe mod n
  • Kryptotekstin y purku selkotekstiksi x: x = y d mod n

RSA-avaimet ovat siis

  • julkiset: moduuli n ja eksponentti e (encrypt)
  • yksityinen: eksponentti d (decrypt)

ja kuten sanottu, salaluukkuna ovat moduulin tekijät, kaksi suurta alkulukua p ja q. Niiden avulla lasketaan e:stä d, kun systeemi muodostetaan (ja e voi siis olla esim. 3, mutta ei 2).

-- JukkaKoskinen?

SivuTiedotLaajennettu edit

Vaativuus Perus
Valmius Valmisteilla
Tyyppi Ydin
Luokitus Uhkat
Mitä Luottamuksellisuus
Miltä Ihmisetön uhka
Missä Organisaatio
Kuka Tite-ammattilainen
Milloin Ennakolta
Miksi Hyvä tapa
Print version |  PDF  | History: r2 < r1 | 
Topic revision: r1 - 18 Apr 2010 - 14:28:26 - MaijuLehtonen?
 

TUTWiki

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TUTWiki? Send feedback