RSA

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8.5.2021 tarkistetusta versiosta . vahvistus vaatii 31 muokkausta .

RSA
Perustamis- / luomis- / esiintymispäivä	1977 [1]
Nimetty	Rivest, Ronald Lynn , Adi Shamir ja Leonard Max Adleman
Kaava, joka kuvaa lakia tai lausetta	$\left(m^{e}\right)^{d}\equiv m{\pmod {n}}$ [2]

RSA (lyhenne sanoista Rivest, Shamir ja Adleman) on julkisen avaimen salausalgoritmi, joka perustuu suuren kokonaisluvun tekijöiden jakamisen ongelman laskennalliseen monimutkaisuuteen .

RSA-salausjärjestelmä oli ensimmäinen järjestelmä, joka soveltui sekä salaukseen että digitaaliseen allekirjoitukseen . Algoritmia käytetään useissa salaussovelluksissa, mukaan lukien PGP , S/MIME , TLS / SSL , IPSEC / IKE ja muut [3] .

Historia

Ajatuksen epäsymmetrisestä julkisen/yksityisen avaimen salausjärjestelmästä antavat Whitfield Diffie ja Martin Hellman , jotka julkaisivat konseptin vuonna 1976. He esittelivät myös digitaalisia allekirjoituksia ja yrittivät soveltaa lukuteoriaa. Heidän muotoilussaan käytettiin jaettua salaista avainta, joka luotiin eksponentialisoimalla jokin luku modulo alkuluku. He jättivät kuitenkin avoimeksi ongelman yksisuuntaisen funktion toteuttamisesta, ehkä siksi, että tekijöiden jakamisen monimutkaisuutta ei silloin ymmärretty hyvin.

Ron Rivest, Adi Shamir ja Leonard Adleman MIT:stä tekivät useita yrityksiä vuoden aikana luodakseen yksisuuntaisen funktion, jota olisi vaikea kääntää. Rivest ja Shamir tietotekniikan tutkijoina ehdottivat monia mahdollisia ominaisuuksia, ja Adleman matemaatikkona oli vastuussa heidän heikkouksiensa löytämisestä. He kokeilivat monia lähestymistapoja, mukaan lukien "reppu" ja "permutaatiopolynomit". Hetken aikaa he ajattelivat, että se, mitä he halusivat saavuttaa, oli mahdotonta ristiriitaisten vaatimusten vuoksi. Huhtikuussa 1977 he viettivät pesachin erään opiskelijan kotona ja joivat paljon Manishevitz-viiniä ennen kuin palasivat kotiinsa puolenyön aikoihin. Rivest, joka ei pystynyt nukkumaan, makasi sohvalle matematiikan oppikirjansa kanssa ja alkoi miettiä yksipuolista toimintaansa. Hän vietti loppuyön ideansa virallistamiseen, ja aamunkoittoon mennessä suurin osa artikkelista oli valmis. Algoritmi tunnetaan nyt nimellä RSA - heidän sukunimiensä alkukirjaimet samassa järjestyksessä kuin heidän paperissaan.

Englantilainen matemaatikko Clifford Cox, joka työskentelee Britannian tiedustelupalvelun Government Communications Headquartersissa (GCHQ), kuvaili vastaavaa järjestelmää sisäisessä asiakirjassa vuonna 1973. Kuitenkin, kun otetaan huomioon sen toteuttamiseen tuolloin tarvittavat suhteellisen kalliit tietokoneet, sitä pidettiin enimmäkseen uteliaisuus, eikä sitä ole sikäli kuin tiedetään sovellettu. Hänen löytönsä paljastettiin kuitenkin vasta vuonna 1997 sen huippusalaisen luokituksen vuoksi.

Elokuussa 1977 ensimmäinen kuvaus RSA-salausjärjestelmästä [5] ilmestyi Martin Gardnerin "Mathematical Games" -sarakkeessa Scientific American -lehdessä Ronald Rivestin [4 ] luvalla . Lukijoita pyydettiin myös tulkitsemaan englanninkielinen lause, joka oli salattu kuvatulla algoritmilla:

9686 1477 8829 7431 0816 3569 8962 1829

9613 1409 0575 9874 2982 3147 8013 9451

7546 2225 9991 6951 2514 6622 3919 5781

2206 4355 1245 2093 5708 8839 9055 5154

Avoimen järjestelmän parametreina käytettiin numeroita n= 1143816...6879541 (129 desimaalin tarkkuutta, 425 bittiä , joka tunnetaan myös nimellä RSA-129 ) ja e=9007. Salauksen purkamisesta tarjottiin 100 dollarin palkkio. Rivestin mukaan luvun tekijöihin laskeminen kestäisi yli 40 kvadriljoonaa vuotta [6] [3] . Kuitenkin hieman yli 15 vuotta myöhemmin, 3. syyskuuta 1993, ilmoitettiin hajautetun laskentaprojektin käynnistämisestä sähköpostitse koordinoidusti RSA-129-numeron tekijöiden selvittämiseksi ja pulman ratkaisemiseksi. Kuuden kuukauden aikana yli 600 vapaaehtoista 20 maasta lahjoitti CPU-aikaa 1 600 laitteeseen (joista kolme oli faksilaitteita). ). Tuloksena päätekijät löydettiin ja alkuperäinen viesti purettiin, joka on lause " THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE " ("Magic words are a squeamish lamb ") [7] [8] . Voittajat lahjoittivat saamansa palkinnon Free Software Foundationille .

