WisFaq!

Vercijferen met behulp van priemgetallen: RSA

Ik heb een vraagje over de codering met behulp van priemgetallen. Hoe werkt dit precies en hoe kan je dit doen?

Dani
7-4-2003

Antwoord

Beste Dani,

Je vraag is niet helemaal duidelijk, maar ik denk dat ik weet wat je bedoelt. Dus ik probeer toch een antwoord te geven.

Verschil tussen coderen en vercijferen
Wat je bedoelt is denk ik vercijferen en niet coderen. Bij coderen hoeft namelijk niet het origineel "onleesbaar" te worden.
Coderen wordt bijvoorbeeld gedaan met een ISBN code.
Bij vercijferen is het de bedoeling dat alleen de ontvanger van een bericht, het origineel weer terug kan vinden en iemand die het vercijferde bericht onderschept niet.
De tak van wetenschap die zich hier mee bezig houdt is de cryptografie.

Inleiding op RSA
De methode waar je denk ik naar vraagt is RSA. Dat is een methode die in 1978 is uitgevonden door Rivest, Shamir en Adleman. Vandaar ook de afkorting.

RSA is een voorbeeld van een Publieke sleutel systeem.
Oudere methoden van vercijfering waren gebaseerd op een gemeenschappelijk geheim (de sleutel) van twee partijen die met elkaar wilden communiceren. RSA is anders. Daar heeft iemand een eigen geheime sleutel. Daarbij hoort ook een zogenaamde publieke sleutel. Die kan hij aan iedereen geven die hij maar wil. De publieke sleutel kan dan worden gebruikt om berichten aan hem te sturen en hij is de enige die de boodschap weer kan ontcijferen.

Sleutels genereren
Stel je wilt zelf zo'n publieke sleutel en geheime sleutel maken. Dan begin je met twee hele grote priemgetallen; p en q.
In het "professionele" gebruik bestaan die getallen binair geschreven uit bijvoorbeeld 512 bits of 1024 bits. Dus dat zijn flinke priemgetallen.

Dan worden deze twee getallen met elkaar vermenigvuldigd. Dit levert een dus nog groter getal op dat als modulus van de modulus berekeningen zal worden gebruikt. Deze modulus N is een onderdeel van de publieke sleutel en dus niet geheim. De kracht van RSA is erop gebaseerd dat het heel moeilijk is om de priemgetallen p en q te vinden ook al weet je wat hun produkt is.

Dan kies je een willekeurig getal e. Vaak wordt hier 2¹⁶+1 voor gebruikt. Dit is het tweede deel van de publieke sleutel.
Dan moet je nog de prive-sleutel uitrekenen. Je houdt p en q natuurlijk geheim maar je moet ook nog een exponent d vinden.
Reken eerst f(N) = (p-1)(q-1) uit.
Dan moet je d vinden zodat ed 1 mod f(N).

Vercijferen
Je hebt nu alle sleutels gevonden. Dan kun je nu beginnen met vercijferde berichten te maken en weer te ontcijferen.
Iemand die je een boodschap wil sturen, maakt daar eerst een getal van: x. Dan berekent hij

x^e mod N = y

y is de vercijferde boodschap en kan hij nu veilig naar je opsturen. Niemand anders dan jij kan hem lezen.

Ontcijferen
Om te onrcijferen doe je het volgende:

y^d mod N, en dan vind je de oorspronkelijk boodschap x terug want:

(x^e)^d = x^ed = x¹ mod N (stelling van Euler)

Het is een heel verhaal geworden en ik hoop maar dat dit antwoord geeft op je vraag. Veel succes en als je meer wilt weten kun je dat natuurlijk hier altijd weer vragen.

gm
9-4-2003