RSA (cryptografie) | algoritme usted om berichten te versleutelen en te ontsleutelen

Gebruikte concepten

RSA gebruikt een aantal concepten uit de cryptografie:

• Een eenrichtingsfunctie die gemakkelijk te berekenen is; een functie vinden die deze functie omkeert, of deze functie berekenen is zeer moeilijk.
• RSA gebruikt een concept dat discrete logaritme heet. Dit werkt ongeveer hetzelfde als het normale logaritme: Het verschil is dat alleen hele getallen worden gebruikt, en dat er in het algemeen een modulusoperatie bij komt kijken. Bijvoorbeeld a^x =b, modulo n. Bij de discrete logaritme gaat het erom de kleinste x te vinden die voldoet aan de vergelijking, wanneer a b en n worden gegeven
• Het kan worden tegengegaan door het algoritme van Shor.

 

Sleutels genereren

De sleutels voor het RSA-algoritme worden als volgt gegenereerd:

1. Kies twee verschillende grote willekeurige priemgetallen p en q . Dit moet geheim blijven.
2. Bereken n = p q {Displaystyle n=pq} .
•  is de modulus voor de openbare sleutel en de privésleutels.
3. Bereken de totiënt: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
4. Kies een geheel getal e {\displaystyle e} zodanig dat 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} , en e {\displaystyle e} is co-priem met ϕ ( n ) {\displaystyle \phi (n)} .
   d.w.z.: e {displaystyle e} en ϕ ( n ) {displaystyle \phi (n)} delen geen andere factoren dan 1 {displaystyle 1}. : gcd ( e , ϕ ( n ) ) = 1 {displaystyle \gcd(e,\phi (n))=1} ; Zie grootste gemene deler.
•  wordt vrijgegeven als de exponent van de openbare sleutel.
5. Bereken d {displaystyle d} om aan de congruentierelatie d e ≡ 1 ( mod ϕ ( n ) ) te voldoen. {\displaystyle de\equiv 1 {\displaystyle d}} .
   d.w.z.: d e = 1 + x ⋅ ϕ ( n ) {displaystyle de=1+x \cdot \phi (n)} voor een geheel getal x {displaystyle x} . (Eenvoudig gezegd: Bereken d = ( 1 + x ⋅ ϕ ( n ) ) / e {Displaystyle d=(1+x ϕ (n))/e} een geheel getal te zijn).
• d {displaystyle d} wordt bewaard als de exponent van de privésleutel.

Opmerkingen over bovenstaande stappen:

• Stap 1: Getallen kunnen probabilistisch worden getest op primaliteit.
• Stap 3: gewijzigd in PKCS#1 v2.0 in λ ( n ) = l c m ( p - 1 , q - 1 ) {lambda (n)={rm {lcm}}(p-1,q-1)} in plaats van ϕ ( n ) = ( p - 1 ) ( q - 1 ) {lambda (n)=(p-1)(q-1)} .
• Stap 4: Een populaire keuze voor de openbare exponenten is e = 2 16 + 1 = 65537 {displaystyle e=2^{16}+1=65537} . Sommige toepassingen kiezen kleinere waarden zoals e = 3 {displaystyle e=3} , 5 {displaystyle 5} of 35 {displaystyle 35} . Dit wordt gedaan om encryptie en handtekeningverificatie sneller te maken op kleine apparaten zoals smartcards, maar kleine publieke exponenten kunnen leiden tot grotere veiligheidsrisico's.
• De stappen 4 en 5 kunnen worden uitgevoerd met het uitgebreide algoritme van Euclides [en]; zie modulair rekenen.

 De openbare sleutel bestaat uit de modulus n en de openbare exponent e .
De persoonlijke sleutel bestaat uit p, q en de privé (of ontcijfering) exponent d die geheim moet blijven.

