RSA (cryptografie)

RSA is een asymmetrisch encryptiealgoritme, dat veel gebruikt wordt bij gegevensoverdracht, bijvoorbeeld voor de beveiliging van transacties. Het algoritme werd in 1977 ontworpen door Ron Rivest, Adi Shamir en Len Adleman, vandaar de afkorting RSA.

Clifford Cocks, een Britse wiskundige, die voor het Government Communications Headquarters werkte, heeft in 1973 in een intern document een gelijkwaardig algoritme beschreven, dat pas in 1997 boven water is gekomen, omdat het als topgeheim geclassificeerd was.

De veiligheid van RSA steunt op het probleem van de ontbinding in factoren bij heel grote getallen: op dit moment is het bijna onmogelijk de twee oorspronkelijke priemgetallen $p$ en $q$ te achterhalen als alleen hun product $pq$ bekend is en $p$ en $q$ groot genoeg zijn. Vergelijk het met een hashfunctie. Het zou te veel tijd in beslag nemen.

Het Massachusetts Institute of Technology heeft in 1983 in de Verenigde Staten het algoritme gepatenteerd, maar dat liep op 21 september 2000 af. Omdat het algoritme werd gepubliceerd voordat er in een ander land patent op werd aangevraagd, kon er in andere landen geen patent meer op worden aangevraagd.

Werking

Sleutels

Veronderstel dat Alice ervoor wil zorgen dat Bob haar een geheim bericht kan zenden over een onveilig medium, per telefoon, internet of post. Alice doet het volgende om een publieke sleutel en een geheime sleutel te maken:

Ze kiest willekeurig twee grote priemgetallen $p$ en $q\neq p$ en berekent het product $N=pq$ .
Ze berekent de indicator $\varphi (N)$ van $N$ . Omdat $N$ een product is van twee priemgetallen, is dat gemakkelijk. Namelijk, de indicator van een priemgetal $p$ is $p-1$ en $\varphi$ is multiplicatief: $\varphi (nm)$ = $\varphi (n)$ $\varphi (m)$ . Dus $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$ .
Ze kiest een geheel getal $e$ (de encryptiesleutel) dat tussen 1 en $\varphi$ ligt: $1<e<\varphi (N)$ en dat onderling ondeelbaar met $\varphi (N)$ is: $\mathrm {ggd} (e,(p-1)(q-1))=1$ . De encryptiesleutel $e$ mag bekend gemaakt worden aan Bob (en eventueel aan de rest van de wereld).
Ze berekent de decryptiesleutel $d$ als modulaire inverse van de encryptiesleutel $e$ , dat wil zeggen dat $de\equiv 1{\bmod {\varphi }}(N)$ , dus $de=k\varphi (N)+1$ voor zekere gehele $k$ . De decryptiesleutel $d$ blijft geheim, ook voor Bob.

Alice kan stap 4 met het uitgebreide algoritme van Euclides uitvoeren. Het getallenpaar $(e,N)$ vormt de publieke sleutel, het getallenpaar $(d,N)$ de geheime sleutel. Daarin is alleen de sleutel $d$ dus geheim, want $N$ is bekend. Alice stuurt het product $N$ en de openbare sleutel $e$ naar Bob via een mogelijk onveilig medium en ze houdt de sleutel $d$ geheim.

Voorbeeld

Alice kiest $p=11$ , $q=29$ , $N=pq=319$ . Dus $\varphi (N)=\varphi (319)=(p-1)(q-1)=280$ .
Alice kiest de publieke sleutel $e=3$ en stuurt deze naar Bob tezamen met het product 319.
Om de kleinst mogelijke geheime sleutel te verkrijgen berekent Alice: ggd(p-1, q-1) = ggd(10, 28) = 2 en neemt $\varphi (N)$ = 280 / 2 = 140.
Alice berekent met het uitgebreide algoritme van Euclides de geheime sleutel $d$ als de inverse van $e$ modulo $\varphi (N)$ :

e\,d=3\,d\equiv 1\,\,{\bmod {1}}40

, waaruit volgt dat

d=47

de decryptiesleutel is die Alice geheim houdt voor Bob en de rest van de wereld.

Versleutelen

