Het RSA-algoritme

© h.hofstede (h.hofstede@hogeland.nl)

       
RSA is een geheimschrift. Maar niet zomaar eentje.
Het is in 1977 ontdekt door Ron Rivest,  Adi Shamir en  Len Adleman.
Wat is er apart aan?

Nou, het is een zogenaamde "publieke cryptografie". Dat betekent het volgende.

Stel dat je aan RSA wilt gaan doen. Dan maak je twee sleutels.
(Een sleutel is een methode om een bericht in een ander bericht om te zetten).
Eentje is jouw eigen privé-sleutel, en die hou je geheim. De andere is jouw publieke sleutel en die maak je aan iedereen bekend. Hoe je die sleutels moet maken volgt later.

       
Als een vreemde jou nou een geheim bericht wil sturen, dan gebruikt hij jouw publieke sleutel om zijn bericht (B) in een niet-leesbaar geheim bericht (G) te veranderen (dat heeft coderen). Dat geheime bericht G stuurt hij naar jou op. Het vreemde is, dat hij met jouw publieke sleutel dat bericht niet ook kunt ontcijferen. De publieke sleutel werkt maar één kant op!!!!
Dus als die vreemde een bericht heeft gecodeerd, en hij is het daarna  per ongeluk vergeten, dan kan hij het zelf ook niet meer ontcijferen! Het is als een kluis die je met de ene sleutel op slot doet, en die je alleen met een andere sleutel open kunt maken. En uit de vorm van de enen sleutel kun je de andere sleutel niet afleiden....
Daarom heet RSA een  asymmetrische coderingsmethode.
Pas met jouw eigen geheime privésleutel kun je het bericht G weer veranderen in het oorspronkelijke bericht B (dat heet décoderen).

Handig toch?
Iedere vreemde kan jou zo een geheim bericht sturen. Je hoeft niet eerst met iemand een geheimschrift-methode af te spreken (die kan immer ook weer onderschept/ontcijferd worden).
       

       
De groene sleutel is voor iedereen openbaar, de rode is geheim.
       
Hoe maak je zulke wonderbaarlijke sleutels?

Als eerste heb je twee priemgetallen nodig. Het liefste flink grote priemgetallen, zeg maar van zo'n 100 cijfers of meer.
Laten we die getallen p1 en p2 noemen. (die moet je overigens ook goed geheim houden)

Volgende stap:

Je vermenigvuldigt nu  p1 en p2 met elkaar en dat levert een enorm nieuw getal (van zo'n 200 cijfers dus). Dat getal heet de modulus m, en het is een deel van jouw publieke sleutel.
       
  Ik zal een mini-voorbeeldje in het groen maken.....
Als voorbeeld neem ik (uit luiheid) eventjes de kleine priemgetallen p1 = 5 en p2 = 7, dus dat geeft  m = 35.
       
Volgende stap:  je gaat nu een getal Φ berekenen. 
Ik hoop dat je nog weet wat priemfactoren van een getal zijn. Dat zijn de priemgetallen waaruit het getal is opgebouwd. (als je dat niet meer weet  moet je eerst deze les doornemen).
Het getal Φ is het volgende:
       
Φ(m) is het aantal getallen kleiner dan m dat géén priemfactor met m gemeenschappelijk heeft
       
Ofwel: het is het aantal getallen, die opgebouwd zijn uit allemaal andere priemgetallen dan de priemgetallen van  m.
       
  In het voorbeeld is m opgebouwd uit de priemfactoren 5 en 7. Dus alle getallen onder de 35 waar een 5 of een 7 inzit vallen af.  Dat zijn 5, 10, 15, 20, 25, 30, 35, 7, 14, 21, 28, 35 dus dat zijn er 11 (35 staat er twee keer bij). Dus blijven er 35 - 11 = 24 getallen over, dus Φ(35) = 24.
       
Je kunt deze f(m) als volgt makkelijker berekenen:
       
Φ(m)  = Φ(p1· p2)  = (p1 - 1)(p2 - 1)
       
Het bewijs daarvan is heel eenvoudig. Het staat eigenlijk al in het voorbeeld:
•  Alle getallen uit de tafel van p1  vallen af, dat zijn er p2
•  Alle getallen uit de tafel van p2 vallen af, dat zijn er p1
•  Maar nu hebben we het getal p1· p2 zélf dubbel meegeteld, dus er moet weer eentje bij.
•  Dan blijft over  p1·p2 - p1 - p2 + 1  =   (p1 - 1)·(p2 - 1)
q.e.d.
   
  (In het voorbeeld kun je dus veel sneller uitrekenen Φ(35) = Φ(5 · 7) = 4 · 6 = 24)
       
Volgende stap

Nu kies je een nieuw getal kleiner dan m, waarvoor geldt dat dat getal géén deler met Φ(m) gemeenschappelijk mag hebben.
(Die voorwaarde is nodig om straks een ontcijfergetal d te kunnen maken, dat zul je verderop zien).
Noem dit getal e. Dan is e dus uit allemaal andere priemfactoren opgebouwd dan Φ(m).
       
  In het voorbeeld is Φ(m) = 24 = 2 • 2 • 2 • 3.  Dus je zou kunnen kiezen e = 5 of e = 7 of e = 25.
Stel dat je neemt e = 7.
       
Je maakt deze getallen  m en e openbaar. Zij vormen samen jouw publieke sleutel.
Als een vreemde nou een bericht B heeft dat hij jou wil sturen, dan kan hij daar een geheim bericht (G) van maken door te berekenen:   G = Be  (mod m).
Dat "mod m" spreek je uit als "modulo m" en als je dat niet kent kun je in deze les lezen wat dat betekent en hoe je handig zulke mod m waarden kunt berekenen.
       
  Laten we zeggen dat je voor het maken van een bericht de erg simpele code A = 01, B = 02, C = 03 enz. gebruikt.(eventueel aangevuld met spatie = 27).
Stel dat je het miniberichtje B = "12"  aan mij wilt versturen (de letter L dus).
Dan bereken je dus  G = 127 (mod 35) = 33
Je verstuurt mij het geheime bericht G = "33".
       
Volgende stap.

Ik ontvang dus van jou het geheime bericht G = "33"
Ik heb intussen ook niet stilgezeten. Ik heb een ontcijfergetal d gemaakt waarvoor geldt:  e • d = 1 (mod Φ). Dat kan niemand anders omdat Φ geheim is, weet je nog?
       
  In dit geval  7 • d = 1 (mod 24)  dus 7 • d = 25, 49, 73, 97, 121, 145, ...... 
De makkelijkste is de eerste die kan:  d = 7  (bij e • d = 49)
       
Zo'n d is altijd te vinden omdat de getallen Φ en e geen gemeenschappelijke priemfactoren hadden.
Bij grote getallen zal het door gewoon proberen niet lukken, maar moet je gebruik maken van het uitgebreid Euclidisch algoritme.
  Als je er met dit algoritme een negatieve d uitkrijgt kun je er altijd aan beide kante f • e bij optellen natuurlijk....
Bijvoorbeeld p1 = 61 en p2 = 719 geeft m = 43859 en Φ = 43080
Het Uitgebreid Euclidisch Algoritme levert  -3767 • 17017 = 1 - 1488 • 43080
Dat geeft -3767 • 17017 + 43080 • 17017  = 1 - 1488 • 43080 + 43080 • 17017
Ofwel  39313 • 17017 = 1 + 15529 • 43080  dus je kunt kiezen d = 39313
       
Volgende stap.

Nu ontcijfer ik jouw geheime bericht G door uit te rekenen:  B = Gd (mod m).
       
  In dit geval bereken ik  B = 337 (mod 35)
337past helaas niet in zijn geheel op mijn GR, maar daar komt het modulorekenen te hulp:
337 (mod 35) = 334 (mod 35) • 333 (mod 35) = 51 • 27 (mod 35) = 1377 (mod35) = 12
       
En daar is jouw bericht al! Het was de letter L!!!
Dus, samengevat:
       

       
Waarom werkt dit?
       
Het komt allemaal omdat de bewerking "tot-de-macht-d"  de inverse is van "tot-de-macht-e"  (beiden mod m).
Dat heeft allemaal te maken met de zogenaamde "kleine stelling van Fermat". Die stelling luidt als volgt:
       

Kleine stelling van Fermat:

Voor elk priemgetal p en elk getal a dat geen priemfactoren p heeft geldt:  ap  = a (mod p)
       
(Het heet trouwens de "kleine" stelling van Fermat, omdat Fermat ook nog een veel bekendere "grote stelling" heeft geformuleerd. Dat is de beroemde stelling:  "xn + yn = zn heeft geen gehele oplossingen voor n >2")

Bijvoorbeeld:   67 = 279936 = 6 + 279930 = 6 + 7 • 39990 = 6 (mod 7)

 
Bewijs .

Neem een willekeurig getal a en een willekeurig priemgetal p dat geen priemfactor van a is.
Als er dan twee getallen n en m zijn waarvoor geldt  n • a = m • a (mod p) dan volgt daaruit dat n = m (mod p)    .....(1)

Kijk maar:
•  Als n • a = m • a (mod p) dan verschillen  n • a en m • a dus een p-voud
•  Dan is p een deler van  n • a - m • a = (n - m) • a
•  Maar omdat p geen deler van a is (gegeven), moet p dus wel een deler van n - m zijn.
•  Dan is  n = m (mod p)

Daarmee is (1) bewezen.
En in "normaal Nederlands"?

Kies het priemgetal p = 7 en het willekeurige getal a = 20

Zoek nu getallen uit de tafel van 20, die precies een 7-voud van elkaar verschillen.

Bijvoorbeeld  60 en 200 verschillen 140.
Dat komt natuurlijk omdat
60 = 3 • 20 en 200 = 10 • 20 
en die 3 en 10 verschillen precies een 7-voud. Dat is altijd zo!

Neem nu een rijtje  getallen  1, 2, 3, 4,..., (p - 1)  die zijn allemaal verschillend.
Als je ze allemaal met a vermenigvuldigt dan krijg je een tweede rijtje van getallen  1a, 2a, 3a, 4a, ..., (p - 1)a
Maar als je de getallen van dit tweede rijtje allemaal mod p neemt, dan krijg je wéér allemaal verschillende getallen.
Dat zegt stelling (1), immers als er twee dezelfden bij zouden zitten, dan zouden de factoren voor de a ook gelijk moeten zijn, en dat kan niet want die zijn 1 tm 1 - p.

Maar omdat beide rijtjes evenveel getallen hebben (namelijk p -1) staan dus in beide rijtjes precies dezelfde getallen
1 tm p - 1. In het tweede rijtje alleen in een andere volgorde.

Als je alle getallen uit zo'n rijtje dan met elkaar vermenigvuldigt krijg je dus óók hetzelfde resultaat, dus:

1 • 2 • 3 • 4 • ... • (p - 1) = 1a • 2a • 3a • 4a • ... • (p -1)a   (mod p)

Haal de factoren a aan de rechterkant bij elkaar:

1 • 2 • 3 • 4 • ... • (p - 1) = 1 • 2 • 3 • 4 • ... • (p -1) • ap - 1   (mod p)

Gelijke termen wegdelen geeft nu 1 = ap - 1  (mod p)

Vermenigvuldig beide kanten met a en je krijgt  a = ap  (mod p) 
De gevraagde stelling.

En in normaal Nederlands?

Schrijf een stukje van de tafel van 20 op, mod 7:

 

1 • 20 mod 7 = 6
2 • 20 mod 7 = 5
3 • 20 mod 7 = 4
4 • 20 mod 7 = 3
5 • 20 mod 7 = 2
6 • 20 mod 7 = 1
 

Nu staan die getallen 1, 2, 3, 4, 5, 6 aan de linkerkant er aan de rechterkant precies weer allemaal.

Dus (mod 7) geldt:

(1•20)•(2•20)•(3•20).....•(6•20)
= 1 • 2 • 3 • ... • 6  (mod 7)

(1•2•3•...•6)•206 = 1•2•3•...•6 (mod7)

206 = 1 (mod 7)  Þ  207 = 20 (mod 7)
       

       
Het ontcijferen van het geheime bericht G gaat nu volgens dit schema:
Daarbij is het volgende gebruikt:
Omdat we eisten dat:   e • d =  1 mod (Φ). Dat zo'n d te vinden is volgt uit de eis dat e en Φ geen gemeenschappelijke deler hebben.
Φ = (p1 - 1)(p2 - 1)    
Hier hadden we net zo goed Kunnen kiezen  B • (Bp2 - 1)(p1 - 1)k dan zou het eindigen met  B(mod p2)
De kleine stelling van Fermat.    
       
Vanwege (3) vinden we hier dus:
Gd = B(mod p1) maar ook Gd = B(mod p2) dus kennelijk is Gd = B mod(p1p2) = B mod(m)
       
Voetnootjes:

•

 RSA is zo moeilijk te ontcijferen omdat het haast niet te doen is om van een enorm getal m te vinden uit welke twee priemgetallen m is opgebouwd. Als m uit veel meer priemfactoren zou bestaan zou dat veel makkelijker te vinden zijn, want zodra je er dan eentje hebt gevonden kun je m daardoor delen en wordt íe snel kleiner.
Verder is RSA ondanks die enorme getallen toch  makkelijk te gebruiken omdat machtsverheffen bij modulorekenen lekker vlot gaat.

•

 Het bericht B dat je wilt versturen mag niet groter zijn dan e. Als dat wel zo is, dan moet je het eerst in kleinere stukken hakken en die één voor één aan mij sturen.
       
De digitale handtekening.
 
RSA geeft ook de mogelijkheid om je eigen verstuurde berichten te voorzien van een digitale handtekening.
Dat komt omdat de versleuteling omkeerbaar is. Jij versleutelt jouw bericht aan mij met mijn publieke sleutel e. Ik ontcijfer jouw geheime bericht met mijn geheime sleutel d.
Maar dat werkt net zo goed andersom. Als ik een bericht met mijn geheime sleutel d maak, dan kun jij dat ontcijferen met mijn publieke sleutel e.

Wat heb je daaraan? Iedereen heeft toch die publieke sleutel?
       
Dat klopt, dus iedereen kan dat ontcijferen, maar alleen ík kon het bericht máken!
Dat betekent dat, als jij het bericht ontcijfert en er komt geen onzin uit, maar iets normaals, dan weet je dat het bericht van mij afkomstig is, en niet van iemand anders.

Dus, als ik jou een geheim bericht wil sturen, dan doe ik het volgende.
Ik maak eerst mijn bericht B geheim met jouw publieke sleutel volgens G = Be (mod m)
Dit geheime bericht G verander ik nu nogmaals, nu met mijn geheime sleutel d. Dus G2 = Gd (mod m)

Als jij nu die G2 krijgt kun je hem eerst ontcijferen met mijn publieke e, en het bericht G wat je daardoor krijgt opnieuw ontcijferen met jouw eigen geheime sleutel d. Als er dan "iets" uitkomt, weet je zeker dat het van mij afkomstig is!!!
       

Stukkie geschiedenis...

In 1977 werd in de Scientific American het RSA systeem uitgelegd. Ronald Rivest daagde de lezers uit een geheime tekst te ontcijferen, die hij had gemaakt door twee grote priemgetallen (van 64 en 65 cijfers) met elkaar te vermenigvuldigen. Dat gaf een getal m van 129 cijfers, en dat gaf hij erbij.
Pas in 1994 had de Nederlandse wiskundige Arjen Lenstra de code ontcijferd, maar daarvoor had hij iets meer dan 1500 computers een half jaar laten rekenen!!!. Dat geeft denk ik wel aan hoe moeilijk die RSA codes te kraken zijn.
Het was overigens de vreemde tekst ‘The magic words are squeamish ossifrage’  (Nederlands:  "de magische woorden zijn kleinzerige lammergier").
Lenstra won er slechts de symbolische prijs van 100 dollar mee. Rivest was nogal gierig, vind je niet?
   
           
In de volgende opgave zetten we letters om in getallen volgens A = 01, B = 02, C = 03,  enz.  en spatie = 27.
Op het volgende adres kun je gemakkelijk machtsverheffen met modulorekenen:
 
           
  OPGAVEN
     
1. a. Mijn publieke code is m = 16113 en   e = 567  
Jij wilt mij graag geheim het woord "KOP" sturen.
Welk getal ga je sturen?
         

6453
  b. Mijn privésleutel was  m = 16113 en d = 6937.
Laat zien dat ik jouw bericht weer ontcijfer als "KOP"
           
2. Ontwerp met de priemgetallen  p1 = 37 en p2 = 137 een publieke en een privésleutel.
           
3. Ikzelf gebruik de privésleutel d = 10259 en de publieke sleutel e = 539  met m = 25957
Mijn vriend Klaas gebruikt de publieke sleutel e = 245 en m = 4841, en zijn privésleutel ken ik uiteraard niet.

Ik heb Klaas gevraagd of hij morgenavond mij in de kroeg wil ontmoeten, en uiteraard versturen wij dit soort belangrijke berichten geheim.
Als antwoord krijg ik drie berichten, waarvan er slechts ééntje van Klaas is. Gelukkig voorziet hij zijn berichten altijd van een digitale handtekening.
De berichten die ik ontvang  zijn:  13446  en   92  en   436.
Onderzoek welk bericht van Klaas is, en of hij mij morgen wil ontmoeten of niet.
           

© h.hofstede (h.hofstede@hogeland.nl)