Martin Gardnerin julkaisun jälkeen kuka tahansa saattoi saada täydellisen kuvauksen uudesta salausjärjestelmästä lähettämällä pyynnön postitse Ronald Rivestille ja mukana kirjekuoressa palautusosoite ja postimerkit 35 sentillä. [5] Täydellinen kuvaus uudesta salausjärjestelmästä julkaistiin Communications of the ACM :ssä helmikuussa 1978 [9] .

Patenttihakemus jätettiin 14. joulukuuta 1977, ja MIT oli merkitty omistajaksi. Patentti 4405829 myönnettiin 20. syyskuuta 1983 ja sen voimassaolo päättyi 21. syyskuuta 2000 [10] . Yhdysvaltojen ulkopuolella keksijillä ei kuitenkaan ollut patenttia algoritmille, koska useimmissa maissa se oli hankittava ennen ensimmäistä julkaisua [11] .

Vuonna 1982 Rivest, Shamir ja Adleman perustivat RSA Data SecuritynEMC jaosto . Vuonna 1989 RSA mainitaan yhdessä symmetrisen salauksen DES kanssa RFC 1115 :ssä , mikä aloitti algoritmin käytön syntyvässä Internetissä [12] , ja vuonna 1990 Yhdysvaltain puolustusministeriö alkaa käyttää algoritmia [13] .

Marraskuussa 1993 julkistettiin avoimesti PKCS1 versio 1.5 , joka kuvaa RSA:n käyttöä salaukseen ja sähköisen allekirjoituksen luomiseen. Standardin uusimmat versiot ovat saatavilla myös RFC :inä ( RFC 2313 - 1.5, 1993; RFC 2437 - 2.0, 1998; RFC 3447 - 2.1, 2002).

Joulukuussa 1997 julkistettiin tiedot, joiden mukaan brittiläinen matemaatikko Clifford Cocks, joka työskenteli Yhdistyneen kuningaskunnan hallituksen viestintäkeskuksessa ( GCHQ ) , kuvaili vuonna 1973 RSA:n kaltaista kryptojärjestelmää [14] .

Algoritmin kuvaus

Johdanto

Julkisen avaimen salausjärjestelmät käyttävät niin sanottuja yksisuuntaisia toimintoja , joilla on seuraava ominaisuus:

jos tiedetään , se on suhteellisen helppo laskea; $x$ $f(x)$
jos tunnetaan , niin ei ole yksinkertaista (tehokasta) tapaa laskea . $y=f(x)$ $x$

Yksipuolisuutta ei ymmärretä matemaattisesti todistettuna yksisuuntaisuutena, vaan käänteisarvon käytännöllisenä mahdottomuutena laskea nykyaikaisilla laskentatyökaluilla ennakoitavissa olevassa aikavälissä.

RSA:n julkisen avaimen salausjärjestelmä perustuu kahden suuren alkuluvun tulon tekijöihin jakamiseen liittyvän ongelman monimutkaisuuteen. Salaukseen käytetään suuren luvun eksponentiointia . Salauksen purkamiseksi (käänteinen toiminta) kohtuullisessa ajassa sinun on kyettävä laskemaan tietyn suuren luvun Euler-funktio , jota varten sinun on tiedettävä luvun hajoaminen alkutekijöiksi.

Julkisen avaimen salausjärjestelmässä jokaisella osallistujalla on sekä julkinen avain ( englanniksi julkinen avain ) että yksityinen avain ( englanniksi yksityinen avain ). RSA-salausjärjestelmässä jokainen avain koostuu kokonaislukuparista. Jokainen osallistuja luo oman julkisen ja yksityisen avaimensa itse. Jokainen niistä pitää yksityisen avaimen salassa, ja julkiset avaimet voidaan jakaa kenelle tahansa tai jopa julkaista. Jokaisen RSA-salausjärjestelmän viestintäosapuolen julkiset ja yksityiset avaimet muodostavat "sovitetun parin" siinä mielessä, että ne ovat keskenään käänteisiä , eli:

\kaikille

voimassa olevat julkiset ja yksityiset avainparit

(p,s)

{\näyttötyyli \olemassa }

vastaavat salaus- ja salauksenpurkutoiminnot siten, että

E_{p}(x)

D_{s}(x)

\kaikille

viestit , missä on sallittujen viestien joukko,

m\in M

M

m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).

Algoritmi julkisten ja yksityisten avainten luomiseen

RSA-avaimet luodaan seuraavasti [15] :

1) valitaan kaksi erilaista satunnaista alkulukua ja tietty koko (esimerkiksi 1024 bittiä kumpikin);

s

q

2) heidän tulonsa lasketaan , jota kutsutaan moduuliksi ;

n=p\cdot q

3) Euler-funktion arvo lasketaan luvusta :

n

\varphi (n)=(p-1)\cdot (q-1)

; 4) valitaan kokonaisluku ( ), joka on alkuluku funktion arvon kanssa ;

e

1<e<\varphi(n)

\varphi (n)

lukua kutsutaan julkiseksi eksponenttiksi ; _ _

e

yleensä ne ottavat alkulukuja, jotka sisältävät pienen määrän yksittäisiä bittejä binäärimuodossa , esimerkiksi alkulukuja Fermat-luvuista : 17, 257 tai 65537, koska tässä tapauksessa nopeaa eksponentiota käyttävään salaukseen kuluva aika on vähemmän;

e

liian pienet arvot , kuten 3, voivat mahdollisesti heikentää RSA-järjestelmän turvallisuutta. [16] ;

e

5) lasketaan luku , joka on kertovasti käänteinen luvulle modulo , eli luku, joka tyydyttää vertailun :

d

e

\varphi (n)

d\cdot e\equiv 1{\pmod {\varphi (n)))

(lukua kutsutaan salaiseksi eksponenttiksi ; se lasketaan yleensä laajennetun Euklidisen algoritmin avulla );

d

6) pari on julkaistu julkisena RSA - avaimena ( RSA public key );

{\näyttötyyli (e,n)}

7) pari toimii RSA : n yksityisenä avaimena ja pidetään salassa .

{\näyttötyyli (d,n)}

Salaus ja salauksen purku

Oletetaan, että Bob haluaa lähettää viestin Alicelle . $m$

Viestit ovat kokonaislukuja välillä - , koprime - n, ts . . $0$ $n-1$ $m\in \mathbb {Z} _{n},\gcd(m,n)=1$

Salausalgoritmi [15] :

Hanki Alicen julkinen avain $(e,n)$
Ota selvää tekstiä $m$
Salaa viesti Alicen julkisella avaimella: $c=E(m)=m^{e}\mod n~~~~(1)$

Salauksen purkualgoritmi :

Vastaanota salattu viesti $c$
Ota yksityinen avaimesi $(d, n)$
Käytä yksityistä avainta viestin salauksen purkamiseen: $m=D(c)=c^{d}\mod n~~~~(2)$

Tätä mallia ei käytetä käytännössä, koska se ei ole käytännössä luotettava (semanttisesti suojattu). Itse asiassa yksisuuntainen funktio E(m) on deterministinen - samoilla syöttöparametrien arvoilla (näppäin ja viesti) se tuottaa saman tuloksen. Tämä tarkoittaa, että salauksen käytännön (semanttisen) luotettavuuden edellytys ei täyty.

Istuntoavaimen salausalgoritmi

Eniten käytössä tällä hetkellä[ milloin? ] on sekoitettu salausalgoritmi, jossa istuntoavain ensin salataan ja sitten osallistujat käyttävät sitä viestiensä salaamiseen symmetrisillä järjestelmillä. Istunnon päätyttyä istuntoavain yleensä tuhoutuu.

Istuntoavaimen salausalgoritmi on seuraava [17] :

Algoritmi :

Hanki Alicen julkinen avain $(e,n)$
Luo satunnainen istuntoavain $m$
Salaa istuntoavain Alicen julkisella avaimella: $c=E(m)=m^{e}\mod n$
Salaa viesti istuntoavaimella käyttämällä symmetristä algoritmia: $M_{A}$ $C=E_{m}(M_{A})$

Algoritmi :

Hyväksy Bobin salattu istuntoavain $c$
Ota yksityinen avaimesi $(d, n)$
Käytä yksityistä avainta istuntoavaimen salauksen purkamiseen: $m=D(c)=c^{d}\mod n$
Pura viestin salaus istuntoavaimella käyttämällä symmetristä algoritmia: $C$ $M_{A}=D_{m}(C)$

Siinä tapauksessa, että istuntoavain on suurempi kuin moduuli , istuntoavain jaetaan vaaditun pituisiin lohkoihin (tarvittaessa täytetään nollia) ja jokainen lohko salataan. $n$

RSA-skeeman oikeellisuus

Yhtälöt ja , joihin RSA-kaavio perustuu, määrittelevät joukon keskenään käänteisiä muunnoksia

(yksi)

(2)

\mathbb {Z} _{n}

Todiste [15] [18]

Todellakin, varten $\forall m\in \mathbb {Z} _{n}$

D\left({E\left(m\right)}\right)=E\left({D\left(m\right)}\right)=m^{ed}\mod n

Näytetään, että:

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod p

