Algorithme RSA

Par BeRgA le 17-04-2005

Présentation du système de cryptage RSA

Le système de cryptage antisymetrique RSA fut inventé en 1978 par Ron Rivest, Adi Shamir et Léonard Adleman (d'où son nom). Aujourd'hui utilisé dans des logiciels de cryptage tel que PGP, dans des protocoles comme SSL, anciennement utilisé pour le cryptage de certaines cartes à puce, RSA se base sur l'utilisation de deux clé, l'une privée, l'autre publique. Comme tout système avancé de cryptographie, il se base sur des notions d'arithmétiques qui peuvent en dérouter plus d'un. Ce tuto a pour but de vous aider à comprendre le fonctionnement de ce système, et à en trouver les faiblesses.
Bien entendu, il n'est pas parfait, donc si un passage est encore obscur, faites le savoir, pour que l'on puisse le remodeler de façon à le rendre plus clair.

Sommaire :
I. Quelques notions d'arithmétique
I. 1. Conguences
I. 2. diviseurs
I. 3. Nombres premiers
I. 4. Fonction d'Euler
I. 5. Théorème d'Euler
II. Fonctionnement de RSA
III. Exemple pratique


I. Quelques notions d'arithmétique


I. 1. Congruences

Dire qu'un nombre entier a est congru à un entier b modulo n signifie que le reste de la division euclidienne de a par n vaut b : il existe un entier relatif k tel que a=k*n + b. Faute de mieux, nous utiliseront les notations suivantes : a=b[n].

I. 2. Diviseurs

Un entier a est diviseur d'un entier b, si la division b/a donne un nombre entier comme résultat. On dit alors que a divise b, ou encore que b est un multiple de a.
Par exemple : 3/2=1.5, donc 2 ne divise pas 3. En revanche, 4/2=2, donc 2 divise 4, 4 est multiple de 2.

I. 3. Nombres premiers

Un entier relatif est dit premier s'il n'est divisible que par un et par lui-même. Par exemple, 13 est premier, mais 12 ne l'est pas (12 est divisible par 1, 12, mais aussi 2, 3, 4, et 6.
Deux entiers sont dits premiers entre eux si le plus grand diviseur commun (PGCD) de ces deux nombres est 1. Prenons par exemple les nombres 12 et 15. Les diviseurs de 12 sont : 1, 2, 3, 4, 6, et 12. Les diviseurs de 15 sont : 1, 3, 5, et 15. Le plus grand diviseur commun à 12 et 15 est 3, donc 12 et 15 ne sont pas premiers entre eux. Par contre, si l'on prend 4 et 9, les diviseurs de 4 sont 1, 2, et 4, ceux de 9 sont 1, 3, et 9. Le PGCD de 4 et 9 est donc 1, 4 et 9 sont premiers entre eux (ou encore 4 est premier avec 9)

I. 4. Fonction d'Euler

Cette fonction Fi associe à un entier n le nombre de nombres inférieurs à n, premiers avec n. Par exemple, Fi(3)=2 (1 et 2 sont premiers avec 3), Fi(4)=2 (1 et 3 sont premiers avec 4, mais pas 2). Si n est premier, alors il n'est divisible que par 1 et lui-même, ce qui signifie que tout nombre inférieur à n, sauf 1, est premier avec n. Si n est premier, on a donc Fi(n)=n-1. De plus, si m et n sont premiers entre eux, alors Fi(m*n)=Fi(m)*Fi(n).

I. 5. Théorème d'Euler

Si on prend deux nombres entiers a et n (n>=2), premiers entre eux, alors a ^ Fi(n) = 1 [n]


II. Fonctionnement de RSA


Prenons deux personnes, Marie et Jean. Marie veut que Jean lui envoie des messages qu'elle seule pourra lire. Ils décident pour cela de crypter leurs messages à l'aide de RSA. Marie va donc se créer une paire de clé : une clé publique (n,e) qui sera accessible à tout le monde, et une clé privée d, qu'elle seule connaitra (même Jean ne la connaitra pas). La paire de clé sera créé de la façon suivante :
- n doit être le produit de deux nombres entiers p et q (assez grands pour garantir une bonne sécurité).
- e est choisi tel que e et Fi(n) soient premiers. Comme n=p*q, avec p et q premiers entre eux (puisque premiers), alors Fi(n)=Fi(p*q)=Fi(p)*Fi(q)=(p-1)*(q-1) (p et q premiers, donc Fi(p)=p-1 et Fi(q)=q-1 ).
- d est choisi tel que d*e=1[Fi(n)] : e*d congru à 1 modulo Fi(n), soit encore d*e=1+k*Fi(n), avec k entier relatif quelconque.

Marie possède donc ses deux paires de clés (n,e) et d, définies ainsi :
- n=p*q, avec p et q premiers,
- PGCD de e et Fi(n) = 1, avec Fi(n)=(p-1)*(q-1),
- d*e = 1 [Fi(n)].

Maintenant, Jean peut envoyé un message à Marie en étant (presque) sûr qu'elle seule pourra le lire. Il souhaite envoyé le message x.
Grâce à la clé publique de Marie (qu'il connait, puisque cette clé est accessible à tout le monde), il va crypter son message de la façon suivante : y = x^e [n]. y est le message codé.
Marie va recevoir le message crypté y, et va le décrypter grace à sa clé privée : z = y^d.
Comme y = x^e, alors z = (x^e)^d = x^(e*d). Or, e a été choisi de telle façon que e*d = 1 + k*Fi(n).
on a donc z = x^(1 + k*Fi(n)) = x * x^(k*Fi(n)) = x * (x^Fi(n))^k. De plus, d'après le théorème d'Euler, x^Fi(n)=1[n], donc on a :
z = x * (1)^n = x * 1 = x.
Marie a donc bien réussi a retrouvé le message d'origine (x), à l'aide de sa clé. Si vous avez bien suivi, et que vous avez un esprit très logique, vous me direz que cela ne fonctionne que si la valeur x du message est premier avec le n de la clé publique. Rassurez vous, on peut démontrer que cela est valable tout le temps. Ceux ki souhaintent voir la démonstration, contactez-nous.


III. Exemple pratique


Nous allons voir ici un exemple pratique de cryptage/decryptage par RSA. Les nombres ont été intentionnellement choisi petits pour faciliter la compréhension (et pour que vous puissiez suivre les étapes à la main), mais sachez qu'en réalité, ils sont beaucoup plus grand (le n de la clé de cryptage possède environ 200 chiffres pour les clés les plus faibles). Les opérations sont donc réalisées par des programmes, et non par les utilisateurs eux-mêmes.
Prenons comme valeur n=21.
On a n=7*3, avec 7 et 3 premiers.
Alors Fi(n)=(7-1)(3-1)=12.
e doit être premier avec Fi(n), donc avec 12. Nous prendrons ici e=5, et donc 5 aussi pour la valeur de d(5*5=25=2*12+1), on a bien d*e=1[12].
Résumons donc :
La clé publique (n,e) vaut (21,5), la clé privée d vaut 5.

Jean souhaite crypté son message, par exemple 2.
Il va donc faire : 2^5=32=11[21] (21=11+1*21). Le message crypté vaut donc 11.
Marie reçoit le message, et va faire : 11^5=161051=7669*21+2=2[21] (les calculs peuvent être simplifiés en appliquant certaines propriétés relatives aux congruences : 11^5= 11 * 11^2 * 11^2 = 11 * 16 * 16 [21] = 11 * 4 [21] =2[21]). Marie a donc bien retrouvé le message initial de Jean, qui valait 2.

Voilà pour le fonctionnement du système RSA. Un tuto sur ces faiblesses suivra certainement celui là

Encore et toujours l'habituel blabla :
Propriété de SoH,
nous contacter pour diffusion