14.1 Zoektocht naar een geschikte eenwegfunctie 14.2 Het RSA-algoritme 14.3 Challenges 14.4 Een voorbeeld 14.5 Complexe berekeningen 14.6 Digitale handtekeningen
14.1 Zoektocht naar een geschikte eenwegfunctie
Ron Rivest, Adi Shamir en Leonard Adleman vormden in 1976, naar aanleiding van het artikel van Diffie en Hellman over asymmetrische vercijfering, een driemanschap in hun zoektocht naar een geschikte eenwegfunctie. Het zou meer dan een jaar van intensief onderzoek vergen voordat in april 1977 Ron Rivest met een oplosing kwam. De oplossing gaat als RSA-encryptie door het leven en het begrijpen van de eenwegfunctie vraagt behoorlijk wat wiskundige kennis. Het algoritme is niet moeilijker dan de encryptie die we in hoofdstuk 13 hebben gebruikt en maakt ook gebruik van de inverse bij modulo-vermenigvuldiging, maar de eenwegfunctie is veel moeilijker te volgen omdat hij gebruik maakt van machtsverheffen in plaats van vermenigvuldigen.
De oplossing die Diffie, Hellman en Merkle bedachten voor het distributieprobleem maakte al gebruik van de rekenregel die stelt dat (ax)y=axy=(ay)x. En het was de modulo-vermenigvuldiging die ervoor zorgde dat het bericht dat Alice naar Bob verstuurde en het bericht dat Bob naar Alice verstuurde voor Eve onleesbaar werd. In de les die erop volgde hebben we gezien dat er een inverse bestaat bij vermenigvuldiging met a modulo m als a en m relatief priem zijn. De oplossing van Rivest lijkt een combinatie van deze dingen te zijn, maar maakt daarbij nog gebruik van twee ingewikkelde stellingen die we verderop in deze les nog zullen bekijken en waarvan we op de sub-pagina's de verdere details zullen bekijken. Verder maken we gebruik van de volgende definitie:
Definitie: f (n) is het aantal priemdelers van een getal n. f (n) wordt de Eulerfunctie, Eulerindicator oftotiëntfunctie genoemd en de waarde wordt vaak aangeduid met de letter K. Het aantal priemdelers van een priemgetal p is het aantal positieve getallen kleiner dan p , dus gelijk aan p-1 als p een priemgetal is: f(p)=p-1 als p een priemgetal is.
14.2 Het RSA-algoritme
Het RSA-Algoritme
Kies twee grote priemgetallen p en q en bereken n=p*q.
Bereken f(n)=(p-1)*(q-1)= K
Kies een getal e dat relatief priem is ten opzichte van K en bereken de inverse d mod K.
Een bericht x dat vercijferd is met xe mod n = y
is nu te ontcijferen met yd mod n = x.
{e,n} heet de publieke sleutel.
{d,n} heet de privé sleutel.
Dat yd mod n = xed mod n is niet moeilijk in te zien. Dat xed mod(n) = x met edmod(K)=1, wordt bewezen voor 0<x<min{p,q} op de subpagina Euler en Fermat met gebruik van de stelling vanEuler. Voor het bestuderen van deze hoofdpagina is het geen bezwaar om met bestudering van deze subpagina tot het eind te wachten.
De RSA-vercijfering werkt als volgt: Alice publiceert het getal n en het getal e. Ze zet het bij wijze van spreken op haar naamkaartje of publiceert het in een encryptiegids waarin Bob het kan vinden. Alice houdt haar sleutel, de priemgetallen p en q, geheim. Bob vercijfert zijn bericht x met de eenwegfunctie xe mod n en verstuurt het resultaat naar Alice. De klare tekst is dus x en de cijfertekst is y=xe mod n. Met haar sleutel en de tabel van Euclides berekent Alice de inverse d en berekent yd mod n. Dit levert haar de klare tekst x.
De vraag is nu wat Eve kan ontdekken als ze het bericht xe mod n voorbij ziet komen. Het is voor haar immers net zo goed mogelijk om in de encryptiegids de publieke sleutel op te zoeken en ze kent dus de waarde van e en n. Het enige wat Eve nog te doen heeft is het opstellen van een tabel bij de cijferfunctie of het vinden van de waarde van d, de inverse van e mod K. Helaas voor Eve kent ze het getal K niet. Alleen door factorisatie van n kan ze K berekenen en dat is iets wat haar niet gaat lukken als de priemgetallen p en q erg groot zijn. Dit probleem staat bekend als het factorisatieprobleem.
14.3 Challenges
Hoe moeilijk is het om de waarde van d te berekenen?
In 1977 schreef Martin Gardner het artikel "A new kind of cipher that would take millions of years to break". Gardner gaf zijn lezers een opgave om een cijfertekst te ontcijferen en loofde een beloning uit van $100 voor degenen die er als eerste in zou slagen. De tekst was vercijferd met volgens RSA-129. Dat wil zeggen dat n een getal was van 129 cijfers. Het zou tot 26 april 1994 duren voordat een groep van 600 vrijwilligers bekend maakte dat ze de ontbinding gevonden hadden: RSA-129 =
114.381.625.757.888.867.669.235.779.976.146.612.010.218.296.721.242.362.562
561.842.935.706.935.245.733.897.830.597.123.563.958.705.058.989.075.147.599
290.026.879.543.541
Sindsdien zijn er steeds nieuwe Challenges uitgeschreven en op 9 mei 2005 werd RSA-200 gekraakt. De RSA-factory schreef steeds nieuwe challenges uit met steeds groter wordende beloningen, maar is daar inmiddels mee gestopt omdat er steeds meer challenges onopgelost bleven en de lol er blijkbaar afging.
Hieronder is een internet-pagina opgenomen die over dit onderwerp handelt. Als je geïnteresseerd bent bevat het ook veel links waarmee je verder op zoek kunt, maar het voert te ver om hier nu uitgebreid bij stil te blijven staan.
In het boek van Simon Singh lezen we dat in 1995 door Simson Garfinkel werd berekend, dat als neen waarde zou hebben van een getal van 130 cijfers, een 100Mhz Intel Pentium-computer met 8 MB ram, een moderne computer voor die tijd, er 50 jaar voor nodig zou hebben om n te ontbinden inp*q. Honderd miljoen computers in een netwerk, wat gelijk stond aan het totale aantal verkochte computers in 1995, zouden n echter in 15 seconden kunnen ontbinden. Met het sneller worden van de computers en het groeien van het netwerk is het dus nodig om steeds grotere priemgetallen te gebruiken. Tegenwoordig worden priemgetallen van enkele honderden cijfers gebruikt om bijvoorbeeld banktransacties te beveiligen. Als de techniek voortschreidt en computers steeds sneller worden, dan zal het steeds sneller gaan om grote waarden van n te ontbinden, maar het werken met grotere waarden van p en q wordt dan ook steeds makkelijker en we weten dat er al priemgetallen zijn met meer dan 10 miljoen cijfers! Dat maakt RSA tot een hele veilige encrypiemethode.
Een techniek die Blindingheet vercijfert de tekst x vóórdat het de eenwegfunctie van de RSA-encryptie ingaat. Op die manier kunnen Alice en Bob gebruik maken van een instantie die RSA-vercijfering voor hen uitvoert. Het is immers goed denkbaar dat Alice en Bob zelf niet over de techniek en apparatuur beschikken om de tekst te vercijferen en ontcijferen.
14.4 Een voorbeeld
We zullen nu eerst een voorbeeld bekijken van RSA-encryptie en daarna een aantal opgaven maken met deze techniek. Hiervoor gebruiken we kleine priemgetallen die dus niet echt de gewenste graad van beveiliging geven, maar die het wel mogelijk maken om berekeningen uit te voeren met een eenvoudig rekenblad en te zien wat er gebeurt.
Reflectie
De vraag waarom de eenwegfunctie goed werkt is niet zo eenvoudig te beantwoorden. We maken immers gebruik van de inversen d en e bij een berekening modulo n. Wat is hier vreemd aan?
Bob heeft de publieke sleutel {23,7387} Hoe kwetsbaar is deze sleutel? De opdracht die Eve heeft om de geheime sleutel te achterhalen is om 7387 te ontbinden in priemfactoren. Ze neemt een rekenblad en deelt 7387 door alle oneven getallen kleiner dan 7387(1/2) 86 tot er een heel getal gevonden wordt: al snel komt ze er achter dat 7387=83*89. Nu kan ze K=(p-1)(q-1) berekenen: K=82*88=7216 Met de tabel van Euclides berekent ze nu de geheime sleutel:1255
Wanneer je een bericht met RSA wilt vercijferen, zet je het bericht eerst om naar een bericht dat bestaat uit getallen. Je kunt bijvoorbeeld de ASCII-codes van de tekens van het toetsenbord nemen. Als we deze codes achter elkaar zetten en vervolgens opsplitsen in blokken van een bepaalde lengte, kunnen we deze blokken vercijferen met het RSA-algoritme. De lengte van deze blokken wordt zo gekozen dat 10l< n, maar niet al te veel kleiner, waarbij l de lengte van de blokken en n de modus.
Invuloefening
In dit voorbeeld geven we de letters van het alfabet hun rangnummer als code. De letter a is dus 00, de letter b 01, enz. Alice wil Bob het bericht "rsa" sturen. Alice splitst de code in blokken van lengte 3 en vercijfert de blokken met de publieke sleutel(5183,17) van Bob.
14.5 Complexe berekeningen
De berekening die Alice uit moet voeren op de klare tekst 171 800 met sleutel (5183,17) leidt onmiddelijk tot een probleem omdat het rekenblad en de rekenmachine de berekeningen niet aan kunnen.
Een mogelijkheid is om de volgende rijtjes uit te rekenen: 1712 mod 5183; 8002 mod 5183
1714 mod 5183; 8004 mod 5183
1718 mod 5183; 8008 mod 5183
17116 mod 5183; 80016 mod 5183
Merk op dat elk volgende getal steeds het kwadraat is van de voorgaande en dat een rekenblad daarbij goede dienst kan bewijzen.
Opmerking: Als je de bovenstaande berekeningen volgt, merk je dat het vercijferen van een bericht door Alice en het ontcijferen door Bob geen pretje is. Op de sub-pagina Euler en Fermat leer je dat er ook shortcuts zijn om dit soort berekeningen uit te voeren.
Invuloefening
Opgave 1
Vercijfer het tweede blok van de boodschap van Alice.
In de invuloefening zie je dat de lengte van de blokken in de cijfertekst niet hetzelfde is als de lengte van de blokken in de originele boodschap. In de praktijk zul je gewoonlijk niet een heel bericht met RSA vercijferen. De rekentijd is hiervoor te lang. RSA wordt meestal gebruikt om een sleutel te versturen van een symmetrisch cryptosysteem waarbij vercijfering minder tijd kost. Naast de sleutel wordt eventueel wat aanvullende informatie verstuurd om te zorgen dat je zeker weet dat niemand wijzigingen in je bericht heeft aangebracht. De lengte l van de boodschap die je wilt versturen is hierdoor korter. Het is dan niet nodig de boodschap op te splitsen in blokken en je hoeft dus ook niet een aantal blokken afzonderlijk te vercijferen. Hierdoor maakt het niet uit als de originele tekst en de cijfertekst niet even lang zijn.
Reflectie
Hoe belangrijk is het dat de blokken van de cijfertekst even lang zijn als de blokken van de klare tekst?
De boodschap van Alice wordt ontvangen door Bob, die het nu met zijn privé-sleutel zal proberen te ontcijferen.
Opgave 2
Ontcijfer het bericht 3685 2677 met de privé-sleutel {5183,593}.
In de volgende opgave controleren we hoe veilig de sleutel van Bob is:
Opgave 3
De publieke sleutel van Bob is (209,13).
Achterhaal de geheime sleutel van Bob.
Opgave 4
Wijzer geworden door opgave 3 kiest Bob de publieke sleutel (1040257,1361). De geheime sleutel van Bob vinden, zal je nu niet zo snel lukken zonder computer.
Wat is er zo moeilijk aan?
Voor kleine p en q is het niet moeilijk om de geheime sleutel uit de publieke sleutel af te leiden, voor (hele) grote p en q wel. Daarom gebruikt men voor p en q getallen van ongeveer 150 cijfers. Het getal n bestaat dan uit ongeveer 300 cijfers. Een getal dat zo groot is, is momenteel zelfs met de allersnelste computers niet binnen een mensenleven te ontbinden. Hierop berust de veiligheid van RSA. Wanneer je de getallen p en q zou kunnen vinden, zou je K eenvoudig kunnen berekenen en de inverse van e met het uitgebreide algoritme van Euclides kunnen berekenen. Je zou dan de vercijferde boodschap kunnen ontcijferen door hem tot de macht dte verheffen mod n.
Dit is een geschikt moment om de tekst onder het kopje Machtsverheffen modulo m door te nemen.
Machtsverheffen modulo m
Onder het kopje (a div m) en (a mod m) van les 12 heb je de somregel en de productregel voor het modulo-rekenen geleerd. We herhalen ze nog even:
Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als amod m = bmod m en c mod m = d mod m dan Somregel: (a+ c)modm = (b+d)modm Productregel: (a*c)modm = (b*d)mod m
Op deze subpagina richten we onze aandacht op het machtsverheffen.
Opgave 1
a) Leg uit dat we voor kwadrateren geen aparte regel nodig hebben.
b) Leg uit dat als je kunt kwadrateren en twee getallen kunt vermenigvuldigen,
dat je dan ook weet hoe je tot de derde en de vierde macht moet verheffen.
c) Leg uit dat je dan dus ook weet hoe je getallen tot een hogere macht kunt verheffen.
Na het maken van opgave 1 voel je de juistheid van de machtenregel wel aan:
Voor gehele getallen x en y en positieve gehele getallen k en d geldt:
als x(mod d)= y(mod d) dan xk(mod d)= yk(mod d).
Opgave 2
Vul de tabel in Z5 in. Met het teken "^" bedoelen we "tot de macht", dus 1^2=12.
Voorbeeld : In Z5is 2^4 = 16(mod 5) = 1
^
0
1
2
3
4
0
1
2
1
3
4
Met behulp van de somregel, de productregel en vooral de machtenregel kunnen we berekeningen die erg moeilijk lijken toch vrij eenvoudig uitvoeren.
We kijken nog eens hoe de regels voor machtsverheffen zijn:
Je weet dat 46 betekent 4*4*4*4*4*4
Leg daarmee uit dat: 34*35=39
Laat ook zien dat (52)3=56
Algemeen: ap*aq=ap+q en (ap)q=ap*q
a) Bereken 225 in Z31.
b) Bereken 3301 in Z25.
c) Bereken 1896 in Z325.
Opgave 4
a) Bereken 1733 in Z553.
b) Bereken 1240 in Z1000.
c) Bereken 73843 in Z640.
Opgave 5
a) Bepaal de rest van 247 bij deling door 47.
b) Bepaal het laatste cijfer van 381. (Tip: reken modulo 10)
c) Onderdeel b kan ook anders. Hoe?
Ga nu verder met het gedeelte over Digitale handtekeningen (14.6)
14.6 Digitale handtekeningen
We hebben in de afgelopen lessen gezien hoe we cryptografie kunnen gebruiken om boodschappen veilig te versturen. In deze paragraaf kijken we naar een andere, maar niet minder belangrijke, toepassing van cryptografie.
Wanneer we een boodschap ontvangen, willen we graag zeker weten dat de afzender inderdaad de persoon is die hij zegt dat hij is. Stel dat een bank een opdracht krijgt waarin staat dat er geld van een bepaalde rekening overgeschreven moet worden naar een andere rekening. De bank wil dan wel graag zeker weten dat de persoon die die opdracht geeft, daartoe gemachtigd is. Hiervoor gebruikt de bank een crypto-systeem. De opdrachtgever moet bepaalde informatie geven die alleen een gemachtigd persoon kan weten.
Door het meesturen van een digitale handtekening kan zekerheid verkregen worden over of de afzender van een bericht is wie hij zegt dat hij is.
Alice verstuurt een bericht aan Bob. Ze stuurt een digitale handtekening mee. De digitale handtekening mag alleen door Alice gemaakt kunnen worden. Dit betekent dat Alice er bepaalde geheime informatie voor nodig moet hebben om de handtekening te kunnen maken. Bob moet de handtekening kunnen controleren en dus heeft hij enige kennis over de informatie van Alice nodig. Hij moet de handtekening immers kunnen onderscheiden van valse handtekeningen. Misschien herken je hierin al de geheime en publieke sleutel die we eerder in de public-key cryptografie tegenkwamen.
Het RSA-cryptosysteem kunnen we gebruiken om een digitale handtekening te maken. De geheime en publieke sleutel worden gekozen als gebruikelijk.
Noem de geheime sleutel van Alice {n,a} en de publieke sleutel van Alice {n,A} met a*A mod KAlice = 1.
Noem de geheime sleutel van Bob {m,b} en de publieke sleutel van Bob {m,B} met b*B mod KBob= 1.
Als Alice een geheime boodschap wil versturen aan Bob en ze bovendien wil dat Bob kan zien dat de boodschap echt van haar komt, gaat ze als volgt te werk.
Alice vercijfert haar boodschap s met haar geheime sleutel {n,a}. Ze berekent dus samodn=t.
Vervolgens vercijfert ze het bericht t met de publieke sleutel {m,B} van Bob, ze berekent dustBmod m = c .
Reflectie
a) Leg uit waarom het bericht c alleen door Alice verstuurd kan zijn. b) Beschrijf hoe het ontcijferen in zijn werk gaat. c) Leg uit waarom dit bericht alleen door Bob gelezen kan worden.
Voorbeeld:
Alice kiest priemgetallen pAlice = 41 en qAlice = 53.
Ga na dat nAlice = 41x53 = 2173 en KAlice = 40 x 52 = 2080
Bob kiest priemgetallen pBob = 47 en qbob = 61.
Ga na dat nBob = 47x61 = 2867 en KBob = 46 x 60 = 2760
Alice kiest de Publieke sleutel {73,2173} en Privé sleutel {57,2173}
Ga na dat 57x73 mod 2080 = 1.
Bob kiest de Publieke sleutel {79,2867} en Privé sleutel {559,2867}
Ga na dat 79x559 mod 2760 =1
Alice verstuurt aan Bob het bericht xxx ik hou van je
De boodschap wordt eerst gecodeerd volgens de ASCII-tabel en daarna verdeeld in blokken van 3 cijfers.
Het eerste blok vercijfert Alice met haar Privé sleutel en daarna vercijfert ze de hele tekst met dePublieke sleutel van Bob. Bob ontcijfert het ontvangen bericht met zijn eigen Privé sleutel en daarna het eerste blok met de Publieke sleutel van Alice.
We bekijken alleen de berekening voor het eerste blok:
De x heeft ASCII-waarde 120.
12057(mod 2173) = 2047, dus het bericht xxx wordt 204720472047
De blokken worden 204 720 472 047
20479(mod 2867) = 2480
72079(mod 2867) = 0736
47279(mod 2867) = 1259
04779(mod 2867) = 0047
Alice stuurt Bob de blokken 2480 0736 1259 0047
Bob ontcijfert:
2480559(mod 2867) = 204
073679(mod 2867) = 720
125979(mod 2867) = 472
004779(mod 2867) = 047. Alice handtekening is dus 204720472047
In blokken wordt dit 2047 2047 2047 en
204773(mod 2173) = 120, de code van x
Merk op dat de lengte van het blok tijdens de berekening verspringt naar een lengte van 4.
Opgave 5
Alice gaat Bob een bericht voorzien van handtekening sturen.
Alice kiest als haar priemgetallen pa=5en qa=13 .
Bob heeft de priemgetallen pb=7 en qb=11 gekozen.
a) Bereken Kaen Kb.
De geheime sleutel van Alice is 17 en de geheime sleutel van Bob is 13.
b) Bereken de publieke sleutels van Alice en Bob.
Alice wil het geheime bericht "6" versturen aan Bob en voorzien van een digitale handtekening.
c) Bereken welk bericht Alice aan Bob gaat sturen.
d) Voer de ontcijfering van het bericht voor Bob uit.
Reflectie
Merk op dat deze manier van boodschappen verzenden erg veel weg heeft van de oplossing waar Diffie in 1975 mee kwam. Het grote verschil is tweeledig: welke verschillen kun je bedenken?
EF.1 De Eulerindicator
EF.2 Somregel en productregel
EF.3 Een regel voor φ(pr)
EF.4 De stelling van Euler
EF.5 De kleine stelling van Fermat
EF.1 - De Eulerindicator
Leonhard Euler (1707-1783) wordt beschouwd als de belangrijkste wiskundige van de achttiende eeuw en is de wiskundige die het meest gepubliceerd heeft. Zijn verzameld werk beslaat zo'n zeventig delen. Euler heeft onder andere de symbolen e, i, en de goniometrische functies sinus, cosinus en tangens geïntroduceerd.
Beroemd is zijn vergelijking waarin de bijzondere getallen 0, 1, e, i en verenigd zijn.
In deze paragraaf zullen we de stelling van Euler bekijken die ons goed van pas komt als we naar wat moderne cryptosystemen gaan kijken. De stelling van Euler gaat over machtsverheffen en maakt het rekenen met grote machten eenvoudiger.
Op de hoofdpagina van les 14 hebben we het getal Kgedefinieerd als het aantal priemdelers van een getal m.
Hieronder volgt een definitie die op hetzelfde neerkomt: Het getal dat aangeeft hoeveel priemdelers een getal heeft staat bekend als de Eulerindicator,Eulerfunctie oftotiëntfunctie.
Definitie:
De Eulerindicator φ(m) is het aantal gehele, niet-negatieve getallen k waarvoor geldt 0 ≤ k ≤ m -1 en ggd(k,m)=1.
We geven het ook wel aan met de letter K.
Eulerindicator φ(m) is vanzelfsprekend gelijk aan het aantal getallen k waarvoor geldt dat
0 ≤ k ≤ m -1 en dat k een inverse in Zm heeft.
Reflectie
Waarom is vanzelfsprekend het aantal φ(m) gelijk aan het aantal getallen k dat een inverse in Zmheeft?
Je weet dat 10=5∙2
Dus alle veelvouden van 2 en 5 hebben een deler gemeen met 10.
Voor 0 ≤ k ≤ 10 -1 zijn dat de getallen: 2,4,6,8 en 5.
Dus k in het rijtje 1,3,7 en 9 heeft de eigenschap dat ggd(k,10)=1
Dus φ(10)=4.
Opgave 1
Bepaal het aantal priemdelers
a. φ(12)
b. φ(5)
c. φ(7)
d. φ(p) als p een priemgetal is.
e. φ(35)
f. Is er een verband tussen de antwoorden op vraag b., c. en e.?
EF.2 - Somregel en productregel
Voor de Eulerindicator gelden bepaalde wetmatigheden. We zagen er al één in opgave 1d. In opgave 3b en opgave 4d zullen we er nog twee bekijken.
We proberen φ(35) te vinden. Nu is 35=5∙7. Merk op dat 5 en 7 priemgetallen zijn.
Hiervoor maken we een blokje van 5 bij 7.
Op de 1e rij zetten we de getallen 1, ..., 7; op de 2e rij 8, .. 14, enzovoorts.
Dan geven we aan welke getallen niet relatief priem zijn met 5 en 7.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Hierin is goed te zien dat elk getal in de 7e kolom uitsluitend veelvouden van 7 bevat. En het zijn ze ook allemaal.
Verder kun je opmerken dat in de andere kolommen steeds precies één getal zit dat een veelvoud is van 5.
Laten we eens kijken of we erachter kunnen komen hoe dat komt:
Bekijk de 1e kolom.
Achtereenvolgens staan daar de getallen : 1, 8, 15, 22, 29
Ofwel: 1, 1+7, 1+2∙7. 1+3∙7. 1+4∙7
Bekijk nu de resten na deling door 5. Dat zijn achtereenvolgens:
1, 3, 0, 2 en 4.
Deze resten zijn alle onderling verschillend!
De resten berekenen we bij het modulo-rekenen waarvoor de volgende regels gelden:
Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als a(modm)=b(modm) en c(modm)=d(modm) dan
Somregel: (a+c)modm=(b+d)modm
Productregel: (a*c)modm=(b*d)modm
Reflectie
Deze resten zijn alle onderling verschillend! Zoek eens uit hoe dat komt.
a) Waarom heeft het rijtje 2, 2+7, 2+2∙7. 2+3∙7. 2+4∙7 dezelfde resten na delen door 5 als 2, 2+2, 2+2∙2. 2+3∙2. 2+4∙2?
In elke kolom staat dus precies één getal dat een veelvoud is van 5.
Dus is φ(35) gelijk aan het aantal kolommen zonder zevenvouden ( dat zijn er 7 -1 = 6),
vermenigvuldigd met het aantal getallen in elke kolom dat geen vijfvoud is (dat zijn er in elke kolom 5 - 1 = 4).
Dit geeft φ(35) = φ(7)∙ φ(5) = 6∙4=24 .
Opgave 2
a) Bepaal φ(77)
b) Bepaal φ(82)
c) Bepaal φ(1055)
d) Bepaal φ(8). Pas op.
Opgave 3
a) Bepaal het aantal priemdelers van p*q als p en q priem zijn en p ≠ q. Leg uit hoe je aan je antwoord komt.
b) Laat zien dat het aantal priemdelers φ(p*q)=φ(p)*φ(q) als p en q priem zijn en p ≠ q.
De regel uit 3b geldt ook als p en q relatief priem zijn. We zullen dit hier niet bewijzen, maar je kunt het natuurlijk zelf proberen.
EF.3 - Een regel voor φ(p r )
We bekijken een voorbeeld: φ(72)=?
Eerst maar eens een tabel maken met behulp van Excel.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Alleen in de laatste kolom staan veelvouden van 7. Alle andere getallen zijn relatief priem met 49.
Immers een gemeenschappelijke deler kan alleen 7 zijn.
Dus zijn er 6 kolommen met 7 getallen die relatief priem zijn met 49. φ(72)=7∙6=42.
Reflectie
Bedenk dat in de 1e kolom elk getal geschreven kan worden in de vorm: 1+k∙7, k=0,1,2,3,4,5,6.
a) Leg uit dat in de 1e kolom dus geen enkel zevenvoud kan voorkomen.
b) Kan er in de 2e kolom een 7-voud voorkomen?
a) Bepaal φ(25).
b) Bepaal φ(125).
c) Bepaal φ(625).
d) Leg uit dat φ(pr) = (p-1)*pr-1.
In opgave 3b en opgave 4d hebben we twee regels aangetoond die nu van belang zijn:
1.φ(p*q)=φ(p)*φ(q) als p en q (relatief) priem zijn en p ≠ q.
2. φ(pr) = (p-1)*pr-1 voor een priemgetal p.
Met deze twee regels voor de Eulerindicator kunnen we voor alle getallen de Eulerindicator berekenen. Om van een getal de Eulerindicator te vinden, schrijven we het getal eerst als product van machten van zijn priemfactoren. Die machten van priemfactoren zijn onderling vanzelfsprekend relatief priem en daarom mogen we de regels toepassen, zoals in het volgende
Voorbeeld:
Bereken φ(18000).
18000=24*32*53. Er geldt dat 24, 32 en 53 relatief priem zijn. We passen daarom de regels toe:
φ(18000)=φ(24)*φ(32)*φ(53) volgens regel 1 φ(18000)=(1*23)*(2*31)*(4*52)=8*6*100=4800 volgens regel 2.
Opgave 5
a) Bepaal φ(640)
b) Bepaal φ(49000)
c) Bepaal φ(245025)
We zouden de Eulerindicator van m ook graag willen uitrekenen zonder m eerst in factoren te ontbinden. Helaas is niet bekend hoe dat zou moeten. In feite is het uitrekenen van de Eulerindicator equivalent met het ontbinden van m in factoren. We zagen op de hoofdpagina hoe nuttig functies zijn die heel erg moeilijk te berekenen zijn als je niet beschikt over extra informatie, zoals de ontbinding van een getal, en juist makkelijk te berekenen zijn als je wel over extra informatie beschikt. De Eulerindicator komt voor in de stelling van Euler en deze stelling helpt ons bij het rekenen met machten.
EF.4 - De stelling van Euler:
Voor alle gehele getallen a en m met ggd(a,m)=1 geldt dat aφ(m)=1 in Zm.
Dit is een resultaat waarmee we grote machten heel snel kunnen reduceren en waardoor ondermeer Alice en Bob wel in staat zijn te vercijferen volgens het algoritme van Diffie en Hellman, maar Eve niet in staat is de sleutel te achterhalen! Zie de opmerking in les 10 hierover.
Voorbeeld:
Bereken 3300 in Z25.
Er geldt ggd(3,25)=1, dus we mogen de stelling van Euler gebruiken: 3φ(25)=1 in Z25 φ(25)=20, dus 320=1 in Z25.
3300=(320)15=115=1.
Opgave 6
Bereken
a) 73843 in Z640
b) 161033 in Z81
c) 252999 in Z99
Uit de stelling van Euler volgt de kleine stelling van Fermat.
EF.5 - De kleine stelling van Fermat
Als p een priemgetal is en a een positief geheel getal en ggd(a,p)=1, dan geldt ap-1=1 mod p .
Opgave 7
Laat zien dat de kleine stelling van Fermat uit de stelling van Euler volgt.
Waarom het RSA algoritme werkt
Het algoritme zegt:
Kies twee grote priemgetallen p en q en bereken n=p*q.
Bereken φ(n)=(p-1)*(q-1)= K
Kies een getal edat relatief priem is ten opzichte van K en bereken
de inverse dmod K.
Een bericht xmet x>0 en xkleiner dan het minimum van p en q, dat vercijferd is met xe mod n = y
is nu te ontcijferen met ydmod n = x.
{e,n} heet de publieke sleutel.
{d,n} heet de privé sleutel.
Bewijs:
Gegeven is n=p*qmet p en q priem.
Kies e,d zodanig dat ed = 1(mod φ(n))
dat wil zeggen ed = 1+k∙φ(n) met φ(n) = (p-1)(q-1).
Nu geldt xed(mod n) = x1+k∙φ(n) (mod n)= x∙xk∙φ(n) (mod n)
en omdat ab(mod p) = {a mod p}b volgt x∙xk∙φ(n) (mod n) = x∙{xφ(n) mod n}k
Met 0<x<min{p,q} en n=p∙q moeten x en n relatief priem zijn, zodat uit de stelling van Euler volgt,
dat xφ(n) mod n= 1 zodat xed(mod n) = x∙{xφ(n) mod n}k= x∙1k= x.
Als x≥min{p,q} dan kan x een veelvoud zijn van p of q. De kans is erg klein omdat er maar weinig van deze getallen zijn, maar in dat geval zijn x en n niet relatief priem. Toch werkt ook in dit geval het RSA algoritme maar het bewijs is veel complexer. Zie voor een uitgebreider bewijs bijvoorbeeld http://pajhome.org.uk/crypt/rsa/maths.html
Samenvatting deel 2
Met de komst van het ARPANET in 1969, uitmondend in het internet in 1982, werd het berichtenverkeer steeds drukker, nam de behoefte aan veilige communicatie steeds verder toe en werd het sleuteldistributieprobleem steeds groter.
Hellman was de eerste die een oplossing voor het probleem vond en werkte het samen met Diffie en Merkle uit. In juni 1976 presenteerden ze hun oplossing aan de buitenwereld, waarbij ze gebruik maakten van de modulo-functie en de exponentiële functie. Het berekenen van een macht modulo m met grote exponent is redelijk eenvoudig te berekenen voor Alice en Bob, terwijl het voor Eve ondoenlijk is de berekening terug te draaien. Daarmee is een zogenaamde eenwegfunctie gecreëerd, een functie die niet omkeerbaar is. Alice en Bob kunnen hiermee openlijk een geheim getal afspreken waarmee een symmetrische sleutel gemaakt kan worden voor verdere vercijfering zonder dat iemand het na kan rekenen. Hiernee is het sleuteldistributie systeem opgelost.
Het Man in the Middle probleem laat zien hoe Eve in de communicatie tussen Alice en Bob kan inbreken. Ze doet zich voor als Bob als ze tegen Alice praat en als Alice als ze tegen Bob praat, zonder dat Alice en Bob daar iets van merken.
In 1975 lanceerde Diffie het idee van een asymmetrische sleutel. Dat wil zeggen dat sleutel {a,n} gebruikt wordt voor encryptie en sleutel {b,n} voor decryptie. Sleutel {a,n}zou je op je visitekaartje kunnen zetten zodat iedereen jou een bericht kan sturen versleuteld met sleutel {a,n}. Alleen jij kunt de berichten ontsleutelen met de geheime sleutel {b,n}. Voorwaarde is, dat het niet mogelijk mag zijn om
met alleen kennis van de publieke sleutel {a,n}, sleutel {b,n} af te leiden en
om sleutel {a,n} te breken
Daarom is het nodig dat sleutel {a,n} zelf een eenwegfunctie is.
Les 11, 12 en 13 laten zien hoe je volgens het uitgebreide algoritme van Euclides een asymmetrische sleutel kunt maken.Volgens de stelling van Bachet-Bézout is er, als a en m onderling priemdelers zijn, een b zodat a∙b = 1 (mod m). Voor iedere x < m geldt dan dat a∙x mod m = y en dat b∙y mod m = b∙a∙x mod m = x. Hierbij is xde klare tekst en y de cijfertekst.
Om het algoritme van Euclides te kunnen hanteren moet je eerst weten wat priemdelers zijn en wat de Grootste Gemene Deler is. Verder moet je kunnen rekenen met
- de gehele deling a div m en
- de modulusfunctie a mod m.
In les 12 heb je geleerd hoe Excel daarbij een handige tool kan zijn.
In les 13 is het algoritme van Euclides uitgebreid om de inverse sleutel {b,m} te vinden, waarmee de vercijferde code kan worden ontsleuteld. Het algoritme stelt je in staat om voor twee getallen a en m met a < m eenvoudig het getal bte vinden,
waarbij a∙b=1 mod m.
Het doel om een asymmetrisch systeem te maken is hiermee nog niet direct bereikt omdat iedereen in principe in staat is met a en m de inverse b te berekenen.
Het duurde tot april 1977 tot Rivest, Shamir en Adleman een asymmetrische sleutel vonden die wel aan voorwaarden 1. en 2. voldeed. Ze maakten daarbij gebruik van twee zeer grote priemgetallen p en q. Je moet hierbij denken aan priemgetallen van 150 cijfers of meer.Het product p∙q is de modulus n bij de vercijfering. Verder gebruiken ze de Eulerfunctie φ(x); deze berekent het aantal priemdelers van x.
Het RSA algoritme zegt nu:
Kies twee grote priemgetallen p en q.
Bereken p∙q=n
Bereken φ(n)=(p-1)∙(q-1)
Kies een getal e relatief priem ten opzichte van φ(n).
Bereken de inverse van e mod φ(n) volgens het algoritme van Euclides.
Vercijfer de code x volgens xemod n = y.
Ontcijfer de code y volgens ydmod n = x.
Blijkbaar geldt xedmod n = x
{e,n} heet de publieke sleutel en wordt aan ieder die het weten wil bekendgemaakt.
{b,n} heet de privé sleutel en blijft een goed bewaard geheim.
De juistheid van de stelling wordt aangetoond voor 0<x<min{p,q} in de subpagina Euler en Fermat. De kracht van het algoritme is, dat Alice eenvoudig φ(n) kan berekenen volgens φ(n)=(p-1)(q-1). Voor Eve is het niet mogelijk om de inverse d te vinden zonder dat ze weet wat p en q zijn. De enige manier om daar toch achter te komen is door n te ontbinden in factoren. Hoe groter de priemgetallen, hoe moeilijker dat wordt en bij de genoemde waarden van p en q is dat zelfs onmogelijk. Het probleem waarvoor Eve zich gesteld ziet, heet het factorisatieprobleem.
Alice kan tonen dat het bericht echt van haar afkomstig is door het begin van het bericht te coderen met haar eigen Privé sleutel. Bob kan met de Publieke sleutel van Alice het berichtje ontcijferen en daaraan zien dat het bericht echt van Alice komt. Daarmee is het Man in the Middle probleem ook opgelost.
Het arrangement 14. Les 14 Rivest, Shamir en Adleman is gemaakt met
Wikiwijs van
Kennisnet. Wikiwijs is hét onderwijsplatform waar je leermiddelen zoekt,
maakt en deelt.
Auteur
Bètapartners
Je moet eerst inloggen om feedback aan de auteur te kunnen geven.
Laatst gewijzigd
2014-12-18 14:15:03
Licentie
Dit lesmateriaal is gepubliceerd onder de Creative Commons Naamsvermelding-GelijkDelen 3.0 Nederland licentie. Dit houdt in dat je onder de voorwaarde van naamsvermelding en publicatie onder dezelfde licentie vrij bent om:
het werk te delen - te kopiëren, te verspreiden en door te geven via elk medium of bestandsformaat
het werk te bewerken - te remixen, te veranderen en afgeleide werken te maken
voor alle doeleinden, inclusief commerciële doeleinden.
Dit materiaal is achtereenvolgens ontwikkeld en getest in een SURF-project (2008-2011: e-klassen als voertuig voor aansluiting VO-HO) en een IIO-project (2011-2015: e-klassen&PAL-student). In het SURF project zijn in samenwerking met vakdocenten van VO-scholen, universiteiten en hogescholen e-modules ontwikkeld voor Informatica, Wiskunde D en NLT. In het IIO-project (Innovatie Impuls Onderwijs) zijn in zo’n samenwerking modules ontwikkeld voor de vakken Biologie, Natuurkunde en Scheikunde (bovenbouw havo/vwo). Meer dan 40 scholen waren bij deze ontwikkeling betrokken.
Organisatie en begeleiding van uitvoering en ontwikkeling is gecoördineerd vanuit Bètapartners/Its Academy, een samenwerkingsverband tussen scholen en vervolgopleidingen. Zie ook www.itsacademy.nl
De auteurs hebben bij de ontwikkeling van de module gebruik gemaakt van materiaal van derden en daarvoor toestemming verkregen. Bij het achterhalen en voldoen van de rechten op teksten, illustraties, en andere gegevens is de grootst mogelijke zorgvuldigheid betracht. Mochten er desondanks personen of instanties zijn die rechten menen te kunnen doen gelden op tekstgedeeltes, illustraties, enz. van een module, dan worden zij verzocht zich in verbinding te stellen met de programmamanager van de Its Academy (zie website).
Gebruiksvoorwaarden: creative commons cc-by sa 3.0
Handleidingen, toetsen en achtergrondmateriaal zijn voor docenten verkrijgbaar via de bètasteunpunten.
Aanvullende informatie over dit lesmateriaal
Van dit lesmateriaal is de volgende aanvullende informatie beschikbaar:
Toelichting
Deze les maakt onderdeel uit van de e-klas 'Cryptografie' voor Havo 5 voor het vak wiskunde D.
Leerniveau
HAVO 5;
Leerinhoud en doelen
Wiskunde D;
Inzicht en handelen;
Eindgebruiker
leerling/student
Moeilijkheidsgraad
gemiddeld
Trefwoorden
e-klassen rearrangeerbaar
14. Les 14 Rivest, Shamir en Adleman
nl
Bètapartners
2014-12-18 14:15:03
Deze les maakt onderdeel uit van de e-klas 'Cryptografie' voor Havo 5 voor het vak wiskunde D.
Leonhard Euler (1707-1783) wordt beschouwd als de belangrijkste wiskundige van de achttiende eeuw en is de wiskundige die het meest gepubliceerd heeft. Zijn verzameld werk beslaat zo'n zeventig delen. Euler heeft onder andere de symbolen e, i, 
en de goniometrische functies sinus, cosinus en tangens geïntroduceerd.
Beroemd is zijn vergelijking waarin de bijzondere getallen 0, 1, e, i en 
