RSA-algoritme | algoritme, der anvendes til at kryptere og dekryptere meddelelser

Anvendte begreber

RSA anvender en række begreber fra kryptografi:

• En envejsfunktion, der er let at beregne; det er meget vanskeligt at finde en funktion, der vender den om, eller at beregne denne funktion.
• RSA anvender et koncept, der kaldes diskret logaritme. Dette fungerer på samme måde som den normale logaritme: Forskellen er, at der kun anvendes hele tal, og at der generelt er tale om en modulusoperation. Som eksempel kan nævnes a^x =b, modulo n. Den diskrete logaritme handler om at finde det mindste x, der opfylder ligningen, når a b og n er angivet
• Den kan potentielt modvirkes af Shors algoritme.

 

Generering af nøgler

Nøglerne til RSA-algoritmen genereres på følgende måde:

1. Vælg to forskellige store tilfældige primtal p {\displaystyle p} og q {\displaystyle q} . Dette skal holdes hemmeligt.
2. Beregn n = p q {\displaystyle n=pq} .
• n {\displaystyle n} er modulet for den offentlige nøgle og de private nøgler.
3. Beregn totienten: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
4. Vælg et helt tal e {\displaystyle e} , således at 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} , og e {\displaystyle e} er en primus til ϕ ( n ) {\displaystyle \phi (n)} .
   Dvs. at e {\displaystyle e} og ϕ ( n ) {\displaystyle \phi (n)} ikke har andre faktorer end 1 {\displaystyle 1} til fælles. : gcd ( e , ϕ ( n ) ) = 1 {\displaystyle \gcd(e,\phi (n))=1} ; Se største fælles divisor.
• e {\displaystyle e} frigives som eksponent for den offentlige nøgle.
5. Beregn d {\displaystyle d} for at opfylde kongruensrelationen d e ≡ 1 ( mod ϕ ( n ) ) {\displaystyle de\equiv 1\!\!\!\!\!\!{\pmod {\phi (n)}}} .
   Dvs.: d e = 1 + x ⋅ ϕ ( n ) {\displaystyle de=1+x\cdot \phi (n)} for et helt tal x {\displaystyle x} . (For at sige det ligeud: Beregn d = ( 1 + x ⋅ ϕ ( n ) ) / e {\displaystyle d=(1+x\cdot \phi (n))/e} til at være et heltal)
• d {\displaystyle d} bevares som eksponent for den private nøgle.

Bemærkninger til ovenstående trin:

• Trin 1: Tal kan testes sandsynlighedsvis for primalitet.
• Trin 3: ændret i PKCS#1 v2.0 til λ ( n ) = l c m ( p - 1 , q - 1 ) {\displaystyle \lambda (n)={{\rm {lcm}}}(p-1,q-1)} i stedet for ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
• Trin 4: Et populært valg for de offentlige eksponenter er e = 2 16 + 1 = 65537 {\displaystyle e=2^{16}+1=65537} . Nogle applikationer vælger mindre værdier som f.eks. e = 3 {\displaystyle e=3} , 5 {\displaystyle 5} , eller 35 {\displaystyle 35} i stedet. Dette gøres for at gøre kryptering og signaturverifikation hurtigere på små enheder som f.eks. smart cards, men små offentlige eksponenter kan føre til større sikkerhedsrisici.
• Trin 4 og 5 kan udføres med den udvidede euklidiske algoritme [en]; se modulær aritmetik.

 Den offentlige nøgle består af modulet n {\displaystyle n\,} og den offentlige (eller krypterings)eksponent e {\displaystyle e\,} .
Den personlige nøgle består af p,q og den private (eller dekrypterings) eksponent d {\displaystyle d\,} , som skal holdes hemmelig.

• Af hensyn til effektiviteten kan der gemmes en anden form for den private nøgle:
• p {\displaystyle p} og q {\displaystyle q} : primtalene fra nøglegenereringen;
• d mod ( p - 1 ) {\displaystyle d{\bmod {(}}p-1)} og d mod ( q - 1 ) {\displaystyle d{\bmod {(}}q-1)} : ofte kaldet dmp1 og dmq1;
• q - 1 mod p {\displaystyle q^{-1}{\bmod {p}}}} : ofte kaldet iqmp.
• Alle dele af den private nøgle skal holdes hemmelige i denne form. p {\displaystyle p\,} og q {\displaystyle q\,} er følsomme, da de er faktorerne for n {\displaystyle n\,} , og gør det muligt at beregne d {\displaystyle d\,} med e {\displaystyle e\,} . Hvis p {\displaystyle p\,} og q {\displaystyle q\,} ikke er gemt i denne form af den private nøgle, slettes de sikkert sammen med andre mellemliggende værdier fra nøglegenerering.
• Selv om denne form giver mulighed for hurtigere dekryptering og signering ved hjælp af den kinesiske restsætning (Chinese Remainder Theorem (CRT)) er den betydeligt mindre sikker, da den muliggør sidekanalangreb [en]. Dette er et særligt problem, hvis det implementeres på smart cards, som har størst fordel af den forbedrede effektivitet. 
  (Start med y ≡ x e ( mod n ) {\displaystyle y\equiv x^{e}\!\!\!\!\!\!{\pmod {n}}} , og lad kortet dekryptere det. Så det beregner ( y d mod p ) {\displaystyle (y^{d}{\bmod {p}}})} eller ( y d mod q ) {\displaystyle (y^{d}{\bmod {q}})} , hvis resultater giver en værdi z {\displaystyle z} . Nu skal der opstå en fejl i en af beregningerne. Så vil gcd ( z - x , n ) {\displaystyle \gcd(z-x,n)} afsløre p {\displaystyle p} eller q {\displaystyle q} .)

 

