Cryptographie : le code RSA

[précédent]-[imprimer]-

menu avec frames sans frame curiosités jeux collège lycée galerie lien p.amigo mail

Cette page présente un dossier sur le code RSA, une méthode de cryptographie moderne très performante inventée par les mathématiciens Rivest, Shamir et Adleman en 1977 au MIT, qui est basée sur le principe des clés publiques et clés privées ...

Définitions :

Il était une fois, il y a très longtemps ...

1900 avant J.-C. : un scribe égyptien utilise un alphabet non usuel (il utilise des symboles).

500 avant J.-C. : les scribes hébreux cryptent par renversement de l'alphabet (A --> Z, B --> Y,…), c'est l'atbash.

50 avant J -C : Jules César lui-même donne naissance à une méthode de chiffrement (qui porte son nom) pour les communications du gouvernement romain :

Méthode de César : il faut décaler toutes les lettres de 3 lettres vers la droite (en revenant au début de l'alphabet si besoin) pour crypter (fonction de chiffrement affine : x --> x+3).
Sa fiabilité à l'époque était totale car personne ne connaissait le ''truc'', aujourd'hui ce type de code, qui conserve la fréquence d'apparition des lettres, n'est plus fiable : on peut facilement le casser en repérant des lettres au départ (''_'' l'espace revient le plus souvent, puis, en français, le ''e'' …), on retrouve alors la fonction de chiffrement.

[haut de page]

Cryptage moderne avec RSA :

Nous n'allons aborder ici qu'un seul type : le code RSA inventé par les mathématiciens Rivest, Shamir et Adleman en 1977 au MIT, Massachusetts Institute of Technology.
C'est le principe des clés publiques et clés privées :
tout le monde peut m'envoyer un message crypté (la clé de chiffrement est publique donc tout le monde peut la connaître) mais je serais le seul à pouvoir le décrypter (la clé de déchiffrement est privée = secrète et "on ne peut pas" la retrouver à partir de la clé de chiffrement publique).

Principe du RSA :

Le message est codé, donc nous avons à faire à un message d'origine fait de nombres.
Le RSA utilise les congruences modulo n, c'est à dire les restes dans une division euclidienne par n.
En effet, pour certains n, il est possible de trouver deux entiers e et d tels que par deux calculs de puissance successifs on retombe sur le reste de départ (le premier calcul crypte, le deuxième redonne le nombre de départ donc décrypte).
Dans la pratique il est très difficile de retrouver le nombre d (de décryptage) même lorsqu'on connaît les nombres n et e.

Bilan :

soit x un nombre du message d'origine, y le nombre correspondant après cryptage.
nombre public : n
clé publique de cryptage : e
clé privée(secrète) de décryptage : d
Cryptage : y = le reste de la division euclidienne de x^e par n.
Décryptage : x = le reste de la division de y^d par n.
Autrement dit : x est le reste de la division de x^ed par n

Quelques éléments pour comprendre les dessous mathématiques de cette histoire :

Comment peut-on être sûr de l'existence des nombres n, e et d et comment peut-on les construire ?

Le petit théorème de Fermat (si p est un nombre premier alors 1 est le reste de la division de x^p-1 par p pour un x<n) nous permet de démontrer que :
si p et q sont deux nombres premiers alors x est le reste de la division de x ^{k (p-1)(q-1)+1} par pq=n

Il ne reste plus qu'à trouver deux nombres e et d tels que ed = k(p-1)(q-1)+1 (autrement dit ed - kn' = 1 où n'=(p-1)(q-1)), c'est le théorème de Bezout qui nous donne l'existence de e et de k si on fixe d premier avec n'=(p-1)(q-1) et c'est l'algorithme d'Euclide étendu qui permet de calculer effectivement ce nombre e (pour faire ce calcul on a besoin de connaître n'=(p-1)(q-1) ce qui est très difficile si on ne connait ni p ni q).

On a alors x ^{k (p-1)(q-1)+1} = x^ed ainsi x est le reste de la division de x^ed par pq=n.

En fin de document il y une démonstration plus précise (avec l'énoncé du théorème de Bezout et celui de l'algorithme d'Euclide) mais elle utilise la notion de congruence.

[haut de page]

Un exemple très simple (très loin de la pratique) :

1) Prenons un alphabet simple de trois lettres a,b et c.
Prenons pour codage de cet alphabet : a = 1, b = 2 et c = 3.

2) Il faut choisir deux nombres premiers secrets : p = 2 et q = 5 :

