​

PROJECT 8: HOOFDSTUK EEN: DE ILLUSIE VAN DE WERKELIJKHEID.  

​

​

​

De RSA is een algoritme dat door moderne computers wordt gebruikt om berichten te versleutelen/versleutelen en te ontsleutelen. Het is een asymmetrisch cryptografisch algoritme. Asymmetrisch betekent dat er twee verschillende sleutels zijn. Dit wordt ook wel public key cryptografie genoemd, omdat een van de sleutels aan iedereen kan worden gegeven. De andere sleutel moet privé worden gehouden. Het algoritme is gebaseerd op het feit dat het vinden van de factoren van grote samengestelde getallen moeilijk is: wanneer de factoren priemgetallen zijn, wordt het probleem priemfactorisatie genoemd. Het is ook een generator voor sleutelpaar (openbare en privésleutel).

​

​

​

• DE NERD-BOX

• Cryptonisch Veiliger

​

• Uw systeem versleutelen

• Uw systeem decoderen

​

• De NERD opvullen

• Ondertekening van de NERD

​

• Houden van de NERD

• xBORDER Cloud-X

​

​

Operatie

RSA omvat een openbare sleutel en een privésleutel. De openbare sleutel kan bij iedereen bekend zijn - hij wordt gebruikt om berichten te versleutelen. Berichten die zijn versleuteld met de openbare sleutel, kunnen alleen worden ontsleuteld met de persoonlijke sleutel. De sleutels voor het RSA-algoritme worden op de volgende manier gegenereerd:

​

1. Kies twee verschillende grote willekeurige priemgetallen p {\displaystyle p\,} en q {\displaystyle q\,}

2. Bereken n = pq {\displaystyle n=pq\,}

3. n {\ Displaystyle n \,} is de modulus voor de openbare sleutel en de privésleutels

4. Bereken de totient : ϕ ( n ) = ( p − 1 ) ( q − 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,} .

5. Kies een geheel getal e {\displaystyle e\,} zodat 1 < e {\displaystyle e\,} < ϕ ( n ) {\displaystyle \phi (n)\,} , en e {\displaystyle e\,} is co-priemgetal naar ϕ ( n ) {\ Displaystyle \ phi (n) \,} dat wil zeggen: e {\ Displaystyle e \,} en ϕ ( n ) {\ Displaystyle \ phi (n) \,} delen geen andere factoren dan 1; ggd ( e {\ Displaystyle e \,} , ϕ ( n ) {\ Displaystyle \ phi (n) \,} ) = 1.

   • e {\ Displaystyle e \,} wordt vrijgegeven als de exponent van de openbare sleutel

6. Bereken d {\ Displaystyle d \,} om te voldoen aan de congruentierelatie de ≡ 1 ( mod ϕ ( n ) ) {\ Displaystyle de \ equiv 1 {\ pmod {\ phi (n)}} \,} dat wil zeggen: de = 1 + x ϕ ( n ) {\displaystyle de=1+x\phi (n)\,} voor een geheel getal x {\displaystyle x\,} . (simpelweg gezegd)  : Bereken d = ( 1 + x ϕ ( n ) ) / e {\displaystyle d=(1+x\phi (n))/e\,} om een geheel getal te zijn)

   • d {\ Displaystyle d \,} wordt gehouden als de exponent van de privésleutel

Opmerkingen over de bovenstaande stappen:

• Stap 1: Getallen kunnen probabilistisch worden getest op primaliteit.

• ​

• Stap 3: gewijzigd in PKCS#1  ( nl ) v2.0 tot λ ( n ) = lcm ( p − 1 , q − 1 ) {\displaystyle \lambda (n)={\rm {lcm}}(p-1,q-1)\,} in plaats van ϕ ( n ) = ( p - 1 ) ( q − 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,} .

• Stap 4: Een populaire keuze voor de publieke exponenten is e {\displaystyle e\,} = 216 + 1 = 65537. Sommige toepassingen kiezen in plaats daarvan voor kleinere waarden, zoals e {\displaystyle e\,} = 3, 5 of 35. Dit wordt gedaan om codering en handtekeningverificatie sneller te maken op kleine apparaten zoals smartcards, maar kleine openbare exponenten kunnen leiden tot grotere veiligheidsrisico's.

• Stappen 4 en 5 kunnen worden uitgevoerd met het uitgebreide Euclidische algoritme  ( nl ); zie modulaire rekenkunde .

De openbare sleutel is gemaakt van de modulus n {\displaystyle n\,} en de openbare (of encryptie) exponent e {\displaystyle e\,} .
De private sleutel is gemaakt van p,q en de private (of decryptie) exponent d {\displaystyle d\,} die geheim moet worden gehouden.