Veronderstel dat Bob een bericht $m$ naar Alice wil zenden. Hij kent $N$ en $e$ , de publieke sleutel, want die heeft Alice hem gezonden. Hij zet de klare tekst $m$ om in een getal $n$ met $0<n<N$ , gebruikmakend van een eerder afgesproken, omkeerbaar en niet-geheim protocol. Bijvoorbeeld, elk teken in een bericht kan worden omgezet in zijn ASCII-code, en de codes samengevoegd tot een enkel getal. Als het nodig is (bijvoorbeeld omdat $n\geq N$ ) kan $m$ worden opgesplitst in tokens en elke token kan afzonderlijk versleuteld worden. Dan berekent hij de cijfertekst (de versleutelde tekst), $c$ met behulp van de vergelijking:

c\equiv n^{e}{\bmod {N}}

Dit kan snel worden gedaan door machtsverheffing door kwadrateren. Bob verzendt dan $c$ naar Alice.

Voorbeeld

Als Bob de letter 'Y', met ASCII-code 89 (< 319), naar Alice wil sturen, versleutelt hij deze en berekent de cijfertekst:

89^{3}{\bmod {3}}19=298

.

Bob stuurt de cijfertekst voor de letter 'Y', het getal 298, naar Alice.

Ontsleutelen

Alice ontvangt de cijfertekst $c=n^{e}$ van Bob, en ze kent haar geheime sleutel $d$ . Ze kan $n$ , de boodschap in numerieke vorm, te weten komen door $c$ tot de macht $d$ te verheffen en dan de volgende ontsleutelingsrelatie toe te passen:

c^{d}\equiv n{\bmod {N}}

Voorbeeld

Om de cijfertekst met de geheime sleutel te ontsleutelen, berekent Alice:^[1]

298^{47}{\bmod {3}}19=89

,

wat inderdaad weer de ASCII-code van de letter 'Y' is.

Als laatste stap krijgt Alice het bericht $m$ door op de numerieke vorm $n$ ervan het afgesproken, niet-geheime, protocol in omgekeerde richting toe te passen.

Kanttekeningen

Omdat $ed\equiv 1{\bmod {\varphi }}(N)$ , lijkt voor de ontsleuteling de congruentie $c^{d}=n^{ed}\equiv n{\bmod {\varphi }}(N)$ voor de hand te liggen, maar merk op dat de congruentie niet modulo $\varphi (N)$ is, maar modulo $N.$

Als de complexiteit die het modulo rekenen met zich meebrengt even wordt vergeten, lijkt de congruentie eenvoudig. Immers, omdat $ed=1$ en $e$ uit de publieke sleutel bekend is, volgt voor de geheime sleutel dat $d=1/e$ . De corresponderende congruentie voor $d$ daarentegen: $ed\equiv 1{\bmod {(}}p-1)(q-1)$ , vraagt de waarden van $p$ en $q$ afzonderlijk om $d$ uit $e$ te verkrijgen. Zoals al in de inleiding is opgemerkt, zijn $p$ en $q$ moeilijk uit $N$ terug te vinden en daarom geeft de congruentie een moeilijk te kraken waarde voor $d$ .

Bewijs congruentie

Het bewijs gebruikt de kleine stelling van Fermat. Die stelt dat voor $p$ priem, $n$ geheel en $\mathrm {ggd} (p,n)=1$ geldt dat:

n^{p-1}\equiv 1{\bmod {p}}

Gegeven is:

ed\equiv 1{\bmod {(}}p-1)(q-1)

Dus

ed-1=k(p-1)(q-1)

voor zekere gehele $k$ . Neemt men aan dat $\mathrm {ggd} (p,n)=1$ , dan volgt:

n^{ed}=n^{ed-1}n=n^{k(p-1)(q-1)}n=(n^{p-1})^{k(q-1)}n\equiv 1^{k(q-1)}n=n{\bmod {p}}

Als $\mathrm {ggd} (p,n)\neq 1$ en omdat $p$ priem is, geldt $n\equiv 0{\bmod {p}}$ , en in totaal

n^{ed}\equiv n{\bmod {p}}\Longrightarrow n^{ed}-n\equiv 0{\bmod {p}}

Analoog:

n^{ed}\equiv n{\bmod {q}}\Longrightarrow n^{ed}-n\equiv 0{\bmod {q}}

Dus is voor zekere gehele $s$ :

n^{ed}-n=sp

en is dit ook een veelvoud van $q$ . Omdat $p$ geen veelvoud van $q$ is moet $s$ dit wel zijn, $s=tq$ voor zekere gehele $t$ . Dus geldt

n^{ed}-n=tpq\Longrightarrow n^{ed}\equiv n{\bmod {p}}q

en omdat $N=pq$ en $n^{ed}=c^{d}$ , is de ontsleutelingsrelatie bewezen.

