RSA

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 maj 2021; verifiering kräver 31 redigeringar .

RSA
Datum för stiftelse/skapande/förekomst	1977 [1]
Döpt efter	Rivest, Ronald Lynn , Adi Shamir och Leonard Max Adleman
Formel som beskriver en lag eller teorem	$\left(m^{e}\right)^{d}\equiv m{\pmod {n}}$ [2]

RSA (en akronym för Rivest, Shamir och Adleman) är en kryptografisk algoritm med offentlig nyckel baserad på beräkningskomplexiteten hos problemet med faktorisering av stora heltal .

RSA-krypteringssystemet var det första systemet som lämpade sig för både kryptering och digital signatur . Algoritmen används i ett stort antal kryptografiska applikationer, inklusive PGP , S/MIME , TLS / SSL , IPSEC / IKE och andra [3] .

Historik

Idén om ett asymmetriskt kryptosystem för offentlig/privat nyckel tillskrivs Whitfield Diffie och Martin Hellman , som publicerade konceptet 1976. De introducerade även digitala signaturer och försökte tillämpa talteori. Deras formulering använde en delad hemlig nyckel skapad genom att exponentialisera något tal modulo ett primtal. Men de lämnade problemet med att implementera en enkelriktad funktion öppet, kanske för att komplexiteten i faktorisering inte var väl förstått vid den tiden.

Ron Rivest, Adi Shamir och Leonard Adleman vid MIT gjorde flera försök under loppet av ett år för att skapa en enkelriktad funktion som skulle vara svår att invertera. Rivest och Shamir, som datavetare, föreslog många potentiella funktioner, och Adleman, som matematiker, var ansvarig för att hitta deras svagheter. De försökte många tillvägagångssätt, inklusive "knapsäck" och "permutationspolynom". Ett tag trodde de att det de ville uppnå var omöjligt på grund av motstridiga krav. I april 1977 tillbringade de pesach hemma hos en student och drack mycket Manishevitz-vin innan de återvände till sitt hem runt midnatt. Rivest, oförmögen att sova, lade sig på soffan med sin mattebok och började fundera på sin ensidiga funktion. Han tillbringade resten av natten med att formalisera sin idé, och i gryningen var det mesta av artikeln klar. Algoritmen är nu känd som RSA - initialerna till deras efternamn, i samma ordning som i deras papper.

Clifford Cox, en engelsk matematiker som arbetar för den brittiska underrättelsetjänsten Government Communications Headquarters (GCHQ), beskrev motsvarande system i ett internt dokument 1973. Men med tanke på de relativt dyra datorer som krävdes för att implementera det vid den tiden, ansågs det mestadels vara en nyfikenhet och, så vitt bekant, har den inte tillämpats. Men hans upptäckt avslöjades först 1997 på grund av dess topphemliga klassificering.

I augusti 1977 dök den första beskrivningen av RSA-kryptosystemet [5] upp i Martin Gardners kolumn "Mathematical Games" i Scientific American med tillstånd av Ronald Rivest [4 ] . Läsarna ombads också att dechiffrera en engelsk fras krypterad med den beskrivna algoritmen:

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

Siffrorna n= 1143816...6879541 (129 decimaler, 425 bitar , även känd som RSA-129 ) och e=9007 användes som parametrar för öppna system. En belöning på 100 $ erbjöds för dekryptering. Enligt Rivest skulle det ta mer än 40 kvadrilljoner år att faktorisera ett tal [6] [3] . Men lite mer än 15 år senare, den 3 september 1993, tillkännagavs lanseringen av ett distribuerat datorprojekt med samordning via e-post för att hitta faktorerna för RSA-129-numret och lösa pusslet. Under loppet av sex månader donerade mer än 600 frivilliga från 20 länder CPU-tid till 1 600 maskiner (varav tre var faxar). ). Som ett resultat hittades primära faktorer och det ursprungliga meddelandet dechiffrerades, vilket är frasen " DE MAGISKA ORDEN ÄR SQUEAMISH OSSIFRAGE " ("Magiska ord är ett bråkigt lamm ") [7] [8] . Vinnarna donerade priset de fick till Free Software Foundation .

Efter publiceringen av Martin Gardner kunde vem som helst få en fullständig beskrivning av det nya kryptosystemet genom att skicka en förfrågan per post till Ronald Rivest med ett bifogat kuvert med en returadress och frimärken för 35 cent. [5] En fullständig beskrivning av det nya kryptosystemet publicerades i Communications of the ACM i februari 1978 [9] .