3) Le nombre public est alors : n = p*q = 2 * 5 = 10 (le nombre n est public mais il n'est pas actuellement possible de retrouver les deux entiers p et q lorsque n est très grand)
on a aussi besoin de : n' = (p-1)(q-1) = 1*4 = 4 (secret)

4) On choisit la clé privée (secrète) : d = 3
Critères de choix : d et n' doivent être premiers entre eux (pgcd (d; n') = 1) et d < n'.

5) Il faut maintenant trouver la clé publique : e
Critères de choix : e doit être positif et tel que - k n' + e d = 1 donc ici e est tel que : - k*4 + e*3 = 1
''Descente'' : Algorithme d'Euclide : 4 = 1*3 + 1
''Remontée'' : 4 - 1*3 = 1 or 1 = (4 - 3)
on remplace 4 - (4 - 3)*3 = 1
on développe 4 - 4*3 + 3*3 = 1
''Au final'' : -2*4 + 3*3 = 1
donc la clé publique e = 3
(en fait dans la pratique e n'est jamais égal à d)

6)

[haut de page]

Un exemple un peu plus proche de la pratique :

1) Prenons comme codage de notre alphabet le code ASCII étendu : codage des caractères du clavier (et autres symboles) par des nombres (entre 0 et 255) sur 1 octet = 8 bits, c'est le codage utilisé par nos ordinateurs pour conserver les informations sous forme numérique. Exemple A=65, B=66 ...

2) Il faut choisir les deux nombres premiers secrets : p = 11 et q = 23.

3) Le nombre public est alors : n = p*q = 11 * 23 = 253
on a aussi besoin de : n' = (p-1)(q-1) = 10*22 = 220 (secret)

4) On choisit la clé privée de décryptage (secrète) : d = 27
Critères de choix : d et n' doivent être premiers entre eux (pgcd (d; n') = 1) et 2 < d < n'.
Ici d=27=3³ or n'=220 n'est pas divisible par 3 donc pgcd (27;220) = 1.

5) Il faut maintenant trouver la clé publique de cryptage : e
Critères de choix : e doit être positif et tel que e d - k n' = 1 donc ici e est tel que : e*27 - k*220 = 1
C'est l'algorithme d'Euclide étendu qui permet de trouver e :

				résultat  e = 163
on "descend" grâce à l'algorithme d'Euclide			-57 = 163 - 220	1 = 163 * 27 - 20 * 220
n'=d q1 + R1	220 = 27 * 8 + 4	4 = 220 - 27 * 8	1 = -27 + (220 - 27 * 8) * 7	1 = - 57 * 27 +7 * 220
d=R1 q2 + R2	27 = 4 * 6 + 3	3 = 27 - 4 * 6	1 = 4 - (27 - 4 * 6) * 1	1 = -27 + 4 * 7
R1=R2 q3 + R3	4 = 3 * 1 + 1	1 = 4 - 3 * 1	1 = 4 - 3 * 1
R2=R3 q4 + R4	3 = 1 * 3 + 0	lire les lignes en "remontant" et chaque ligne de gauche à droite.

6) Cryptons maintenant le message très secret suivant : "salut"

Le message d'origine est : "salut", le message codé est 115097108117116 et le message crypté est 092080146167139.

^(*) La calculatrice de Windows en affichage scientifique est capable de faire les calculs modulaires de cet exemple (reste(97¹⁶³;253) par exemple) mais une calculatrice de collège en est incapable.

Pour les plus endurants on peut néanmoins se servir d'une calculatrice de collège mais avec quelques astuces : la calculatrice est dépassé par le calcul reste(115¹⁶³;253) mais ce calcul peut être décomposé en une série de calculs plus simples et dans les limites de la calculatrice :
On "décompose" d'abord 163 : 163 = 2 * 3 *3 *3 * 3 + 1
Ensuite la calculatrice peut faire ls calculs suivants :
reste(97²;253) = 48    (on tape 97² / 253 on trouve 37,18... on tape alors 97² - 253 * 37 et on trouve 48)
reste(48³;253) = 31
reste(31³;253) = 190
reste(190³;253) = 170
reste(170³;253) = 246 et enfin
reste(246*97;253) = 80
Pour le décryptage on décompose 27 : 27 = 3 * 3 * 3.

Dans la pratique :

Les deux nombres premiers secrets p et q sont si grands (ils dépassent les 100 chiffres) qu'il est quasi impossible de les retrouver connaissant le nombre public n et donc il est quasi impossible de retrouver la clé privée secrète d.

