La banque en ligne, les connexions et les messageries que nous utilisons chaque jour sont toutes chiffrées. Au cœur de ce chiffrement se trouve un fait mathématique très simple : multiplier deux nombres premiers est facile, mais décomposer le produit en ces deux nombres premiers est extrêmement difficile.
Vérifier que 15 = 3×5 ne prend aucun temps. Dans l'autre sens — « quelle est la décomposition en facteurs premiers de 15 ? » — c'est encore facile. Les ennuis commencent quand les nombres deviennent grands. Multiplier deux nombres premiers pour obtenir un nombre de plus de 600 chiffres ne prend presque aucun temps à un ordinateur, mais retrouver à partir de cet énorme nombre les deux nombres premiers de départ est en pratique impossible, même pour un superordinateur. Le chiffrement RSA utilise justement cette asymétrie — « facile à multiplier, difficile à factoriser » — comme clé.
Tu peux tester l'idée avec de petits nombres. Prends les nombres premiers p=5 et q=11 : n=p×q=55. Considère un message comme un seul nombre (m) : tu peux le chiffrer avec une clé publique (e), puis le déchiffrer pour retrouver le nombre de départ avec une clé secrète (d) que toi seul connais. Tout le monde peut voir les n et e utilisés pour chiffrer, mais retrouver le message d'origine à partir d'eux exige de factoriser n pour trouver p et q. Notre exemple (n=55) se résout instantanément en 5×11, mais le vrai RSA utilise un n de plus de 600 chiffres : on estime que le factoriser prendrait plus longtemps que l'âge de l'Univers, même si tous les ordinateurs existant aujourd'hui s'y mettaient ensemble.
RSA a été créé en 1977 par Rivest, Shamir et Adleman (RSA reprend les initiales de leurs noms). Le fait que « la difficulté de la factorisation n'a jamais été démontrée mathématiquement, mais qu'en pratique personne n'a jamais trouvé de méthode rapide » est, en somme, ce qui protège aujourd'hui notre sécurité en ligne.
Il existe aussi d'autres types de chiffrement. La cryptographie sur les courbes elliptiques (ECC) repose sur un autre problème mathématique difficile — le problème du logarithme discret sur une courbe elliptique — au lieu de la factorisation. Elle atteint une sécurité comparable avec une clé plus courte que RSA, c'est pourquoi elle est très utilisée dans les smartphones et les portefeuilles de cryptomonnaies. Une nouvelle menace se profile aussi : les ordinateurs quantiques. On sait qu'un algorithme quantique, l'algorithme de Shor, peut en théorie factoriser beaucoup plus vite ; dès qu'existeront de grands ordinateurs quantiques stables, RSA comme ECC pourraient devenir vulnérables. C'est pourquoi la « cryptographie post-quantique », fondée sur de nouveaux problèmes mathématiques qui restent difficiles même pour les ordinateurs quantiques, est un domaine de recherche très actif : l'Institut national des normes et de la technologie des États-Unis (NIST) a publié en 2024 les premières normes officielles de cryptographie post-quantique. Sur notre page d'activité, tu peux ressentir toi-même la difficulté de la factorisation avec de petits nombres, et suivre pas à pas le chiffrement et le déchiffrement en générant ta propre clé RSA.