Калькулятор RSA: ключи, шифрование, расшифровка и подпись

Как работает RSA

RSA — асимметричный алгоритм шифрования и подписи, предложенный в 1977 году Ривестом, Шамиром и Адлеманом. Он основан на том, что перемножить два больших простых числа легко, а разложить произведение на множители — практически невозможно.

1. Выбирают два больших простых числа p и q и вычисляют модуль n = p · q.
2. Вычисляют функцию Эйлера φ(n) = (p − 1)(q − 1).
3. Выбирают открытую экспоненту e, взаимно простую с φ(n), — обычно 65537.
4. Находят закрытую экспоненту d — обратный к e элемент по модулю φ(n): e · d ≡ 1 (mod φ(n)). Для этого применяют расширенный алгоритм Евклида.

Открытый ключ — пара (e, n), её можно публиковать. Закрытый ключ — d (и числа p, q), его хранят в секрете.

шифрование: c = m^e mod n; расшифровка: m = c^d mod n

подпись: s = m^d mod n; проверка: m = s^e mod n

Пример

p = 61, q = 53. Тогда n = 3233, φ(n) = 60 · 52 = 3120. Берём e = 17 — оно взаимно просто с 3120. Закрытая экспонента d = 2753, потому что 17 · 2753 = 46 801 = 15 · 3120 + 1. Сообщение m = 65 шифруется в c = 65¹⁷ mod 3233 = 2790, а 2790²⁷⁵³ mod 3233 снова даёт 65.

Почему RSA надёжен и когда — нет

Чтобы найти d, нужно знать φ(n), а для этого — разложить n на множители. Для модуля в 2048 бит (617 десятичных цифр) лучшие известные алгоритмы потребовали бы непосильного времени, поэтому 2048 бит — минимальная рекомендуемая длина ключа сегодня, а для долгосрочной защиты используют 3072–4096 бит.

Этот калькулятор — учебный. Ключи из 16–128 бит раскладываются на множители мгновенно, а «учебник RSA» без дополнения (padding) уязвим: одинаковые сообщения дают одинаковые шифротексты, а малые сообщения можно восстановить. В реальных системах используют схемы OAEP для шифрования и PSS для подписи, а подписывают не само сообщение, а его хеш.

Функция Кармайкла

Вместо φ(n) можно использовать λ(n) = НОК(p − 1, q − 1). Полученная по ней экспонента d меньше и работает точно так же; так поступают современные стандарты. Калькулятор показывает оба варианта.

Текстовые сообщения

В режиме «Текст» строка переводится в байты UTF-8, а байты — в одно большое число. Оно должно быть меньше n, поэтому для текста нужен ключ подходящей длины: каждый байт требует 8 бит модуля.