AANSLUITINGSPROJECT TUE - VO
[ startpagina ] [ omhoog ] [ getalRSA ] [ RSAsysteem ]

Getaltheorie die gebruikt wordt in RSA

Het RSA-cryptosysteem is een geheimschrift waarin een aantal rekenmethoden en oude stellingen uit de wiskunde gebruikt worden. Als je RSA wilt doorgronden dan moet je eerst iets weten over de begrippen deler en veelvoud, klokrekenen,  priemgetallen en de stellingen van Fermat en Euler. 

Klokrekenen

Bij veel geheimschriften wordt gebruik gemaakt van een soort "klokberekening". Stel je een klok voor met de getallen 0 , 1, 2, ... 25.

Je ziet dan de letter a als 0, de letter b als 1, enzovoort, dus de letter z als 25. 
Met deze klok kun je nu rekenen: c + 7 bijvoorbeeld levert dan 2 + 7 = 9, en dat stelt de letter j voor. Evenzo levert x + 7 de letter e, want 23 + 7 = 30 en dat is gelijk aan 4 op deze klok.

In de wiskunde heet klokrekenen modulo rekenen.

Rekenen modulo 26 houdt in dat we alleen werken met de getallen 0 , 1, 2, ... 25. Als je bij je berekeningen antwoorden krijgt die buiten de verzameling {0 , 1, 2, ... 25} liggen, moet je bij het antwoord net zolang 26 erbij tellen of eraf trekken tot het antwoord weer in {0 , 1, 2, ... 25} zit. We schrijven in plaats van = om in de gaten te houden dat we aan het klokrekenen zijn. Op het einde van de regel schrijven we "(mod 26)" om de modulus (in dit geval 26) te onthouden.

Voorbeelden:
20 + 10 4 (mod 26) want  30 en 4 zijn hetzelfde modulo 26,
6*6 10 (mod 26) want 36 en 10 zijn hetzelfde modulo 26,
2⁶ 12 (mod 26)  want 64 en 12 zijn hetzelfde modulo 26.

Je kunt ook zeggen dat 2⁶ 12 (mod 26) omdat 2⁶ = 64 en 12 een veelvoud van 26 verschillen. Op de cirkel zijn ze hetzelfde. Nog een andere manier om hetzelfde te zeggen, is dat je van elke berekening het antwoord deelt door 26 en dat je de rest neemt. We noemen dit ook wel reduceren modulo 26.

Je kunt natuurlijk ook een ander klokgetal kiezen. De koppeling met de letters a, b, ... z gaat dan verloren. 

Voorbeelden:
180 + 1110 = 1290 291 (mod 999)
5*18 = 90 12 (mod 13)
2⁷ = 128 58 (mod 70)

Met geschikte software kun je ook voor zeer grote grote getallen moduloberekeningen maken , bijvoorbeeld 2¹²³ (mod 123456).

Voorbeelden:
Mathematica:     Mod[2^123 , 123456]   resultaat 57920
Maple:               2&^123 mod 123456    resultaat 57920

• Een bestand voor machtsberekeningen met grote getallen

Deler, veelvoud en (grootste) gemeenschappelijke factor

Een natuurlijk getal b is een deler (engels divisor) van een positief natuurlijk getal a als er een natuurlijk getal k bestaat zodanig dat a = k.b. Het getal a noem je een veelvoud van b. Als b geen deler is van a dan zeg je dat a niet deelbaar is door b

Voorbeelden:
3 is een deler van 12 want 12 = 4.3
13 is een deler van 260 want 260 = 20.13
3 is geen deler van 14 want er bestaat geen geheel getal k waarvoor geldt 14 = k.3
1 en 11 zijn delers  van 11 want 11 = 11.1

Als twee natuurlijke getallen een gemeenschappelijke deler hebben dan zijn zeg je ook wel dat ze een factor gemeen hebben.

Voorbeelden:
21 en 70 hebben 7 als gemeenschappelijke deler
13 en 32 hebben geen gemeenschappelijke factor
8 en 100 hebben 2 als gemeenschappelijke factor

In het laatste voorbeeld is ook 4 een gemeenschappelijke deler van 8 en 100. Omdat er geen grotere gemeenschappelijke factor bestaat noem je 4 de grootste gemene deler van 8 en 100. Dat noteer je met ggd(8 , 100) = 4. 

Voorbeelden:
ggd(100, 75) = 25
ggd(13, 101) = 1
ggd(p , p²) = p

In het Engels wordt de grootste gemene deler afgekort met gcd (greatest common divisor).

• Link naar een site waar je ggd's kunt bepalen (get GCD)
• Nog een link naar een site voor ggd's bepalingen
• Een bestand voor de ggd van zeer grote getallen

Priemgetallen

