RSA en de getaltheorie

13 uur is 1 uur en 23 uur is 11 uur. 1 en 11 zijn de respectievelijke resten bij deling door 12. Notatie: 13 mod 12=1 of 13≈1 (mod 12), omdat 13 = 1*12 + 1. Dus ook geldt: 37≈1 en 13≈37 (mod 12). Het oneindige wordt a.h.w. afgebeeld op het eindige.

Algemeen: g₁≈g₂ (mod n) als –gegeven g₁, g₂, n en c- er getallen k₁ en k₂ te vinden zijn, zodat g₁=k₁*n + c en g₂=k₂*n + c, waarbij g₁, g₂, k₁, k₂, n en c gehele getallen zijn met n>0 en 0 ≤c˂ n.

Bij de RSA-cryptografie wordt een getal g geëncrypt en dat levert getal c op. De formule is: c≈g^e (mod n). e en n vormen te samen de public key en n is het product van twee zeer grote priemgetallen. Het product bestaat uit meer dan 200 cijfers.

De inverse is: g≈c^d (mod n). Waarbij d en n te samen de private key vormen.

Te bewijzen is: c^d≈(g^e)^d≈g (mod n).

Het getal g uit G={1,2,3,4,6,8,9,11 …. 29,31,32,33,34} heeft als kenmerken: 0˂g˂35 en niet zijnde het priemgetal 5 of 7 of een veelvoud daarvan. De verzameling van getallen is een gesloten multiplicatieve groep:

Als g₁, g₂ ꜫ G dan ook (g_1*g₂)mod 35ꜫG. (ꜫ uitspreken als “element van”).

Er is een eenheidselement nl. 1 met g*1= g.

Als g₁ꜫ G dan is er een inverse g₂ꜫ G met (g_1*g₂)mod 35=1.

(Zo is de inverse van 11 16, omdat (11*16) mod 35=1. Dus niet 1/11, want breuken kennen we in Modulo-rekenen niet.)

(g_1*g₂)mod 35=(g_2*g₁)mod 35, wat G tot Abelse groep maakt.

De groep G bestaat uit 24 getallen, omdat (5-1)*(7-1)=24. Algemeen: φ(n)=(p-1)*(q-1). Waarbij n het product is van de priemgetallen p en q, dus φ(35)=24.

not (g₁ ≈ g₂) => not (g₁*g ≈ g₂*g), omdat (g₁*g ≈ g₂*g)=> (g₁ ≈ g₂).

Dus vermenigvuldig je bijv. de getallen 4 en 29 met 3 dan verschillen ook de resultaten (4*3 mod 35=12 en 29*3 mod 35= 17). En 34 heeft weer een ander resultaat etc.

g^φ(n) ≈1 (mod n). Dus bijv. 11²⁴ ≈1 (mod 35).

De e van g^e mag geen deler –buiten 1- gemeen hebben met φ(n). De verhouding tussen de exponenten e & d is gedefinieerd als: (e*d)mod φ(n)= 1. Hierin zit de inversie.

Met deze stellingen en definities is te bewijzen: g = ^(e) => c = ^(d) => g. Maar het bewijs geldt alleen als g niet het priemgetal p of q is, noch een veelvoud daarvan. Maar dat is ook weer op te lossen. En bij zeer grote priemtallen nadert (p-1)*(q-1)/(p*q) 1, dus de kans dat je een “verkeerd” getal hebt is ongeveer 0.

Nu is natuurlijk hier niets bewezen en weinig toegelicht. Wat ik heb willen laten zien, is hoe dit soort cryptografie geworteld is in de wiskunde i.c. getaltheorie.

De profundis.

rkh, 14-07-2019