Chiffre RSA

Le RSA (d'après les initiales de ses créateurs Ronald Rivest, Adi Shamir et Leonard Adleman) est un algorithme de cryptographie asymétrique fondé sur l'arithmétique modulaire et la difficulté de factoriser un grand entier $ n $ produit de deux grands nombres premiers. Utilisant une clé publique et une clé privée, RSA peut être utilisé à la fois pour le chiffrement et pour les signatures numériques.

Le chiffrement RSA repose sur une opération mathématique appliquée à un entier représentant le message. Dans sa forme mathématique simplifiée, avec la clé publique $ (n,e) $, le message $ M $ est chiffré par $$ C \equiv M^e \pmod n $$

En pratique, cette opération n'est pas utilisée seule pour chiffrer directement un message : un schéma de padding, comme RSAES-OAEP, transforme d'abord le message en une représentation adaptée au chiffrement.

Si la représentation entière du message est supérieure ou égale à $ n $, elle doit être découpée en blocs dont les valeurs sont inférieures à $ n $. En pratique, la taille maximale du message dépend également du schéma de padding utilisé.

Le déchiffrement RSA nécessite la clé privée correspondant à la clé publique utilisée lors du chiffrement. Dans la forme mathématique simplifiée, le message clair $ M $ est calculé avec : $$ M \equiv C^d \pmod n $$ avec $ C $ le message chiffré et $ (n,d) $ les paramètres privés correspondants.

En pratique ce nombre brut n'est pas le message ASCII lui-même, car il est modifié avec un schéma de padding qu'il faudra retirer.

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.

Un message RSA brut est généralement représenté par un ou plusieurs nombres entiers, accompagnés de paramètres de clé comme $ n $ et $ e $.

Dans les applications réelles, les données RSA peuvent toutefois être représentées sous différentes formes : nombres binaires, hexadécimaux, fichiers PEM, structures ASN.1 ou données encodées en Base64.

La taille de RSA est généralement exprimée en bits et correspond à la taille du module $ n $ (généralement 1024, 2048 ou 3072 bits)

RSA a notamment été utilisé dans TLS/HTTPS pour les certificats et, dans les anciennes versions de TLS, pour le transport de clés.

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 valeurs 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é publique ($ 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

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

La valeur $ e=65537 $ est issue d'un compromis cout-efficacité.

Une valeur de $ e $ trop grande augmente les temps de calculs. Une valeur de $ e $ trop petite augmente les possibilités d'attaque.

$ 65357 $ est un nombre de Fermat $ 65357 = 2^{2^4} + 1 $ ce qui permet une simplification dans la génération des nombres premiers.

Cette valeur est devenue un standard, il n'est pas recommandé de la changer dans le cadre d'échanges sécurisés.

Le nombre trouvé est un nombre entier représentant la valeur décimale du contenu en clair.

Généralement, ce nombre peut être transcrit selon le codage de caractères utilisé (comme ASCII ou Unicode).

Un certificat RSA est un fichier texte contenant les données utiles à un échange cryptographique par RSA.

Il existe 2 types de certificat :

— le certificat public, qui commence par -----BEGIN PUBLIC KEY----- et qui contient les valeurs des clés publiques $ N $ et $ e $.

— le certificat privé, qui commence par -----BEGIN RSA PRIVATE KEY----- et qui contient toutes les valeurs : $ N $, $ e $, $ d $, $ q $ et $ p $. Ce fichier est généralement conservé précieusement et ne doit jamais être divulgué.

Un certificat X.509 est différent d'une clé RSA : il contient notamment une clé publique et des informations sur son propriétaire, ainsi qu'une signature permettant d'en authentifier le contenu.

Un ordinateur quantique suffisamment grand et tolérant aux erreurs pourrait factoriser efficacement les grands nombres grâce à l'algorithme de Shor. Cela compromettrait la sécurité de RSA.

Les ordinateurs quantiques actuels ne disposent toutefois pas des capacités nécessaires pour factoriser les modules RSA utilisés en pratique. Cette menace motive le développement et le déploiement progressif de cryptographies post-quantiques.

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