Pourquoi le RSA brut (textbook) ne suffit pas

On suppose ici RSA connu : n = p × q, un exposant public e, un exposant privé d, et le chiffrement c = m^e mod n. Ce cours part d'un constat gênant : appliqué tel quel, RSA est dangereux.

Le RSA « scolaire »

On appelle RSA textbook (ou RSA brut) le schéma présenté dans les manuels : on prend le message, on le voit comme un nombre m, et on calcule directement c = m^e mod n. Rien d'autre. Aucun traitement du message avant chiffrement.

C'est parfait pour comprendre le principe. C'est catastrophique en pratique, pour trois raisons.

Défaut n°1 : c'est déterministe

Le même message donne toujours le même chiffré. La fonction m -> m^e mod n n'a aucune part de hasard.

message "OUI"  --chiffrer-->  c = 8F2A...   (toujours identique)
message "NON"  --chiffrer-->  c = 51CD...   (toujours identique)

Conséquence : un espion qui observe le canal peut reconnaître un message déjà vu. Si les messages possibles sont peu nombreux (« oui » / « non », un vote, un code PIN à 4 chiffres), il chiffre lui-même chaque possibilité avec la clé publique et compare. C'est une attaque par dictionnaire : la clé privée n'est jamais touchée.

Défaut n°2 : c'est malléable

RSA est homomorphe pour la multiplication. En multipliant deux chiffrés, on multiplie les clairs correspondants :

c1 = m1^e mod n
c2 = m2^e mod n
c1 × c2 = (m1^e)(m2^e) = (m1 × m2)^e mod n

Le produit c1 × c2 est donc le chiffré valide de m1 × m2. Un attaquant peut fabriquer le chiffré d'un message qu'il n'a jamais pu chiffrer lui-même, ou transformer un message intercepté sans le lire. Il « bricole » le texte clair à distance.

Défaut n°3 : les petits messages

Si le message est petit et l'exposant petit, m^e peut ne pas dépasser n. Il n'y a alors aucune réduction modulo n, et retrouver m revient à une simple racine. C'est le sujet de la leçon suivante.

La parade : le remplissage aléatoire

La solution commune est d'ajouter du hasard et de la structure au message avant de le chiffrer : c'est le remplissage (padding). Le standard sûr pour le chiffrement RSA s'appelle OAEP.

• On brasse le message avec des octets aléatoires, de sorte que chiffrer deux fois « OUI » donne deux chiffrés différents : fini le déterminisme et le dictionnaire.
• La structure imposée fait qu'un chiffré « bricolé » (produit de deux chiffrés) donne, une fois déchiffré, un remplissage invalide que l'on rejette : fini la malléabilité.

En résumé

Le RSA textbook est déterministe (donc attaquable par dictionnaire), malléable (c1 × c2 chiffre m1 × m2) et fragile sur les petits messages. Le remplissage aléatoire OAEP corrige ces défauts en rendant le chiffrement imprévisible et vérifiable. On ne chiffre jamais avec du RSA brut.