Kaksi tapausta on mahdollista:

$m\not \equiv 0\mod p$ .

Koska luvut ja ovat keskenään käänteisiä kertolaskumoduulin suhteen , ts $e$ $d$ $\varphi (n)=(p-1)(q-1)$

ed=1+k(p-1)(q-1)

jollekin kokonaisluvulle ,

k

sitten:

{\begin{aligned}m^{ed}&\equiv m^{1+k\left({p-1}\right)\left({q-1}\right)}&\equiv &\mod p \\&\equiv m\left({m^{p-1}}\right)^{k\left({q-1}\right)}&\equiv &\mod p\\&\equiv m\ vasen(1\oikea)^{k\left({q-1}\right)}&\equiv m&\mod p\end{aligned}}

jossa toinen identiteetti seuraa Fermatin lauseesta .

Harkitse toista tapausta:

m\equiv 0\mod p

sitten

m^{ed}\equiv 0\equiv m\mod p

Eli tasa-arvo kaikille $m$

m^{ed}\equiv m\mod p

Samalla tavalla voidaan osoittaa, että:

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod q

Sitten Kiinan jäännöslauseesta

\forall m\in \mathbb {Z} _{n}:m^{ed}\equiv m\mod n

Esimerkki

Vaihe	Toiminnan kuvaus	Operaation tulos
Avaimen sukupolvi	Valitse kaksi eri alkulukua	$p = 3557$ , $q = 2579$
	Laske tuote	$n=p\cdot q=3557\cdot 2579=9173503$
	Laske Euler-funktio	$\varphi (n)=(p-1)(q-1)=9167368$
	Valitse avoin näytteilleasettaja	$e=3$
	Laske salainen eksponentti	${\begin{aligned}d&=(k\cdot \varphi (n)+1)/e\\&=(2\cdot 9167368+1)/3\\&=6111579\end{aligned))$
	Julkaise julkinen avain	$\{e,n\}=\{3.9173503\}$
	Tallenna yksityinen avain	$\{d,n\}=\{6111579,9173503\}$
Salaus	Valitse salattava teksti	$m = 111111$
Salaus	Laske salateksti	${\begin{aligned}c&=E(m)\\&=m^{e}\mod n\\&=111111^{3}\mod 9173503\\&=4051753\end{aligned}}$
Salauksen purku	Laske alkuperäinen viesti	${\begin{aligned}m&=D(c)=\\&=c^{d}\mod n\\&=4051753^{6111579}\mod 9173503\\&=111111\end{aligned}}$

Digitaalinen allekirjoitus

RSA-järjestelmää voidaan käyttää paitsi salaukseen myös digitaaliseen allekirjoitukseen .

Oletetaan, että Liisa (puoli ) tarvitsee lähettää Bobille (side ) viestin , joka on vahvistettu sähköisellä digitaalisella allekirjoituksella . $A$ $B$ $m$

Algoritmi :

Ota selvää tekstiä $m$
Luo digitaalinen allekirjoitus yksityisellä avaimellasi : $s$ $\vasen\{d,n\oikea\}$

s=S_{A}\left(m\right)=m^{d}\mod n

Lähetä pari , joka koostuu viestistä ja allekirjoituksesta. $\vasen\{m,s\oikea\}$

Algoritmi :

Hyväksy pari $\vasen\{m,s\oikea\}$
Hanki Alicen julkinen avain $\vasen\{e,n\oikea\}$
Laske viestin esikuva allekirjoituksesta:

m'=P_{A}\left(s\right)=s^{e}\mod n

Tarkista allekirjoituksen aitous (ja viestin muuttumattomuus) vertaamalla ja $m$ $m'$

Koska digitaalinen allekirjoitus tarjoaa sekä viestin kirjoittajan autentikoinnin että todisteen allekirjoitetun viestin sisällön eheydestä, se on analoginen käsin kirjoitetun asiakirjan lopussa olevaan allekirjoitukseen.

Digitaalisen allekirjoituksen tärkeä ominaisuus on, että kuka tahansa, jolla on pääsy sen tekijän julkiseen avaimeen, voi tarkistaa sen. Yksi viestien vaihdon osallistujista voi digitaalisen allekirjoituksen aitouden tarkastettuaan siirtää allekirjoitetun viestin jollekin toiselle, joka pystyy myös varmistamaan tämän allekirjoituksen. Osapuoli voi esimerkiksi lähettää osapuolelle sähköisen shekin. Kun osapuoli on tarkistanut sekissä olevan osapuolen allekirjoituksen , se voi siirtää sen pankkiinsa, jonka työntekijöillä on myös mahdollisuus tarkistaa allekirjoitus ja suorittaa vastaava rahatapahtuma. $A$ $B$ $B$ $A$

