RSA

Le système RSA : une clef, un facteur, et quelques opérations...

RSA est un algorithme de chiffrement asymétrique, il sera utilisé dans PGP pour créé des clés temporaires. Nous allons étudier son principe de fonctionnement à travers un exemple.
Le principe du codage par factorisation restant le même quelle que soit la taille du nombre, nous allons nous contenter ici d’un tout petit nombre, qui constituerait un gros secret pour un élève de CM2, mais pas pour un espion.

Le colonel Dupond, adepte du cryptage RSA, a donc donné à tous ses agents la clé N=391 et le facteur k=3. N est un nombre composé par le produit des deux facteurs premiers 17 et 23 (17x23=391). On prends ses deux facteurs diminués de 1 : 17-1=2x2x2x2 et 23-1=2x11. Le PGCD de ces deux nombres est donc 2. On considère alors l’indicateur d’Euler L(N)=16x22, dont on prend la moitié Z, soit 176.

A partir de ce nombre, on cherche les nombres de la forme m.Z+1, le premier étant (1x176)+1=177, le second (2x176)+1=353, et ainsi de suite. Il faut ensuite décomposer ce m.Z+1, ce qui difficile, parfois même impossible. Ici 177=3x59, mais 353 est premier. Nous nous contenterons donc de 3x59 (k=3 et k’=59).

Le colonel Dupont envoie donc à tous ses honorables correspondants le nombre clef 391 et le facteur 3. Il garde pour lui seul k’=59. Justement, Durand doit passer le voir sous peu et veut lui dire « arrive le 8 ». Un message ultra-secret qu’il va coder avec 3 et 391. Pour commencer il convertit son texte en chiffres en prenant par exemple a=01, b=02, ..., espace=00, 0=30, 1=31, 2=32, ..., ce qui lui donne 0118180922050012050038.

Il regroupe ce nombre en tranches ayant moins de chiffres que la clef 391, donc en tranches de deux chiffres : 01 18 18 09 ... Chacun de ses nombres représente la variable texte ou T. Il va maintenant effectuer l’opération C=T^3 (mod 391) pour obtenir la succesion 1 358 358 338 91 ... 132. Ajoutant des 0 si nécessaire pour n’avoir que des nombres de trois chiffres comme la clef, il note 001358358338091...000132, et c’est cette suite de chiffres qu’il envoie au colonel.

Celui-ci possède la clef k’=59, va maintenant utiliser la congruence T=C^59 (mod 391) après avoir découpé le message en tranches de trois chiffres puisque la clef N en a trois. Il va ainsi retrouver 01 pour 001, 18 pour 358 - car 358^59 (mod 391) donne 18 - et ainsi de suite. Il ne lui reste plus qu’à prendre son tableau de correspondance alphabétique pour recueillir « arrive le 8 ». Bien entendu, codage et décodage se font sur ordinateur vu la longueur des opérations.

L’adversaire, bien qu’il connaisse la clef publique 391 et la facteur 3, ne peut décrypter le message car il lui faudrait avoir la clef secrète k’=59. Et pour avoir celle-ci, il devrait décomposer N en facteur premiers, ce qui est certes facile avec 391, mais impossible actuellement - à moins d’y consacrer des siècles ou de recourir à la divination - avec un nombre de 150 à 200 chiffres. Il pourrait certes tenter de calculer un racine k-ième modulo N, mais cela est virtuellement impossible car il n’existe aucun algorithme permettant de faire cette opération en un temps raisonnable pour N composé.

En contrepartie, le calcul d’une puissance modulo N est à la portée de tout ordinateur, ou même d’une calculatrice de poche programmable. Pour le moment, la sécurité du cryptage RSA repose sur la puissance des ordinateurs et sur les connaissances en arithmétique. Tout progrès dans un domaine comme dans l’autre peut obliger à allonger la clef, où à chercher une autre fonction qui soit facile dans un sens, et quasiment impraticable dans l’autre.

Article extrait de Sciences&Vie n°953, février 1997.
RSA sont les initiales de Rivest Shamir Adelman, les inventeurs de ce procedé