Patentansökan lämnades in den 14 december 1977, med MIT listad som ägare. Patent 4405829 utfärdades den 20 september 1983 och upphörde att gälla den 21 september 2000 [10] . Men utanför USA hade uppfinnarna inget patent på algoritmen, eftersom det i de flesta länder var nödvändigt att skaffa det innan den första publiceringen [11] .

1982 grundade Rivest, Shamir och Adleman RSA Data Security division av EMC . 1989 nämns RSA, tillsammans med det symmetriska chiffret DES , i RFC 1115 , och startar därmed användningen av algoritmen i det begynnande Internet [12] , och 1990 börjar det amerikanska försvarsdepartementet använda algoritmen [13] .

I november 1993 publiceras öppet version 1.5 av PKCS1- , som beskriver användningen av RSA för kryptering och skapande av en elektronisk signatur. De senaste versionerna av standarden finns också tillgängliga som RFC ( RFC 2313 - 1.5, 1993; RFC 2437 - 2.0, 1998; RFC 3447 - 2.1, 2002).

I december 1997 offentliggjordes information enligt vilken den brittiske matematikern Clifford Cocks, som arbetade vid UK Government Communications Centre ( GCHQ ) , beskrev ett kryptosystem liknande RSA 1973 [14] .

Beskrivning av algoritmen

Introduktion

Kryptografiska system med offentlig nyckel använder så kallade envägsfunktioner , som har följande egenskap:

om känt är det relativt lätt att beräkna; $x$ $f(x)$
om det är känt så finns det inget enkelt (effektivt) sätt att beräkna . $y=f(x)$ $x$

Ensidighet förstås inte som en matematiskt bevisad enkelriktighet, utan den praktiska omöjligheten att beräkna det ömsesidiga värdet med hjälp av moderna beräkningsverktyg inom ett överskådligt tidsintervall.

RSA-krypteringssystemet för publik nyckel är baserat på komplexiteten i problemet med faktorisering av produkten av två stora primtal. För kryptering används driften av exponentieringsmodulo ett stort antal. För att dekryptera (omvänd operation) inom rimlig tid måste du kunna beräkna Euler-funktionen för ett givet stort tal, för vilket du behöver veta sönderdelningen av talet till primtalsfaktorer.

I ett kryptografiskt system med offentlig nyckel har varje deltagare både en offentlig nyckel ( engelsk offentlig nyckel ) och en privat nyckel ( engelsk privat nyckel ). I det kryptografiska systemet RSA består varje nyckel av ett par heltal. Varje deltagare skapar sin egen offentliga och privata nyckel på egen hand. Var och en av dem håller den privata nyckeln hemlig, och offentliga nycklar kan delas med vem som helst eller till och med publiceras. De offentliga och privata nycklarna för varje meddelandedeltagare i RSA-krypteringssystemet bildar ett "matchat par" i den meningen att de är ömsesidigt inversa , dvs.

\för alla

giltiga offentliga och privata nyckelpar

(p,s)

\exists

motsvarande kryptering och dekrypteringsfunktioner så att

E_{p}(x)

D_{s}(x)

\för alla

meddelanden , var är uppsättningen av tillåtna meddelanden,

m\in M

M

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

Algoritm för att generera offentliga och privata nycklar

RSA-nycklar genereras enligt följande [15] :

1) två olika slumpmässiga primtal och en given storlek väljs (till exempel 1024 bitar vardera);

sid

q

2) deras produkt beräknas , vilket kallas modulen ;

n=p\cdot q

3) värdet på Euler-funktionen beräknas från talet :

n

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

; 4) ett heltal ( ) väljs som är coprime med värdet på funktionen ;

e

1<e<\varphi(n)

\varphi (n)

numret kallas en offentlig exponent ; _

e

vanligtvis tar de som primtal som innehåller ett litet antal enstaka bitar i binär notation , till exempel primtal från Fermat-talen : 17, 257 eller 65537, eftersom i detta fall den tid som krävs för kryptering med snabb exponentiering kommer att vara kortare;

e

värden som är för små , såsom 3, kan potentiellt försvaga säkerheten för RSA-systemet. [16] ;

e