Kryptering af meddelelse

Alice giver sin offentlige nøgle ( n , e ) {\displaystyle (n,e)} til Bob og holder sin private nøgle hemmelig. Bob ønsker at sende besked M {\displaystyle M} til Alice.

Først omdanner han M {\displaystyle M} til et tal m {\displaystyle m} , der er mindre end n {\displaystyle n} , ved hjælp af en aftalt reversibel protokol kendt som en padding-ordning. Derefter beregner han den ciffertekst c {\displaystyle c\,} , der svarer til:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Dette kan gøres hurtigt ved hjælp af eksponering ved kvadrering. Bob sender derefter c {\displaystyle c\,} til Alice.

 

Afkodning af meddelelse

Alice kan gendanne m {\displaystyle m\,} fra c {\displaystyle c\,} ved at bruge sin private nøgle d {\displaystyle d\,} i følgende procedure:

Givet m {\displaystyle m\,} , kan hun genfinde de oprindelige særskilte primtal ved at anvende den kinesiske restsætning på disse to kongruenser, hvilket giver

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Således,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Derfor:

m = c d m o d n {\displaystyle m=c^{d}\ mod\ n}

Et arbejdseksempel

Her er et eksempel på RSA-kryptering og dekryptering. De primtal, der anvendes her, er for små til, at vi kan kryptere noget sikkert. Du kan bruge OpenSSL til at generere og undersøge et rigtigt nøglepar.

1. Vælg to tilfældige primtal p {\displaystyle p} og q {\displaystyle q\,} :

p = 61 {\displaystyle p=61} og q = 53 {\displaystyle q=53\,} ;

2. Beregn n = p q {\displaystyle n=pq\,} :

n = 61 × 53 = 3233 {\displaystyle n=61\ gange 53=3233\!} ;

3. Beregn totienten ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} :

ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120\!} ;

4. Vælg e > 1 {\displaystyle e>1} coprime til 3120 {\displaystyle 3120\,} :

e = 17 {\displaystyle e=17\,} ;

5. Vælg d {\displaystyle d\,} til at opfylde e d ≡ 1 mod ϕ ( n ) {\displaystyle ed\equiv 1{\bmod {\phi (n)}}} :

d = 2753 {\displaystyle d=2753\,} , med 17 × 2753 = 46801 = 1 + 15 × 3120 {\displaystyle 17\ gange 2753=46801=1+15\ gange 3120} .

 Den offentlige nøgle er ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). For en polstret meddelelse m {\displaystyle m\,} bliver krypteringsfunktionen c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}}} :

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}}233\,}

Den private nøgle er ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Dekrypteringsfunktionen m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} bliver:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}}233\,}

 For eksempel for at kryptere m = 123 {\displaystyle m=123} , beregner vi

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}}233=855}

For at dekryptere c = 855 {\displaystyle c=855} beregner vi

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}}233=123}

Begge disse beregninger kan beregnes hurtigt og nemt ved hjælp af kvadrat-og-multiplikator-algoritmen for modulær eksponering.

 

Udledning af RSA-ligningen fra Eulers sætning

RSA kan let udledes ved hjælp af Eulers sætning og Eulers totientfunktion.

Vi starter med Eulers sætning,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}}

skal vi vise, at dekryptering af en krypteret meddelelse med den korrekte nøgle vil give den oprindelige meddelelse. Givet en polstret meddelelse m, beregnes den krypterede tekst c ved at

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}}

Ved at indsætte den i dekrypteringsalgoritmen får vi følgende

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}}}

Vi ønsker at vise, at denne værdi også er kongruent med m. Værdierne for e og d er valgt, så de opfylder,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}}

Det vil sige, at der findes et helt tal k, således at

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\ gange \phi (n)+1}

Nu erstatter vi den krypterede og derefter dekrypterede meddelelse,

m e d ≡ m k k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{{\phi (n)}\right)^{k}{\pmod {n}}}\end{aligned}}}

Vi anvender Eulers teorem og opnår resultatet.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}}

 

Polstringsordninger

Når RSA anvendes i praksis, skal den kombineres med en eller anden form for padding-ordning, så ingen værdier af M resulterer i usikre ciphertexter. RSA kan have visse problemer, hvis den anvendes uden padding:

• Værdierne m = 0 eller m = 1 giver altid krypterede tekster svarende til henholdsvis 0 eller 1 på grund af eksponeringens egenskaber.
• Ved kryptering med små krypteringseksponenter (f.eks. e = 3) og små værdier af m kan det (ikke-modulære) resultat af m e {\displaystyle m^{e}}} være strengt mindre end modulet n. I dette tilfælde kan krypterede tekster let dekrypteres ved at tage eth-roden af den krypterede tekst uden hensyn til modulet.
• RSA-kryptering er en deterministisk krypteringsalgoritme. Den har ingen tilfældig komponent. Derfor kan en angriber med held iværksætte et angreb med valgt klartekst mod kryptosystemet. De kan lave en ordbog ved at kryptere sandsynlige klartekster med den offentlige nøgle og lagre de resulterende ciphertexter. Angriberen kan derefter observere kommunikationskanalen. Så snart de ser ciffertekster, der passer til dem i deres ordbog, kan angriberne bruge denne ordbog til at få kendskab til meddelelsens indhold.

I praksis kan de to første problemer opstå, når der sendes korte ASCII-meddelelser. I sådanne meddelelser kan m være en sammenkædning af et eller flere ASCII-kodede tegn. En meddelelse bestående af et enkelt ASCII NUL-tegn (hvis numeriske værdi er 0) vil blive kodet som m = 0, hvilket giver en ciffertekst på 0, uanset hvilke værdier af e og N der anvendes. På samme måde vil et enkelt ASCII SOH (hvis numeriske værdi er 1) altid give en ciffertekst på 1. For systemer, der konventionelt anvender små værdier af e, f.eks. 3, vil alle ASCII-meddelelser med et enkelt tegn, der er kodet efter dette skema, være usikre, da den største m vil have værdien 255, og 255³ er mindre end ethvert rimeligt modul. Sådanne klartekster kan genfindes ved simpelthen at tage kubikroden af den krypterede tekst.

For at undgå disse problemer indlejrer praktiske RSA-implementeringer typisk en form for struktureret, randomiseret polstring i værdien m, før den krypteres. Denne udfyldning sikrer, at m ikke falder inden for området af usikre plaintexter, og at en given meddelelse, når den er udfyldt, vil blive krypteret til en af et stort antal forskellige mulige ciphertexter. Sidstnævnte egenskab kan øge omkostningerne ved et ordbogsangreb ud over en rimelig angriberes muligheder.

Standarder som PKCS er omhyggeligt designet til at sikre, at beskederne er beskyttet inden RSA-kryptering. Fordi disse ordninger fylder klarteksten m med et vist antal ekstra bits, skal størrelsen af den ikke-polstrede meddelelse M være noget mindre. RSA-padding-ordninger skal være omhyggeligt udformet for at forhindre avancerede angreb. Dette kan gøres lettere ved at have en forudsigelig meddelelsesstruktur. I de tidlige versioner af PKCS-standarden blev der anvendt ad hoc-konstruktioner, som senere viste sig at være sårbare over for et praktisk adaptivt angreb på den valgte ciffertekst. Moderne konstruktioner anvender sikre teknikker som f.eks. optimal asymmetrisk krypteringspadding (OAEP) til at beskytte meddelelser og samtidig forhindre disse angreb. PKCS-standarden indeholder også behandlingsordninger, der er udformet til at give yderligere sikkerhed for RSA-signaturer, f.eks. den probabilistiske signaturordning for RSA (RSA-PSS).

 

Signering af meddelelser

Antag, at Alice bruger Bobs offentlige nøgle til at sende ham en krypteret meddelelse. I meddelelsen kan hun hævde at være Alice, men Bob har ingen mulighed for at verificere, at meddelelsen faktisk er fra Alice, da alle kan bruge Bobs offentlige nøgle til at sende ham krypterede meddelelser. Så for at verificere en meddelelses oprindelse kan RSA også bruges til at signere en meddelelse.

Lad os antage, at Alice ønsker at sende en signeret meddelelse til Bob. Hun fremstiller en hash-værdi af meddelelsen, forhøjer den til potensen af d mod n (ligesom ved dekryptering af en meddelelse) og vedhæfter den som en "signatur" til meddelelsen. Når Bob modtager den signerede meddelelse, forhøjer han signaturen til potensen e mod n (ligesom ved kryptering af en meddelelse) og sammenligner den resulterende hash-værdi med meddelelsens faktiske hash-værdi. Hvis de to værdier stemmer overens, ved han, at ophavsmanden til meddelelsen var i besiddelse af Alices hemmelige nøgle, og at meddelelsen ikke er blevet ændret siden da.

Bemærk, at sikre padding-ordninger som RSA-PSS er lige så vigtige for sikkerheden ved signering af meddelelser som for kryptering af meddelelser, og at den samme nøgle aldrig bør anvendes til både kryptering og signering.