RSA sans encodage : factoriser n’est pas la seule façon de perdre

RSA est souvent présenté par un problème difficile : retrouver les facteurs d'un grand entier. On en déduit parfois qu'un programme utilisant de grands nombres est forcément sûr. Cette déduction oublie le protocole. Il existe des propriétés algébriques du RSA brut que l'on peut exploiter sans factoriser le module.

Le petit exemple suivant ne vise aucun service réel. Ses nombres sont volontairement minuscules pour que toutes les opérations soient vérifiables. Il illustre un raisonnement que l'on rencontre en cryptographie et dans les exercices CTF : avant de chercher une attaque coûteuse, regarder ce que l'algèbre permet déjà.

Un chiffrement entièrement calculable

Prenons les nombres premiers $p=5$ et $q=11$. Alors $n=pq=55$ et $\varphi(n)=(p-1)(q-1)=40$. Choisissons l'exposant public $e=3$. Son inverse modulo $40$ vaut $d=27$, puisque $3\times27=81\equiv1\pmod{40}$.

Le chiffrement brut d'un entier $m$ est :

Pour $m=7$, on trouve $c=7^3\bmod55=13$. Le déchiffrement calcule $13^{27}\bmod55=7$. Jusqu'ici, le mécanisme fait ce qu'on lui demande. Cela ne prouve encore aucune propriété de sécurité du message.

Modifier sans connaître

La multiplication des chiffrés correspond à la multiplication des messages modulo $n$ :

Choisissons $r=2$. On peut calculer $r^e=8$ avec la clé publique, puis construire $c'=13\times8\bmod55=49$. Le déchiffrement de $49$ donne $14$, c'est-à-dire deux fois le message initial.

On n'a pas retrouvé le secret, mais on a modifié le message de façon prévisible. C'est la malléabilité. Si le message représente directement une quantité ou une instruction sans vérification d'intégrité, le protocole peut déjà être en difficulté.

Le problème devient plus fort si une interface déchiffre des chiffrés choisis, en refusant seulement le chiffré original. Lui soumettre $c'$ peut révéler $mr\bmod n$. Si $r$ est inversible modulo $n$, multiplier par son inverse permet de retrouver $m$. Dans notre exemple, l'inverse de $2$ modulo $55$ vaut $28$ et $14\times28\bmod55=7$.

Un autre défaut, même sans interface de déchiffrement

Le RSA brut est déterministe. Un message donné produit toujours le même chiffré sous une même clé. Si les messages possibles sont peu nombreux, leur chiffrement public permet de tester des hypothèses par comparaison. Un espace de clés immense ne compense pas un espace de messages minuscule et reconnaissable.

Par exemple, chiffrer directement un code de statut parmi dix valeurs permet à quiconque possède la clé publique de construire la table des dix chiffrés. Aucun oracle, aucune mesure de temps et aucune factorisation ne sont nécessaires. Le chiffrement masque mal un choix que l'on peut énumérer.

L’encodage fait partie de la construction

La RFC 8017 distingue les primitives RSA des schémas complets, dont RSAES-OAEP pour le chiffrement et RSASSA-PSS pour la signature. OAEP introduit notamment un encodage aléatoire structuré avant l'exponentiation. On ne doit pas remplacer ce schéma par « quelques octets aléatoires ajoutés au message ».

L'encodage ne dispense pas non plus de traiter correctement les erreurs. Une implémentation peut révéler de l'information par ses réponses ou ses temps de calcul. Et signer n'est pas simplement « chiffrer avec la clé privée » : les objectifs et les encodages d'une signature sont différents.

Pour une application, on utilise une bibliothèque cryptographique et un protocole éprouvés, souvent une construction hybride : un mécanisme à clé publique protège du matériel de clé, puis un chiffrement symétrique authentifié protège les données. Le détail exact dépend du protocole choisi.

Vérifier l’algèbre, puis chercher la frontière

n, e, d = 55, 3, 27
message, r = 7, 2
ciphertext = pow(message, e, n)
modified = ciphertext * pow(r, e, n) % n
decoded = pow(modified, d, n)
recovered = decoded * pow(r, -1, n) % n
assert (ciphertext, modified, decoded, recovered) == (13, 49, 14, 7)

Ce script vérifie une identité, pas la sécurité d'une bibliothèque. Dans l'analyse d'un exercice, la prochaine question utile est de savoir quelles entrées sont contrôlables et quelles sorties sont observables. Une propriété algébrique devient une attaque seulement lorsqu'une interface lui donne un effet exploitable. Cette séparation entre primitive, encodage et protocole rend le raisonnement beaucoup plus précis que « RSA est cassé ».