5) ett tal beräknas som är multiplikativt inverst till talet modulo , det vill säga ett tal som uppfyller jämförelsen :

d

e

\varphi (n)

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

(talet kallas den hemliga exponenten ; det beräknas vanligtvis med den utökade euklidiska algoritmen );

d

6) paret publiceras som en offentlig RSA - nyckel ( publik RSA-nyckel );

(e,n)

7) paret spelar rollen som en privat RSA -nyckel och hålls hemligt .

(d,n)

Kryptering och dekryptering

Anta att Bob vill skicka ett meddelande till Alice . $m$

Meddelanden är heltal i intervallet från till , coprime till n, dvs. . $0$ $n-1$ $m\in \mathbb {Z} _{n},\gcd(m,n)=1$

Krypteringsalgoritm [15] :

Få Alices publika nyckel $(e,n)$
Ta klartext $m$
Kryptera ett meddelande med Alices publika nyckel: $c=E(m)=m^{e}\mod n~~~~(1)$

Dekrypteringsalgoritm :

Ta emot krypterade meddelanden $c$
Ta din privata nyckel $(d,n)$
Använd den privata nyckeln för att dekryptera meddelandet: $m=D(c)=c^{d}\mod n~~~~(2)$

Detta schema används inte i praktiken på grund av att det inte är praktiskt tillförlitligt (semantiskt säkrat). Faktum är att envägsfunktionen E(m) är deterministisk - med samma värden på ingångsparametrarna (nyckel och meddelande) ger den samma resultat. Detta innebär att det nödvändiga villkoret för chifferets praktiska (semantiska) tillförlitlighet inte är uppfyllt.

Sessionsnyckelkrypteringsalgoritm

Mest använda just nu[ när? ] är en blandad krypteringsalgoritm där sessionsnyckeln först krypteras, och sedan använder deltagarna den för att kryptera sina meddelanden med symmetriska system. När sessionen avslutas förstörs vanligtvis sessionsnyckeln.

Sessionsnyckelns krypteringsalgoritm är som följer [17] :

Algoritm :

Få Alices publika nyckel $(e,n)$
Skapa en slumpmässig sessionsnyckel $m$
Kryptera sessionsnyckeln med Alices publika nyckel: $c=E(m)=m^{e}\mod n$
Kryptera meddelandet med sessionsnyckeln med en symmetrisk algoritm: $M_{A}$ $C=E_{m}(M_{A})$

Algoritm :

Acceptera Bobs krypterade sessionsnyckel $c$
Ta din privata nyckel $(d,n)$
Använd den privata nyckeln för att dekryptera sessionsnyckeln: $m=D(c)=c^{d}\mod n$
Dekryptera meddelandet med sessionsnyckeln med en symmetrisk algoritm: $C$ $M_{A}=D_{m}(C)$

I fallet när sessionsnyckeln är större än modulen delas sessionsnyckeln in i block med den erforderliga längden (om nödvändigt, utfylld med nollor) och varje block krypteras. $n$

RSA-schemats korrekthet

Ekvationerna och , på vilka RSA-schemat är baserat, definierar ömsesidigt inversa transformationer av mängden

(ett)

(2)

\mathbb {Z} _{n}

Bevis [15] [18]

Ja, för $\forall m\in \mathbb {Z} _{n}$

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

Låt oss visa att:

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

Två fall är möjliga:

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

Eftersom talen och är ömsesidigt inversa med avseende på multiplikation modulo , dvs $e$ $d$ $\varphi (n)=(p-1)(q-1)$

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

för något heltal ,

k

sedan:

{\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\ left(1\right)^{k\left({q-1}\right)}&\equiv m&\mod p\end{aligned}}

där den andra identiteten följer av Fermats sats .

Tänk på det andra fallet:

m\ekvivalent 0\mod sid

sedan

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

Alltså, för alla , jämlikheten $m$

m^{ed}\equiv m\mod sid

På samma sätt kan man visa att:

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

Sedan, från den kinesiska restsatsen

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

Exempel

