Hoe krijgen we met RSA de verbinding veilig?

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: g^e 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: c^d 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).

 

   2³ mod 33 = 8 (omdat 8 = 0 * 33 + 8, zoals 14 uur 2 uur is, omdat 14=1*12 +2)

   8⁷ 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: x^e 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 g₁#g₂ è F(g₁)#F(g₂). 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: g^e mod n = c, met g als variabele. Per definitie is dit ook te schrijven als: g^e = k₁*n + c of c=g^e – k₁*n.  En laten we van H(c) maken: c^d mod n = g. Vullen we c hierin dan krijgen we: (g^e – k₁*n)^d mod n = g.

(g^e – k₁*n)^d mod n = (g^e*d – k₂ * n) mod n = g^e*d mod n – (k₂ * n) mod n = g^e*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=k₁*p (met k₁= 1, 2 etc.). (k₁*p)^e mod p*q =c oftewel (k₁*p)^e = k₂*p*q + c.

Deel beide kanten door p: k₁^e*p^{e -1} = k₂*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 g^e*d mod n = g è g^e*d = k₁*p*q + g. Links en rechts delen door g geeft: g^e*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 g₁€G en g₂€G è (g₁*g₂) mod p*q € G.

Bewijs uit het ongerijmde: g₁*g₂ = k*p*q + c. Is c geen element van G dan is deze te herschrijven als bijv. c=ç*p.

è  (g₁*g₂₎/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: g^{k*(p-1)*(q-1)}mod p*q=1 (dit deel heb ik niet zelf bedacht).

Eerst een tussenstelling: Als g, g₁, g₂ € G dan: g₁#g₂ èg*g₁ mod p*q # g*g₂ mod p*q.

Bewijs uit het ongerijmde: Stel g*g₁ mod p*q = g*g₂ mod p*q è g*g₁ – k₁*p*q = g*g₂ – k₂*p*q è g*(g₁ - g₂) = k₃*p*q è g*((g₁ - g₂)/(p*q)) = k₃è (g₁ - g₂) = 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 g₁ = g₂. Q.E.D.

Hier staat dat g*g₁ mod p*q bijv. g₅ oplevert en dat dus g*g₂ mod p*q dat niet zal doen.

 

Bewijs:

(g*g₁ * g*g₂ * g*g₃ * ……. g*g_(p-1)(q-1)) mod p*q =

( ( (g*g₁) mod p*q)   * ((g*g₂) mod p*q) *  ……. ((g*g_(p-1)(q-1)) mod p*q) ) mod p*q=

( g₅ * g₂ *….. g_(p-1)(q-1)* …….g₇) mod p*qè

(g*g₁ * g*g₂ * g*g₃ * ……. g*g_(p-1)(q-1)) – k₁*p*q=( g₅ * g₂ *….. g_(p-1)(q-1)* …….g₇) –k₂*p*q.

g^(p-1)*(q-1)*(g₁*g₂*g₃* ……. g_(p-1)(q-1)) – k₁*p*q=( g₅* g₂ *….. g_(p-1)(q-1)* …….g₇) –k₂*p*q.

(g^(p-1)*(q-1) – 1) *(g₁*g₂*g₃* ……. g_(p-1)(q-1))= k₃*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*g₁ * g*g₂ * g*g₃ * ……. g*g_(p-1)(q-1)) k keer herhalen.

Uiteindelijk hebben we dus g^{k*(p-1)*(q-1)}mod p*q=1.

 

 

We hebben nu g^(e*d-1) mod p*q =1 en g^{k*(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 g²⁷ mod 33 =(g²⁰ * g⁷) mod 33 = ((g²⁰mod 33) * (g⁷ mod 33)) mod 33= g⁷ mod 33. Er geldt immers g²⁰mod 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           2^x           2^x 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 g⁰ =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: 4¹⁰ mod 33 = 2¹⁰*2¹⁰ mod 33=1.

Er zou dan voor bepaalde getallen gelden: g₁#g₂ è g₁^e mod (p*q) = g₂^e 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: g₁#g₂ èg₁^e mod (p*q) #g₂^e mod (p*q).

 

Ditmaal geen bewijs uit het ongerijmde.

g₁^e mod (p*q)=c₁. Deze c₁ invullen in c₁^d mod (p*q) è

(g₁^e – k₁*p*q)^d mod (p*q)= g₁^e*d mod (p*q) = (g₁*g₁^{(e*d -1)}) mod (p*q) =

(g₁ mod (p*q))*(g₁^{(e*d -1)}) mod (p*q)) mod (p*q) = g₁ mod (p*q) = g₁.

 

Dus g₁ è c₁ en c₁ è g₁ en niet bijv. g₅. 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

 rkh, 08-12-2021