De Rabobank bijv. versleutelt het berichtenverkeer tussen jou en de bank. Aan de éne kant wordt geëncrypt en aan de andere kant wordt gedecrypt en andersom. Dat wordt gedaan met dezelfde sleutel (symmetrische cryptografie). Deze sleutel (een getal of een in cijfers omgezette tekst) moet aan beide kanten bekend zijn, maar voor derden een geheim. Daarvoor gebruikt de bank RSA.
Het gaat zo: De bank is in bezit van een public key (e,n) en een private key (d,n), die geheim is. Op jouw
apparaat wordt min of meer at random een getal (g) gegenereerd. Met de public
key wordt g geëncrypt: ge mod
n = c. Het versleutelde resultaat (c) gaat over de lijn naar de bank. De
bank vervolgens maakt van de bijbehorende private key gebruik om g te
berekenen: cd mod n = g.
Aan beide kanten bezitten ze nu de sleutel (g) om berichten te versleutelen
resp. te ontsleutelen. De verbinding is nu veilig.
Een voorbeeld met n= 33, e=3, d=7 en g=2 (n wordt de modulus
genoemd en mod staat voor modulo rekenen oftewel klok-rekenen of restbepaling).
23
mod 33 = 8 (omdat 8 = 0 * 33 + 8, zoals 14 uur 2 uur is, omdat 14=1*12 +2)
87
mod 33 = 2 (omdat 2.097.152= 63.550* 33 + 2)
Het eerste plaatje hieronder verbeeldt deze processen.
De getallen n en e zijn in principe publiek. Onderschept
iemand c en wil hij g vinden dan moet dit probleem worden opgelost: xe mod n = c.
Bij een n van 200 cijfers en een groot getal voor e ziet
het vlak met punten in het tweede plaatje verderop er heel anders uit. Het is
totale chaos en er zit niet anders
op dan de getallen tussen 1 en n-1 uit te proberen.
Wat mij interesseert is: had ik dit allemaal zelf kunnen
bedenken?
Het probleem dat voorligt is: vind de functies F en H,
zodat F(g)=c en H(c)=g. Waaruit volgt: H(F(g))=g en g1#g2
è
F(g1)#F(g2). F is publiek, want je moet weten hoe c te
berekenen. Ondanks het bekend zijn van F moet g niet dan met grote moeite zijn
af te leiden uit c (mocht dit getal onverhoopt van de lijn zijn afgetapt).
Kwadrateren is de inverse van worteltrekken. Hiervoor
geldt inderdaad: H(F(g))=g. Staat F voor kwadrateren en c=16 dan weet je meteen
dat g=4. Dus de functies voldoen toch niet.
Er wordt iets vooruit gezet en teruggedraaid of
doorgedraaid en het aantal getallen is eindig. Zouden we dan niet aan de
cijferplaat van een klok denken?
Laten we van F(g) maken: ge mod n = c, met g als variabele. Per definitie is dit
ook te schrijven als: ge = k1*n + c of c=ge –
k1*n. En laten we van H(c)
maken: cd mod n = g.
Vullen we c hierin dan krijgen we: (ge – k1*n)d
mod n = g.
(ge – k1*n)d mod n = (ge*d
– k2 * n) mod n = ge*d mod n – (k2 * n) mod n
= ge*d mod n = g.
Het is nu de taak de
juiste combinatie van n, e , d te vinden. Merk op, dat de laatste
formule voor alle g’s geldt.
Wat betreft n.
Het getal wordt zomaar cadeau gedaan. Je zou n als product van twee
priemgetallen kunnen aanbieden: n =p*q. Zo’n product is notoir moeilijk te
ontleden. De opdracht is nu de juiste combinatie van d, e, p en q te vinden.
Wat betreft g.
Is g één van de priemgetallen of een veelvoud daarvan dan komen we in de
problemen. Stel g=k1*p (met k1= 1, 2 etc.). (k1*p)e
mod p*q =c oftewel (k1*p)e = k2*p*q + c.
Deel beide kanten door p: k1e*pe
-1 = k2*q + c/p. Voor c moet
dan gelden dat c = p of een veelvoud van p. Dat is een inperking van
mogelijkheden en je wilt nu juist zoveel mogelijk chaos. Dus we kiezen een g,
die geen priemgetal laat zien bij ontleden (factoriseren).
We gaan terug naar formule ge*d mod n = g è ge*d = k1*p*q
+ g. Links en rechts delen door g geeft: ge*d-1 = k*p*q + 1 ofwel g(e*d-1) mod p*q =1.
Wat betreft groep G.
Het getal g ligt tussen 0 en p*q en g is p noch q noch een veelvoud daarvan. In
ons voorbeeld: G={1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32}.
Stelling: Als g1€G en g2€G è
(g1*g2) mod p*q € G.
Bewijs uit het ongerijmde: g1*g2 =
k*p*q + c. Is c geen element van G dan is deze te herschrijven als bijv. c=ç*p.
è (g1*g2)/p
= k*q + ç. Rechts van = staat opgeteld een geheel getal en links een
breuk, want niet deelbaar door p. Dat kan niet, dus c€ G. Q.E.D.
Hoeveel elementen bevat deze gesloten multiplicatieve groep?
Het is aantal is p*q -1 – (q-1) – (p-1)= p*q –q –p +1= (p-1)*(q-1). In ons
voorbeeld met p=3 en q=11 is het aantal 20.
Stelling: gk*(p-1)*(q-1)mod
p*q=1 (dit deel heb ik niet zelf bedacht).
Eerst een tussenstelling: Als g, g1, g2 € G dan:
g1#g2 èg*g1
mod p*q # g*g2 mod p*q.
Bewijs uit het
ongerijmde: Stel g*g1 mod p*q = g*g2 mod p*q è g*g1 – k1*p*q
= g*g2 – k2*p*q è
g*(g1 - g2) = k3*p*q è
g*((g1 - g2)/(p*q)) = k3è (g1 - g2)
= k*p*q, want een breuk kan niet en g niet deelbaar door p*q.
Het verschil kan
hoogstens q*p -1 -1 èk=0
en g1 = g2. Q.E.D.
Hier staat dat g*g1
mod p*q bijv. g5 oplevert en dat dus g*g2 mod p*q dat
niet zal doen.
Bewijs:
(g*g1 * g*g2 * g*g3 *
……. g*g(p-1)(q-1)) mod p*q =
( ( (g*g1) mod p*q) * ((g*g2) mod p*q) * ……. ((g*g(p-1)(q-1)) mod p*q) ) mod
p*q=
( g5 * g2 *….. g(p-1)(q-1)*
…….g7) mod p*qè
(g*g1 * g*g2 * g*g3 *
……. g*g(p-1)(q-1)) – k1*p*q=( g5 * g2
*….. g(p-1)(q-1)* …….g7) –k2*p*q.
g(p-1)*(q-1)*(g1*g2*g3*
……. g(p-1)(q-1)) – k1*p*q=( g5* g2
*….. g(p-1)(q-1)* …….g7) –k2*p*q.
(g(p-1)*(q-1) – 1) *(g1*g2*g3*
……. g(p-1)(q-1))= k3*p*q.
Dit klopt alleen als (g(p-1)*(q-1) – 1)/p*q =
k è
g(p-1)*(q-1)=k*p*q +1 oftewel: g(p-1)*(q-1)mod p*q=1.
Je kunt dit (g*g1 * g*g2 * g*g3
* ……. g*g(p-1)(q-1)) k keer herhalen.
Uiteindelijk hebben we dus gk*(p-1)*(q-1)mod p*q=1.
We hebben nu g(e*d-1) mod p*q =1 en gk*(p-1)*(q-1)mod
p*q=1 è
e*d-1= k*(p-1)*(q-1)è
e*d mod
(p-1)*(q-1)=1.
De opdracht is nu gegeven een p en q de juiste e en d te
vinden (hier is ook een algoritme voor).
Gaan we terug naar ons voorbeeld e*d mod 20= 1. Oplossingen
zijn (3,7) en (9,9). Aan dat laatste heb je natuurlijk niets. (3,27) is geen
oplossing, omdat g27 mod 33 =(g20 * g7) mod 33
= ((g20mod 33) * (g7 mod 33)) mod 33= g7 mod
33. Er geldt immers g20mod 33=1. Dus 27 wordt gewoon gereduceerd tot
7.
Voor e en d geldt, dat ze (dus) inliggen tussen 1 en
(p-1)*(q-1) en dat ze geen andere deler gemeen hebben met (p-1)*(q-1) dan 1.
Dat laatste is nog te bewijzen.
Ik laat eerst zien, waarom e geen deler kan zijn van
(p-1)*(q-1).
x 2x
2x mod33
0 1 1
1 2 2
2 4 4
3 8 8
4
16 16
5 32 32
6 64 31
7 128
29
8 256 25
9 512 17
10
1024 1
11
20 1
Vanaf x=10 herhaalt zich het treintje:{1,2,4,8 …17}.
Je hebt de zekerheid dat g0 =1 en dat g(p-1)*(q-1)
mod p*q =1 (eerder bewezen). Tussen de beide uitersten past 1 trein of meerdere
treintjes van getallen. In ons voorbeeld in principe: 1, 2,4,5,10. Concreet
passen in ons geval twee treintjes. Maar het gezochte getal e kan dus nooit 10
zijn, want dan zou voor bijv. 4 moeten gelden: 410 mod 33 = 210*210
mod 33=1.
Er zou dan voor bepaalde getallen gelden: g1#g2 è
g1e mod (p*q) = g2e mod (p*q). En
dat is iets wat we niet willen. De facto zullen 2 en 4 altijd deel uitmaken van
G.
Een algemenere stelling: ggd (e, (p-1)*(q-1)=1.
Bewijs: Stel e en (p-1)*(q-1) hebben r als
gemeenschappelijke deler (zoals bij 6 en 20 2 gemeenschappelijk is).
e*d =
k*(p-1)*(q-1) + 1 è (e/r)*d =
k* ((p-1)*(q-1))/r + 1/r.
Links staat een geheel getal en ((p-1)*(q-1))/r is een
geheel getal en dus blijft een breuk over. Dus krijg je nooit een oplossing
voor d. Q.E.D.
Voor de volledigheid controleren we nog: g1#g2 èg1e
mod (p*q) #g2e mod (p*q).
Ditmaal geen bewijs uit het ongerijmde.
g1e
mod (p*q)=c1. Deze c1 invullen in c1d
mod (p*q) è
(g1e
– k1*p*q)d mod (p*q)= g1e*d mod
(p*q) = (g1*g1(e*d -1)) mod (p*q) =
(g1 mod
(p*q))*(g1(e*d -1)) mod (p*q)) mod (p*q) = g1 mod (p*q) = g1.
Dus g1 è c1
en c1 è g1
en niet bijv. g5. Tussen de groepen G en C (zelfde als G) is een
bijectieve relatie, dus het klopt inderdaad. In plaatje 2 heeft dan ook elk
punt een andere hoogte.
De profundis