Skede	Operationsbeskrivning	Operationsresultat
Nyckelgenerering _	Välj två olika primtal	$p=3557$ , $q=2579$
	Beräkna produkt	$n=p\cdot q=3557\cdot 2579=9173503$
	Beräkna Euler-funktionen	$\varphi (n)=(p-1)(q-1)=9167368$
	Välj en öppen utställare	$e=3$
	Beräkna hemlig exponent	${\begin{aligned}d&=(k\cdot \varphi (n)+1)/e\\&=(2\cdot 9167368+1)/3\\&=6111579\end{aligned))$
	Publicera offentlig nyckel	$\{e,n\}=\{3.9173503\}$
	Spara privat nyckel	$\{d,n\}=\{6111579,9173503\}$
Kryptering	Välj text att kryptera	$m=111111$
Kryptering	Beräkna chiffertext	${\begin{aligned}c&=E(m)\\&=m^{e}\mod n\\&=111111^{3}\mod 9173503\\&=4051753\end{aligned}}$
Dekryptering	Beräkna originalmeddelandet	${\begin{aligned}m&=D(c)=\\&=c^{d}\mod n\\&=4051753^{6111579}\mod 9173503\\&=111111\end{aligned}}$

Digital signatur

RSA-systemet kan användas inte bara för kryptering utan även för digital signatur .

Anta att Alice (sida ) behöver skicka ett meddelande till Bob (sida) som bekräftas av en elektronisk digital signatur . $A$ $B$ $m$

Algoritm :

Ta klartext $m$
Skapa en digital signatur med din privata nyckel : $s$ $\left\{d,n\right\}$

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

Skicka ett par bestående av ett meddelande och en signatur. $\left\{m,s\right\}$

Algoritm :

Acceptera ett par $\left\{m,s\right\}$
Få Alices publika nyckel $\left\{e,n\right\}$
Beräkna meddelandeförbild från signatur:

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

Verifiera signaturens äkthet (och meddelandets oföränderlighet) genom att jämföra och $m$ $m'$

Eftersom en digital signatur ger både autentisering av författaren till ett meddelande och bevis på integriteten hos innehållet i det signerade meddelandet, är det analogt med en handskriven signatur i slutet av ett handskrivet dokument.

En viktig egenskap hos en digital signatur är att den kan verifieras av alla som har tillgång till författarens publika nyckel. En av deltagarna i meddelandeutbytet kan, efter att ha verifierat den digitala signaturens äkthet, överföra det signerade meddelandet till någon annan som också kan verifiera denna signatur. En part kan till exempel skicka en elektronisk check till parten. Efter att parten kontrollerat partens underskrift på checken kan den överföra den till sin bank, vars anställda också har möjlighet att kontrollera signaturen och utföra motsvarande monetära transaktion. $A$ $B$ $B$ $A$

Observera att det signerade meddelandet inte är krypterat . Den skickas i sin ursprungliga form och dess innehåll är inte skyddat från integritetskränkningar. Genom att kombinera ovanstående kryptering och digitala signaturscheman kan RSA skapa meddelanden som är både krypterade och digitalt signerade. För att göra detta måste författaren först lägga till sin digitala signatur i meddelandet och sedan kryptera det resulterande paret (bestående av själva meddelandet och signaturen till det) med hjälp av den publika nyckeln som tillhör mottagaren. Mottagaren dekrypterar det mottagna meddelandet med sin privata nyckel [17] . Om vi drar en analogi med att skicka vanliga pappersdokument, så liknar denna process hur om författaren till dokumentet satte sitt sigill under det och sedan lade det i ett papperskuvert och förseglade det så att kuvertet endast öppnades av person som meddelandet var adresserat till. $m$

Hastigheten för RSA-algoritmen

Eftersom nyckelgenerering sker mycket mer sällan än operationer som implementerar kryptering, dekryptering, samt skapande och verifiering av en digital signatur, representerar beräkningsuppgiften den huvudsakliga beräkningskomplexiteten. Detta problem kan lösas med den snabba exponentieringsalgoritmen . Med denna algoritm kräver beräkningen modulo multiplikationsoperationer [ 19] . $a=b^{c}{\bmod {n))$ $m^{e}{\bmod {n))$ $O\vänster(\ln e\höger)$

Mer

representerar i det binära systemet: $e$

e=e_{k}\cdot 2^{k}+e_{k-1}\cdot 2^{k-1}+\dots +e_{1}\cdot 2+e_{0}

, var

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

ställ in och beräkna sedan för $m_{0}=m$ $i=1,\prickar ,k$

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

hittas och kommer att vara det önskade värdet $m_{k}$ $m^{e}{\bmod {n))$