Huomaa, että allekirjoitettua viestiä ei ole salattu . Se lähetetään alkuperäisessä muodossaan, eikä sen sisältöä ole suojattu yksityisyyden loukkauksilta. Yhdistämällä yllä olevat salaus- ja digitaaliset allekirjoitukset, RSA voi luoda viestejä, jotka ovat sekä salattuja että digitaalisesti allekirjoitettuja. Tätä varten kirjoittajan on ensin lisättävä viestiin digitaalinen allekirjoitus ja sitten salattava tuloksena oleva pari (joka koostuu itse viestistä ja sen allekirjoituksesta) vastaanottajalle kuuluvalla julkisella avaimella. Vastaanottaja purkaa vastaanotetun viestin salauksen yksityisellä avaimellaan [17] . Jos vedetään analogia tavallisten paperiasiakirjojen lähettämiseen, tämä prosessi on samanlainen kuin jos asiakirjan kirjoittaja laittaisi sinettinsä sen alle, sitten laittaisi sen paperikuoreen ja sinetöi sen niin, että kirjekuoren avasi vain henkilö, jolle viesti on osoitettu. $m$

RSA-algoritmin nopeus

Koska avainten luomista tapahtuu paljon harvemmin kuin salausta, salauksen purkamista sekä digitaalisen allekirjoituksen luomista ja todentamista toteuttavia toimintoja, laskentatehtävä edustaa pääasiallista laskennallista monimutkaisuutta. Tämä ongelma voidaan ratkaista käyttämällä nopeaa eksponentioalgoritmia . Tätä algoritmia käytettäessä laskenta vaatii modulo-kertooperaatioita [ 19] . $a=b^{c}{\bmod {n))$ $m^{e}{\bmod {n))$ $O\left(\ln e\right)$

Lisää

edustaa binäärijärjestelmässä: $e$

e=e_{k}\cpiste 2^{k}+e_{k-1}\cpiste 2^{k-1}+\pisteet +e_{1}\cpiste 2+e_{0}

, missä

e_{k}=1,e_{i}\in \left\{0,1\right\}

aseta ja laske sitten $m_{0}=m$ $i=1,\pisteet,k$

m_{i}=\left(m_{i-1}^{2}\cdot m^{e_{ki}}\right){\bmod {n}}

löytyy ja on haluttu arvo $m_{k}$ $m^{e}{\bmod {n))$

Koska jokainen laskenta vaiheessa 2 vaatii korkeintaan kolme modulokertoa ja tämä vaihe suoritetaan kerran, algoritmin monimutkaisuus voidaan arvioida arvolla . $n$ $k\leq \log _{2}e$ $O(\ln e)$

Julkisilla ja yksityisillä avaimilla suoritettavien toimintojen suoritusajan analysoimiseksi oletetaan, että julkinen avain ja yksityinen avain täyttävät suhteet , . Sitten niiden soveltamisprosesseissa suoritetaan vastaavasti myös modulo-kertoja . $\vasen\{e,n\oikea\}$ $\vasen\{d,n\oikea\}$ $\log _{2}e=O(1)$ $\log _{2}d\leq \beta$ $O\vasen(1\oikea)$ $O\left(\beta\oikea)$

Siten operaatioiden suoritusaika kasvaa nollasta poikkeavien bittien lukumäärän kasvaessa avoimen eksponentin e binääriesityksessä . Salausnopeuden lisäämiseksi e :n arvoksi valitaan usein 17 , 257 tai 65537 - alkuluvut , joiden binääriesitys sisältää vain kaksi yksikköä :

Heurististen arvioiden mukaan salaisen eksponentin pituus , joka riippuu ei-triviaalilla tavalla avoimesta eksponentista ja moduulista , on suurella todennäköisyydellä lähellä pituutta . Siksi tietojen salauksen purku on hitaampaa kuin salaus ja allekirjoituksen vahvistaminen on nopeampaa kuin sen luominen. $d$ $e$ $n$ $n$

RSA-algoritmi on paljon hitaampi kuin AES ja muut algoritmit, jotka käyttävät symmetrisiä lohkosalauksia .

Kiinalaisen jäännöslauseen käyttäminen salauksen purkamisen nopeuttamiseksi

Kun sanomaa puretaan tai allekirjoitetaan RSA-algoritmissa, laskettu eksponentti on melko suuri määrä (luokkaa 1000 bittiä). Siksi tarvitaan algoritmi, joka vähentää operaatioiden määrää. Koska yksityisen avaimen omistaja tuntee luvut ja hajotuksessa , voimme laskea: $s$ $q$ $N = pq$

m_{p}=C^{d}{\bmod {p}}=C^{d{\bmod {p-1}}}{\bmod {p}},

m_{q}=C^{d}{\bmod {q}}=C^{d{\bmod {q-1}}}{\bmod {q}}.