Ondertekenen

RSA kan ook worden gebruikt om een bericht digitaal te ondertekenen. Veronderstel dat Alice een ondertekend bericht wil zenden naar Bob. Ze berekent dan een hashwaarde uit het bericht, versleutelt die met haar geheime sleutel, en voegt dat als een handtekening bij het bericht. Deze handtekening kan alleen met haar publieke sleutel worden ontsleuteld. Wanneer Bob het ondertekende bericht ontvangt, ontsleutelt hij de handtekening met Alices publieke sleutel, en vergelijkt de berekende hashwaarde met de eigenlijke hashwaarde van het bericht. Als die gelijk zijn, weet hij dat de auteur van het bericht de geheime sleutel van Alice bezit en dat het bericht na verzending niet meer is veranderd.

Veiligheid

Veronderstel dat Charlotte, een afluisteraar, de publieke sleutel $N$ en $e$ , en de cijfertekst $c$ onderschept. Ze kan niet rechtstreeks aan de geheime sleutel $d$ komen, omdat Alice die geheimhoudt. De meest voor de hand liggende manier voor Charlotte om $n$ te vinden uit $c$ , is om $N$ in de factoren $p$ en $q$ te ontbinden, zodat ze $(p-1)(q-1)$ kan berekenen en $d$ kan vinden uit $e$ . Er is nog geen methode gevonden om getallen in polynomiale tijd in factoren te ontbinden met een gewone computer, de benodigde tijd wordt veel sneller groter dan bij lineair groter wordende getallen, maar het is niet bewezen dat er geen bestaat.

Het is ook niet bewezen dat de enige manier om $n$ uit $c$ te berekenen, is om $N$ in factoren te ontbinden, maar er is nog geen gemakkelijkere manier ontdekt, tenminste geen publiek bekende. Daarom wordt algemeen verondersteld dat Charlotte het bericht niet kan terugvinden als $N$ groot genoeg is.

Als $N$ uit 256 of minder bits bestaat, kunnen de factoren in een paar uur met een personal computer worden gevonden, gebruik makende van software die op het internet vrij toegankelijk is. Als $N$ 512 bits, kan sinds 1999 het ontbinden in factoren door enkele honderden computers in een aanvaardbare tijd worden uitgevoerd. Het is tegenwoordig aan te raden $N$ ten minste 1024 bits lang te kiezen. De 2013 NIST standaard FIPS 186-4 beveelt drie lengtes aan voor veilige moduli: 1024, 2048 of 3072 bits, die bestaan uit de respectievelijke aantallen decimale cijfers: 309, 617 en 972.

Peter Shor heeft in 1994 aangetoond dat wanneer er een kwantumcomputer zou bestaan, die in principe de een getal in polynomiale tijd in priemfactoren kan ontbinden. Mochten kwantumcomputers daarom werkelijkheid worden, dan maakt het algoritme van Shor RSA en andere soortgelijke algoritmes onbruikbaar. Als een efficiënte methode voor het ontbinden in factoren met een gewone computer zou worden gevonden, of als een kwantumcomputer zou worden gemaakt, dan kunnen nog langere sleutels een tijdelijke oplossing bieden, maar zo'n veiligheidslek in RSA zou wel retroactief zijn: de publieke sleutel en de cijfertekst kunnen worden bijgehouden totdat het mogelijk wordt om het bericht te ontcijferen. Dat is een reden om op de lange termijn niet alleen RSA gebruiken.

Praktische bedenkingen

Sleutels

Om de grote priemgetallen $p$ en $q$ te vinden, worden meestal eerst willekeurige getallen van de juiste grootte gekozen. Die getallen worden dan getest met snelle methoden, die de meeste niet-priemgetallen uitsluiten. Als dan een getal wordt gevonden dat waarschijnlijk een priemgetal is, kan op een zekere, maar langzamere, manier worden nagegaan of het getal inderdaad priem is.

De priemgetallen $p$ en $q$ mogen niet te dicht bij elkaar liggen, want anders zou de fermatfactorisatie voor $N$ succesvol kunnen zijn. Bovendien kan, als $p-1$ of $q-1$ alleen kleine priemfactoren hebben, $N$ snel in factoren worden ontbonden, zodat deze waarden voor $p$ en $q$ ook moeten worden gemeden.