Eftersom varje beräkning i steg 2 inte kräver mer än tre modulo-multiplikationer och detta steg utförs en gång, kan komplexiteten hos algoritmen uppskattas med värdet . $n$ $k\leq \log _{2}e$ $O(\ln e)$

För att analysera exekveringstiden för operationer med publika och privata nycklar, anta att den publika nyckeln och den privata nyckeln uppfyller relationerna , . Sedan, i processerna för deras tillämpning, utförs också modulo-multiplikationer . $\left\{e,n\right\}$ $\left\{d,n\right\}$ $\log _{2}e=O(1)$ $\log _{2}d\leq \beta$ $O\vänster(1\höger)$ $O\vänster(\beta\höger)$

Sålunda växer exekveringstiden för operationer med en ökning av antalet bitar som inte är noll i den binära representationen av den öppna exponenten e . För att öka krypteringshastigheten väljs ofta värdet på e lika med 17 , 257 eller 65537 - primtal , vars binära representation endast innehåller två enheter :

Enligt heuristiska uppskattningar är längden på den hemliga exponenten , som beror på ett icke-trivialt sätt på den öppna exponenten och modulen , nära längden med hög sannolikhet . Därför är datadekryptering långsammare än kryptering, och signaturverifiering är snabbare än att den skapas. $d$ $e$ $n$ $n$

RSA-algoritmen är mycket långsammare än AES och andra algoritmer som använder symmetriska blockchiffer .

Använder den kinesiska restsatsen för att påskynda dekryptering

Vid dekryptering eller signering av ett meddelande i RSA-algoritmen kommer den beräknade exponenten att vara ett ganska stort antal (i storleksordningen 1000 bitar). Därför krävs en algoritm som minskar antalet operationer. Eftersom siffrorna och i nedbrytningen är kända för ägaren av den privata nyckeln, kan vi beräkna: $sid$ $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}}.

Eftersom och är nummer av ordning , kommer dessa operationer att kräva två som höjer numret till en 512-bitars effektmodulo ett 512-bitars nummer. Detta är betydligt (för 1024-bitars testning visade 3 gånger) snabbare än en höjning till en 1024-bitars effektmodulo ett 1024-bitars nummer. Därefter återstår att återställa genom och vad som kan göras med den kinesiska restsatsen [20] . $sid$ $q$ $2^{512},$ $m$ $m_{p}$ $m_{q},$

RSA-krypteringsanalys

Algoritmens styrka är baserad på komplexiteten i att beräkna den inversa funktionen till krypteringsfunktionen [21]

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

För att beräkna från kända måste du hitta sådana $m$ $c,e,n$ $d$

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

det vill säga hitta det inversa elementet av k i den multiplikativa restgruppen modulo $e$ $\varphi(n).$

Att beräkna den omvända modulo är inte svårt, men angriparen vet inte värdet på . För att beräkna Euler-funktionen för ett känt tal måste du känna till sönderdelningen av detta tal i primtalsfaktorer. Att hitta sådana faktorer är en svår uppgift, och att känna till dessa faktorer är en "hemlig dörr" ( engelska bakdörr ), som används för beräkning av nyckelns ägare. Det finns många algoritmer för att hitta primtalsfaktorer, den så kallade faktoriseringen , den snabbaste idag är den generella talfältssiktmetoden , vars hastighet för ett k-bitars heltal är $\varphi (n)$ $n$ $d$

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

för vissa .

c<2

Under 2010 beräknade en grupp forskare från Schweiz, Japan, Frankrike, Nederländerna, Tyskland och USA framgångsrikt data krypterad med en 768-bitars RSA-krypteringsnyckel. Att hitta primtalsfaktorer utfördes med den allmänna metoden för talfältssikten [22] . Enligt forskarna kan endast RSA-nycklar med en längd på 1024 bitar eller mer efter deras arbete betraktas som ett tillförlitligt krypteringssystem. Dessutom bör kryptering med en nyckel på 1024 bitar överges under de kommande tre till fyra åren [23] . Från och med den 31 december 2013 stöder Mozilla-webbläsare inte längre CA-certifikat med RSA-nycklar mindre än 2048 bitar [24] .

Dessutom, när algoritmen är felaktigt eller suboptimalt implementerad eller används, är speciella kryptografiska attacker möjliga, såsom attacker på scheman med en liten hemlig exponent eller scheman med ett gemensamt valt modulvärde.

Attacker på RSA-algoritmen

Wieners attack mot RSA

Vissa applikationer behöver påskynda dekrypteringsprocessen i RSA-algoritmen. Därför väljs en liten dekrypteringsexponent. I fallet där dechiffreringsexponenten kan bestämmas i polynomtid med hjälp av Wiener-attacken [20] , baserat på fortsatta bråktal . $d<N^{\frac {1}{4}}$ $d$

Mer Givet ett reellt tal definierar vi sekvenser:

\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}$ på $i\geq 2,$

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

på

i\geq 2.

Heltal kallas fortsatta bråk , som representerar rationella tal som konvergenter. Var och en av de lämpliga fraktionerna är irreducerbara och tillväxthastigheten för deras nämnare är jämförbar med den exponentiella. Ett av de viktiga resultaten av teorin om fortsatta bråk : $a_{0},a_{1},a_{2},...$ $\alfa,$ ${\frac {p_{i}}{q_{i}}}-$

Om den irreducerbara bråkdelen uppfyller ojämlikheten:

{\frac {p}{q))

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

sedan en av konvergenterna i den fortsatta fraktionsexpansionen . ${\frac {p}{q}}-$ $\alfa$

Anta att vi har en modul och Låt angriparen veta krypteringsexponenten E, som har egenskapen

N=pq,

q<p<2q.

Ed=1\mod \varphi ,

där Vi kommer också att anta att eftersom detta är sant i de flesta applikationer. Av antagandena följer det

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

E<\varphi ,

Ed-k\varphi=1.

Följaktligen,

$\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}}.

Detta visar att en ganska bra uppskattning för Indeed,

{\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}}}}.

Eftersom det är uppenbart , eftersom det antogs att betyder, $E<\varphi ,$ $,k<d.$ $d<{\frac {1}{4}}N^{\frac {1}{4}}.$

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

Eftersom gcd är en konvergent i expansionen av en fraktion till en kontinuerlig . Således kan du ta reda på avkodningsexponenten genom att omväxlande ersätta nämnare för lämpliga bråk i uttrycket: $(k,d)=1,$ ${\frac {k}{d}}-$ ${\frac {E}{N}}$

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

för något slumptal Efter att ha erhållit likhet finner vi att det totala antalet lämpliga bråk, som måste kontrolleras, uppskattas som $M.$ $d.$ $O(logN).$

Generaliserad Wiener-attack

Wienerattacken som beskrivs ovan är endast möjlig om angriparen är medveten om ojämlikheten

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

där är den hemliga exponenten och är RSA-modulen. Bonnet och Derfey, med hjälp av en tvådimensionell analog av Coppersmith's Theorem , kunde generalisera Wieners attack [20] till fallet när $d$ $N$

d\leq N^{0,292}.

Tillämpningar av RSA

RSA-systemet används för programvaruskydd och i digitala signatursystem .

Det används också i PGP öppna krypteringssystem och andra krypteringssystem (till exempel DarkCryptTC och xdc-formatet) i kombination med symmetriska algoritmer .

På grund av den låga krypteringshastigheten krypteras meddelanden vanligtvis med mer effektiva symmetriska algoritmer med en slumpmässig sessionsnyckel (till exempel AES , IDEA , Serpent , Twofish ), och endast denna nyckel krypteras med RSA, så ett hybridkryptosystem implementeras . En sådan mekanism har potentiella sårbarheter på grund av behovet av att använda en kryptografiskt stark pseudoslumptalsgenerator för att generera en slumpmässig symmetrisk krypteringssessionsnyckel.

Anteckningar