• Voor de efficiëntie kan een andere vorm van de privésleutel worden opgeslagen:
• p {playstyle p} en q {playstyle q} : de priemgetallen van de sleutelgeneratie;
• d mod ( p - 1 ) {(}p-1)} en d mod ( q - 1 ) {(}q-1)} : vaak dmp1 en dmq1 genoemd;
• q - 1 mod p {{displaystyle q^{-1}{{bmod {p}}} : vaak iqmp genoemd.
• Alle delen van de privésleutel moeten in deze vorm geheim blijven. p en q zijn gevoelig omdat zij de factoren zijn van n en de berekening van d op basis van e mogelijk maken. Als p ( ) en q ( ) niet zijn opgeslagen in deze vorm van de privésleutel, worden ze veilig verwijderd, samen met andere tussenliggende waarden van de sleutelgeneratie.
• Hoewel deze vorm snellere ontcijfering en ondertekening mogelijk maakt door gebruik te maken van het Chinese Remainder Theorem (CRT), is het aanzienlijk minder veilig omdat het aanvallen via het zijkanaal mogelijk maakt [en]. Dit is vooral een probleem bij implementatie op smartcards, die het meest profiteren van de verbeterde efficiëntie. 
  (Begin met y ≡ x e ( mod n ) {{{displaystyle y}equiv x^{e}}. en laat de kaart dat ontcijferen. Hij berekent dus ( y d mod p ) {{displaystyle (y^{d}{bmod {p}})} of ( y d mod q ) {{displaystyle (y^{d}{bmod {q}})} , waarvan de resultaten een waarde z {{displaystyle}} opleveren. waarvan de resultaten een bepaalde waarde z opleveren . Veroorzaak nu een fout in een van de berekeningen. Dan zal gcd ( z - x , n ) {gcd(z-x,n)} p {displaystyle p} of q {displaystyle q} .)

 

Bericht versleutelen

Alice geeft haar openbare sleutel ( n , e ) aan Bob en houdt haar privésleutel geheim. Bob wil bericht M {displaystyle M} naar Alice sturen.

Eerst verandert hij M {{displaystyle M} in een getal m {{displaystyle m} dat kleiner is dan n {{displaystyle n} met behulp van een overeengekomen omkeerbaar protocol, bekend als een opvulschema. Vervolgens berekent hij de cijfertekst c die overeenkomt met:

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

Dit kan snel gebeuren met de methode van exponentiëren door kwadrateren. Bob stuurt vervolgens c {{³} naar Alice.

 

Bericht ontcijferen

Alice kan m ( ) herstellen van c ( ) door haar privésleutel d ( ) te gebruiken in de volgende procedure:

Gegeven m , kan zij de oorspronkelijke afzonderlijke priemgetallen terugvinden, door de Chinese reststelling toe te passen op deze twee congruenties.

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

Dus,

c d ≡ m mod n {{displaystyle c^{d}}}} .

Daarom:

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

Een werkend voorbeeld

Hier is een voorbeeld van RSA-versleuteling en -ontsleuteling. De hier gebruikte priemgetallen zijn te klein om veilig iets te versleutelen. U kunt OpenSSL gebruiken om een echt sleutelpaar te genereren en te onderzoeken.

1. Kies twee willekeurige priemgetallen p {playstyle p} en q {playstyle q,} :

p = 61 {displaystyle p=61} en q = 53 {displaystyle q=53} ;

2. Bereken n = p q {{playstyle n=pq,} :

n = 61 × 53 = 3233 {Displaystyle n=61 maal 53=3233!} ;

3. Bereken de totiënt ϕ ( 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. Kies e > 1 {displaystyle e>1} coprime to 3120 {displaystyle 3120,} :

e = 17 {displaystyle e=17,} ;

5. Kies d {{displaystyle d\,} om te voldoen aan e d ≡ 1 mod ϕ ( n ) {{displaystyle ed\equiv 1{bmod {\phi (n)}} :

d = 2753 {displaystyle d=2753,} , met 17 × 2753 = 46801 = 1 + 15 × 3120 {displaystyle 17 maal 2753=46801=1+15 maal 3120} .

 De openbare sleutel is ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Voor een opgevuld bericht m wordt de coderingsfunctie c = m e mod n {{displaystyle c=m^{e}{{bmod {n}}} :

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

De privésleutel is ( n = 3233 {{displaystyle n=3233} , d = 2753 {displaystyle d=2753} ). De ontcijferingsfunctie m = c d mod n {{displaystyle m=c^{d}{{bmod {n}}} wordt:

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

 Bijvoorbeeld, om m = 123 te
versleutelen, berekenen we m=123. berekenen we

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

Om c = 855 te ontcijferen {Displaystyle c=855} berekenen we

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

Beide berekeningen kunnen snel en gemakkelijk worden uitgevoerd met het kwadraat-en-vermenigvuldigingsalgoritme voor modulaire exponentiatie.

 

RSA-vergelijking afleiden uit de stelling van Euler

RSA kan gemakkelijk worden afgeleid met behulp van de stelling van Euler en de totiëntfunctie van Euler.

Te beginnen met de stelling van Euler,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{{{{{]n}}}}}

moeten we aantonen dat ontcijfering van een gecodeerd bericht, met de juiste sleutel, het oorspronkelijke bericht oplevert. Gegeven een opgevuld bericht m, wordt de cijfertekst c berekend door

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

In het ontcijferingsalgoritme hebben we dan

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

Wij willen aantonen dat deze waarde ook congruent is met m. De waarden van e en d zijn zo gekozen dat ze voldoen aan,

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

Dat wil zeggen dat er een geheel getal k bestaat, zodat

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

Nu vervangen wij het gecodeerde en vervolgens gedecodeerde bericht,

m e d ≡ m 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 ^{k\phi (n)} ^equiv m ^left(m^{{k\phi (n)}right)^{k}{pmod {n}} }end{aligned}}}.

Wij passen de stelling van Euler toe en komen tot het resultaat.

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

 

Opvulschema's

Bij gebruik in de praktijk moet RSA worden gecombineerd met enige vorm van opvulling, zodat geen enkele waarde van M resulteert in onveilige cijferteksten. RSA zonder opvulling kan enkele problemen opleveren:

• De waarden m = 0 of m = 1 leveren altijd cijferteksten gelijk aan 0 respectievelijk 1 op, vanwege de eigenschappen van exponentiëring.
• Bij vercijfering met kleine vercijferingsexponenten (bijv. e = 3) en kleine waarden van de m, kan het (niet-modulaire) resultaat van m e {{e}} strikt kleiner zijn dan de modulus n. In dit geval kunnen cijferteksten gemakkelijk worden ontcijferd door de eth-wortel van de cijfertekst te nemen zonder rekening te houden met de modulus.
• RSA-codering is een deterministisch coderingsalgoritme. Het heeft geen willekeurige component. Daarom kan een aanvaller met succes een "chosen plaintext"-aanval uitvoeren op het cryptosysteem. Hij kan een woordenboek maken door waarschijnlijke plaintexts te versleutelen met de openbare sleutel, en de resulterende cijferteksten op te slaan. De aanvaller kan dan het communicatiekanaal observeren. Zodra zij cijferteksten zien die overeenkomen met die in hun woordenboek, kunnen de aanvallers dit woordenboek gebruiken om de inhoud van het bericht te achterhalen.

In de praktijk kunnen de eerste twee problemen zich voordoen wanneer korte ASCII-berichten worden verzonden. In dergelijke berichten kan m de aaneenschakeling zijn van een of meer ASCII-gecodeerde tekens. Een bericht dat bestaat uit een enkel ASCII NUL-teken (waarvan de numerieke waarde 0 is) wordt gecodeerd als m = 0, wat een cijfertekst van 0 oplevert, ongeacht de waarden van e en N die worden gebruikt. Evenzo zou een enkele ASCII SOH (waarvan de numerieke waarde 1 is) altijd een cijfertekst van 1 opleveren. Voor systemen die gewoonlijk kleine waarden van e gebruiken, zoals 3, zouden alle ASCII-berichten met één teken die met dit schema zijn gecodeerd onveilig zijn, aangezien de grootste m een waarde van 255 zou hebben, en 255³ minder is dan elke redelijke modulus. Dergelijke klaarteksten kunnen worden hersteld door eenvoudigweg de derdemachtswortel van de cijfertekst te nemen.

Om deze problemen te vermijden, voegen praktische RSA-implementaties gewoonlijk een vorm van gestructureerde, willekeurige opvulling toe aan de waarde m alvorens deze te vercijferen. Deze opvulling zorgt ervoor dat m niet in het bereik van onveilige klaarteksten valt, en dat een gegeven bericht, eenmaal opgevuld, zal versleutelen tot een van een groot aantal mogelijke cijferteksten. Deze laatste eigenschap kan de kosten van een woordenboekaanval verhogen tot boven de mogelijkheden van een redelijke aanvaller.

Standaarden zoals PKCS zijn zorgvuldig ontworpen om berichten veilig op te vullen vóór de RSA-versleuteling. Omdat deze regelingen de klaartekst m opvullen met een aantal extra bits, moet de omvang van het niet-opgevulde bericht M iets kleiner zijn. RSA-opvulsystemen moeten zorgvuldig worden ontworpen om geavanceerde aanvallen te voorkomen. Dit kan worden vergemakkelijkt door een voorspelbare berichtstructuur. Vroege versies van de PKCS-standaard gebruikten ad-hocconstructies, die later kwetsbaar bleken voor een praktische adaptieve gekozen cijfertekstaanval. Moderne constructies maken gebruik van veilige technieken zoals optimale asymmetrische encryptie opvulling (OAEP) om berichten te beschermen en tegelijkertijd deze aanvallen te voorkomen. De PKCS-standaard heeft ook verwerkingsschema's die zijn ontworpen om extra veiligheid te bieden voor RSA-handtekeningen, bijvoorbeeld het Probabilistic Signature Scheme for RSA (RSA-PSS).

 

Berichten ondertekenen

Stel dat Alice de openbare sleutel van Bob gebruikt om hem een gecodeerd bericht te sturen. In het bericht kan zij beweren Alice te zijn, maar Bob kan niet controleren of het bericht werkelijk van Alice afkomstig is, aangezien iedereen de openbare sleutel van Bob kan gebruiken om hem gecodeerde berichten te sturen. Om de herkomst van een bericht te verifiëren, kan RSA dus ook worden gebruikt om een bericht te ondertekenen.

Stel dat Alice een ondertekend bericht naar Bob wil sturen. Zij produceert een hashwaarde van het bericht, verhoogt deze tot de macht d mod n (net als bij het ontcijferen van een bericht), en voegt deze als "handtekening" toe aan het bericht. Wanneer Bob het ondertekende bericht ontvangt, verhoogt hij de handtekening tot de macht e mod n (net als bij het versleutelen van een bericht), en vergelijkt de resulterende hashwaarde met de werkelijke hashwaarde van het bericht. Als de twee overeenstemmen, weet hij dat de auteur van het bericht in het bezit was van de geheime sleutel van Alice, en dat er sindsdien niet met het bericht is geknoeid.

Merk op dat veilige opvulsystemen zoals RSA-PSS even essentieel zijn voor de veiligheid van het ondertekenen van berichten als voor het vercijferen ervan, en dat dezelfde sleutel nooit mag worden gebruikt voor zowel vercijfering als ondertekening.