• Voor efficiëntie kan een andere vorm van de privésleutel worden opgeslagen:

  • p {\displaystyle p\,} en q {\displaystyle q\,} : de priemgetallen van de sleutelgeneratie,

  • d mod ( p − 1 ) {\ Displaystyle d \ mod (p-1) \,} en d mod ( q − 1 ) {\ Displaystyle d \ mod (q-1) \,} : vaak dmp1 en dmq1 genoemd.

  • q − 1 mod ( p ) {\ Displaystyle q ^ {-1} \ mod (p) \,} : vaak genoemd iqmp

• Alle delen van de privésleutel moeten in deze vorm geheim worden gehouden. p {\displaystyle p\,} en q {\displaystyle q\,} zijn gevoelig omdat ze de factoren zijn van n {\displaystyle n\,} , en laten de berekening toe van d {\displaystyle d\,} gegeven e {\ weergavestijl e\,} . Als p {\displaystyle p\,} en q {\displaystyle q\,} niet worden opgeslagen in deze vorm van de persoonlijke sleutel, worden ze veilig verwijderd samen met andere tussenliggende waarden van het genereren van sleutels.

• Hoewel dit formulier snellere decodering en ondertekening mogelijk maakt met behulp van de Chinese Remainder Theorem (CRT) , is het aanzienlijk minder veilig omdat het zijkanaalaanvallen mogelijk maakt  ( nl ). Dit is een bijzonder probleem indien geïmplementeerd op smartcards , die het meest profiteren van de verbeterde efficiëntie. (Begin met y = xe ( mod n ) {\displaystyle y=x^{e}{\pmod {n}}} en laat de kaart dat decoderen. Dus het berekent yd ( mod p ) {\displaystyle y^{d }{\pmod {p}}} of yd ( mod q ) {\displaystyle y^{d}{\pmod {q}}} waarvan de resultaten een waarde geven z {\displaystyle z} Nu, induceer een fout in één dan zal ggd ( z − x , n ) {\displaystyle \gcd(zx,n)} p {\displaystyle p} of q {\displaystyle q} onthullen.

Bericht versleutelen

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

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

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

Dit kan snel worden gedaan met behulp van de methode van machtsverheffing door kwadrateren . Bob stuurt dan c {\displaystyle c\,} naar Alice.

Bericht decoderen

Alice kan m {\displaystyle m\,} van c {\displaystyle c\,} herstellen door haar privésleutel d {\displaystyle d\,} te gebruiken in de volgende procedure:

m = cd mod n {\displaystyle m=c^{d}{\bmod {n}}}

Gegeven m {\displaystyle m\,} , kan ze de oorspronkelijke onderscheiden priemgetallen herstellen, door de Chinese reststelling toe te passen op deze twee congruentieopbrengsten

med ≡ m mod pq {\displaystyle m^{ed}\equiv m{\bmod {pq}}} .

Dus,

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

Een werkend voorbeeld

Hier is een voorbeeld van RSA-codering en -decodering. De parameters die hier worden gebruikt zijn kunstmatig klein, maar je kunt OpenSSL ook gebruiken om een echt sleutelpaar te genereren en te onderzoeken .

1. Kies twee willekeurige priemgetallen.

2.   : p = 61 {\displaystyle p=61} en q = 53 ; {\displaystyle q=53;} Bereken n = pq {\displaystyle n=pq\,}

3.   : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}

4. Bereken de totient ϕ ( n ) = ( p − 1 ) ( q − 1 ) {\ Displaystyle \ phi (n) = (p-1) (q-1) \,}

5.   : ϕ ( n ) = ( 61 − 1 ) ( 53 − 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}

6. Kies e > 1 {\displaystyle e>1} coprime naar 3120

7.   : e = 17 {\displaystyle e=17}

8. Kies d {\displaystyle d\,} om te voldoen aan de mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}

9.   : d = 2753 {\displaystyle d=2753}

10.   : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

De openbare sleutel is ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Voor een opgevuld bericht m {\displaystyle m\,} wordt de versleutelingsfunctie c = me 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 decoderingsfunctie m = cd mod n {\displaystyle m=c^{d}{\bmod {n}}} wordt:

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

Om bijvoorbeeld m = 123 {\displaystyle m=123} te versleutelen, berekenen we

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

Om c = 855 {\displaystyle c=855} te ontcijferen, berekenen we

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

Beide berekeningen kunnen efficiënt worden berekend met behulp van het kwadraten-en-vermenigvuldigen-algoritme voor modulaire machtsverheffing  ( nl ).

