R.S.A.
(#rsa4newbies)

(v1.0) par Lucifer48 [Immortal Descendants]
(30 Septembre 1999)

Ron Rivest, Adi Shamir et Leonard Adleman ont inventé ce système en 1978. Il est basé sur la difficulté de factoriser un nombre qui est le produit de deux nombres premiers.

Sommaire:
Principe du RSA
RSA en 8 lignes
Un peu de partique
Conclusion

Principe du RSA

Soient p et q, deux nombres premiers. Posons: n = p * q

Remarque: Il est conseillé de choisir des grands nombres premiers. En effet, il est facile de retrouver p et q lorque n est petit...

n est la seconde partie de la clef (publique et privée). On doit maintenant trouver un nombre e, tel que e et (p-1)*(q-1) soient premiers entre eux.

Remarque: Le PGCD (GCD en anglais) désigne le Plus Petit Commun Multiple. Pour trouver le pgcd de deux entiers positifs, on utilise l'algorithme d'Euclide. Ansi:
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

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.

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)

RSA en 8 lignes

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

Un peu de partique

Pour tous les calculs, j'ai utilisé le logiciel Mathematica. Petit aperçu: 
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}}

Quelques exemples:

Conclusion

Le RSA n'est donc pas un système parfait, sa lenteur en est son principal défaut. Le choix de e et d ne doit pas se faire au hasard. Cependant, il est d'une étonnante simplicité.

Je voudrais juste terminer en disant que j'ai essayé d'expliquer les choses le plus simplement possible, en gardant un minimun de rigueur dans l'écriture; j'espère que les matheux n'auront pas trop les cheveux qui se hérisseront sur la tête en lisant ceci ;) toutefois, s'il y avait une erreur ou quelques imprécisions, merci de bien vouloir m'écrire (je vous accorde que ma démonstration est un peu incomplète...) ; je serais ravi d'améliorer ce tutorial :)

Greetings: All ID members (Volatility, Torn@do, alpine, ...), SiFLyiNG, Eternal Bliss, ACiD BuRN, Duelist, LaZaRuS, ... and wonderful people in #cracking4newbies & #win32asm (WazerPup, X-Calibre, MisterE, ...).


(c) Lucifer48. All rights reserved & reversed