Les codes transportés par les cartes bleues, les secrets des plus grandes entreprises, les données transférées sur internet… tous sont protégés par un système de cryptage identique : le RSA. Pourquoi règne-t-il une telle confiance autour du RSA ? Qu’est-ce qui fait sa fiabilité ?

La première partie de notre TPE nous a permis d’exposer le principe du RSA. Ainsi, la traduction du message repose sur le calcul des clés privées, lorsque l’on connaît les clés publiques. Evidemment, si les clés publiques sont :

N=10 et c=3,

Il sera très facile de trouver P=2 et Q=5, et U=3, et le message sera traduit facilement par n’importe qui, mais si :

N=27997833911221327870829467638722601621070446786955428537560009929326128400107609345671052955360856061822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983

Effectivement, il sera très compliqué de trouver :

P=3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349 et Q=7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467

(Cette factorisation a été réalisée en 2005 et était la première factorisation en produit de facteurs premiers d’un nombre de 200 chiffres. Pour information, récemment, RSA 768 a été factorisé, ce qui signifie qu’un nombre de 232chiffres décimaux a été factorisé en produit de facteurs premiers.)

Les ordinateurs modernes, même les plus puissants, ne peuvent pas trouver la factorisation en produit de facteurs premiers d’un très grand nombre, c’et pourquoi des récompenses sont proposées aux équipes de chercheurs capables de « casser » RSA-1000, RSA-2000… de l’ordre de plusieurs centaines de milliers de dollars.

C’est la principale raison pour laquelle le RSA est un système très fiable : lorsque la clé n est un nombre très grand, trouver sa factorisation en produit de facteurs premiers est pratiquement impossible, d’autant plus que si l’on a réussi à trouver une factorisation, même si il y a beaucoup de chances que ce soit la bonne, il se peut que celle utilisée par l’expéditeur en soit une autre.

Les nombres de Mersenne sont des nombres premiers calculables par une relation très simple :

Mp=(2^p)-1

Où p est un nombre premier.

Cette formule n’est pas toujours vraie et quelques tests, dont celui de Lucas-Lehmer, nous permettent de vérifier si le nombre obtenu est effectivement premier. Cependant, cette formule étant très connue, les nombres premiers obtenus par celle-ci sont en quelque sorte répertoriés et un produit de deux nombres premiers de Mersenne (c’est le nom qu’on leur donne) est, selon le langage spécifique, « grillé », et le code serait facilement cassé.

De ce fait, rien ne vaut deux nombres premiers parfaitement anonymes, à 500 chiffres, pour que le code soit absolument indéchiffrable. Pour le trouver, rien ne vaut la technique la plus simple et qui reste la meilleure : choisir un nombre impair au hasard, ayant 500 chiffres, un théorème conjecturé par Gauss et prouvé par un mathématicien du 20eme siècle prouve que l’on a alors une chance sur 1150, ce qui reste très raisonnable. Le produit obtenu sera alors extrêmement dur à factoriser, voire impossible.

On comprend ainsi pourquoi la taille des clés RSA les plus courantes est de 1024 Bits (ce qui correspond à un produit de facteurs premiers de 309 chiffres) : ce nombre de chiffre pour un produit de facteurs premiers est suffisamment grand pour qu’il soit difficile à factoriser.