Hoe werkt het RSA?

Jellis, 17 jaar
18 februari 2013

Hoe kan je een boodschap coderen met het RSA zonder gebruik te maken van computerprogramma's?

Antwoord

Dag Jellis,

RSA is een zogenaamd publieke-sleutel cryptografie methode. Het vernuftige hieraan is dat je een sleutel-paar hebt, de publieke en geheime sleutel (in plaats van slechts 1 sleutel). Een boodschap die versleuteld is met de geheime sleutel kan enkel terug leesbaar gemaakt worden met de publieke sleutel en omgekeerd. Dit lost een groot probleem in de vroegere versleutelingstechnieken op: "hoe krijg ik de (enige en dus geheime) sleutel bij de ontvanger?".

Nu kan je zo'n sleutelpaar aanmaken en iedereen die maar wil de publieke sleutel geven. Als jij dan iets versleutelt met jouw geheime sleutel (die je dus nooit aan iemand mag tonen), kan iedereen die je publieke sleutel heeft die boodschap ontcijferen.

Een ander voordeel is dat je de sleutels in laagjes kan aanbrengen. Stel dat jij een geheime boodschap wil sturen aan je vriend Alex en jullie hebben allebei zo'n RSA sleutelpaar. Dan zal jij eerst je boodschap versleutelen met de publieke sleutel van Alex (1e laagje) en dan met jouw geheime sleutel (2e laagje). Jouw vriend kan dan het buitenste laagje "wegkrabben" door te ontsleutelen met jouw publieke sleutel en daarna het binnenste laagje met zijn geheime sleutel. Zo zorg je ervoor dat je andere vrienden (die ook jouw publieke sleutel hebben) toch niet je geheime boodschap voor Alex kunnen lezen.

Maar hoe werk dat nu wiskundig? Het ganse principe is gebaseerd op twee grote priemgetallen (hééééél grote priemgetallen) die je met mekaar gaat vermenigvuldigen. Als je enkel het product van die twee kent, is het zeer erg moeilijk om dat product terug te gaan opsplitsen (factoriseren) in die twee priemgetallen. Daarnaast maakt het algoritme gebruik van modulo rekenen: dat is rekenen waarbij je de rest van een gehele deling gaat berekenen. Je kan bijvoorbeeld rekenen modulo 12, dat is onze dagdagelijkse klok: als het nu 9u 's ochtends is en ik tel daar 8u bij, dan is het resultaat 5u (9+8 = 17; 17 mod 12 = 5 want 17 - 1 x 12 = 5). Met onze andere dagklok rekenen we modulo 24.

Het RSA algoritme ziet eruit als volgt:

Sleutels aanmaken

  • kies p,q: twee grote priemgetallen
  • n = p *q : het product van die twee
  • m = (p-1)*(q-1): een hulpgetal
  • e: de publieke sleutel, een getal dat we moeten zoeken dat "relatief priem" is ten opzichte van m; dit wil zeggen dat m en e geen gemeenschappelijke delers mogen hebben
  • d: de geheime sleutel, zoek d zodat (e*d) mod m = 1 waarbij 'mod' staat voor modulo rekenen.

Je mag dus nooit p,q of d bekendmaken, want dan kunnen al je boodschappen ontcijferd worden!

Het versleutelen gebeurt dan als volgt (dit is je boodschap):

  • c = (te) mod n

Je gaat dus eerst je boodschap (letters, tekst) moeten omzetten naar een numeriek alfabet (bv. bits en bytes)

Het ontsleutelen is dan de "omgekeerde" bewerking (c is de versleutelde tekst):

  • t = (cd) mod n

Normaliter gebruik je dus computerprogramma's om dit allemaal (snel) te doen, maar je kan het zelf eens met de hand proberen. Neem bv. p = 11 en q = 13. Dan is n = p * q = 143. En dan is m = (p-1)*(q-1) = 120.

Nu moeten we een getal zoeken dat relatief priem is ten opzichte van m. Een trucje daarvoor is beginnen met getallen net kleiner dan √e (da's de zeef van Eratosthenes, maar da's een ander verhaal). Je kan bijvoorbeeld e = 11 nemen, want 11 en 120 hebben geen gemeenschappelijke priemfactoren (behalve 1).  Dit is je publieke sleutel. En nu moet je d zoeken zodat (e*d) mod m gelijk is aan 1, m.a.w. de rest van de deling van e*d door m moet 1 zijn. Na een beetje zoeken, zal je vinden dat d = 11 (het feit dat je publieke en geheime sleutel dezelfde zijn, is geen goed plan in de echte boze wereld, maar hier komt het omdat we zulke kleine getallen nemen).

Nu heb je dus de geheime sleutel (e = 11), de publieke sleutel (d = 11) en de versleutelmodulo (n=143).

Stel dat je een boodschap naar je vriend Alex wil sturen, dan moet je die eerst omzetten in gehele getallen (met een computer naar bits en bytes). En stel dat die boodschap het getal 7 is (Alex moet om 7u aan je deur staan om naar school te vertrekken).

De versleutelde boodschap zal dan c = 711 mod 143 zijn, m.a.w. de rest van de deling 1977326743 door 143. En dat is 106. Je ziet dat als je die machtsverheffing zo maar gaat doen, je heel snel bij heel grote getallen komt. Gelukkig zijn er trucjes bij modulo rekenen om die machten niet helemaal te moeten uitrekenen en bestaan er vereenvoudigingsregels. 

Dus jij stuurt naar Alex het bericht '106'. Alex neemt jouw publieke sleutel bij de hand en doet de ontsleutelingsoperatie: t = 10611 mod 143. Dus we zoeken de rest bij deling door 143 van 18982985583354248390656. En dat blijkt 7 te zijn.

Hopelijk is dit een beetje duidelijk. Je kan best een beetje oefenen met het modulo rekenen en nog eens gaan kijken hoe het ook alweer zat met priemfactoren en ontbinden in priemfactoren. En dan natuurlijk nog eens een ander voorbeeldje nemen (bv p = 31 en q = 37).

Groeten en veel rekenplezier,

Gert

Reacties op dit antwoord

Er zijn nog geen reacties op deze vraag.

Enkel de vraagsteller en de wetenschapper kunnen reageren op een antwoord.

Zoek andere vragen

© 2008-2022
Ik heb een vraag wordt gecoördineerd door EOS vzw