↑ Bevakar fortfarande hemligheter efter år av attacker, RSA tjänar utmärkelser för sina grundare - Society for Industrial and Applied Mathematics .
↑ Introduktion till modern kryptografi (engelska) - 2 - CRC Press , 2015. - P. 411. - 583 s. — ISBN 978-1-4665-7026-9
↑ 1 2 Bakhtiari, Maarof, 2012 , sid. 175.
↑ A Quarter Century of Recreational Mathematics, av Martin Gardner (engelska) (länk ej tillgänglig) . Scientific American. — "Ronald L. Rivest vid Massachusetts Institute of Technology tillät mig att vara den första att avslöja - i kolumnen i augusti 1977 - det "publickey" chiffersystem som han var med och uppfann." Hämtad 3 mars 2012. Arkiverad från originalet 23 juni 2012.
↑ 12 Gardner , 1977 .
↑ Bruce Schneier. Factoring - State of the Art och prognoser (engelska) (inte tillgänglig länk) (12 februari 1995). Hämtad 3 mars 2012. Arkiverad från originalet 23 juni 2012.
↑ Donald T. Davis. En diskussion om RSA-129-aktivitet (engelska) (länk ej tillgänglig) (25 november 2003). Hämtad 3 mars 2012. Arkiverad från originalet 23 juni 2012.
↑ Chmora A. L. 4.6.4. Kraftattack baserad på distribuerad beräkning // Modern tillämpad kryptografi. - 2002. - 2000 exemplar. — ISBN 5-85438-046-3 .
↑ Rivest, Shamir, Adleman, 1978 .
↑ Ronald L. Rivest et al. Kryptografiskt kommunikationssystem och metod
↑ Adam Back. PGP-tidslinje (engelska) (nedlänk) . Hämtad 3 mars 2012. Arkiverad från originalet 23 juni 2012.
↑ J. Linn. Sekretessförbättring för e-post via Internet: Del III - Algoritmer, lägen och identifierare (engelska) (länk ej tillgänglig) (augusti 1989). Hämtad 18 mars 2012. Arkiverad från originalet 23 juni 2012.
↑ RSA Security Inc. Företagshistorik (engelska) (länk ej tillgänglig) . Finansieringsuniversum. Hämtad 18 mars 2012. Arkiverad från originalet 23 juni 2012.
↑ CC Cocks En anteckning om "icke-hemlig kryptering" Arkiverad från originalet den 4 augusti 2009. (engelska) 20 november 1973
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996 , 8.2. RSA-kryptering med offentlig nyckel.
↑ Boneh, 1999 .
↑ 1 2 Bruce Schneier. Tillämpad kryptografi 2nd edition C++-protokoll, algoritmer och källor
↑ Rivest, Shamir, Adleman, 1978 , s. 7-8.
↑ Rivest, Shamir, Adleman, 1978 , sid. åtta.
↑ 1 2 3 H. SMART Programmeringsvärlden Kryptografi - ed. Technosphere, Moskva 2006
↑ Yang S. Y. Cryptanalysis of RSA. - M.-Izhevsk: Forskningscentrum "Regular and Chaotic Dynamics", Izhevsk Institute of Computer Research, 2011. - 312 sid.
↑ RSA-768 faktoriseringsmeddelande Arkiverad 13 april 2014 på Wayback Machine
↑ RSA-768 Factorization Arkiverad 13 december 2012 på Wayback Machine
↑ Datum för utfasning av MD5-baserade signaturer och 1024-bitars moduler . Hämtad 2 mars 2013. Arkiverad från originalet 20 november 2012. (obestämd)

Litteratur

Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Theory / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
Gardner M. En ny sorts chiffer som skulle ta miljoner år att bryta // Sci . amer. - NYC : NPG , 1977. - Vol. 237, Iss. 2. - S. 120-124. — ISSN 0036-8733 ; 1946-7087 - doi:10.1038/SCIENTIFICAMERICAN0877-120
Rivest R. , Shamir A. , Adleman L. En metod för att erhålla digitala signaturer och kryptosystem med publika nyckel (engelska) // Commun. ACM - [New York] : Association for Computing Machinery , 1978. - Vol. 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 (engelska) - CRC Press , 1996. - 816 sid. — ( Diskret matematik och dess tillämpningar ) — ISBN 978-0-8493-8523-0
Boneh D. Tjugo år av attacker mot RSA Cryptosystem // Notices Amer . Matematik. soc. / F. Morgan - AMS , 1999. - Vol. 46, Iss. 2. - S. 203-213. — ISSN 0002-9920 ; 1088-9477
Bakhtiari M. , Maarof M. A. Serious Security Weakness in RSA Cryptosystem (engelska) // IJCSI - 2012. - Vol. 9, Iss. 1, nr 3. - S. 175-178. — ISSN 1694-0814 ; 1694-0784

Nils Ferguson , Bruce Schneier . Praktisk kryptografi = Praktisk kryptografi: Designa och implementera säkra kryptografiska system. - M . : Dialektik, 2004. - 432 sid. - 3000 exemplar. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort