Math
RSA sur de petits nombres
Un message traverse deux puissances modulaires sur une table de bois et de laiton. Exécutez les étapes entières, explorez la permutation et cherchez un diviseur avec un compteur exact.
Ce qui se passe
Un message traverse deux puissances modulaires sur une table de bois et de laiton. Exécutez les étapes entières, explorez la permutation et cherchez un diviseur avec un compteur exact.
Le bois et le laiton sont une illustration, pas une machine à chiffrer historique. Glissez avec le bouton droit pour tourner l’atelier.
Arithmétique pédagogique sur de petits entiers. Sans encodage OAEP/PSS ni format de message sécurisé. La division d’essai ne mesure pas la sécurité du vrai RSA.
Équations du module
Équations clé de manuel p = 61, q = 53 : n = 3233, phi = (p−1)(q−1) = 3120, e = 17, d = e^(−1) mod phi = 2753, e·d mod phi = 1 65 -> 2790 -> 65 le chiffrement est une PERMUTATION de Z_n pour des nombres premiers distincts p,q et gcd(e, phi) = 1 : m -> m^e donne exactement n images distinctes (3233 sur 3233), et TOUT message revient y compris les 113 messages qui ont un facteur commun avec n - c'est le théorème des restes chinois, et NON le théorème d'Euler, qui n'en dit rien messages invariants par le chiffrement : exactement (1 + gcd(e−1, p−1))·(1 + gcd(e−1, q−1)) (61, 53, 17) -> 25 ; (11, 13, 7) -> 21 ; (17, 19, 5) -> 15 ; (31, 37, 11) -> 33 ; jamais moins de quatre, et c'est de l'arithmétique, non un défaut nombre de divisions d'essai jusqu'à trouver un facteur (ce n'est pas la meilleure attaque de factorisation connue) : n = 3233 -> 52 en simple, 16 sur les nombres premiers (jusqu'au facteur 53) n = 1022117 -> 1008 en simple, 169 sur les nombres premiers (jusqu'au facteur 1009) sqrt(n) n'est qu'une échelle de référence pour la division d'essai ; le nombre d'étapes dépend du plus petit facteur. Ces nombres ne mesurent pas la sécurité réelle de RSA. Le RSA brut est pédagogique ; en pratique, le chiffrement/la signature emploient des schémas tels que OAEP/PSS. Domaine des clés pédagogiques : nombres premiers distincts p,q ; 3 <= e < n ; gcd(e,phi(n)) = 1 ; 0 <= m,c < n. Les représentants hors intervalle sont rejetés, et non réduits silencieusement.