D'autre part RSA crypte en fait par blocs de caractères donc il ne conserve pas la fréquence d'apparition des lettres.
En fait on peut crypter tout nombre plus petit que n, si on avait eu n = 123456789123456789 on aurait alors pu crypter d'un seul bloc le nombre 115097108117116 < n qui était le message codé de l'exemple ci-dessus.

[haut de page]

Annexe : Preuves

La preuve suivante utilise les notions de congruences modulo n, de factoriel, de combinaison de k éléments parmi p notée C(k ; p) ...

Prouvons tout d'abord le petit théorème de Fermat : si p est premier alors pour tout 1< x < p on a x^{p - 1} = 1 [p] :

Preuve du petit théorème de Fermat :
Etape 1 : pour tout k < p on a : k ! (p - k) ! C(k ; p) = p ! ainsi p | k ! (p - k) ! C(k ; p) et comme p est premier p est premier avec k et (p - k) donc (th de Gauss : si a |bc et a premier avec b alors a|c) : p | C(k ; p).
Etape 2 : Pour p = 2 c'est évident.
Pour p >2, par récurrence sur x :
Pour x = 1 c'est évident. Supposons que la proposition est vraie jusqu'à x< p - 1, montrons la pour x+1.
(x+1)^p = x^p + [somme (pour k de 1 à p-1) de C(k ; p) x^k ] + 1 or (étape 1) p | C(k ; p) donc
(x+1)^p = x^p + 1 [p] or (hypothèse de récurrence) x^{p - 1} = 1 [p] donc x^p = x [p] et
(x+1)^p = x + 1 [p] et comme x+1 non nul [p] on divise tout par x + 1 on a donc (x+1)^{p - 1} = 1 [p]. CQFD

Nous allons maintenant prouver que si p et q sont eux nombres premiers on a :
pour tout x < n : x^{1 + kn'} = x [n] où n' = (p-1) (q-1) et n = pq.

Preuve :
x^{1 + kn'} = x * x ^kn' [n]
or d'après le petit théorème de Fermat x^p-1 = 1 [p] et x^q-1 = 1 [q] donc x^{(p-1)(q-1)= n'} = 1 [pq=n] car pgcd (p;q)=1,
ainsi x ^kn' = 1 [n] et x^{1 + kn'} = x [n]. CQFD

Le fait qu'il existe un couple d'entiers naturels (e ; k) tels que ed - kn' = 1 où n'=(p-1)(q-1) et d premier avec n' vient du Théorème de Bezout : p et q sont premiers entre eux ssi il existe m et n dans Z tels que pm + qn = 1.

Preuve du théorème de Bezout (en bref) :
pZ + q Z = {pn + qm ; n et m dans Z} est un sous groupe de Z donc il existe d tel que dZ = pZ + q Z et d est le pgcd de p et q donc d = 1 ainsi pZ + q Z = Z et il existe m et n entiers tels que pm + qn = 1. CQFD

Preuve de l'existence de e et k :
comme d est premier avec n' il existe E et K entiers relatifs tels que Ed - Kn' = 1 on fait la division euclidienne de E par n' : soit E = n'q + e avec e positif (e<n'); on a donc ed - kn' = 1 où k = K - qd or kn' = ed - 1 > -1 donc en divisant par n' on voit que k est positif. CQFD

Comment trouver e (et k) :
On sait que pgcd (a;b) = pgcd (b;r) où r est le reste de la division de a par b l'algorithme d'Euclide en découle.
Algorithme d'Euclide : Pour trouver le pgcd de a et b :
(1) faire la division euclidienne de a par b, on trouve le reste r.
(2) si r = 0 alors pgcd (a;b) = b.
(3) sinon, on remplace a par b, b par r et on recommence à (1).

Dans notre cas on applique l'algorithme d'Euclide avec n' et d au départ on trouve 1 comme dernier reste non nul (car d et n' sont premiers entre eux), on isole 1 on obtient une égalité (E), en isolant chacun des différents restes obtenus,
en remplaçant successivement dans (E) puis en factorisant de manière à faire apparaître d et n', on trouve l'égalité
ed - kn' = 1 et donc la clé de cryptage e.

[haut de page]

Références :

Sites persos dédiés à la cryptographie : Les pages perso d'Alban et cryptologie.free.fr.
Un portail en anglais sur la cryptographie : http://world.std.com/~franl/crypto/.
Un grand dossier sur la cryptographie : securite-web.com.
Un cours de cryptanalyse : http://perso.wanadoo.fr/gilb/.
Une lettre, en français, concernant la vulnérabilité des codages : counterpane.com.

[haut de page]