In moderne geheimschriften wordt vaak modulo een priemgetal gerekend.  De reden daarvoor zal verderop duidelijk worden. Priemgetallen zijn positieve, gehele getallen die niet te schrijven zijn als het product van twee kleinere positieve, gehele getallen. Bijvoorbeeld 15 is niet priem, want 15 = 3*5 maar 11 is wel priem. Je kunt ook zeggen dat een priemgetal precies twee positieve delers heeft, namelijk 1 en zichzelf. Er bestaan oneindig veel priemgetallen en met computers kost het weinig moeite om grote priemgetallen te bepalen. 

Voorbeelden:
het eerste priemgetal groter dan 10⁵⁰       
resultaat: 
100000000000000000000000000000000000000000000000151
Een random priemgetal met 100 cijfers
resultaat:  
4895124596351439279653580471831004686022317082464571006275028404339038329279377976381756089823338641  

• Meer priemgetallen 1

• Meer priemgetallen 2

• Een lijst met de allergrootste priemgetallen

De (kleine) stelling van Fermat

De Franse wiskundige Fermat (1601-1665) ontdekte een mooie wetmatigheid als je modulo een priemgetal werkt.

(Kleine) Stelling van Fermat
Als p een priemgetal is en a een getal dat niet door p deelbaar is, dan geldt  a^p-1 1 (mod p)
Met niet deelbaar wordt bedoeld dat p geen deler is van a.

Voorbeeld:
2⁶ = 64 = 9*7 + 1 1 (mod 7)
19² = 361 = 120*3 + 1 1 (mod 3)

Het bewijs van de stelling is niet heel moeilijk. Je kunt het vinden via bewijs Fermat

De Eulerfunctie

De volgende stelling gaat nog een stapje verder dan de stelling van Fermat. We hebben eerst een notatie nodig.

Definitie
De functie j(n) (spreek phi uit) van Euler telt voor elk natuurlijk getal n hoeveel kleinere positieve getallen er zijn die geen factor met n gemeen hebben.

Voorbeelden:
j(7) = 6 want 1, 2, 3, 4, 5 en 6 hebben geen factor gemeenschappelijk met 7
j(8) = 4 want 1, 3, 5 en 7 hebben geen factor gemeenschappelijk met 8 (2, 4 en 6 wel)
j(10) = 4 want 1, 3, 7 en 9 hebben geen factor gemeenschappelijk met 10 (2, 4, 5, 6 en 8 wel)

Als n een priemgetal is dan hoef je niet veel getallen te tellen. Bekijk bijvoorbeeld n = 29. De natuurlijke getallen 1, 2, 3, ... 28 zijn allen kleiner dan 29 en hebben geen gemeenschappelijke factor met 29 want dat is een priemgetal. In het algemeen geldt:

Stelling
Als p een priemgetal is dan geldt j(p) = p-1 

Voorbeeld:
j(101) = 100 want 101 is een priemgetal.

Voor het product van twee priemgetallen ligt de zaak iets gecompliceerder. Toch kun je uit een eenvoudig getallenvoorbeeld een regel halen. Bekijk nogmaals n = 10 = 2*5 en schrap systematisch de getallen die een factor gemeenschappelijk hebben met 10.

Het aantal is dus gelijk aan 10 - 2 - 5 + 1 = 4. Er geldt dus j(10) = 4

Dit is eenvoudig te veralgemeniseren. Als m het product van twee priemgetallen is, n = p*q  dan is j(n) gelijk aan n - p - q +1. Er zijn immers q p-vouden en p q-vouden die je weg moet strepen. Omdat n zowel door p als door q deelbaar is schrap je dat getal twee keer door. Je moet er dus weer 1 bij optellen.. Conclusie:

Stelling
Als p en q priemgetallen zijn dan geldt  j(p*q) = p*q - p - q + 1 = (p-1)*(q-1)

Voorbeeld:
j(77) = j(7*11) = 6*10 = 60 want 7 en 11 zijn priemgetallen.

Deze functie speelt een belangrijke rol in het RSA-systeem en hij komt ook tevoorschijn in de stelling van Euler. Deze stelling lijkt veel op de stelling van Fermat.

Stelling van Euler 
Als a geen factor gemeen heeft met n dan geldt dat  a^j(n) 1 (mod n)

Voorbeeld:
10⁶⁰  1 (mod 77)
3¹⁰⁰⁰ (3⁴)¹⁰⁰⁰ 1¹⁰⁰⁰  (mod 10) 1

Het bewijs van de Stelling van Euler verloopt precies hetzelfde als het bewijs van de Stelling van Fermat. Dit keer vermenigvuldig je de getallen die geen factor met n gemeen hebben.

De bovenstaande begrippen en stellingen zijn vrij oud. Fermat (1601-1665) en Euler (1707-1783) zijn al meer dan 200 jaar dood. In de 20^e eeuw hebben drie wiskundigen; Rivest, Shamir en Adleman deze stellingen geraffineerd toegepast bij het maken van een niet te kraken geheimschrift: het RSA-cryptosysteem.

Naar het RSA-cryptosysteem