Het RSA Algoritme Erik Aarts
-1-
1
Wiskunde............................................................................................................................ 3 1.1 Het algoritme van Euclides ........................................................................................ 3 1.1.1 Stelling 1 ............................................................................................................ 4 1.2 Het uitgebreide algoritme van Euclides ..................................................................... 5 1.3 Modulo rekenen.......................................................................................................... 7 1.3.1 Optellen, aftrekken en vermenigvuldigen bij modulo rekenen .......................... 8 1.3.2 Delen bij modulo rekenen .................................................................................. 8 1.3.3 Machtsverheffen bij modulo rekenen................................................................. 9 1.4 Handige stellingen bij modulo rekenen.................................................................... 11 1.4.1 Stelling 4 .......................................................................................................... 11 1.4.2 Stelling 5 .......................................................................................................... 11 1.4.3 Stelling 6 .......................................................................................................... 11 2 Geheimschrift voor computers ......................................................................................... 11 2.1 Asymmetrische sleutels............................................................................................ 12 2.2 Geheimschriften met asymmetrische sleutels .......................................................... 12 2.3 RSA .......................................................................................................................... 13 2.3.1 Stelling 7 .......................................................................................................... 15 3 Slot ................................................................................................................................... 16 4 Bewijzen van alle stellingen die niet in de tekst zijn bewezen ........................................ 17
Inleiding De cryptografie, oftewel geheimschrift, heeft een lange geschiedenis. De Romeinen gebruikten al geheimschrift in het leger. Het beste boek over de geschiedenis van het geheimschrift is wel het (uit het Engels vertaalde) boek van Simon Singh: Code. Hij vertelt prachtige verhalen over geheimschrift in de oudheid en de Middeleeuwen. De cryptografie is een eeuwenlang durende wedstrijd geweest tussen code makers en code brekers. Singh gaat ook uitgebreid in op de Enigma, de “geheimschriftmachine” die in de 2e Wereldoorlog gebruikt werd door de Duitsers om hun onderlinge communicatie te beveiligen. Deze machine werd al vrij vroeg in de oorlog gekraakt door de Engelsen waardoor zij de communicatie van de Duitsers af konden luisteren. De Duitsers hadden dit niet door, pas na de oorlog bleek dat de Engelsen van alle Duitse plannen op de hoogte waren. De uitvinding van de computer heeft de cryptografie sterk veranderd. Door de brute rekenkracht van een computer werden bijna alle tot dan toe bestaande geheimschriften waardeloos omdat ze gemakkelijk te kraken zijn met een computer. Maar gelukkig zijn er weer nieuwe vormen van cryptografie ontwikkeld die ook met een computer niet te kraken zijn. Dit boekje gaat over de bekendste moderne vorm van geheimschrift. Dit geheimschrift is bedacht door 3 mensen (althans zij waren de eersten die hun idee in het openbaar bekend maakten): Rivest, Shamir en Adleman. -2-
De letters van hun achternamen vormen de naam van dit geheimschrift: RSA. Met het RSA algoritme (computerprogramma) kan iedereen berichten sturen die niet te ontcijferen zijn door anderen. Het algoritme wordt overal toegepast om computers te beveiligen, en om te zorgen dat computers met elkaar kunnen communiceren op een veilige manier. Zonder moderne cryptografie zou het bijvoorbeeld onmogelijk zijn om veilig te kunnen internet bankieren. Dit boekje legt uit hoe het RSA algoritme werkt. Het gaat niet over de praktijk van computer beveiliging maar over de (briljante) wiskundige theorie achter het RSA algoritme. Als je snapt hoe het werkt kun je deze kennis daarna gaan toepassen om computers veiliger te maken. Maar eerst dus de theorie, en die wordt hier uitgelegd. Veel plezier!
1
Wiskunde
Om het RSA systeem te kunnen begrijpen beginnen we met twee basisideeën: 1. het algoritme van Euclides 2. modulo rekenen.
1.1 Het algoritme van Euclides Het algoritme van Euclides is een manier om de grootste gemene deler te berekenen. Het begrip grootste gemene deler leggen we uit aan de hand van een voorbeeld.. 522 en we willen deze breuk vereenvoudigen. De meeste mensen Stel we hebben de breuk 738 lossen het als volgt op: je deelt eerst boven en onder door hetzelfde getal (bijvoorbeeld 2), en dan ga je verder. Kortom je probeert een getal te vinden waardoor je de teller en de noemer kan delen. Na de deling probeer je weer verder te komen. 522 261 87 29 = = = en dan stop je. Als we meteen gezien hadden dat 522 en 738 beiden 738 369 123 41 deelbaar zijn door 18 waren we sneller klaar geweest. Het getal 18 is de grootste gemene deler van 522 en 738. Definitie van grootste gemene deler 1. a is een deler van b als je b door a kan delen. 2. c is een gemene deler van a en b als je a en b door c kan delen. “Gemeen” betekent hier dus niet “vals” maar “gemeenschappelijk”. -3-
3. c is de grootste gemene deler van a en b als er geen grotere is (“da’s logisch” zou Cruijff zeggen). We schrijven dan c = ggd (a, b) . Opgave 1 ggd(24,18) = ggd(48,39) = ggd(37,23) = Als de getallen groter worden, wordt het lastiger om de grootste gemene deler te vinden alleen door te proberen. De Griekse wiskundige Euclides (325-265 v.C.) heeft hier al over nagedacht. In zijn boek “De Elementen” (boek 7 propositie 2) staat een berekening om de grootste gemene deler te vinden. Het basisidee achter zijn algoritme is
1.1.1 Stelling 1 ggd (a, b) = ggd (a − b, b) als a > b .
Om de tekst wat leesbaarder te houden staan een aantal bewijzen achterin het boek. Het bewijs van stelling 1 staat in hoofdstuk 6. Een manier om de grootste gemene deler van twee getallen a en b te bepalen zou zijn: • • •
als a = b heb je ggd(a,a) = a, je bent klaar. als a < b draai je a en b om, ggd(b,a) = ggd(a,b) als a > b om ggd(a,b) te berekenen, bereken je ggd(a-b,b).
Je trekt dus telkens het kleinste getal van het grootste getal af. Omdat je telkens met kleinere getallen gaat werken, kom je op een gegeven moment in het eerste geval uit ( a = b ) en dan ben je klaar. Als we dit toepassen op het vinden van de grootste gemene deler van 522 en 738 krijgen we: ggd (522, 738) = ggd (738,522) = ggd (216, 522) = ggd (522, 216) = ggd (216,306) = ggd (216,90) = ggd (126,90) = ggd (36, 90) = ggd (54,36) = ggd (36,18) = ggd (18,18) = 18
Er zijn erg veel stappen nodig om tot het antwoord te komen. Euclides’ idee was dan ook om met delingen en resten te werken in plaats van telkens af te trekken. Voor de rest voeren we een nieuwe naam in: mod. We zullen later zien waar die naam vandaan komt. Dus in plaats van “14 gedeeld door 4 is 3 rest 2” schrijven we nu “14 mod 4=2”. Definitie van mod • r = a mod n , als je a deelt door n is de rest r. Bijvoorbeeld a=14, n=4. Dan geldt r=2. Opgave 2 -4-
35 mod 8 = 43 mod 6 = 196 mod 13 = Het algoritme van Euclides gebruikt de regel ggd (a, b) = ggd (b, a mod b) . De regel ggd (a, b) = ggd (b, a mod b) is het herhaald toepassen van de regels ggd (a, b) = ggd (a − b, b) en ggd (a, b) = ggd (b, a ) en zullen we niet bewijzen. Algoritme van Euclides om ggd (a, b) (met a > b) te berekenen gaat als volgt: • als b = 0 dan ggd(a,0)=a • als b ≠ 0 om ggd (a, b) te berekenen, bereken je ggd (b, a mod b) . Het algoritme van Euclides is sneller dan het vorige algoritme: ggd (738,522) = ggd (522, 216) = ggd (306, 216) = ggd (216,90) = ggd (90,36) = ggd (36,18) = ggd (18,18) = 18
Opgave 3 Bepaal met het algoritme van Euclides ggd(738,27) ggd(37,77) In opgave 3 zien we dat de grootste gemene deler 1 kan zijn. Als de grootste gemene deler 1 is noemen we de getallen co-priem. De getallen 8 en 9 zijn co-priem, want ze hebben geen andere deler gemeenschappelijk dan 1. Maar 8 en 10 zijn niet co-priem, want 8 en 10 zijn beide deelbaar door 2. Definitie • Als ggd (a, b) = 1 zijn a en b co-priem. Opgave 4 Welke paren getallen zijn co-priem? 15 en 24 24 en 7 24 en 14 21 en 55 De begrippen grootste gemene deler, mod en co-priem komen nog vaak terug in de rest van dit boek.
1.2 Het uitgebreide algoritme van Euclides We gaan het algoritme van Euclides nu uitbreiden. Het uitgebreide algoritme kan het volgende probleem oplossen:
-5-
Probleem Stel ggd (a, b) = c . Vind dan getallen k en l zo dat c = k ⋅ a + l ⋅ b We noemen dit “c schrijven als een lineaire combinatie van a en b”. Voorbeeld ggd(10,18) = 2 Zoek een k en l zo dat 2 = k ⋅10 + l ⋅18 . Oplossing: k = 2 en l = −1 want 2 = 2 ⋅10 − 18 We zullen het algoritme uitleggen met een voorbeeld. We nemen a=99 en b=78. We gaan een tabel maken met 4 kolommen. We beginnen bovenaan en voegen telkens een nieuwe rij toe tot we klaar zijn. Bij elke stap in het algoritme van Euclides maken we een nieuwe rij. We gaan eerst de ggd (99, 78) berekenen. 99 mod 78 = 21. Dus we gaan ggd(78,21) berekenen. Zo gaan we verder tot we uitkomen op ggd(3,0). In de tweede kolom houden we bij “hoeveel keer het getal er in past”. Als we klaar zijn weten we dat ggd (99, 78) = 3 . Nu gaan we getallen k en l zoeken zo dat 3 = k ⋅ 99 + l ⋅ 78 want we willen 3 schrijven als een lineaire combinatie van 99 en 78. ggd(99,78) ggd(78,21) ggd(21,15) ggd(15,6) ggd(6,3) ggd(3,0)
99 = 78 + 21 78 = 3 ⋅ 21 + 15 21 = 1 ⋅15 + 6 15 = 2 ⋅ 6 + 3 6 = 2⋅3+ 0 ggd(3,0)=3
In de derde kolom komen de vergelijkingen uit de tweede kolom te staan, waarbij de rest vooraan komt te staan. In de tweede kolom staat …=…+ rest, in de derde kolom staat dan rest =…-… ggd(99,78) ggd(78,21) ggd(21,15) ggd(15,6) ggd(6,3) ggd(3,0)
99 = 78 + 21 78 = 3 ⋅ 21 + 15 21 = 1 ⋅15 + 6 15 = 2 ⋅ 6 + 3 6 = 2⋅3+ 0 ggd(3,0)=3
21 = 99 − 78 15 = 78 − 3 ⋅ 21 6 = 21 − 1 ⋅15 3 = 15 − 2 ⋅ 6 0 = 6 − 2⋅3
De laatste kolom vullen we van onder naar boven. We schrijven in alle vakjes behalve de drie onderste “3=”. De regel uit de derde kolom ( 3 = 15 − 2 ⋅ 6 ) schrijven we over in de vierde kolom. De onderste twee vakjes laten we leeg.
-6-
ggd(99,78) ggd(78,21) ggd(21,15) ggd(15,6) ggd(6,3) ggd(3,0)
99 = 78 + 21 78 = 3 ⋅ 21 + 15 21 = 1 ⋅15 + 6 15 = 2 ⋅ 6 + 3 6 = 2⋅3+ 0 ggd(3,0)=3
21 = 99 − 78 15 = 78 − 3 ⋅ 21 6 = 21 − 1 ⋅15 3 = 15 − 2 ⋅ 6 0 = 6 − 2⋅3
3= 3= 3= 3 = 15 − 2 ⋅ 6
We gaan nu van onder naar boven de vergelijkingen uit de derde kolom invullen in de vierde kolom. Als we bovenaan zijn gekomen hebben we de lineaire combinatie die we zochten gevonden (de eerste kolom laten we even weg i.v.m. ruimtegebrek). 99 = 78 + 21 78 = 3 ⋅ 21 + 15 21 = 1 ⋅15 + 6 15 = 2 ⋅ 6 + 3 6 = 2⋅3+ 0 ggd(3,0)=3
21 = 99 − 78 15 = 78 - 3 ⋅ 21 6 = 21 − 1 ⋅15 3 = 15 − 2 ⋅ 6 0 = 6 − 2⋅3
3 = 3 ⋅ 78 − 11 ⋅ (99 − 78) = 14 ⋅ 78 − 11 ⋅ 99 3 = 3 ⋅ (78 - 3 ⋅ 21) − 2 ⋅ 21 = 3 ⋅ 78 − 9 ⋅ 21 − 2 ⋅ 21 = 3 ⋅ 78 − 11 ⋅ 21 3 = 15 − 2 ⋅ (21 − 1 ⋅15) = 15 − 2 ⋅ 21 + 2 ⋅15 = 3 ⋅ 15 − 2 ⋅ 21 3 = 15 − 2 ⋅ 6
We zijn begonnen met a = 99 en b = 78. De ggd(99,78) bleek 3 te zijn. Met het uitgebreide algoritme zien we dat 3 = 14 ⋅ 78 − 11 ⋅ 99 (bovenste regel in de laatste kolom). Dus 14 en –11 zijn de getallen die we zochten. We hebben 3 geschreven als combinatie van 99 en 78.
1.3 Modulo rekenen In het vorige hoofdstuk zijn we het woord mod tegengekomen, en mod is een afkorting van het Latijnse woord modulo. Modulo betekent rest. Om te kunnen modulo rekenen gaan we werken met een nieuw is-gelijk-teken-met-drie-streepjes: ... ≡ ...(mod...) Definitie a ≡ b (mod n) als a mod n = b mod n Dus twee getallen zijn aan elkaar gelijk modulo n als hun resten na deling door n aan elkaar gelijk zijn. Het getal n noemen we de modulus. Een voorbeeld. Neem n = 7 . Dan geldt • •
1 ≡ 8 (mod 7) . Want 1 mod 7 = 1 en 8 mod 7 = 1 . 8 ≡ 15 (mod 7) . Want 8 mod 7 = 1 en 15 mod 7 = 1
We mogen de tekens ook “koppelen” zoals we dat bij de gewone = doen: • 1 ≡ 8 ≡ 15 ≡ 22 ≡ 29 ≡ 36 (mod 7) • 2 ≡ 9 ≡ 16 ≡ 23 ≡ 30 ≡ 37 (mod 7) De (mod 7) hoort dan bij alle is-tekens. De eerste keer dat je dit ziet is het misschien even wennen. Toch ben je deze manier van rekenen al vaak tegengekomen. Als je klok kijkt reken je namelijk modulo 12.
-7-
Stel we hebben de volgende opgave: Het is 11 uur. Jan gaat 3 uur wandelen. Hoe laat komt hij terug? Met het nieuwe ≡ -teken kunnen we dit eindelijk netjes opschrijven: 11 + 3 ≡ 14 ≡ 2 (mod 12) , dus om 2 uur. Het woord mod wordt op twee verschillende manieren gebruikt: 1. tussen twee getallen in. Dan is het de rest na deling, zoals in: 15 mod 7 = 1 . 2. tussen haakjes achter het ≡ -teken. Dan geeft het aan welke modulus bij het ≡ -teken hoort, zoals in 1 ≡ 8 (mod 7) . Haal deze notaties niet door elkaar!
1.3.1 Optellen, aftrekken en vermenigvuldigen bij modulo rekenen Modulo rekenen erg lijkt op gewoon rekenen. Het voordeel is dat je altijd met kleine getallen kunt werken. Als je grote getallen krijgt (groter dan n), neem je de rest en reken je daarmee verder. Dat mag omdat de volgende regels gelden voor modulo rekenen: • • •
x + y ≡ ( x mod n) + ( y mod n) (mod n) x − y ≡ ( x mod n) − ( y mod n) (mod n) x ⋅ y ≡ ( x mod n) ⋅ ( y mod n) (mod n)
Bereken de volgende sommen op twee manieren. Eerst reken je de som gewoon uit en neemt dan de rest. Daarna neem je eerst de rest en maak je dan de som. Voorbeeld 14 + 15 mod 6 . Methode 1: 14+15=29, 29 mod 6 = 5. Antwoord is 5 Methode 2: 14 mod 6 = 2, 15 mod 6 = 3, 2+3=5. Antwoord is 5 Opgave Bereken op twee manieren: 23 ⋅15 mod 7 14 ⋅15 mod 6 23 − 15 mod 7 15 − 23 mod 8
1.3.2 Delen bij modulo rekenen Zoals je misschien gemerkt hebt hebben we niets gezegd over (modulo) delen. Optellen, aftrekken en vermenigvuldigen gaat prima. Delen kan echter niet omdat er bij een deling verschillende uitkomsten kunnen zijn. Stel we rekenen modulo 24. Dan geldt 1 ⋅ 6 ≡ 6 (mod 24), 5 ⋅ 6 ≡ 30 ≡ 6 (mod 24), 9 ⋅ 6 ≡ 54 ≡ 6 (mod 24)
-8-
6 (mod 24) ? Is het 1, 5 of 9? Alle drie de antwoorden zijn 6 goed, en daarom kunnen we niet delen als we modulo rekenen.
Wat is de uitkomst van de som
Er zijn wel regels die te maken hebben met delen, en dat zijn deze twee. 1. Je kunt soms links en rechts dezelfde factor wegstrepen. Als je gewoon rekent mag je uit de vergelijking 6 ⋅ x = 6 ⋅ 9 de 6 wegstrepen. Je houdt dan x = 9 over. Het getal 0 mag je nooit wegstrepen. Wegstrepen mag ook bij modulo rekenen als de modulus een priemgetal is. Stel p is een priemgetal en je hebt de gelijkheid a ⋅ x ≡ b ⋅ x (mod p ) met niet x ≡ 0 (mod p ) Dan geldt a ≡ b (mod p ) . (Stelling 2) 2. Als je modulo n rekent kun je van elke x die co-priem is met n de inverse x −1 berekenen. Dit is in feite “1 gedeeld door x”, want x ⋅ x −1 ≡ 1 (mod n) . (Stelling 3) De bewijzen van stellingen 2 en 3 staan in hoofdstuk 6. In het bewijs van stelling 3 staat ook hoe je de inverse (tot de macht −1 ) kan berekenen. Opgave Bereken 4−1 (mod 7) .
1.3.3 Machtsverheffen bij modulo rekenen We hebben nu optellen, aftrekken, vermenigvuldigen en delen gehad. Het wordt nu tijd voor machtsverheffen. Machtsverheffen is herhaald vermenigvuldigen, daarom geldt x y ≡ ( x mod n) y (mod n) Het is echter niet zo dat x y ≡ x y mod n (mod n) . Je mag wel de modulus nemen van het grondtal maar niet van de macht! Als je met machten rekent is het handig de rest te nemen zo gauw je boven de modulus uitkomt. Bijvoorbeeld 25 ≡ 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2 ≡ 4 ⋅ 2 ⋅ 2 ⋅ 2 ≡ 8 ⋅ 2 ⋅ 2 ≡ 3 ⋅ 2 ⋅ 2 ≡ 6 ⋅ 2 ≡ 1 ⋅ 2 ≡ 2 (mod 5) . Door Excel te gebruiken om heel veel berekeningen tegelijk uit te voeren kunnne we bepaalde regelmatigheden ontdekken bij het machtsverheffen. En deze regelmatigheden vormen de kern van het RSA algoritme. Opdracht Start Excel (of een ander spreadsheet programma) op met een nieuw werkblad. Excel kent de mod functie. De uitdrukking x mod n zet je in Excel als MOD ( x; n) De grondtallen komen op de verticale as, de exponenten op de horizontale. • • •
In cel A1 zetten we de modulus waarmee we gaan rekenen. Zet daar om te beginnen een priemgetal in, bijvoorbeeld 7. Zet in cel B1 het getal 2. In rij 1 moeten nu de getallen vanaf 2 komen, C1=3, D1=4 enz.
-9-
•
Zet in cel C1 de formule “=B1+1”. Kopieer deze formule tot en met de kolom AI (in AI1 staat dan 35). Kopiëren kan in Excel gemakkelijk met de vulgreep (“fill handle”). Als je rechtsonder in een cel gaat staan verandert de cursor in een +-teken zoals in de afbeelding hieronder. Als je dan (naar rechts) sleept wordt de formule gekopiëerd.
Voor de eerste kolom doe je exact hetzelfde als voor de eerste rij. Zet in A2 getal 2, in A3 zet je “=A2+1” en kopiëer de formule naar beneden, tot rij 35. In cel B2 zet je nu de formule =MOD((A2*$A2);$A$1)*($A2<$A$1) Deze formule gebruikt de MOD functie van Excel. In cel B2 komt nu 4 ( 22 mod 7 ) te staan. $A$1 is het getal dat je in cel A1 hebt gezet. De cel A1 “misbruiken” we om de modulus op te slaan. Het stukje “*($A2<$A$1)” zorgt er voor dat in de rijen waar het grondtal groter is dan de modulus nullen verschijnen. Dit is in feite niet juist maar hierdoor blijft de boel wat overzichtelijker. De formule in cel B2 moet naar rechts en naar beneden gekopieerd worden. Helaas kan dit niet in 1 keer, je moet het rij voor rij of kolom voor kolom doen. Als je het goed hebt gedaan ziet het er als volgt uit:
Opdracht Vul in cel A1 verschillende getallen in en kijk wat er gebeurt. Als je in A1 een priemgetal zet krijg je een kolom met allemaal enen erin. Welke kolom is dat?
- 10 -
Als het goed is heb je zojuist ontdekt dat x p −1 ≡ 1 (mod p ) als p een priemgetal is. Dit gaan we bewijzen in het volgende hoofdstuk.
1.4 Handige stellingen bij modulo rekenen 1.4.1 Stelling 4 We kunnen bewijzen dat: Stelling 4 x p −1 ≡ 1 (mod p ) als p een priemgetal is en niet x ≡ 0 (mod p ) Het bewijs staat in hoofdstuk 6.
1.4.2 Stelling 5 Nu we dit hebben bewezen kunnen we ook het volgende bewijzen: Stelling 5 x1+ k ( p −1) ≡ x (mod p ) als p een priemgetal is. Bewijs van stelling 5. Stel dat niet x ≡ 0 (mod p ) . Dan geldt x1+ k ( p −1) ≡ x ⋅ x k ( p −1) ≡ x ⋅ ( x p −1 ) k ≡ x ⋅1k ≡ x ⋅1 ≡ x (mod p) . Als x ≡ 0 (mod p ) geldt de stelling ook, want 01+ k ( p −1) ≡ 0 (mod p ) . Einde bewijs van stelling 5. Opgave Controleer de stelling x1+ k ( p −1) ≡ x (mod p ) in je Excel werkblad, bijvoorbeeld voor p = 13 . Hoe heb je dat gedaan?
1.4.3 Stelling 6 Dit is de Chinese rest stelling: Stelling 6 Als x ≡ y (mod p ) en x ≡ y (mod q ) en p en q zijn co-priem, dan geldt x ≡ y (mod p ⋅ q ) . Het bewijs staat in hoofdstuk 6. Opgave Vul 4 getallen groter dan 10 in in de Chinese reststelling en laat zien dat de stelling klopt voor deze 4 getallen. Nu we de wiskundige theorie hebben gehad kunnen we teruggaan naar het onderwerp van dit boekje: geheimschrift.
2
Geheimschrift voor computers
- 11 -
2.1 Asymmetrische sleutels
Eindelijk kunnen we nu overstappen naar het onderwerp van dit boek: het RSA cryptosysteem. Om dit systeem uit te leggen maken we een vergelijking met een heel andere manier van geheim communiceren. Stel Astrid en Bert willen met elkaar op afstand communiceren zonder dat ze afgeluisterd kunnen worden. Ze kunnen dan geheimschrift gebruiken. Maar ze kunnen ook hun brieven in een envelop stoppen en hem heel goed dichtplakken. Helaas is een envelop gemakkelijk te openen. Maar stel dat er lichtgewicht kluisjes bestaan die je per post kan versturen. Deze kluisjes hebben een cijferslot van 4 cijfers. Dan kunnen Astrid en Bert elkaar brieven sturen door ze in het kluisje te stoppen en het kluisje op te sturen. Omdat niemand de code kent kan niemand de brieven lezen. Het nadeel is wel dat Astrid en Bert elkaar één keer moeten zien om de code af te spreken. En ze moeten er op vertrouwen dat de ander de code geheim houdt. Maar voor deze twee problemen is een oplossing. Er bestaan ook kluisjes met twee codes: 1. de sluitcode. Dit is de code die je nodig hebt om het kluisje dicht te doen. 2. de opencode. Hiermee kan je het kluisje openen. Het werkt als volgt. Astrid en Bert kopen ieder een eigen kluisje. Ze houden allebei de opencode van hun kluisje geheim, ze vertellen het ook niet aan elkaar. Het enige wat de ander hoeft te weten is de sluitcode. Hierover kunnen ze elkaar opbellen of E-mailen. De sluitcode is helemaal niet geheim, iedereen mag hem weten. Bert stuurt nu eerst zijn lege kluisje naar Astrid. Astrid stopt er wat in, en sluit Bert’s kluisje met zijn sluitcode. Dan stuurt ze beide kluisjes naar Bert. Omdat alleen Bert de opencode van zijn kluisje weet kan niemand anders het kluisje openen. Als Bert de twee kluisjes krijgt opent hij zijn kluisje. Hij leest de brief, schrijft een antwoord en stopt het antwoord in Astrid’s kluisje. Hij sluit het kluisje met haar sluitcode en stuurt beide kluisjes terug. Op deze manier kunnen Astrid en Bert met elkaar communiceren zonder dat iemand ze afluistert. Verder 1. hoeven ze elkaar niet meer te ontmoeten om een sleutel af te spreken. 2. ze weten allebei zeker dat niemand anders kan meeluisteren omdat er maar één persoon is die de opencode weet. Dit is een mooi verhaal maar in de praktijk werkt het niet. Kluisjes zijn zwaar en het is dus heel duur om telkens twee kluisjes op te sturen. En kluisjes zijn ook altijd te kraken met goed gereedschap. Laten we dus toch maar eens kijken of Astrid en Bert niet via geheimschrift kunnen communiceren.
2.2 Geheimschriften met asymmetrische sleutels Bij geheimschrift zetten we een tekst eerst om in een onleesbare tekst. Dit heet coderen. De onleesbare tekst sturen we op. De ontvanger zet de onleesbare tekst weer om in de oorspronkelijke tekst, dit noemen we decoderen. Andere woorden die vaak gebruikt worden zijn: vercijferen, encryptie, ontcijferen, decryptie. De oorspronkelijke tekst noemen we de klare tekst. De gecodeerde tekst noemen we de cijfertekst. Om te kunnen coderen en decoderen heb je sleutels nodig. De sleutel vertelt hoe je de tekst kan coderen en decoderen. Als er maar één sleutel is, noemen we het systeem dat je gebruikt symmetrisch. Bij een symmetrisch geheimschrift decodeer je een gecodeerde tekst door het coderings proces achterstevoren uit te voeren zodat je de klare tekst weer terug krijgt.
- 12 -
s m
c
m = klare tekst (message) c = cijfertext s = sleutel Dit is te vergelijken met het kluisje waarbij de code om te openen en te sluiten hetzelfde waren. Het RSA geheimschrift systeem is echter asymmetrisch. Er zijn twee sleutels. De eerste sleutel vertelt hoe je moet coderen, dit is de codeersleutel (vergelijkbaar met de sluitcode van het kluisje). De tweede sleutel zegt hoe te decoderen, en heet de decodeersleutel. Dit is de opencode van het kluisje.
e m
d c
m
Als Astrid en Bert met elkaar communiceren hebben ze allebei twee sleutels, er zijn dus in totaal 4 sleutels in het spel. Als Astrid een berichtje stuurt codeert ze het met Bert’s codeersleutel. Bert kan het dan lezen met zijn decodeersleutel. Bert codeert zijn antwoord met Astrid’s codeersleutel zodat alleen Astrid het kan decoderen. De codeersleutels zijn niet geheim maar openbaar. Daarom worden ze openbare sleutels genoemd. De decodeersleutels worden geheime sleutels genoemd. Als Astrid en Bert hun openbare codeersleutels publiceren, bijvoorbeeld door ze op hun website te zetten, kan iedereen geheime boodschappen naar Astrid en Bert sturen. Iedereen kan teksten coderen met de openbare sleutel. De gecodeerde tekst is alleen door de geadresseerde te lezen en niet door anderen, ook niet door de afzender, omdat niemand de geheime decodeersleutels van Astrid en Bert weet. De ontwikkeling van asymmetrische geheimschrift systemen met openbare sleutels is een grote revolutie geweest op het gebied van geheimschrift.
2.3 RSA
Rivest, Shamir en Adleman hebben niet het idee van de openbare sleutels bedacht (dat waren Diffie en Hellman), maar zij hebben wel het eerste geheimschrift systeem bedacht dat er mee werkt. Omdat het algoritme met getallen werkt moet de tekst eerst worden omgezet in getallen:
abc t
010
e m
d c
010 m
abc t
Tekst kan natuurlijk op verschillende manieren omgezet worden naar getallen. Wij gebruiken de volgende methode:
- 13 -
1. We kiezen eerst een blokgrootte. De blokgrootte is het aantal letters dat samen een getal vormt. Als je een blokgrootte kiest van één wordt elke letter apart omgezet. Je geheime tekst is dan makkelijk te kraken met frequentieanalyse. Het is dus aan te raden om een blokgrootte groter dan drie te kiezen. 2. Voor elke letter neem je de ASCII waarde en telt daar 100 bij op. Dan heeft het getal altijd lengte 3. Zie bijgaande tabel: 132 165 166 167 168 169
A B C D E
F 170 L 176 R 182 X 188 d 200 j G 171 M 177 S 183 Y 189 e 201 k H 172 N T Z 190 F 202 l I O U a 197 g 203 m J P V b 198 h 204 n K Q W c 199 i 205 o
206 207 208 209 210 211
p 212 v 218 q w r x s y t z u
Coderen met RSA gaat als volgt. De klare tekst wordt eerst omgezet in een getal, noem dit getal m. Het vercijferen gebeurt door machtsverheffen tot de macht e modulo n. Ontcijferen gebeurt ook door machtsverheffen, tot de macht d modulo n. Het getal dat we er uit krijgen zetten we om naar klare tekst.
abc t
c=me
010 m
m=cd c
010 m
abc t
Om dit goed te laten werken moeten we getallen drie getallen zoeken, e, d en n zo dat we m weer terug krijgen na ontcijferen. We weten uit het vorige hoofstuk dat x1+ k ( p −1) ≡ x (mod p) . We willen dat (me ) d ≡ m (mod n) en dus me d ≡ m (mod n) Het ligt voor de hand om n gelijk te nemen aan p (een priemgetal), en e en d zo te kiezen dat e ⋅ d = 1 + k ( p − 1) oftewel e ⋅ d ≡ 1 (mod ( p − 1)) . Laten we eens naar een voorbeeld kijken. Eerst kiezen we een priemgetal p, bijvoorbeeld p=29. Dan geldt dat x ≡ x 29 ≡ x57 ≡ x85 (mod 29) . We kiezen e en d zo dat e ⋅ d ≡ 1 (mod 28) , bijvoorbeeld e = 19 en d = 3 , of e = 5 en d = 17 . Om te coderen nemen we c = m19 (mod 29) . c is het getal dat we gaan versturen. Om te 3
decoderen nemen we m = c3 (mod 29) . Er geldt c3 ≡ m19 ≡ m57 ≡ m (mod 29) . Dus je krijgt inderdaad de klare tekst die hoort bij m terug.
De openbare sleutel is nu (19,29). De geheime sleutel is (3,29). Helaas werkt dit systeem niet want het is gemakkelijk te kraken. Als je de openbare sleutel (e,n) weet kun je d eenvoudig berekenen door de inverse te nemen: d = e−1 (mod ( p − 1))
- 14 -
De volgende (en echt, dit is de laatste) stap is dat we een andere modulus nemen. Voor n nemen we het product van twee verschillende priemgetallen. Opgave Zoek uit met behulp van Excel bij welke exponenten geldt x? ≡ x (mod p ⋅ q) als p en q priem zijn. Doe dit door de volgende rijtjes aan te vullen:
x1 ≡ x 9 ≡ x17 ≡ x 25 ≡ x (mod 15) , dus x1+ 4⋅k ≡ x (mod 15) x... ≡ x... ≡ x... ≡ x... ≡ x (mod 21) x... ≡ x... ≡ x... ≡ x... ≡ x (mod 35) 1 1+ k ⋅ ⋅( p −1)⋅( q −1) 2
≡ x (mod p ⋅ q) . Dit is echter niet zo makkelijk te bewijzen. Het lijkt dat x Het is eenvoudiger om te bewijzen dat x1+ k ⋅( p −1)⋅( q −1) ≡ x (mod p ⋅ q) . De factor
1 laten we dus even weg en we gaan bewijzen dat x1+ k ⋅( p −1)⋅( q −1) ≡ x (mod p ⋅ q) . 2
waarbij p en q priemgetallen zijn,
2.3.1 Stelling 7 x1+ k ⋅( p −1)⋅( q −1) ≡ x (mod p ⋅ q) , met p en q priem. Bewijs Als x ≡ 0 (mod pq ) geldt de stelling. Als niet x ≡ 0 (mod pq ) ook. Bewijs: k ⋅( q−1)
≡ x ⋅1
k ⋅( p −1)
≡ x ⋅1
x1+ k ⋅( p −1)⋅( q −1) ≡ x ⋅ x k ⋅( p −1)⋅( q −1) ≡ x ⋅ x ( p −1) x1+ k ⋅( p −1)⋅( q −1) ≡ x (mod p) x1+ k ⋅( p −1)⋅( q −1) ≡ x ⋅ x k ⋅( p −1)⋅( q −1) ≡ x ⋅ x ( q −1) x1+ k ⋅( p −1)⋅( q −1) ≡ x (mod q)
k ⋅( q−1)
≡ x (mod p) dus
k ⋅( p −1)
≡ x (mod q) dus
Met de Chinese reststelling krijgen we x1+ k ⋅( p −1)⋅( q −1) ≡ x (mod p ⋅ q) en dit moesten we bewijzen. Einde bewijs stelling 7. Net als in de vorige paragraaf willen we weer exponenten e en d zoeken zo dat d c = me mod pq en m = c d mod pq . Dan geldt me ≡ me⋅d ≡ m (mod pq) . We zoeken e en d zo dat e ⋅ d = 1 + k ⋅ ( p − 1) ⋅ (q − 1) oftewel e ⋅ d ≡ 1 (mod ( p − 1)(q − 1)) . We kiezen eerst een e zo dat e en ( p − 1)(q − 1) co-priem zijn. Dan kunnen we de inverse van e berekenen, zo dat e ⋅ e−1 ≡ 1 (mod ( p − 1)(q − 1)) . De d die we zoeken is dus e−1 . Het lijkt nu alsof we nog steeds een systeem hebben dat makkelijk te kraken is. Opgave De publieke sleutel is: e = 37, n = 265 . De boodschap is 217 57 232 232 225 46 De blokgroote is 1. Wat is de klare tekst ?
- 15 -
Het kraken ging als volgt: • bereken de priemfactoren p en q van n. • bereken e−1 (mod ( p − 1)(q − 1)) Toch is dit systeem niet te kraken als je zorgt dat n heel groot is. De eerste stap is dan namelijk heel moeilijk. Van het getal 255 waren de factoren nog gemakkelijk te bereken. Maar stel dat je voor p en q heel grote priemgetallen neemt. Je kan ze zo groot kiezen dat het met hedendaagse computers onmogelijk is om de factoren van n te vinden. Samenvattend bestaat het RSA systeem uit de volgende stappen: • • • • • • •
kies twee priemgetallen p en q, n = p ⋅ q . p,q zijn geheim, n is niet geheim kies een getal e, co-priem met (p-1)(q-1). De GGD(e,((p-1)(q-1)))=1. (p-1)(q-1) is geheim bereken d als inverse van e, e ⋅ d ≡ 1 (mod ( p − 1)(q − 1)) publiceer (e,n), dit is je publieke sleutel houd d geheim, (d,n) is je geheime steutel. Coderen doe je zo: c = me (mod n) En decoderen gaat zo: m = c d (mod n)
Opgave Bereken zelf getallen e,d en n die ongeveer 200 cijfers lang zijn. Hiervoor heb je een crypto rekenmachine nodig, bijvoorbeeld die op http://crypto.aartsvandertogt.nl . Maak dan een geheime tekst. Zet die om (neem een blokgrootte groter dan 25 letters). E-mail de cijfertekst naar iemand en geeft ook d en n. De ander kan hiermee de boodschap decoderen.
3
Slot
Je begrijpt nu hoe encryptie werkt in moderne computers. Om computers echt te beveiligen is dit nog maar het begin. Omdat de sleutels zulke grote getallen zijn worden ze meestal ook op de computer opgeslagen en niet op een briefje geschreven. Maar dan moet je wel zorgen dat niemand je sleutel kan kopiëren. Een ander probleem is dat je niet zeker weet of sleutels wel echt zijn. Als iemand je een USB stick geeft met de sleutel er op is er geen probleem. Als je sleutels gaat mailen bijvoorbeeld is er al kans dat iemand onderweg de sleutel verandert. Het leuke van assymmetrische sleutels is dat ze niet alleen gebruikt kunnen worden om boodschappen geheim te houden maar dat ze ook gebruikt kunnen worden als handtekening. Als je namelijk je berichten codeert met je eigen geheime sleutel kan iedereen de boodschap decoderen met je publieke sleutel. Het is dan wel zeker dat jij de schrijver bent (anderen kunnen geen teksten maken die met jouw sleutel decodeerbaar zijn). Dus heb je het document ondertekend. Ik hoop dat je nu begrijpt hoe het RSA algoritme werkt en dat je verder gaat lezen over moderne cryptografie!
- 16 -
4
Bewijzen van alle stellingen die niet in de tekst zijn bewezen
Stelling 1 ggd (a, b) = ggd (a − b, b) als a > b . Bewijs van Stelling 1 2. Als c een deler is van a en van b, dan is c ook een deler van a-b. Stel a = k ⋅ c en b = l ⋅ c , dan is a − b = k ⋅ c − l ⋅ c = (k − l ) ⋅ c 3. Als c een deler is van a en van b, dan is c ook een deler van a+b (zelfde manier). 4. Als c een deler is van a − b en b, dan is c ook een deler van a (door 2. ( a − b )+b=a) 5. uit 1. en 3. volgt dat de paren (a,b) en ( a − b ,b) dezelfde gemene delers hebben, dus is ggd (a, b) = ggd (a − b, b) Einde Bewijs van Stelling 2 Bewijs: Er geldt a ⋅ x = b ⋅ x + k ⋅ p . a. a ⋅ x = b ⋅ x + k ⋅ p b. a ⋅ x − b ⋅ x = k ⋅ p c. (a − b) ⋅ x = k ⋅ p d. p is een deler van a-b of p is een deler van x. Maar p is geen deler van x want dan zou gelden x ≡ 0 (mod p ) . Dus is p een deler van a-b en geldt a − b = l ⋅ p e. a − b = l ⋅ p f. a = b + l ⋅ p g. a ≡ b (mod p ) We hebben nu bewezen dat je de x-en mag wegstrepen als de x niet 0 is. Bewijs van Stelling 3. Dit doen we met het uitgebreide algoritme van Euclides. De getallen x en n zijn co-priem, dus ggd(x,n)=1. Dan vinden we met het algoritme getallen k en l zo dat 1 = k ⋅ x + l ⋅ n . Oftewel 1 ≡ k ⋅ x (mod n) . De l die we vinden is onbelangrijk, maar de k die we vinden met het algoritme is precies de gezochte x −1 ! Er is overigens maar 1 inverse.Stel dat x 2 verschillende inverses zou hebben: xa−1 en xb−1 . Dan zou gelden x ⋅ xa−1 ≡ 1 (mod n) en x ⋅ xb−1 ≡ 1 (mod n) . Dan
ook x ⋅ xa−1 ≡ x ⋅ xb−1 (mod n) . We mogen de x wegstrepen links en rechts. Dus xa−1 en xb−1 zijn aan elkaar gelijk. Er is dus maar 1 inverse! Bewijs van Stelling 4
We kijken naar de getallen 1, 2,3,..., ( p − 1) . We gaan al deze getallen met x vermenigvuldigen (x is niet 0). Dan krijgen we de rij 1 ⋅ x, 2 ⋅ x,3 ⋅ x,..., ( p − 1) ⋅ x . Voor deze rij geldt: • Geen enkel getal in de rij is gelijk aan 0: Noem het getal waarmee je x vermenigvuldigt a. ax ≡ 0 (mod p ) betekent dat ax door p gedeeld kan worden. Als ax door p gedeeld kan worden kan a gedeeld worden door p of x kan gedeeld worden door p. Dus a ≡ 0 (mod p ) of x ≡ 0 (mod p ) . Dit kan allebei niet.
- 17 -
Alle getallen in de rij zijn verschillend: Neem 2 getallen in de rij, a ⋅ x en b ⋅ x ( a ≠ b ). Als a ⋅ x ≡ b ⋅ x (mod p ) dan geldt a ≡ b (mod p ) want je kan links en rechts door x delen. Dus alle getallen 1 ⋅ x, 2 ⋅ x,3 ⋅ x,..., ( p − 1) ⋅ x zijn verschillend. We kijken even hoe dit er in de praktijk uit ziet. Neem bijvoorbeeld p = 11 . Bovenaan staat de rij 1, 2,3,..., ( p − 1) . Daaronder staan de rijen die je krijgt door te vermenigvuldigen met 1, 2, 3 enz. Je ziet in dit voorbeeld: • er zijn geen nullen. • in een rij staan nooit twee dezelfde getallen. •
1 2 3 4 5 6 7 8 9 10
1
2
3
4
5
6
7
8
9
10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 1 3 5 7 9
3 6 9 1 4 7 10 2 5 8
4 8 1 5 9 2 6 10 3 7
5 10 4 9 3 8 2 7 1 6
6 1 7 2 8 3 9 4 10 5
7 3 10 6 2 9 5 1 8 4
8 5 2 10 7 4 1 9 6 3
9 7 5 3 1 10 8 6 4 2
10 9 8 7 6 5 4 3 2 1
Als je in deze tabel alle getallen uit een willekeurige rij of kolom met elkaar vermenigvuldigt, krijg je altijd 10!= 3628800 als uitkomst. Dit idee passen we toe op de rijen 1,2,…,p-1 en 1 ⋅ x, 2 ⋅ x,3 ⋅ x,..., ( p − 1) ⋅ x . Omdat we net hebben bewezen dat in de twee rijen precies dezelfde getallen voorkomen (in een andere volgorde) moeten hun producten gelijk zijn: 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ ( p − 1) = 1 ⋅ x, 2 ⋅ x,3 ⋅ x,..., ( p − 1) ⋅ x (mod p ) We kunnen 1, 2, 3, enz. wegstrepen en houden over 1 ≡ x p −1 (mod p) . En dit is wat we moesten bewijzen. Einde bewijs van Stelling 4. Bewijs van stelling 6 x ≡ y (mod p ) x= y+k⋅ p x− y = k⋅ p x − y is deelbaar door p. x − y is ook deelbaar door q (op dezelfde manier). Omdat p en q co-priem zijn is x − y ook deelbaar door pq. x − y = l ⋅ p⋅q x ≡ y (mod p ⋅ q ) Einde bewijs van Stelling 6.
- 18 -
