| RSA (Rivest-Shamir-Adleman) is een veelgebruikt cryptosysteem met publieke sleutel. Het is gebaseerd op de praktische moeilijkheid van het ontbinden van het product van twee grote priemgetallen. Hier is een overzicht:
Hoe RSA werkt:
1. Sleutelgeneratie:
* Kies twee verschillende priemgetallen, *p* en *q*. Hoe groter deze zijn, hoe veiliger de encryptie.
* Bereken *n =p * q*. *n* is de modulus.
* Bereken φ(n) =(p-1)(q-1). Dit is de totient-functie van Euler, die het aantal gehele getallen kleiner dan *n* vertegenwoordigt die relatief priem zijn ten opzichte van *n*.
* Kies een geheel getal *e* (openbare exponent) zodat 1 <*e* <φ(n) en ggd(e, φ(n)) =1 (grootste gemene deler is 1; *e* en φ(n) zijn coprime). Een gebruikelijke keuze is 65537 (2
16
+ 1).
* Bereken *d* (privé exponent) zodat *d* * e ≡ 1 (mod φ(n)). Dit betekent dat *d* * *e* een rest van 1 overlaat wanneer gedeeld door φ(n). Dit wordt doorgaans gedaan met behulp van het uitgebreide Euclidische algoritme.
2. Openbare sleutel: De publieke sleutel is het paar (*n*, *e*). Dit wordt openbaar gedeeld.
3. Privésleutel: De privésleutel is het paar (*n*, *d*). Dit moet geheim worden gehouden.
4. Codering: Een bericht *M* coderen (weergegeven als een getal kleiner dan *n*):
* Cijfertekst *C* =*M
e
* (mod *n*)
5. Decodering: Om de cijfertekst *C* te decoderen:
* Platte tekst *M* =*C
d
* (mod *n*)
Waarom het werkt: De stelling van Euler stelt dat als *a* en *n* coprime zijn, *a
φ(n)
≡ 1 (mod n)*. De keuze voor *d* en de modulaire rekenkunde zorgen ervoor dat de decodering het oorspronkelijke bericht correct herstelt. Het breken van RSA is afhankelijk van het in factoren verwerken van *n* in *p* en *q*, wat rekenkundig niet haalbaar is voor voldoende grote priemgetallen.
RSA-cijfers oplossen:
De moeilijkheid bij het oplossen van numerieke RSA-problemen hangt af van de informatie die wordt gegeven. Hier volgen voorbeelden van typische problemen en hoe u deze kunt oplossen:
Voorbeeld 1:Encryptie
* Probleem: Gegeven *p* =11, *q* =13, *e* =7 en bericht *M* =5, codeert u het bericht.
* Oplossing:
1. Bereken *n* =*p* * *q* =11 * 13 =143
2. Bereken φ(n) =(11-1)(13-1) =120
3. Controleer of ggd(7, 120) =1 (ze zijn coprime)
4. Versleutelen:*C* =*M
e
* (mod *n*) =5
7
(mod. 143)
* 5
7
=78125
* 78125 ÷ 143 ≈ 546 met een rest van 67
* Daarom *C* =67
Voorbeeld 2:decodering
* Probleem: Gegeven *p* =11, *q* =3, *e* =7, en cijfertekst *C* =10, decodeer de cijfertekst.
* Oplossing:
1. Bereken *n* =*p* * *q* =11 * 3 =33
2. Bereken φ(n) =(11-1)(3-1) =20
3. Vind *d* zo dat *d* * *e* ≡ 1 (mod φ(n)) Dit betekent 7 * *d* ≡ 1 (mod 20). Je kunt dit oplossen met behulp van het Uitgebreide Euclidische Algoritme of met vallen en opstaan. *d* =3 werkt omdat (7 * 3) =21 ≡ 1 (mod 20).
4. Ontsleutelen:*M* =*C
d
* (mod *n*) =10
3
(mod. 33)
* 10
3
=1000
* 1000 ÷ 33 ≈ 30 met een rest van 10
* Daarom *M* =10
Voorbeeld 3:d (privé-exponent) vinden
Voor het vinden van 'd' is vaak het Uitgebreide Euclidische Algoritme vereist, wat hier buiten het bestek van een eenvoudige uitleg valt. Voor kleinere aantallen kan vallen en opstaan echter wel werken. Je zoekt naar een getal 'd' dat voldoet aan de congruentie *d* * e ≡ 1 (mod φ(n)).
Belangrijke overwegingen:
* Grote aantallen: RSA in de echte wereld gebruikt extreem grote priemgetallen (honderden of duizenden bits). Handmatige berekeningen zijn onmogelijk; gespecialiseerde software is vereist.
* Modulaire rekenkunde: Het begrijpen van modulaire rekenkunde is cruciaal voor het werken met RSA. Veel rekenmachines en programmeertalen hebben ingebouwde functies voor modulaire machtsverheffing.
* Beveiliging: De veiligheid van RSA hangt volledig af van de moeilijkheid om grote getallen te ontbinden. Naarmate de rekenkracht toeneemt, moet ook de omvang van de gebruikte priemgetallen toenemen om de veiligheid te behouden.
Deze voorbeelden illustreren de basisprincipes. Voor meer geavanceerde problemen zul je waarschijnlijk computerhulpmiddelen en een dieper begrip van de getaltheorie moeten gebruiken. |
