Калькулятор RSA
Выберите два простых числа p и q, открытую экспоненту e и сообщение — число m меньше n. Калькулятор построит пару ключей, найдёт d как обратное к e по модулю φ(n), зашифрует m в c и расшифрует обратно — удобно для проверки задач по RSA.
Работает в браузере: всё, что вы вводите, никуда не отправляется.
Как пользоваться
- Введите два разных простых числа p и q. С небольшими, вроде 61 и 53, числа остаются обозримыми.
- Введите открытую экспоненту e — больше 1, меньше φ(n) и взаимно простую с φ(n).
- При желании введите сообщение m — целое число меньше n. Калькулятор покажет закрытую экспоненту d, шифротекст c и результат расшифровки, который должен совпасть с m.
Как работает RSA
- Ключи. n = p × q, φ(n) = (p − 1)(q − 1). Выбирают e с НОД(e, φ(n)) = 1 и вычисляют d = e⁻¹ mod φ(n). Открытый ключ — (e, n), закрытый — (d, n).
- Шифрование. c = mᵉ mod n.
- Расшифровка. m = cᵈ mod n. Это работает, потому что e × d = 1 + kφ(n), а по теореме Эйлера m^φ(n) ≡ 1 (mod n).
Большие степени считаются быстрым возведением в квадрат, поэтому даже 64-битные простые обрабатываются мгновенно. p и q проверяются детерминированным тестом Миллера — Рабина.
Пример
p = 61, q = 53, e = 17, m = 65.
- n = 61 × 53 = 3233, модуль длиной 12 бит.
- φ(n) = 60 × 52 = 3120; λ(n) = НОК(60, 52) = 780.
- d = 17⁻¹ mod 3120 = 2753; строка проверки: 17 × 2753 mod 3120 = 1.
- Открытый ключ (17; 3233), закрытый — (2753; 3233).
- c = 65¹⁷ mod 3233 = 2790, а 2790²⁷⁵³ mod 3233 возвращает 65.
Советы
- Сначала e, потом проверка. На практике обычно берут 65537, но с маленькими p и q оно часто больше φ(n) — тогда подойдут 3, 7 или 17.
- Сообщение — это число. Текст сначала переводят в числа (например, коды символов), и каждое число должно быть меньше n.
- d вручную находят расширенным алгоритмом Евклида; калькулятор расширенного алгоритма Евклида покажет все шаги поиска обратного элемента.
Частые вопросы
Как вычисляется закрытый ключ d?
d — обратный элемент к e по модулю φ(n), то есть число, для которого e × d ≡ 1 (mod φ(n)). Его находят расширенным алгоритмом Евклида. Для p = 61, q = 53 и e = 17 φ(n) = 3120 и d = 2753, потому что 17 × 2753 = 46 801 = 15 × 3120 + 1.
Почему e должно быть взаимно простым с φ(n)?
Только тогда у e есть обратный элемент по модулю φ(n). Если у e и φ(n) есть общий делитель, d не существует и однозначно расшифровать сообщение нельзя. Калькулятор в таком случае называет общий делитель.
Чем φ(n) отличается от λ(n)?
φ(n) = (p − 1)(q − 1) — функция Эйлера, λ(n) = НОК(p − 1, q − 1) — функция Кармайкла, она делит φ(n). Для поиска d подходят обе; с λ получается меньшее d (413 вместо 2753 в примере), его используют современные стандарты.
Можно ли так шифровать настоящие данные?
Нет. Числа здесь крошечные, дополнения нет, поэтому n легко разложить, а одинаковые сообщения видны сразу. Это инструмент для учёбы и проверки домашних заданий; для реального шифрования нужна проверенная библиотека и ключи от 2048 бит.
Почему сообщение должно быть меньше n?
Шифрование идёт по модулю n, поэтому m и m + n дают одинаковый шифротекст. Сообщение, не меньшее n, после расшифровки нельзя отличить от меньшего.