Difference: RSA(2-A) (r2 vs. r1)

r2 - 26 Sep 2010 - 11:10 - MarkoHelenius r1 - 18 Apr 2010 - 14:31 - MaijuLehtonen?

RSA (2-A)

RSA (2-A)

Tunnetuimmassa julkisen avaimen systeemissä RSA:ssa algoritmi on symmetrinen ja "1-to-1". Vain avain on erilainen eri suuntiin. Jos lukupari (k,n) on jompikumpi avain, niin x:n salaus/purku tapahtuu RSA:ssa laskemalla potenssi fk(x) = xk mod n. Vaikka moduuli 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.

Tunnetuimmassa julkisen avaimen systeemissä RSA:ssa algoritmi on symmetrinen ja "1-to-1". Vain avain on erilainen eri suuntiin. Jos lukupari (k,n) on jompikumpi avain, niin x:n salaus/purku tapahtuu RSA:ssa laskemalla potenssi fk(x) = xk mod n. Vaikka moduuli 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.

Hieman teoriaa taustaksi. 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

Hieman teoriaa taustaksi. 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.

(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.

Esimerkki. Valitaan alkuluvut p=5 ja q=11, jolloin n=55 ja Phi=4·10=40. Olkoon e=3. Seuraavaksi pitäisi ratkaista yhtälö ed=1 mod Phi eli 3d=1 mod 40. Tämä onnistuu päässälaskullakin: 3d=41 ei tosin käy, mutta 3d=81 (=9·9) toteutuu kun d=27.

Esimerkki. Valitaan alkuluvut p=5 ja q=11, jolloin n=55 ja Phi=4·10=40. Olkoon e=3. Seuraavaksi pitäisi ratkaista yhtälö ed=1 mod Phi eli 3d=1 mod 40. Tämä onnistuu päässälaskullakin: 3d=41 ei tosin käy, mutta 3d=81 (=9·9) toteutuu kun d=27.

Olkoon viesti m=13. Tällöin kryptoteksti on c=me mod n = 133 mod 55 =2197 mod 55 = 52. Laskimella, jossa tarkkuus riittää, voi heti todeta että cd mod n = 5227 mod 55 = 13. Suoraan korotettuna potenssi on noin 2·1046. On selvää, ettei tällaista operaatiota ehdi eikä mahdu tekemään millään kohtuullisilla resursseilla, kun luvut ovat monisatanumeroisia. Sen vuoksi potenssilasku tehdään seuraavaan tapaan, joka tekee tämän esimerkinkin mahdolliseksi vaikka laskimessa ei olisi kuin vaikkapa kahdeksan numeron tarkkuus.

Olkoon viesti m=13. Tällöin kryptoteksti on c=me mod n = 133 mod 55 =2197 mod 55 = 52. Laskimella, jossa tarkkuus riittää, voi heti todeta että cd mod n = 5227 mod 55 = 13. Suoraan korotettuna potenssi on noin 2·1046. On selvää, ettei tällaista operaatiota ehdi eikä mahdu tekemään millään kohtuullisilla resursseilla, kun luvut ovat monisatanumeroisia. Sen vuoksi potenssilasku tehdään seuraavaan tapaan, joka tekee tämän esimerkinkin mahdolliseksi vaikka laskimessa ei olisi kuin vaikkapa kahdeksan numeron tarkkuus.

Esitetään eksponentti kakkosen potenssien summana: 27 = 16+8+2+1, eli binäärilukuna 11011. Tämä tarkoittaa, että

Esitetään eksponentti kakkosen potenssien summana: 27 = 16+8+2+1, eli binäärilukuna 11011. Tämä tarkoittaa, että

c27=c1· c2· c8· c16 = c· c2· (x2)2· y2, missä on merkitty x= c2 ja y = (x2)2.

c27=c1· c2· c8· c16 = c· c2· (x2)2· y2, missä on merkitty x= c2 ja y = (x2)2.

Laskemalla vaiheittain neliöitä ja kertomalla niitä keskenään, päästään 26 kertolaskun sijasta 7:llä. Kun lisäksi joka välissä redusoidaan modulo 55, muistissa oleva luku ei koskaan ylitä arvoa 2916 (=54·54). ///

Laskemalla vaiheittain neliöitä ja kertomalla niitä keskenään, päästään 26 kertolaskun sijasta 7:llä. Kun lisäksi joka välissä redusoidaan modulo 55, muistissa oleva luku ei koskaan ylitä arvoa 2916 (=54·54). ///

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ä luku.

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ä luku.

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".

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".

RSA:ta käytetään allekirjoitukseen toisinpäin kuin salaukseen, jonka kuka tahansa voi tehdä julkisella avaimella. Allekirjoitus muodostetaan yksityisellä ja se todennetaan julkisella avaimella: Vain se, joka tuntee yksityisen eksponentin d, voi tuottaa viestistä m potenssin s=md mod n. Kun m ja s lähetetään yhdessä, kuka tahansa, joka tuntee vastaavan julkisen avaimen e, voi tarkistaa että m = se mod n. Jos siis d on osapuolen A yksityinen avain, niin A ei voi kiistää allekirjoittaneensa ja lähettäneensä viestiä m -- paitsi väittämällä että hänen avaimensa on paljastunut ... (tässä yhteydessä tarvitaan avaintenhallintaa ).

RSA:ta käytetään allekirjoitukseen toisinpäin kuin salaukseen, jonka kuka tahansa voi tehdä julkisella avaimella. Allekirjoitus muodostetaan yksityisellä ja se todennetaan julkisella avaimella: Vain se, joka tuntee yksityisen eksponentin d, voi tuottaa viestistä m potenssin s=md mod n. Kun m ja s lähetetään yhdessä, kuka tahansa, joka tuntee vastaavan julkisen avaimen e, voi tarkistaa että m = se mod n. Jos siis d on osapuolen A yksityinen avain, niin A ei voi kiistää allekirjoittaneensa ja lähettäneensä viestiä m -- paitsi väittämällä että hänen avaimensa on paljastunut ... (tässä yhteydessä tarvitaan avaintenhallintaa ).

-- JukkaKoskinen?

-- 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
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
r2 - 26 Sep 2010 - 11:10 - MarkoHelenius r1 - 18 Apr 2010 - 14:31 - MaijuLehtonen?

View topic | View difference interwoven | History: r2 < r1 | More topic actions
 
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