Math
RSA на маленьких числах
Сообщение проходит две степени по модулю на столе из дерева и латуни. Выполняйте целочисленные шаги, исследуйте перестановку и ищите делитель с точным счётчиком.
Что происходит
Сообщение проходит две степени по модулю на столе из дерева и латуни. Выполняйте целочисленные шаги, исследуйте перестановку и ищите делитель с точным счётчиком.
Дерево и латунь — иллюстрация, а не историческая шифровальная машина. Правая кнопка вращает установку.
Учебная арифметика малых чисел. Нет кодирования OAEP/PSS и защищённого формата сообщений. Пробное деление не измеряет стойкость настоящего RSA.
Уравнения модуля
Уравнения учебный ключ 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 шифрование есть ПЕРЕСТАНОВКА Z_n для различных простых p,q и gcd(e, phi) = 1: m -> m^e даёт ровно n различных образов (3233 из 3233), и КАЖДОЕ сообщение возвращается включая 113 сообщений, имеющих общий множитель с n - это китайская теорема об остатках, а НЕ теорема Эйлера, которая о них ничего не говорит сообщения, шифруемые в самих себя: ровно (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; никогда меньше четырёх, и это арифметика, а не изъян число пробных делений до нахождения множителя (это не лучшая известная атака факторизации): n = 3233 -> 52 при переборе всех чисел, 16 при переборе простых (до множителя 53) n = 1022117 -> 1008 при переборе всех чисел, 169 при переборе простых (до множителя 1009) sqrt(n) - лишь ориентир масштаба для пробного деления; числа зависят от наименьшего множителя. Эти числа не измеряют реальную стойкость RSA. Чистый RSA учебный; настоящее шифрование/подписи используют схемы вроде OAEP/PSS. Область учебного ключа: различные простые p,q; 3 <= e < n; gcd(e,phi(n)) = 1; 0 <= m,c < n. Представители вне диапазона отвергаются, а не молча приводятся.
