Утилиты · Современная криптография
RSA: учебный калькулятор
RSA на маленьких числах: простые p и q, ключи, шифрование и расшифровка, разложение n на множители.
Считается в вашем браузере. Текст никуда не отправляется.
Как пользоваться
Наверху — открытый ключ: числа n и e. Если поле d пустое, утилита сама раскладывает n на два простых множителя (методом ро Полларда), считает φ(n) = (p − 1)(q − 1) и закрытую экспоненту d. Для чисел до 22 цифр это происходит сразу, для бóльших нажмите «Разложить n» и наберитесь терпения — именно в этом и состоит защита RSA.
В режиме «Расшифровать» вставьте шифровку — числа через пробел, запятую или с новой строки; лишние скобки не мешают. Каждое число c превращается в m = cd mod n. Ниже те же числа показаны буквами: 1 — А, 2 — Б, … 33 — Я (алфавит с ё) или A = 1 … Z = 26. Таблица под результатом показывает каждый шаг.
В режиме «Зашифровать» можно ввести слово — его буквы превратятся в номера и будут зашифрованы по одной, — или сами числа. Каждое число должно быть меньше n.
Свои ключи
Блок «Сделать ключи из двух простых» строит пару ключей из p, q и e и проверяет, что всё правильно: оба числа простые и разные, e не имеет общих делителей с φ(n). Кнопки «Случайные простые» подбирают p и q нужной длины. Последний блок показывает расширенный алгоритм Евклида, которым из e и φ(n) получают d.
Частые вопросы
Почему шифровать по одной букве плохо?
Одинаковые буквы дают одинаковые числа, и шифр превращается в простую замену — её ломает частотный анализ. Настоящий RSA шифрует большие числа со случайной «набивкой» (схема OAEP), а чаще всего им шифруют не сам текст, а ключ для AES.
Насколько большие числа в настоящем RSA?
Сегодня n обычно 2048 или 3072 бита — больше 600 цифр. Самое большое разложенное RSA-число из открытого конкурса, RSA-250, имеет 250 цифр; на его разложение в 2020 году ушло около 2700 лет процессорного времени.
Что такое e = 65537?
Самая популярная открытая экспонента в реальных ключах: в двоичной записи это единица, пятнадцать нулей и ещё единица, поэтому возводить в эту степень быстро. Для маленьких учебных n она часто слишком велика, поэтому здесь по умолчанию 17.
Подробно о том, почему всё это работает, — в уроке об открытом ключе. Все вычисления выполняются в браузере.