La méthode RSA
La méthode RSA est la première réalisation de systèmes de cryptage à clef publique mais Diffie et Hellman en avaient eu l'idée en 1976. Elle fut publiée en 1977 par Rivest, Shamir, et Adleman qui fondèrent ensuite leur compagnie en 1982 à Redwood City en Californie.
La factorisation des grands nombres n'est pas seulement un agréable passe-temps pour des théoriciens de l'arithmétique mais une base incontournable pour la conception de systèmes de cryptographie à clef publique.
En effet, la recherche des facteurs premiers de grands nombres était considérée comme un problème intéressant mais uniquement du point de vue de la théorie mathématique jusqu'à ce que Rivest, Shamir, et Adleman (RSA) proposent en 1978 d'utiliser la quasi impossibilité de retrouver les facteurs premiers à partir du produit de deux grands nombres entiers comme technique de cryptographie. Cette technique novatrice était destinée à protéger de l'information particulièrement sensible. L'expérience de la pratique des meilleurs algorithmes de factorisation suggère que cette dernière est en effet un problème NP-complet, c'est-à-dire qu'il ne peut être résolu par des algorithmes de complexité polynomiale. La méthode RSA devint ainsi la clef de voûte des systèmes de cryptographie à clef publique et rencontra un grand engouement dans les milieux bancaires et militaires.
Les textes sont des entiers positifs compris entre 0 et 2^{512}. Les clefs sont des quadruplets (p ,q ,e ,d) avec p un entier premier de 256 bits, q un nombre premier de 258 bits et d et e des grands nombres tels que (de-1) soit divisible par (p-1)(q-1). On peut alors définir EK(T) = T^e mod pq, DK(C) = C^d mod pq.
Maintenant, EK est facilement programmable à partir de la paire (pq, e), mais il n'y a pas de façons évidentes de programmer DK à partir de la paire (pq, e). Ainsi qui que ce soit qui génère K peut publier (pq, e).N'importe qui peut lui envoyer un message, il est le seul qui puisse le lire.
Exemple de codage par factorisation et de déchiffrage
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 X, 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 X envoie donc à tous ses honorables correspondants le nombre clef 391 et le facteur 3. Il garde pour lui seul k’=59. Justement, Y 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 succession 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.
RSA Data Security est devenu le standard de référence avec plus de 75 millions de copies de cette technologie utilisées de par le monde. RSA est utilisée par des logiciels comme Netscape Navigator ou encore par Microsoft Windows et des centaines d'autres produits informatiques. RSA fait partie des standards proposés pour Internet et le World Wide Web aussi bien que pour les réseaux de commerce électronique et les réseaux financiers.