Er mag geen methode om priemfactoren te zoeken worden gebruikt die een eventuele aanvaller enige informatie geeft over de priemgetallen. Een goede toevalsgenerator moet worden gebruikt. Coppersmith heeft in 1997 aangetoond dat als iemand de helft van de cijfers van $p$ of $q$ kan raden, hij gemakkelijk de andere helft kan berekenen.

Het is belangrijk dat de geheime exponent $d$ groot genoeg is. Wiener heeft in 1990 aangetoond dat als $p$ tussen $q$ en $2q$ ligt, wat veel voorkomt, en $d<N^{1/4}/3$ , $d$ op een efficiënte manier uit $N$ en $e$ kan worden berekend.

Snelheid

RSA is veel trager dan Data Encryption Standard en andere symmetrische encryptiealgoritmes. Bob vercijfert in de praktijk gewoonlijk zijn bericht met een symmetrisch algoritme en de symmetrische sleutel, kort in vergelijking met het bericht, met RSA. Het symmetrisch versleutelde bericht en de met RSA versleutelde sleutel worden dan beiden naar Alice verstuurd.

Deze methode zorgt voor bijkomende veiligheidsmoeilijkheden. De methode voor symmetrische encryptie moet veilig zijn, niet gemakkelijk te kraken zonder de sleutel, en de symmetrische sleutel moet met een goede toevalsgenerator worden gemaakt, want anders zou Charlotte om RSA heen kunnen door de symmetrische sleutel te raden.

Sleutelverdeling

Zoals bij alle encryptiemethoden, is het belangrijk hoe de publieke sleutels worden verspreid. We moeten ons bewust zijn van de mogelijkheid van een man-in-the-middle-aanval. Veronderstel dat Charlotte de communicatie tussen Alice en Bob kan onderscheppen. Ze ontvangt dan een publieke sleutel van Alice, maakt zelf een nieuwe publieke en geheime sleutel en stuurt haar eigen publieke sleutel naar Bob, die denkt dat hij de publieke sleutel van Alice ontvangt. Dan kan ze verdere berichten van Bob, vercijferd met haar publieke sleutel, ontvangen, ontcijferen met haar geheime sleutel, en eventueel veranderd weer met de eerder ontvangen publieke sleutel vercijferd naar Alice sturen. Alice denkt dan dat het bericht rechtstreeks van Bob komt. Alice en Bob kunnen in principe niet merken dat Charlotte ertussen zit. Verdedigingen tegen zo'n aanval zijn meestal gebaseerd op digitale certificaten of andere onderdelen van een public key infrastructure. Uiteraard is de beste oplossing dat Alice en Bob de sleutels, of een controlegetal, vergelijken tijdens een echte ontmoeting.

Tijdsgebaseerde aanvallen

Kocher beschreef in 1995 een ingenieuze nieuwe aanval op RSA: als Charlotte de hardware van Alice kent en de tijd nodig voor het ontcijferen van verschillende bekende cijferteksten kan meten, kan ze de geheime sleutel $d$ snel vinden.^[2] Om deze aanval af te slaan, moet de ontsleuteling in een constante tijd gebeuren.

Aangepast gekozen cijfertekst aanvallen

Daniel Bleichenbacher beschreef in 1996 een poging om met RSA versleutelde berichten met de PKCS #1 v1 redundantiefunctie, een redundantiefunctie voegt structuur toe aan een RSA-bericht, zodat het mogelijk is om te weten of een ontsleuteld bericht goed is, te ontsleutelen. Omwille van zwakke plekken in het PKCS #1 schema kon Bleichenbacher een aanval tegen de RSA-implementatie van het Transport Layer Security protocol opzetten, en mogelijk de sleutels te weten komen. Daarom raden cryptografen nu aan om alleen redundantietesten te gebruiken, waarvan is bewezen dat ze veilig zijn. RSA Laboratories heeft nieuwe versies van PKCS #1 vrijgegeven, die niet gevoelig zijn voor deze aanvallen.

voetnoten

↑ Gebruik modpow(298,47,319) op: bigint - large integer package, of in Python 3: 298**47%319.
↑ (en) PC Kocher. Advances in Cryptology — CRYPTO ’96, 1996. hoofdstuk Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, blz 104–113, ISBN 9783540615125

websites

(en) RSA
RSA Encryptie Applicatie. gearchiveerd

[1] Gebruik modpow(298,47,319) op: bigint - large integer package, of in Python 3: 298**47%319.

[2] (en) PC Kocher. Advances in Cryptology — CRYPTO ’96, 1996. hoofdstuk Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, blz 104–113, ISBN 9783540615125

[1]

[2]