Koska ja ovat järjestyksen numeroita , nämä toiminnot vaativat kaksi luvun nostamista 512-bittiseksi tehomoduuliksi 512-bittiseksi numeroksi. Tämä on huomattavasti (1024 bitin testaus osoitti 3 kertaa) nopeampaa kuin 1024-bittisen tehomodulin nostaminen 1024-bittiseen numeroon. Seuraavaksi on vielä palautettava ja mitä voidaan tehdä käyttämällä kiinalaista jäännöslausetta [20] . $s$ $q$ $2^{512},$ $m$ $m_{p}$ $m_{q},$

RSA-skriptianalyysi

Algoritmin vahvuus perustuu salausfunktion käänteisfunktion laskemisen monimutkaisuuteen [21]

c=E(m)=m^{e}\mod n

Jotta voit laskea tunnetuista , sinun on löydettävä sellainen $m$ $c,e,n$ $d$

e\cdot d\equiv 1{\pmod {\varphi (n))),

eli etsi k : n käänteisalkio multiplikatiivisesta jäännösryhmästä modulo $e$ $\varphi(n).$

Käänteisen moduulin laskeminen ei ole vaikeaa, mutta hyökkääjä ei tiedä arvoa . Jotta voit laskea tunnetun luvun Euler-funktion , sinun on tiedettävä tämän luvun jakautuminen alkutekijöiksi. Tällaisten tekijöiden löytäminen on vaikea tehtävä, ja näiden tekijöiden tunteminen on "salainen ovi" ( englanniksi backdoor ), jota avaimen omistaja käyttää laskennassa . Alkutekijöiden löytämiseen on olemassa monia algoritmeja, ns. factorization , joista nopein on nykyään yleislukukenttäseulamenetelmä , jonka nopeus k-bittiselle kokonaisluvulle on $\varphi (n)$ $n$ $d$

\exp((c+o(1))k^{\frac {1}{3}}\log ^{\frac {2}{3}}k)

joillekin .

c<2

Vuonna 2010 joukko tutkijoita Sveitsistä, Japanista, Ranskasta, Alankomaista, Saksasta ja Yhdysvalloista onnistui laskemaan dataa, joka oli salattu 768-bittisellä RSA-salausavaimella. Alkutekijöiden löytäminen suoritettiin yleisellä lukukenttäseulan menetelmällä [22] . Tutkijoiden mukaan heidän työnsä jälkeen vain vähintään 1024 bitin pituisia RSA-avaimia voidaan pitää luotettavana salausjärjestelmänä. Lisäksi 1024-bittisellä avaimella salauksesta tulisi luopua seuraavien kolmen tai neljän vuoden aikana [23] . 31. joulukuuta 2013 alkaen Mozilla-selaimet eivät enää tue CA-varmenteita, joiden RSA-avaimet ovat alle 2048 bittiä [24] .

Lisäksi, jos algoritmi on toteutettu tai käytetty väärin tai alioptimaalisesti, erityiset kryptografiset hyökkäykset ovat mahdollisia, kuten hyökkäykset skeemoihin, joissa on pieni salainen eksponentti, tai skeemoja, joilla on yhteinen valittu moduuliarvo.

Hyökkäykset RSA-algoritmia vastaan

Wienerin hyökkäys RSA:ta vastaan

Joidenkin sovellusten on nopeutettava RSA-algoritmin salauksen purkuprosessia. Siksi valitaan pieni salauksenpurkueksponentti. Tapauksessa, jossa purkueksponentti voidaan määrittää polynomiajassa käyttämällä Wiener-hyökkäystä [20] , jatkuvien murtolukujen perusteella . $d<N^{\frac {1}{4}}$ $d$

Lisää Kun annetaan reaaliluku , määrittelemme sekvenssit:

\alpha \in \mathbb {R}

$\alpha _{0}=\alpha ,p_{0}=q_{0}=1,p_{1}=a_{0}a_{1}+1,q_{1}=a_{1},$
$\alpha _{i}=\lfloor \alpha _{i}\rfloor ,\alpha _{i+1}={\frac {1}{\alpha _{i}-a_{i}}},$
$p_{i}=a_{i}p_{i-1}+p_{i-1}$ klo $i\geq 2,$

q_{i}=a_{i}q_{i-1}+q_{i-1}

klo

i\geq 2.

Kokonaislukuja kutsutaan jatkuviksi murtoluvuiksi , jotka edustavat rationaalilukuja konvergentteina. Jokainen sopiva murtoluku on redusoitumaton, ja niiden nimittäjien kasvunopeus on verrattavissa eksponentiaaliseen. Yksi jatkuvien murtolukujen teorian tärkeimmistä tuloksista : $a_{0},a_{1},a_{2},...$ $\alpha,$ ${\frac {p_{i}}{q_{i}}}-$

Jos pelkistymätön murto -osa täyttää epäyhtälön:

{\frac {p}{q))

\left|\alpha -{\frac {p}{q}}\right|\leq {\frac {1}{2q^{2}}},

sitten yksi jatkuvan jakeen laajennuksen konvergenteista . ${\frac {p}{q}}-$ $\alpha$

Oletetaan, että meillä on moduuli ja anna hyökkääjän tietää salauseksponentti E, jolla on ominaisuus

N = pq,

q<p<2q.

Ed=1\mod \varphi ,

jossa Oletetaan myös, että koska tämä on totta useimmissa sovelluksissa. Oletuksista seuraa, että

\varphi =\varphi (N)=(p-1)(q-1).

E<\varphi ,

Ed-k\varphi=1.

Näin ollen

$\left|{\frac {E}{\varphi }}-{\frac {k}{d}}\right|={\frac {1}{d\varphi }}.$

\left|N-\varphi \right|=\left|p+q-1\right|<3N^{\frac {1}{2}}.

Tämä osoittaa, että melko hyvä likiarvo Indeedille,

{\frac {E}{N}}-

{\frac {k}{d}}.

\left|{\frac {E}{N}}-{\frac {k}{d}}\right|=\left|{\frac {Ed-Nk}{dN}}\right|=\left| {\frac {Ed-k\varphi -Nk+k\varphi }{dN}}\right|=\left|{\frac {1-k(N-\varphi )}{dN}}\right|\leq \left|{\frac {3kN^{\frac {1}{2}}}{dN}}\right|={\frac {3k}{dN^{\frac {1}{2}}}}.

Koska on ilmeistä Myös, koska oletettiin, että tarkoittaa, $E<\varphi ,$ $,k<d.$ $d<{\frac {1}{4}}N^{\frac {1}{4}}.$

\left|{\frac {E}{N}}-{\frac {k}{d}}\right|<{\frac {1}{2d^{2}}}.

Koska gcd on konvergentti murto-osan laajennuksessa jatkuvaksi . Siten voit selvittää dekoodauseksponentin korvaamalla lausekkeeseen vuorotellen sopivien murtolukujen nimittäjät: $(k,d)=1,$ ${\frac {k}{d}}-$ ${\frac {E}{N}}$

(M^{E})^{d}=M\mod N

jollekin satunnaisluvulle Saatuamme yhtäläisyyden, löydämme tarkistettavien sopivien murtolukujen kokonaismääräksi arviolta $M.$ $d.$ $O(logN).$

Yleistetty Wiener-hyökkäys

Yllä kuvattu Wiener-hyökkäys on mahdollinen vain, jos hyökkääjä on tietoinen epätasa-arvosta

d\leq {\frac {1}{3}}N^{\frac {1}{4}},

missä on salainen eksponentti ja RSA-moduuli. Bonnet ja Derfey pystyivät Coppersmithin lauseen kaksiulotteista analogia käyttäen yleistämään Wienerin hyökkäyksen [20] tapaukseen, jolloin $d$ $N$

d\leq N^{0,292}.

RSA:n sovellukset

RSA - järjestelmää käytetään ohjelmistojen suojaukseen ja digitaalisissa allekirjoitusmalleissa .

Sitä käytetään myös avoimessa PGP - salausjärjestelmässä ja muissa salausjärjestelmissä (esimerkiksi DarkCryptTC ja xdc-muoto) yhdessä symmetristen algoritmien kanssa .

Matalasta salausnopeudesta johtuen viestit salataan yleensä tehokkaammilla symmetrisillä algoritmeilla satunnaisella istuntoavaimella (esim. AES , IDEA , Serpent , Twofish ), ja vain tämä avain salataan RSA:lla, jolloin toteutetaan hybridisalausjärjestelmä . Tällaisella mekanismilla on mahdollisia haavoittuvuuksia, jotka johtuvat tarpeesta käyttää kryptografisesti vahvaa näennäissatunnaislukugeneraattoria satunnaisen symmetrisen salausistuntoavaimen luomiseen.

Muistiinpanot

