Игрушечный RSA
Соберите RSA своими руками. Даны два простых числа p и q и открытая экспонента e, взаимно простая с φ = (p − 1)(q − 1). Открытый ключ — пара (N = p·q, e), секретный — число d, обратное к e по модулю φ. Найдите N и d и зашифруйте сообщения: шифр числа x — это xe mod N.
Настоящий RSA берёт простые числа длиной в тысячу бит и обязательно перемешивает сообщение со случайными байтами перед шифрованием; здесь числа маленькие, а схема — учебная. Но арифметика та же самая.
Вход
В первой строке p, q, e и число сообщений k (p, q — различные простые меньше 2³¹; 3 ≤ e < φ; 1 ≤ k ≤ 20 000). Во второй — k сообщений, целых чисел от 0 до N − 1.
Выход
В первой строке N и d (0 < d < φ). Дальше k строк — шифры сообщений по порядку.
Примеры
Пример 1
61 53 17 3 65 0 3232
3233 2753 2790 0 3232
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 5 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Как найти число, обратное к e по модулю φ? Подойдёт ли малая теорема Ферма, которой мы считали обратный в статье?
2Подсказка 2
Если вы пишете на Go: N бывает почти 2⁶², а x·x mod N требует перемножить два таких числа. Помещается ли произведение в 64 бита?
3Идея
Обратный элемент по модулю φ даёт расширенный алгоритм Евклида. Ферма здесь не годится: φ = (p−1)(q−1) — чётное и уж точно не простое. Шифрование — быстрое возведение в степень по модулю N. Почему расшифровка cd возвращает сообщение, объясняет теорема Эйлера: e·d = 1 + k·φ, и xed ≡ x (mod N).
4Разбор
Считаем N и φ, затем d расширенным Евклидом и приводим его в диапазон от 0 до φ − 1 (алгоритм может вернуть отрицательный коэффициент). Каждое сообщение возводим в степень e по модулю N.
В Python достаточно pow(x, e, N): целые сколь угодно длинные. В Go произведение двух остатков по модулю N ≈ 2⁶² занимает до 124 бит, поэтому умножаем через bits.Mul64 — она возвращает старшие и младшие 64 бита произведения, — и берём остаток через bits.Div64. Тот же приём работает в любом языке с 64-битными целыми.
Эталон на Python заодно проверяет, что cd mod N возвращает исходное сообщение: хороший способ убедиться, что d найдено верно.
4+Решение
5Сложность
O(log φ) на расширенный алгоритм и O(log e) умножений на сообщение — при e = 65 537 это 19 умножений: 17 возведений в квадрат и 2 домножения. Всего O(k log e).
6Типичные ошибки
- Обратный по Ферма. eφ−2 mod φ — обратный только для простого модуля. Ловится первым же примером.
- Переполнение в Go.
a * b % nдля 62-битных чисел молча теряет старшие биты, и шифры выходят неверными на больших тестах. - Отрицательный d. Расширенный Евклид может дать отрицательный коэффициент; его нужно привести по модулю φ.