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. Представники поза межами діапазону відхиляються, а не зводяться мовчки.
