ArithmétiqueNotion · Glossaire
code RSA
RSA est un algorithme cryptographique asymétrique fondé sur l’arithmétique modulo le produit de deux grands nombres premiers. Une clé publique est diffusée et une clé privée reste secrète : selon l’usage, elles permettent de chiffrer et déchiffrer, ou de signer et vérifier. Sa sécurité pratique suppose notamment que la factorisation du module reste hors de portée et que les clés, les messages et le schéma de remplissage respectent les conditions prévues.
Sommaire
Ce que vous allez apprendre
- Relier la paire de clés au produit de deux nombres premiers.
- Suivre un chiffrement RSA numérique puis contrôler le déchiffrement.
- Distinguer chiffrement, signature numérique et chiffrement symétrique.
- Identifier les limites d'un exemple à petit module.
En clair
Imaginez une boîte aux lettres dont chacun peut refermer la trappe, mais dont seul le destinataire possède la clé d'ouverture. RSA transpose cette dissymétrie au calcul : une clé publique circule, tandis qu'une clé privée reste secrète.
Le verrou vient de deux grands nombres premiers. Les multiplier est direct ; retrouver ces facteurs à partir de leur produit est le problème difficile sur lequel repose la sécurité annoncée. Le même couple de clés intervient aussi dans la signature numérique, avec un rôle différent du chiffrement.
Définition
RSA est un algorithme asymétrique à clé publique, conçu en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman au Massachusetts Institute of Technology. Il utilise deux clés mathématiquement liées. La clé publique peut être diffusée ; la clé privée doit rester secrète. Pour chiffrer, un message est d'abord représenté par un entier compatible avec le module choisi.
Deux nombres premiers distincts, notés p et q, donnent le module n. La clé publique contient ce module et un exposant public e. L'exposant privé d est choisi pour inverser l'action de e dans l'arithmétique modulaire appropriée. Pour un entier-message m, le chiffrement produit un entier c, puis le déchiffrement retrouve m : et .
La difficulté de retrouver les deux facteurs premiers à partir d'un grand module fonde la sécurité décrite par la source : aucun algorithme efficace en temps polynomial n'est connu pour ce problème dans le cadre classique. RSA sert au chiffrement et à la signature numérique. Ces deux usages ne se réduisent pas à échanger mécaniquement les rôles « chiffrer » et « déchiffrer » : leur objectif et leurs opérations de contrôle diffèrent.
Un exemple, pas à pas
Voici un exemple volontairement minuscule, destiné au calcul et non à la sécurité. Les données sont les nombres premiers p = 61 et q = 53, l'exposant public e = 17 et l'entier-message m = 65.
1. Multipliez les deux nombres premiers pour obtenir le module n : .
2. Calculez le nombre d'entiers inversibles utilisé ici : . Le nombre 17 est premier avec 3120.
3. Choisissez l'exposant privé d comme inverse de 17 modulo 3120. La valeur d = 2753 convient, car .
4. Chiffrez l'entier-message 65 avec la clé publique formée de 3233 et 17 : . L'entier chiffré est donc c = 2790.
5. Déchiffrez 2790 avec l'exposant privé 2753 : . Le contrôle est refaisable : le résultat final est exactement l'entier-message 65, compris entre 0 et 3232.
En pratique
Pour envoyer une information confidentielle, l'expéditeur utilise la clé publique du destinataire. Le destinataire conserve la clé privée nécessaire au déchiffrement. Le critère visible est le besoin de secret pendant le transport.
Pour une signature numérique, le but change : il s'agit de permettre un contrôle public lié au détenteur de la clé privée, et non de cacher le contenu. Le critère est donc l'authentification et l'intégrité recherchées plutôt que la confidentialité.
Dans les deux cas, la clé publique peut circuler, tandis que la clé privée ne doit pas être transmise. Si deux personnes doivent partager le même secret de calcul, on se trouve dans un cadre symétrique, différent du principe RSA.
À ne pas confondre
RSA et chiffrement symétrique. RSA emploie une paire de clés aux rôles distincts ; un chiffrement symétrique repose sur un secret partagé. Si l'émetteur et le destinataire utilisent le même secret, ce n'est pas le mécanisme asymétrique de RSA.
Chiffrement et signature numérique. Le chiffrement vise à rendre un message illisible sans la clé ou le secret de déchiffrement approprié. La signature vise à fournir un contrôle public lié au signataire. Un contenu que tout le monde peut lire mais dont l'origine doit être contrôlée relève de la signature, pas du chiffrement confidentiel.
Multiplication et factorisation. Construire le module à partir de deux facteurs premiers est une multiplication. Retrouver ces deux facteurs à partir du seul module est une factorisation. Dans l'exemple, 61 × 53 donne 3233 ; le problème inverse part de 3233.
Limites et pièges
Un petit module ne protège rien. Dans l'exemple, 3233 se factorise en 61 × 53 avec des moyens élémentaires. Le symptôme est précisément la petitesse des facteurs. Il faut lire ces valeurs comme une démonstration arithmétique, jamais comme des paramètres de sécurité.
Le message doit appartenir au domaine du calcul. L'entier-message est pris entre 0 et n − 1. Avec n = 3233, la valeur charnière 3233 n'est pas un nouveau représentant : elle vaut 0 modulo 3233. Il faut encoder le message dans le domaine prévu avant l'opération RSA.
La difficulté n'est pas une impossibilité démontrée. La source affirme qu'aucun algorithme efficace connu ne factorise en temps polynomial un grand produit de deux nombres premiers. Elle n'affirme pas qu'un tel algorithme ne pourra jamais exister. Il faut conserver cette formulation conditionnelle.
La clé privée ne « chiffre » pas simplement une signature. Cette formule rapide masque la différence d'objectif entre confidentialité et authentification. Il faut raisonner selon l'usage — chiffrer ou signer — et vérifier l'opération attendue, plutôt que permuter deux verbes.
Pour aller plus loin
Le glossaire nombre premier précise la nature des deux facteurs qui servent à construire le module RSA.
La fiche Factorisation approfondit l'opération inverse dont la difficulté soutient le principe de sécurité présenté ici.
La fiche chiffrement replace RSA dans le problème général qui consiste à rendre une information illisible sans l'accès prévu.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres