Chiffre RSA

Le chiffrement RSA est purement mathématique, tout message doit d'abord être codé par des nombres entiers (n'importe quel encodage fonctionne: ASCII, Unicode, voire A1Z26). Pour le chiffrement RSA a besoin des nombres $ n $ et $ e $ appelées les clés publiques.

Le message (numérique) est décomposé en nombres (inférieurs à $ n $), pour chaque nombre M, le message (numérique) chiffré C est $$ C \equiv M^{e}{\pmod {n}} $$

Exemple : Chiffrer le message R,S,A (encodé 82,83,65 en ASCII) avec la clé publique $ n = 1022117 $ et $ e = 101 $ soit $ C = 828365^{101} \mod 1022117 = 436837 $, donc le message chiffré est 436837.

Le déchiffrement nécessite de connaitre la clé privée $ d $ et la clé publique $ n $. Pour tout message (numérique) chiffré C, le message (numérique) clair M se calcule modulo n : $$ M \equiv C^{d}{\pmod {n}} $$

Exemple : Déchiffrer le message C=436837 avec la clé publique $ n = 1022117 $ et la clé privée $ d = 767597 $, soit $ M = 436837^{767597} \mod 1022117 = 828365 $, 82,83,65 est le message clair (soit les lettres R,S,A)

RSA a besoin d'une clé publique (constituée de 2 nombres $ (n, e) $) et d'une clé privée (1 seul nombre $ d $).

- Sélectionner 2 nombres premiers distincts $ p $ et $ q $ (plus ils sont grands et plus le chiffrement sera robuste)

- Calculer $ n = p \times q $

- Calculer l'indicatrice d'Euler $ \phi(n) = (p-1)(q-1) $

- Sélectionner un entier $ e \in \mathbb{N} $, premier avec $ \phi(n) $ tel que $ e < \phi(n) $

- Calculer l'inverse modulaire $ d \in \mathbb{N} $, ie. $ d \equiv e^{-1} \mod \phi(n) $ (via l'algorithme d'Euclide étendu)

Avec ces nombres, le couple $ (n,e) $ est appelée la clé publique et le nombre $ d $ est la clé privée.

Exemple : $ p = 1009 $ et $ q = 1013 $ donc $ n = pq = 1022117 $ et $ \phi(n) = 1020096 $. Les nombres $ e = 101 $ et $ \phi(n) $ sont premiers entre eux et $ d = 767597 $.

Les clés sont renouvelées régulièrement afin d'éviter tous risques de divulgation de la clé privée. Il est indispensable ne ne jamais utiliser plusieurs fois la même valeur de p ou q pour éviter des attaques par recherche de PGCD.

Le message est entièrement numérique est normalement accompagné au moins d'une clé (numérique aussi).

En pratique les clés sont parfois affichés en hexadécimal, ou stockées dans un certificat (codé en base64).

La longueur des dépend de la complexité du RSA mis en oeuvre (1024 ou 2048 sont courants)

Le chiffrement RSA est utilisé dans le protocole HTTPS

Méthode 1 : Factorisation en nombres premiers de $ n $ pour retrouver $ p $ et $ q $.

Le chiffre RSA repose sur l'hypothèse qu'il n'est pas possible de retrouver rapidement les valeurs $ p $ et $ q $, c'est pourquoi la valeur $ n $ est publique. Pour retrouver la clé privée, un pirate doit être en mesure de réaliser la décomposition en facteurs premiers du nombre $ n $ pour retrouver ses 2 facteurs $ p $ et $ q $. En pratique, cette décomposition n'est possible que pour les petites valeurs, c'est-à-dire une clé $ n $ comportant moins de 30 chiffres (pour les algorithmes et les ordinateurs actuels), entre 30 et 100 chiffres, compter plusieurs minutes ou heures, et au delà, le calcul peut durer plusieurs années... Avec $ p $ et $ q $ la clé privée $ d $ peut être calculée et les messages peuvent être déchiffrés.

Méthode 2 : Retrouver le facteur commun à plusieurs clés publiques $ n $

La génération des clés est aléatoire mais il n'est pas improbable qu'un facteur $ p $ (ou $ q $) puisse être utilisé pour calculer les valeur de 2 clés publiques $ n $ différentes. En calculant le PGCD de 2 clés, si la valeur trouvée est différente de 1, alors le PGCD est un premier facteur de $ n $ (donc $ p $ ou $ q $), en divisant $ n $ par le pgcd se trouve le second facteur ($ p $ ou $ q $).

Méthode 3 : Attaque par texte chiffré choisi

Etant donné une clé publiqué ($ n $, $ e $) et un message chiffré connu $ c \equiv m^e \pmod{n} $, il est possible de demander au correspondant de déchiffrer un message chiffré choisi $ c' $. En se basant sur la propriété $ m_1^e m_2^e \equiv (m_1 m_2)^e \pmod{n} $, le déchiffrement d'un message $ c' \equiv c \times r^e \pmod{n} $ avec $ r $ un nombre choisi (inversible modulo $ n $) renverra la valeur $ m \times r \pmod{n} $. En calculant $ m \times r \times r^{-1} \pmod{n} $ (avec $ r^{-1} $ l'inverse modulaire) se retrouve $ m $ le message original.

Méthode 4 : Problème des messages trop courts avec petit exposant e

Pour un exposant petit ($ e = 3 $) et un message $ m $ court (inférieur à $ n^{1/e} $) alors le message chiffré $ c = m^e $ est inférieur à $ n $, donc le calcul du modulo n'a pas d'effet et il est possible de retrouver le message $ m $ en calculant $ c^(1/e) (racine $ e $-ième).

Méthode 5 : Attaque de Wiener pour des clé privées $ d $ trop petites

Si la clé privée $ d $ est petite par rapport au message $ n $ et telle que $ d<\frac{1}{3}n^{\frac{1}{4}} et que $ p $ et $ q $ sont proches $ q < p < 2q $, alors en calculant des approximations de $ n/e $ à l'aide de fractions continues, il est possible de retrouver la valeur de $ p $ et $ q $ et donc la valeur de $ d $.

Pour retrouver la clé privée, un pirate doit être en mesure de réaliser la décomposition en facteurs premiers du nombre $ n $ pour retrouver ses 2 facteurs $ p $ et $ q $. Pour les petites valeurs (jusqu'au million ou au milliard), c'est assez rapide avec les algorithmes et les ordinateurs actuels, mais au delà, lorsque les nombres $ p $ et $ q $ ont plusieurs centaines de chiffres, la décomposition nécessite en moyenne plusieurs centaines ou milliers d'années de calcul. Il existe des bases de données répertoriant les factorisations comme ici (lien)

Avec les nombres $ p $ et $ q $ la clé privée $ d $ peut être calculée et les messages peuvent être déchiffrés.

Ronald Rivest, Adi Shamir et Leonard Adleman ont décrit l'algorithme en 1977 puis l'ont breveté en 1983.