Scholieren.com forum

FF een stukje geplakt van een profielwerkstuk
http://www.betasteunpunt.rug.nl/jan_...encryptie.html

Misschien heb je er wat aan:

Publieke sleutels
Whitfield Diffie en Martin Hellman zaten met een probleem. Ze wilden een manier verzinnen waarop het mogelijk was een bericht naar de ander te versturen, zonder dat ze van tevoren een sleutel hadden afgesproken. Want het probleem was natuurlijk, hoe spreek je zo’n sleutel af, via de telefoon kan het afgeluisterd worden, en via de post kan het onderschept worden. De enige veilige manier was het persoonlijk te vertellen, maar dan was de zin van het bericht opsturen ook weg.
Toen bedachten ze dit: Als je nou het bericht in een metalen koffertje doet met een slot erop (waarvan jij de sleutel hebt). Die stuur je op naar de ontvanger. De ontvanger kan het koffertje niet openen, want heeft de sleutel niet. Wat hij doet is zijn eigen slot er op zetten (waar hij het sleuteltje van heeft). Dit pakketje met die twee sloten stuurt hij weer terug naar jou. Jij haalt je eigen slot er af, en stuurt het terug naar hem. Hij haalt zijn slot er af, en hij kan er bij!
Wat een vondst, zul je op het eerste gezicht denken. Maar helaas valt dat een beetje tegen. Want in de wiskunde is het zo, wat er als laatst op gaat, moet er als eerst af. Kijk maar:
Sleutel van persoon 1:
abcdefghijklmnopqrstuvwxyz
HFSUGTAKVDEOYJBPNXWCQRIMZL

Sleutel persoon 2:
abcdefghijklmnopqrstuvwxyz
CPMGATNOJEFWIQBURYHXSDZKLV

Bericht morgen twaalf uur
Vercijferd met sleutel 1: YBXAGJ CIHHOT QQX
Vercijferd met sleutel 2: LPKCNE MJOOBX RRK
Ontcijferd met sleutel 1: zphtqk xnllor vvh
Ontcijferd met sleutel 2: wbsfnx tgyyhq zzs (hier had dus morgen twaalf uur moeten staan)

Zoals je ziet, werkt dit niet. We hebben hier namelijk niet te maken met een standaard rekensommetje. Het blijkt dus dat we hier niet te maken hebben met een tweewegsfunctie. Bij een tweewegsfunctie maakt het namelijk niet uit in welke volgorde je de vercijfering ongedaan maakt. Een voorbeeld is het vermenigvuldigen:
3 (sleutel 1) * 8 (te vercijferen ‘bericht’) = 24 (vercijfering 1)
2 (sleutel 2) * 24 (vercijfering 1) = 48 (vercijfering 2)
48 / 3 (sleutel 1) = 16 (ontcijfering stap 1)
16 / 2 (sleutel 2) = 8 (= te vercijferen bericht)
de laatste twee stappen kun je ook andersom doen, het maakt niet uit:
48 / 2 (sleutel 2) = 24 (ontcijfering stap 1)
24 / 3 (sleutel 1) = 8 (= te vercijferen bericht)

Conclusie, een vermenigvuldiging kun je wel omkeren. En de volgorde waarop maakt niet uit. Maar wat kun je dan niet omkeren? Een modulaire functie kun je niet omkeren.
Modulair rekenen leerde je eigenlijk al op de basisschool. Je moest delen, en soms hield je wat over. Dat noemde je dan ‘rest’. Die rest is eigenlijk de uitkomst van zo’n modulaire berekening. Modulair rekenen doen we met de % operator (soms wordt ook MOD gebruikt)
7 / 3 = 2 rest 1
7 % 3 = 1
Stel nu weet je die 3 en die 1. Het is nu onmogelijk te achterhalen wat dat andere cijfer is. Namelijk
7 % 3 = 1
maar ook
16 % 3 = 1
en zo zijn er nog veel meer mogelijkheden.

Na twee jaar lang proberen vond Hellman een oplossing voor dit probleem. Persoon 1 en persoon 2 spreken twee getallen af: Y en P. P is een priemgetal (alleen zonder rest deelbaar door zichzelf en 1, voorbeeld 3 en 11) en Y moest kleiner zijn dan P. Beide waarden zijn niet geheim. Dus persoon 1 belt persoon 2 op en ze spreken af Y = 7 en P = 11).
1. Nu kiest persoon 1 een willekeurig getal, bijvoorbeeld 3 en houdt dat geheim. We noemen dat getal A.
Persoon 2 kiest ook een willekeurig getal, bijvoorbeeld 6 en houdt dat geheim, we noemen het getal B.
2. Persoon 1 rekent het volgende uit: Y^A % P = hier 7^3 % 11 = 2 we noemen dit a. En persoon 1 verstuurt dit getal naar persoon 2.
Persoon 2 doet precies hetzelfde: Y^B % P = 7^6 % 11 = 4 noemen we b. Persoon 2 stuurt deze uitkomst naar persoon 1.
3. Persoon 1 berekent b(getal persoon 2)^A % 11 = 4^3 % 11 = 9
Persoon 2 berekent a(getal persoon 1)^B % 11 = 2^6 % 11 = 9

Beide personen hebben nu hetzelfde getal in handen: de sleutel. Een een of andere afluisteraar kan deze waarde niet achterhalen. Stel hij/zij vangt alle waarden op die afgesproken en verteld zijn via de telefoon, dan nog weet die persoon niet welke waarde hij/zij in stap 2 moet nemen voor A of B.

Later gingen Ronal Rivest, Adi Shamir en Leonard Adleman hierop door. En ontwikkelde het RSA Algoritme. Waar het op neer komt is dit:
Persoon 1 kiest p en q allebei priemgetallen. Bijvoorbeeld p = 17.159 en q = 10.247 als je deze twee met elkaar vermenigvuldigt dan krijg je de publieke sleutel van deze persoon N. N=175.828.273 Bedenk hierbij dat niemand kan achterhalen uit welke twee getallen deze publieke sleutel is ontstaan.
Dit bericht werd gecodeerd met behulp van de eenwegfunctie die Rivest ontworpen heeft.
Rivest ontwierp een eenwegfunctie zodat het mogelijk was om, als je de waarden van p en q weet, het bericht te decoderen. Het RSA algoritme was geboren.
Ook deze code is te breken. Je zou namelijk alle mogelijkheden van p en q kunnen nagaan en kijken of je uit de cijfertekst weer zinnige tekst kunt maken. Om een beeld te geven van hoe lang dit duurt. Er is ooit een wedstrijd uitgeschreven in de Scientific American, waar een publieke sleutel en een cijfertekst werd afgedrukt. De publieke sleutel:
114.381.625.757.888.867.669.235.779.976.146.612.010.218.296.721.242.36 2.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
Het duurde 17 jaar voor dit getal in factoren werd ontbonden, door een groep van 600 vrijwilligers, die als de computers op hun werk en thuis niks te doen hadden, hieraan aan het rekenen waren. Het is technisch uitvoerbaar om een bericht te vercijferen met een voldoende grote waarde van N (publieke sleutel), zodat alle computers op de planeet het cijferschrift niet zouden kunnen breken binnen de leeftijd van het universum. Op internet vond ik dit: ‘RSA in 2 lines of perl’. Perl is een taal die vooral erg populair is voor UNIX, maar ook steeds meer op komt in de Windows wereld. Er wordt gebruikgemaakt van reguliere expressies, en dat is ook ongeveer zover als een gemiddeld persoon zal komen, want verder is er vrij weinig van te volgen.