RSA-vergelijking afleiden uit de stelling van Euler

RSA kan eenvoudig worden afgeleid met behulp van de stelling van Euler en de totient-functie van Euler.

Beginnend met de stelling van Euler,

m φ ( n ) ≡ 1 ( mod n ) {\ Displaystyle m ^ {\ varphi (n)} \ equiv 1 {\ pmod {n}}}

Met behulp van modulaire rekenkunde kan de vergelijking worden herschreven als

Vermenigvuldig beide zijden met m

m ≡ m φ ( n ) + 1 ( mod n ) {\displaystyle m\equiv m^{\varphi (n)+1}{\pmod {n}}}

Euler's totient functie heeft de eigenschap voor sommige waarden p en q,

φ ( p × q ) = φ ( p ) × φ ( q ) {\ Displaystyle \ varphi (p \ times q) = \ varphi (p) \ times \ varphi (q)}

Daarom kan de vergelijking worden herschreven als

m ≡ m φ ( p × q ) + 1 ( mod p × q ) {\displaystyle m\equiv m^{\varphi (p\times q)+1}{\pmod {p\times q}}}

Verder geldt voor alle gehele getallen k nog steeds de volgende relatie:

m ≡ mk × φ ( p × q ) + 1 ( mod p × q ) {\ Displaystyle m \ equiv m ^ {k \ times \ varphi (p \ times q) + 1}{ \ pmod {p \ times q} }}

De waarde d is afgeleid van de volgende vergelijking, waarbij e een groot priemgetal is en voor sommige k zodanig dat d een geheel getal is:

d = k × φ ( p × q ) + 1 e {\displaystyle d={k\times {\varphi (p\times q)+1} \over {e}}}

En volgens exponentregels geldt de volgende verklaring:

m = mek × φ ( p × q ) + 1 e {\displaystyle m=m^{e^{k\times {\varphi (p\times q)+1} \over {e}}}}

Aangezien de e's zullen opheffen. Dus bij het versleutelen van de cijfertekst m,

c ≡ me ( mod p × q ) {\displaystyle c\equiv m^{e}{\pmod {p\times q}}}

De oorspronkelijke waarde van m kan worden afgeleid uit c door c te verhogen tot d.

m ≡ cd ( mod p × q ) med ( mod p × q ) ≡ mek × φ ( p × q ) + 1 e ( mod p × q ) {\displaystyle m\equiv c^{d}{\pmod { p\times q}}\equiv m^{e^{d}}{\pmod {p\times q}}\equiv m^{e^{k\times {\varphi (p\times q)+1} \over {e}}}{\pmod {p\times q}}}

De vergelijking toont de gelijkwaardigheid.en de voortgang

opvulschema's

Bij gebruik in de praktijk moet RSA worden gecombineerd met een vorm van opvulschema , zodat geen waarden van M resulteren in onveilige cijferteksten. RSA gebruikt zonder opvulling kan enkele problemen hebben:

• De waarden m = 0 of m = 1 produceren altijd cijferteksten die gelijk zijn aan respectievelijk 0 of 1, vanwege de eigenschappen van machtsverheffing.

• Bij het coderen met kleine encryptie-exponenten (bijv. e = 3) en kleine waarden van de m, kan het (niet-modulaire) resultaat van me {\displaystyle m^{e}} strikt kleiner zijn dan de modulus n. In dit geval kunnen cijferteksten gemakkelijk worden gedecodeerd 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 gekozen leesbare tekstaanval tegen het cryptosysteem lanceren. Ze kunnen een woordenboek maken door waarschijnlijke leesbare tekst onder de openbare sleutel te versleutelen en de resulterende cijferteksten op te slaan. De aanvaller kan dan het communicatiekanaal observeren. Zodra ze cijferteksten zien die overeenkomen met die in hun woordenboek, kunnen de aanvallers dit woordenboek gebruiken om de inhoud van het bericht te leren.

In de praktijk kunnen de eerste twee problemen optreden bij het verzenden van korte ASCII -berichten. 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) zou worden gecodeerd als m = 0, wat een cijfertekst van 0 oplevert, ongeacht welke waarden van e en N worden gebruikt. Evenzo zou een enkele ASCII SOH (waarvan de numerieke waarde 1 is) altijd een cijfertekst van 1 produceren. Voor systemen die gewoonlijk kleine waarden van e gebruiken, zoals 3, zouden alle ASCII-berichten met één karakter die met dit schema zijn gecodeerd onveilig zijn, aangezien de grootste m zou een waarde van 255 hebben, en 2553 is kleiner dan een redelijke modulus. Dergelijke leesbare teksten kunnen worden teruggevonden door simpelweg de derdemachtswortel van de cijfertekst te nemen.

