Lumière sur le chiffrement RSA

Un peu d’histoire

L’algorithme du chiffrement RSA a été proposé en 1977 par Ron Rivest, Adi Shamir et Len Adleman; et fût breveté par le MIT en 1983. Celui-ci expira le 21 Septembre 2000.

Utilisation

Le chiffrement par RSA est très utilisé dans le web, et plus particulièrement dans le e-commerce pour les certificats SSL. En effet, cela permet d’authentifier et de signer numériquement une connexion et/ou un document.

Principe

Un petit exemple pour illustrer ce principe:

Alice va créer une paire de clés: une clé privée et une clé publique. Elle donnera la clé publique à Bob, Carole, Denis, … qui l’utiliseront pour chiffrer leurs données confidentielles pour ensuite les renvoyer à Alice. Celle-ci va utiliser sa clé privée pour déchiffrer ces données.

Plus concrètement, c’est comme si:

1. Alice donne un coffre-fort ouvert à Bob.
2. Bob y glisse son message, referme le coffre, et le rend à Alice.
3. Alice étant la seule à posséder la clé pour ouvrir le coffre, elle est donc la seule à pouvoir voir le message de Bob.

Un peu de mathématiques

Les formules

Soit la paire de clés , respectivement clé publique, clé privée.

Pour chiffrer un message: f(c) : 

Pour déchiffrer un message: g(m) :

En fait, la fonction f(c) est une fonction trappe (ou à sens unique). Cela signifie que les images de la fonction n’admettent pas d’antécédents évidents. Le seul moyen de les trouver, c’est de connaître la « trappe de la fonction » pour pouvoir l’inverser.

Remarques

En Mathématiques, vaut en algorithmique  % 

Les algorithmes du PGCD et du test de primalité sont disponibles ici.

Implémentation

1. Choisir 2 nombres premiers p et q « suffisamment grands ».
2. Calculer n:
3. Calculer l’indicatrice d’Euler de n, soit:
4. Prendre au hasard tel que soit premier avec (Petit rappel, cela signifie que leur PGCD = 1)
5. D’après le théorème de Bachet-Bézout, e étant premier avec , il est inversible modulo ; c’est à dire qu’il existe un entier d tel que . En utilisant l’identité de Bézout qui nous dit que ; on sait que
6. On a notre paire de clés: et

Chiffrer les données

1. On convertit chaque caractères en ASCII et on les met bout à bout.
2. On découpe cette chaine en blocs que taille(n) – 1 caractères. Ex: Si n = 1073, un bloc fera 3 caractères.
3. On complète le dernier bloc avec des 0, si il fait moins de 3 caractères
4. On applique la formule f(c) = m^e mod n et on met bout à bout chaque image de la fonction.

Pour déchiffrer, c’est exactement la même chose, mais en utilisant la clé privée.

Un petit exemple

1. On prend 2 nombres et aléatoirement:
2. On calcule n:
3. L’indicatrice d’Euler
4. On prend . n’est pas premier avec … On en prend un autre
5. . Nous avons notre clé publique: .
6. On va calculer d: . Vérification: 71 * 1079 % 1008 = 1. On a maintenant notre clé privée:
7. On va chiffrer « HELLO »: m = ASCII(HELLO) = 7269767679.
8. taille(n) – 1 = 3. m = 726 976 767 900
9. 726^71 %  1073 = 436
   976^71 % 1073 = 822
   767^71 % 1073 = 825
   900^71 % 1073 = 552
   Finalement, le message chiffré devient: 436 822 825 552
10. Pour le déchiffrer:
    436^1079 % 1073 = 726
    822^1079 % 1073 = 976
    825^1079 % 1073 = 767
    552^1079 % 1073 = 900
    On retrouve bien 72 69 76 76 79, soit HELLO.