Module n
φ(n) (p − 1)(q − 1)
Clé publique (e, n)
Clé privée d e · d mod φ(n) = 1

Les clés

    Comment trouver d : l'algorithme d'Euclide étendu

    Chaque ligne divise les deux lignes au-dessus d'elle. Dans la ligne de reste 1, la dernière colonne donne d (ajoutez φ(n) s'il est négatif).

    QuotientResteCoefficient de e

    Le message

    Caractère Code m Résultat

    Envoyé sur le réseau

    BitCarréMultiplier par m

    Casser la clé

    Opération

    Plus d'informations sur RSA

    Démo du chiffrement RSA

    RSA permet à n'importe qui de verrouiller un message avec votre clé publique, tandis que vous seul pouvez l'ouvrir avec votre clé privée. Derrière, il n'y a que quelques lignes d'arithmétique scolaire : deux nombres premiers, une multiplication, un reste et un inverse astucieux. Construisez une paire de clés à partir de nombres premiers de votre choix, chiffrez et déchiffrez un message caractère par caractère, signez-le pour que chacun puisse vérifier qu'il vient de vous, puis jouez l'attaquant et factorisez n pour comprendre pourquoi les vraies clés ont besoin de centaines de chiffres. Choisissez deux nombres premiers p et q, ou appuyez sur Nouveaux nombres premiers. L'application construit la clé publique (e, n) et la clé privée d, et montre comment l'algorithme d'Euclide étendu trouve d. Tapez un message : chaque caractère est chiffré avec la clé publique et déchiffré avec la clé privée. Cliquez sur une ligne pour voir la puissance calculée par élévation au carré répétée. Passez à Signer pour signer plutôt avec la clé privée, et appuyez sur Factoriser n pour voir à quelle vitesse les petites clés tombent.

    Comment ça marche

    1. Saisissez deux nombres premiers p et q, ou choisissez une taille et appuyez sur Nouveaux nombres premiers ; l'application calcule n, φ(n), e et d, et montre comment d est trouvé.
    2. Tapez un message et choisissez Chiffrer ou Signer. Chaque caractère est transformé en nombre et élevé à une puissance mod n ; cliquez sur une ligne pour voir l'élévation au carré répétée.
    3. Appuyez sur Factoriser n pour laisser Eve décomposer n en ses deux nombres premiers et retrouver la clé privée.

    Comment fonctionnent les clés

    Multipliez deux nombres premiers : n = p × q. Avec p = 61 et q = 53, n = 3233. Le nombre φ(n) = (p − 1)(q − 1) = 3120 compte les nombres inférieurs à n qui n'ont aucun facteur commun avec lui, et seul quelqu'un qui connaît p et q peut le calculer. Choisissez e = 17, qui n'a aucun facteur commun avec 3120, et trouvez d tel que e × d dépasse de 1 un multiple de φ(n) : ici d = 2753, car 17 × 2753 = 46801 = 15 × 3120 + 1. Publiez (e, n) et gardez d. Un message m devient c = mᵉ mod n, et le théorème d'Euler garantit que cᵈ mod n redonne m.

    Pourquoi il est difficile à casser

    Tout ce dont un attaquant a besoin est caché dans les facteurs de n. Avec n = 3233, ce n'est pas une protection : en essayant les diviseurs impairs, on trouve 53 après environ deux douzaines d'essais. Mais l'effort croît avec la racine carrée de n. Un module de 2048 bits compte environ 617 chiffres, et aucune méthode connue, sur aucun ordinateur existant aujourd'hui, ne peut le factoriser en un temps utile. Signer revient à faire tourner RSA à l'envers : s = mᵈ mod n ne peut être produit qu'avec la clé privée, et chacun peut vérifier que sᵉ mod n redonne m.

    Questions fréquemment posées

    Pourquoi personne ne peut-il calculer d à partir de la clé publique ?

    Pour trouver d, il faut φ(n) = (p − 1)(q − 1), et pour obtenir φ(n), il faut p et q. Les retrouver à partir de n revient à le factoriser, et pour des nombres de plusieurs centaines de chiffres, aucune méthode rapide n'est connue. La démo vous permet de factoriser des clés miniatures en une fraction de seconde, ce qui montre précisément pourquoi les vraies clés sont si grandes.

    Pourquoi le message est-il chiffré caractère par caractère ?

    Parce que les clés de la démo sont petites : RSA ne peut chiffrer qu'un nombre inférieur à n. Avec n = 3233, chaque code de caractère tient, mais pas une phrase entière. Le vrai RSA utilise un module de 2048 bits ou plus, complète le message par des octets aléatoires pour que le même message ne soit jamais chiffré deux fois de la même façon et, en pratique, ne chiffre qu'une courte clé destinée à un chiffrement plus rapide comme AES.

    À quoi sert l'élévation au carré répétée ?

    Elle calcule d'énormes puissances comme m²⁷⁵³ mod n sans jamais écrire le nombre gigantesque. Écrivez l'exposant en binaire, puis parcourez ses bits : élevez le résultat courant au carré pour chaque bit et multipliez-le par m pour chaque 1, en prenant le reste mod n à chaque fois. Un exposant de 2048 bits ne demande qu'environ 2048 élévations au carré.

    Quelle est la différence entre chiffrer et signer ?

    Chiffrer utilise la clé publique du destinataire, de sorte que seule la clé privée du destinataire peut annuler l'opération. Signer utilise la clé privée de l'expéditeur, de sorte que chacun peut vérifier la signature avec la clé publique de l'expéditeur et savoir que le message vient du détenteur de cette clé et n'a pas été modifié.

    Mon message est-il envoyé quelque part ?

    Non. Tout est calculé dans votre navigateur, et vos nombres premiers et votre message restent dans le stockage local de ce navigateur.

    Prêt à l'essayer ?

    Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

    Aller à l'éditeur