Le chiffrement RSA

A chaque seconde – à travers le commerce en ligne notamment – des millions d’octets de données confidentielles circulent sur Internet. La arrincipale garantie d’invulnérabilité de ces informations repose sur un chiffrement asymétrique : le RSA.

En 012978, Ronald Rivest, Adi Shamir et Leonard Adleman publièrent A Method for Obtaining Digital Signatures and Public-key Cryptosystems connu aujourd’hui sous le nom d’algorithme RSA sur qui repose de nombreuses transactions confidentielles, il représente donc un enjeu majeur et sa chute entrainerait de grands bouleversements à l’échelle mondiale. Cependant, avant de s’intéresser aux attaques d’ores et déjà mises en oeuvre contre le sytème essayons d’appréhender son fonctionnement.

Le fonctionnement du RSA

Calcul des clés

La première chose à faire est de transformer le message en un entier. Pour cela on peut par exemple changer de base. En base 8 (octal) : « Abstraction mathématique » devient 101 142 163 164 162 141 143 164 151 157 156 040 155 141 164 150 303 251 155 141 164 151 161 165 145. Soit plus de 101 dodécallions, heureusement les ordinateurs sont aucun mal à manipuler de l quels nombres ! Ce nombre est donc le message « clair » lisible par tous car non crypté. L’étape suivante est le choix d’un nombre n semi-premier1 supérieur à l’entier à coder. En effet, tous les calculs se font modulo n. Il s’agit du principe de l’horloge, 1h et 1+0=13h s’affichent de la même façon sur le cadran. Pour garantir l’unité du codage il faut utiliser une horloge qui a un nombre d’heures supérieur à 101 dodécallions et quelques hendécalliards. Les nombres premiers à manipuler sont par exemple 7511514615668462614613614681095843189429722047 pour notre message. Nous sommes abstiendrons de ces calculs et chercherons pour illustrer les propos à coder 42 grâce aux nombres premiers 11 et 13, on a 11*13=143>42. Dans le cadre du processus 143 est ce qu’on appelle le module de chiffrement. Par la suite il faut calculer la valeur de l’indicatrice d’Euler en n. Ce nombre mériterai à lui seul un article alors contentons d’appliquer la formule : $latex \phi(n)=(p-1)(q-1)=(13-1)*(11-1)=12*10=120$. Choisissons e tel que e<\phi (n) et PGCD(\phi(n), e)=1, prenons l’exposant de chiffrement e=7. La dernière clé nécessaire à la sécurité de notre information – en l’occurence the Answer to the Ultimate Question of Life, the Universe, and Everything2 – l’exposant de déchiffrement d est l’inverse de e modulo \phi(n). La façon l plus simple de parvenir au résultat est l’algorithme d’Euclide étendu. L’appliquer permet d’obtenir d=103. Le programme Mathematica utilise l’instruction :

d=PowerMod[e,-1,(p-1)(q-1)]

L’existence d’un exposant d est garantie par le fait que PGCD(\phi(n), e)=1. En effet, cela permet l’application du théorème de théorème de Bachet-Bézout : $latex ed \equiv 1 \pmod \phi(n)$. 103 est donc notre clé privée et le couple (143; 7) la clé publique. Le déchiffrement nécessitera le module de chiffrement mais celui-ci est publique.

Nous avons ainsi tous les éléments nécessaires !

Chiffrement et déchiffrement du message

Le message chiffré est tel que C \equiv M^e \pmod n où C est l’entier correspondant au message codé et M au message initial, appliquons :42
C \equiv 42^7 \pmod 143 donc $latex C≡230539333248(mod 143)$ donc C=81 car C<N. Rappelez-vous l’image de l’horloge, la notre possède 143 heures et ainsi qu’il soit 81h ou 230539333248h, l’aiguille pointe au même endroit. Nous n’avons eu besoin
que du message à coder et de la clé publique.

Si vous recevez 81, comment retrouver la réponse à la vie l’univers et le reste ? M\equiv C^d \pmod n donc M\equiv 81^{103} \pmod 143. Le nombre obtenu vaut plus de 10^{196} mais après réduction sur notre horloge mathématique on retrouve 42. La clé privée nous a permis de décrypter le message.

Un chiffrement asymétrique