Om deze problemen te vermijden, integreren praktische RSA-implementaties meestal een vorm van gestructureerde, willekeurige opvulling in de waarde m voordat deze wordt versleuteld. Deze opvulling zorgt ervoor dat m niet binnen het bereik van onveilige leesbare tekst valt en dat een gegeven bericht, eenmaal opgevuld, zal versleutelen tot een van een groot aantal verschillende mogelijke cijferteksten. De 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 slaan voorafgaand aan RSA-codering. Omdat deze schema's de leesbare tekst m opvullen met een aantal extra bits, moet de grootte van het niet-opgevulde bericht M iets kleiner zijn. RSA-paddingschema's moeten zorgvuldig worden ontworpen om geavanceerde aanvallen te voorkomen. Dit kan worden vergemakkelijkt door een voorspelbare berichtenstructuur. Vroege versies van de PKCS-standaard gebruikten ad-hocconstructies , die later kwetsbaar werden bevonden voor een praktische adaptief gekozen cijfertekstaanval . Moderne constructies maken gebruik van veilige technieken zoals Optimal Asymmetric Encryption Padding (OAEP) om berichten te beschermen en deze aanvallen te voorkomen. De PKCS -standaard heeft ook verwerkingsschema's die zijn ontworpen om extra beveiliging te bieden voor RSA-handtekeningen, bijvoorbeeld het probabilistische handtekeningschema voor RSA ( RSA-PSS ).

Berichten ondertekenen

Stel dat Alice de openbare sleutel van Bob gebruikt om hem een versleuteld bericht te sturen. In het bericht kan ze beweren Alice te zijn, maar Bob kan op geen enkele manier controleren of het bericht daadwerkelijk van Alice afkomstig was, aangezien iedereen de openbare sleutel van Bob kan gebruiken om hem versleutelde 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. Ze produceert een hash-waarde van het bericht, verhoogt het tot de macht van d mod n (net als bij het ontcijferen van een bericht), en voegt het als een "handtekening" toe aan het bericht. Wanneer Bob het ondertekende bericht ontvangt, verheft hij de handtekening tot de macht e mod n (net als het versleutelen van een bericht) en vergelijkt de resulterende hash-waarde met de werkelijke hash-waarde van het bericht. Als de twee het eens zijn, 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.

Houd er rekening mee dat veilige opvulschema's zoals RSA-PSS net zo essentieel zijn voor de beveiliging van het ondertekenen van berichten als voor het versleutelen van berichten, en dat dezelfde sleutel nooit mag worden gebruikt voor zowel versleuteling als ondertekening.

Referenties

Andere websites

• Het originele RSA-octrooi zoals ingediend bij het Amerikaanse octrooibureau door Rivest; Ronald L. (Belmont, MA), Shamir; Adi (Cambridge, MA), Adleman; Leonard M. (Arlington, MA), 14 december 1977, Amerikaans octrooischrift 4.405.829  .

• PKCS #1: RSA-cryptografiestandaard (website RSA Laboratories )

  • De PKCS #1- standaard "geeft aanbevelingen voor de implementatie van cryptografie met openbare sleutels op basis van het RSA- algoritme, met betrekking tot de volgende aspecten: cryptografische primitieven ; versleutelingsschema 's; handtekeningschema 's met appendix; ASN.1- syntaxis voor het weergeven van sleutels en voor het identificeren van de schema's ".

• Uitleg van RSA met gekleurde lampen op YouTube

• Grondige doorloop van RSA

• Priemgetal verbergen-en-zoeken: hoe de RSA-codering werkt

• Onur Aciicmez, Cetin Kaya Koc, Jean-Pierre Seifert: over de kracht van eenvoudige takvoorspellingsanalyse

• Een nieuwe kwetsbaarheid in RSA-cryptografie, CAcert NEWS Blog

• Voorbeeld van een RSA-implementatie met PKCS#1-opvulling (GPL-broncode)

• Kocher's artikel over timing-aanvallen

• Een geanimeerde uitleg van RSA met zijn wiskundige achtergrond door CrypTool

• Geheime cijfers hacken met Python , hoofdstuk 24, cryptografie met openbare sleutels en het RSA-cijfer

• Grim, James. "RSA-codering" . Nummerfiel. Brady Haran .

• Hoe RSA-sleutel wordt gebruikt voor versleuteling in de echte wereld

• Priemgetallen, factorisatie en hun relatie met versleuteling

​

​

​

N