R.S.A.
(#rsa4newbies)
(v1.2) par Lucifer48 [Immortal Descendants]
(5 Février 2000)
Principe du RSA
RSA en 8 lignes
Un peu de pratique
Conclusion
PGCD(a,b) = PGCD(b,a) = PGCD(b, a mod b) et PGCD(c,0) = c
On dit que a et b sont premiers entre eux si PGCD(a,b)=1. Il est aussi possible de trouver la notation:
a est premier avec b.
Remarque2: Les seuls éléments inversibles de Z/(p-1)(q-1)Z sont les éléments
premiers avec e. Lisez la suite pour mieux comprendre.
e est très important, car il sera utilisé lors du cryptage. Calculons maintenant la première
composante de la clef privée (notons la d).
d = inv(e) [(p-1)*(q-1)] <=> d = inv(e) dans Z/(p-1)(q-1)Z <=> e*d = 1 [(p-1)*(q-1)] <=> d = e^-1 mod ((p-1)*(q-1))
Ces quatre notations sont équivalentes.
Plus pratiquement, on peut utiliser le théorème de Bezout pour obtenir l'inverse de e:
e * U + ((p-1)*(q-1)) * V = PGCD(e,(p-1)*(q-1)) = 1 (U et V sont des entiers)
et donc,
U mod ((p-1)*(q-1)) = inv(e) = e^-1
Exemple: Utilisation (manuelle) du théorème de Bezout:
31 div 13 = 2 reste 5 13 div 05 = 2 reste 3 05 div 03 = 1 reste 1 02 div 01 = 2 reste 0 PGCD(31,13)= 1 ;31 et 13 sont premiers entre eux 1 = 3 - 2 1 = 3 - (5 - 3) 1 = 3*2 - 5 1 = 2*(13 - 5*2) - 5 1 = 2*13 - 4*5 - 5 1 = 2*13 - 5*5 1 = 2*13 -5*(31 - 13*2) 1 = 12*13 - 5*31 Et donc: inv(13)=12 (dans Z/31Z)
Il est ensuite facile d'obtenir d.
La clef publique est: (e,n).
La clef privée est: (d,n).
Encryption: Le message M a encrypter doit être un nombre appartenant à Z/nZ
(découper le texte converti en chiffre en petits blocs de longueur strictement inférieur au
nombre de décimale de n).
C = M^e [n]
Remarque: w appartient à Z/nZ si w < n.
Décryption: C'est tout aussi simple.
M = C^d [n]
Remarque: Le message aurait pu être crypté avec d et décrypté avec
e. En pratique, on utilise une clef publique (d) courte et une clef privée (e) longue, ce qui rend
le décryptage plus rapide que le cryptage.
Pourquoi ça marche? Courte démonstration. Les calculs suivants sont effectués dans
Z/nZ.
C^d = (M^e)^d = M^(ed) de plus, e*d = 1 [(p-1)*(q-1)] <=> ed - 1 = k*(p-1)*(q-1) k est dans N* par suite, M^(ed) = M^(k*(p-1)*(q-1) + 1) Posons u= k*(p-1)*(q-1) + 1 si M^u = M [p] et M^u = M [q] alors, M^u = M [p*q] et comme n=p*q, il s'ensuit que C^d = M
Remarque: On aurait pu aussi utiliser le théorème d'Euler (mais n'est pas valable tout le temps):
Si PGCD((p-1)*(q-1),M) = 1 alors M^((p-1)*(q-1)) = 1 et donc, M^(k*(p-1)*(q-1) + 1) = M.1^k = M = C^d (valable uniquement si (p-1)*(q-1) et M sont premiers entre eux)
n = p * q (p et q sont premiers) PGCD(e,(p-1)*(q-1)) = 1 d = e^-1 mod ((p-1)*(q-1)) (e,n): clef publique. (d,n): clef privée. p et q ne servent plus... M^e mod n = M_crypté (M < n) M_crypté^d mod n = M
in[1]:= PrimeQ[2000] out[1]= False in[2]:= { Prime[1], Prime[2], Prime[3], Prime[4], Prime[2000] } out[2]= { 2, 3, 5, 7, 17389 } in[3]:= PowerMod[157,-1,2668] out[3]= 17 in[4]:= Mod[1234^31,466883] out[4]= 446798 in[5]:= FactorInteger[519920418755535776857] //Timing out[5]= {13.35 Second, {{22801763489, 1}, {22801763513, 1}}} in[6]:= Needs["NumberTheory`FactorIntegerECM`"] in[7]:= $Packages out[7]= {NumberTheory`FactorIntegerECM`, Global`, System`} in[8]:= FactorIntegerECM[519920418755535776857] //Timing out[8]= {3.07 Second, 22801763513} in[9]:= breakRSA[x_]:= Module[{i}, i=FactorIntegerECM[x]; List[i, x/i] ] in[10]:= breakRSA[519920418755535776857] //Timing out[10]= {3.07 Second, {22801763513, 22801763489}} in[11]:= GCD[31,13] out[11]= 1 in[12]:= ExtendedGCD[31,13] out[11]= {1, {-5, 12}}
Remarque (importante): Pour les calculs du genre: a^b [n] (b positif), ne surtout pas utiliser
la fonction Mod[a^b, n] mais PowerMod[a,b,n] qui est carrément plus rapide.
Quelques exemples:
p = 113 ; q = 541 ; n = p * q = 61133 ; (p-1)*(q-1) = 60480. Je choisis e = 121 (GCD[121,60480]=1) inv(e) = 57481 (inférieur à (p-1)*(q-1)) donc d = 57481. Pour crypter M=1234567890, je dois donc découper M en petits morceaux de longueur inférieur à n (4 est ici le maximum): M1=1234, M2=5678, M3=90. C1 = M1^e [n] = 1234^121 [61133] = 40691 C2 = M2^e [n] = 5678^121 [61133] = 19203 C3 = M3^e [n] = 90^121 [61133] = 32121 C = 406911920332121 Pour décrypter, je découpe le message (crypté) en morceaux de longueur n (ici 5). M1 = C1^d [n] = 40691^57481 [61133] = 1234 M2 = C2^d [n] = 19203^57481 [61133] = 5678 M3 = C3^d [n] = 32121^57481 [61133] = 90 M = 1234567890
p = 3571 ; q = 7919 ; n = p * q = 28278749 ; (p-1)*(q-1) = 28267260. Je choisis e = 213889 (GCD[213889,28267260]=1) inv(e) = 2241409 (inférieur à (p-1)*(q-1)) donc d = 2241409. M ="Hello world" = 7210110810811132119111114108100, je découpe en morceaux de longueur 7: M1 = 7210110, M2 = 8108111, M3 = 3211911, M4 = 1114108, M5 = 100. C1 = M1^e [n] = 7210110^213889 [28278749] = 12840449 C2 = M2^e [n] = 8108111^213889 [28278749] = 16339096 C3 = M3^e [n] = 3211911^213889 [28278749] = 25181491 C4 = M4^e [n] = 1114108^213889 [28278749] = 24666021 C5 = M5^e [n] = 100^213889 [28278949] = 17846443 C = 1284044916339096251814912466602117846443 On découpe le C en morceaux de 8 chiffres. M1 = C1^d [n] = 12840449^2241409 [28278749] = 7210110 M2 = C2^d [n] = 16339096^2241409 [28278749] = 8108111 M3 = C3^d [n] = 25181491^2241409 [28278749] = 3211911 M4 = C4^d [n] = 24666021^2241409 [28278749] = 1114108 M5 = C5^d [n] = 17846443^2241409 [28278749] = 100 M = 7210110810811132119111114108100
p = 10007 ; q = 53239 ; n = p * q = 532762673 ; (p-1)*(q-1) = 532699428. Je choisis e = 17 (GCD[17,532699428]=1) inv(e) = 62670521 (inférieur à (p-1)*(q-1)) donc d = 62670521. M = 123 C = M^e [n] = 123^17 [532762673] = 270099428 M = C^d [n] = 270099428^62670521 [532762673] = 123
in[1]:= solveRSA[n_, e_]:= Module[{j}, j=breakRSA[n]; PowerMod[e, -1, (First[j]-1)*(Last[j]-1)]] in[2]:= solveRSA[532762673, 17] out[2]= Out[12]= 62670521