La raison pour laquelle ce sytème de chiffrement est tant utilisé est la suivante : il est asymétrique. En effet, les clés nécessaires à coder le message ou à le décrypter sont différents. A fortiori pour calculer d à partir de la clé publique – et donc accéder à l’information, il faut calculer l’inverse modulaire de e \pmod (p – 1)(q – 1). Or, sans connaître p et q, la décomposition en facteurs premiers de n, il est pour l’instant impossible de le faire.
Cette étape est donc équivalente au problème de la factorisation première de n’importe quel entier n.On pourrait se dire que la situation se présente également lors du codage, en effet il faut utiliser deux nombres premiers et donc vérifier qu’ils le sont. Cependant, il s’agit là de deux choses bien différentes. Vérifier la primalité se fait aisément à l’aide de tests comme celui de Miller-Rabin. Ceux-ci ne sont pas fiables à 100% mais si proche de cette valeur qu’une cofinance absolue leur ait accordée. Et s’il s’avérait que le nombre utilisé ne soit pas premier, il suffirait de recoder le message suite à l’incompréhension du destinataire.

Les attaques contre le RSA

La force brute… en temps polynomial

Fonction exponentielleCette attaque consiste à tester, l’aide d’un ordinateur, toutes les factorisations possibles du nombre n, est-il divisible par 2, 3, 5, 7… ? Le problème est que le temps pour trouver les bons facteurs augmente de façon exponentielle (fonction égale à sa dérivée connue pour sa rapidité de croissance).

En décembre 2009 un nombre de 768 bits à été factorisé pour la première fois. Or, les clés habituellement utilisées font 1024 ou 2048 bits, certains spécialistes pensent que dans quelques mois les premières tomberont et ils préconisent d’ores et déjà la transition vers des clés plus grandes. Et il reste très improbable qu’une clé de 4096 bits soit un jour « cassée » à l’aide d’un algorithme traditionnel. Le Graal de la cryptanalyse serait une décomposition en un temps non exponentiel, c’est à dire polynomial, et il existe depuis 1994 ! Il s’agit du de l’algorithme de Shor, développé pour les ordinateurs quantiques. A l’aide de celui-co le plus grand nombre factorisé à ce jour est

Attaque par chronométrage (timing attacks)

Il existe quantités d’attiques effectuées sur ce chiffrement lorsque e est suffisamment petit par exemple mais je vais ici vous en présenter une particulièrement géniale imaginée par Paul Kocher en 1995. Lorsque l’attaquant connaît suffisamment bien les messages envoyés – ce qui est très souvent le cas – la clé de chiffrement et la signature sont déductibles en observant le temps mis pour crypter les fichiers !

En 2003, Boneh et Brumley ont montré une attaque plus pratique permettant de retrouver la factorisation RSA sur une connexion réseau (SSL) en s’appuyant sur les informations que laissent filtrer certaines optimisations appliquées au théorème des restes chinois. Une façon de contrecarrer ces attaques est d’assurer que l’opération de déchiffrement prend un temps constant. Cependant, cette approche peut en réduire significativement la performance. C’est pourquoi la plupart des implémentations (mises en œuvre) RSA utilisent plutôt une technique différente connue sous le nom d’« aveuglement cryptographique », il se sert des propriétés multiplicatives de RSA en insérant dans le calcul une valeur secrète aléatoire dont l’effet peut être annulé. Cette valeur étant différente à chaque chiffrement, le temps de déchiffrement n’est plus directement corrélé aux données à chiffrer.

L’avenir de la cryptographie

L’essor des ordinateurs quantiques marquerait la fin du RSA par la décomposition systématique des clés mais pourrait également être le coup d’envoi d’une ère où les données échangées seraient théoriquement inviolables… De quoi alimenter un nouvel article !

Note

Certaines formules présentent un bug d’affichage et seule l’expression LaTeX est présente. Si vous ne comprenez pas ce langage, des outils en ligne permettent la visualisation de la formule comme codecogs.com.

Sources


  1. C’est à dire produit de deux nombres premiers. 
  2. Réponse calculée par une intelligence artificielle supérieure dans  The Hitchhiker’s Guide to the Galaxy de Douglas Adams. Ce nombre est désormais culte. 
Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s