↑ RSA suojelee edelleen salaisuuksia vuosien hyökkäysten jälkeen, ja se ansaitsee tunnustuksia perustajilleen - Society for Industrial and Applied Mathematics .
↑ Johdatus moderniin kryptografiaan (englanti) - 2 - CRC Press , 2015. - S. 411. - 583 s. — ISBN 978-1-4665-7026-9
↑ 1 2 Bakhtiari, Maarof, 2012 , s. 175.
↑ A Quarter Century of Recreational Mathematics, kirjoittanut Martin Gardner (englanniksi) (linkki ei saatavilla) . Tieteellinen amerikkalainen. - "Ronald L. Rivest Massachusetts Institute of Technologysta antoi minun olla ensimmäinen, joka paljastaa - elokuun 1977 kolumnissa - "julkisen avaimen" salausjärjestelmän, jonka hän oli yhdessä keksinyt." Haettu 3. maaliskuuta 2012. Arkistoitu alkuperäisestä 23. kesäkuuta 2012.
↑ 12 Gardner , 1977 .
↑ Bruce Schneier. Factoring - State of the Art and Predictions (englanniksi) (linkki ei saatavilla) (12. helmikuuta 1995). Haettu 3. maaliskuuta 2012. Arkistoitu alkuperäisestä 23. kesäkuuta 2012.
↑ Donald T. Davis. Keskustelu RSA-129-aktiviteetista (englanniksi) (linkki ei saatavilla) (25. marraskuuta 2003). Haettu 3. maaliskuuta 2012. Arkistoitu alkuperäisestä 23. kesäkuuta 2012.
↑ Chmora A. L. 4.6.4. Hajautettuun laskentaan perustuva tehohyökkäys // Moderni sovellettu kryptografia. - 2002. - 2000 kappaletta. — ISBN 5-85438-046-3 .
↑ Rivest, Shamir, Adleman, 1978 .
↑ Ronald L. Rivest et ai. Kryptografinen viestintäjärjestelmä ja -menetelmä
↑ Adam Takaisin. PGP-aikajana (englanniksi) (downlink) . Haettu 3. maaliskuuta 2012. Arkistoitu alkuperäisestä 23. kesäkuuta 2012.
↑ J. Linn. Internet-sähköpostin tietosuojan parantaminen: Osa III - Algoritmit, tilat ja tunnisteet (englanniksi) (linkki ei ole käytettävissä) (elokuu 1989). Haettu 18. maaliskuuta 2012. Arkistoitu alkuperäisestä 23. kesäkuuta 2012.
↑ RSA Security Inc. Yrityksen historia (englanniksi) (linkki ei saatavilla) . Rahoitusuniversumi. Haettu 18. maaliskuuta 2012. Arkistoitu alkuperäisestä 23. kesäkuuta 2012.
↑ CC Cocks Huomautus "ei-salaisesta salauksesta" Arkistoitu alkuperäisestä 4. elokuuta 2009. (englanniksi) 20. marraskuuta 1973
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , 8.2. RSA julkisen avaimen salaus.
↑ Boneh, 1999 .
↑ 1 2 Bruce Schneier. Applied Cryptography 2nd edition C++ protokollat, algoritmit ja lähteet
↑ Rivest, Shamir, Adleman, 1978 , s. 7-8.
↑ Rivest, Shamir, Adleman, 1978 , s. kahdeksan.
↑ 1 2 3 H. SMART Ohjelmoinnin maailma Kryptografia - toim. Technosphere, Moskova 2006
↑ Yang S. Y. RSA:n kryptaanalyysi. - M.-Izhevsk: Tutkimuskeskus "säännöllinen ja kaoottinen dynamiikka", Izhevsk Computer Research Institute, 2011. - 312 s.
↑ RSA-768:n tekijöitä koskeva ilmoitus Arkistoitu 13. huhtikuuta 2014 Wayback Machinessa
↑ RSA-768 Factorization Arkistoitu 13. joulukuuta 2012 Wayback Machinessa
↑ Päivämäärät MD5-pohjaisten allekirjoitusten ja 1024-bittisten moduulien asteittaiselle poistamiselle . Haettu 2. maaliskuuta 2013. Arkistoitu alkuperäisestä 20. marraskuuta 2012. (määrätön)

Kirjallisuus

Diffie W. , Hellman M.E. Uusia suuntauksia kryptografiassa // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1976. - Voi. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
Gardner M. Uudenlainen salaus, jonka rikkoutuminen kestäisi miljoonia vuosia // Sci . amer. - NYC : NPG , 1977. - Voi. 237, Iss. 2. - s. 120-124. — ISSN 0036-8733 ; 1946-7087 - doi:10.1038/SCIENTIFICAMERICAN0877-120
Rivest R. , Shamir A. , Adleman L. Menetelmä digitaalisten allekirjoitusten ja julkisen avaimen salausjärjestelmien hankkimiseksi (englanniksi) // Commun. ACM - [New York] : Association for Computing Machinery , 1978. - Voi. 21, Iss. 2. - s. 120-126. — ISSN 0001-0782 ; 1557-7317 - doi:10.1145/359340.359342
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (englanti) - CRC Press , 1996. - 816 s. — ( Diskreetti matematiikka ja sen sovellukset ) — ISBN 978-0-8493-8523-0
Boneh D. Kaksikymmentä vuotta hyökkäyksiä RSA:n salausjärjestelmää vastaan // Notices Amer . Matematiikka. soc. / F. Morgan - AMS , 1999. - Voi. 46, Iss. 2. - s. 203-213. — ISSN 0002-9920 ; 1088-9477
Bakhtiari M. , Maarof M. A. Serious Security Weakness in RSA Cryptosystem (englanniksi) // IJCSI - 2012. - Vol. 9, Iss. 1, nro 3. - P. 175-178. — ISSN 1694-0814 ; 1694-0784

Nils Ferguson , Bruce Schneier . Käytännön kryptografia = Käytännön kryptografia: Turvallisten kryptografisten järjestelmien suunnittelu ja toteutus. - M . : Dialektiikka, 2004. - 432 s. - 3000 kappaletta. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
muu	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti