Как сгенерировать ключи RSA: пример на малых числах

Дано: простые числа $p = 43$ и $q = 59$, открытая экспонента $e = 13$, сообщение $m = 1234$. Найти: открытый и закрытый ключи RSA, шифртекст и проверку расшифровкой.

Пара ключей собирается из четырёх чисел: модуль $n = pq$, значение функции Эйлера $\varphi(n) = (p-1)(q-1)$, открытая экспонента $e$ и обратная к ней по модулю $\varphi(n)$ закрытая экспонента $d$. Ответ: открытый ключ $(2537,\ 13)$, закрытый ключ $(2537,\ 937)$, шифртекст $c = 2391$. Калькулятор сверху пересчитает всю пару под другие простые и другое сообщение, ниже - решение по шагам.

Решение по шагам

Шаг 1. Модуль. Перемножаем простые:

$$n = pq = 43 \cdot 59 = 2537.$$

Модуль публикуется открыто, а вот сами множители 43 и 59 с этого момента становятся секретом: именно из них считается всё остальное.

Шаг 2. Значение функции Эйлера. Для произведения двух различных простых оно считается по формуле:

$$\varphi(n) = (p-1)(q-1) = 42 \cdot 58 = 2436.$$

Это число знает только владелец ключа. Тот, кто видит лишь $n = 2537$, посчитать $\varphi(n)$ не может, не разложив модуль на множители.

Шаг 3. Проверка открытой экспоненты. Экспонента $e$ годится, если она взаимно проста с $\varphi(n)$, то есть $\gcd(e, \varphi(n)) = 1$. Прогоняем алгоритм Евклида для пары 2436 и 13:

$$\begin{aligned} 2436 &= 187 \cdot 13 + 5, \\ 13 &= 2 \cdot 5 + 3, \\ 5 &= 1 \cdot 3 + 2, \\ 3 &= 1 \cdot 2 + 1, \\ 2 &= 2 \cdot 1 + 0. \end{aligned}$$

Последний ненулевой остаток равен единице, значит $e = 13$ подходит. Подробный разбор самого алгоритма с делениями и коэффициентами Безу лежит в разборе как найти НОД двух чисел, здесь он нужен как проверка.

Шаг 4. Закрытая экспонента. Разворачиваем цепочку делений снизу вверх, выражая единицу через 13 и 2436:

$$\begin{aligned} 1 &= 3 - 1 \cdot 2 = 3 - (5 - 3) = 2 \cdot 3 - 5, \\ &= 2 \cdot (13 - 2 \cdot 5) - 5 = 2 \cdot 13 - 5 \cdot 5, \\ &= 2 \cdot 13 - 5 \cdot (2436 - 187 \cdot 13) = 937 \cdot 13 - 5 \cdot 2436. \end{aligned}$$

Коэффициент при 13 и есть искомое: $d = 937$. Проверка занимает строчку: $13 \cdot 937 = 12181 = 5 \cdot 2436 + 1$, то есть $ed \equiv 1 \pmod{2436}$.

Шаг 5. Шифрование. Шифртекст считается как $c = m^e \bmod n$. Возводить 1234 в тринадцатую степень целиком нельзя - число не влезет ни в какой калькулятор, поэтому берём последовательные квадраты по модулю 2537:

Показатель раскладывается в сумму степеней двойки: $13 = 8 + 4 + 1$, поэтому перемножаем три остатка из таблицы:

$$c = 812 \cdot 2159 \cdot 1234 \bmod 2537 = 41 \cdot 1234 \bmod 2537 = 2391.$$

Техника подробно разобрана в задаче как быстро возвести в степень - без неё ручной счёт в RSA невозможен.

Шаг 6. Проверка расшифровкой. Расшифровка устроена симметрично: $m = c^d \bmod n$. Показатель 937 в двоичной записи равен 1110101001, то есть девять возведений в квадрат и пять домножений - четырнадцать умножений по модулю. Результат: $2391^{937} \bmod 2537 = 1234$, исходное число восстановилось.

Ответ. Открытый ключ $(n, e) = (2537,\ 13)$, закрытый ключ $(n, d) = (2537,\ 937)$, шифртекст сообщения 1234 равен 2391, обратное преобразование даёт исходное 1234.

Формула: почему расшифровка возвращает исходное число

Всё держится на одном условии, наложенном при выборе $d$:

$$ed \equiv 1 \pmod{\varphi(n)}, \qquad \text{то есть} \qquad ed = 1 + k\varphi(n).$$

В нашем случае $k = 5$: произведение 12181 ровно на единицу больше, чем пять раз по 2436. Подставим это в цепочку преобразований и посмотрим, что происходит с сообщением:

$$(m^e)^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot \left(m^{\varphi(n)}\right)^{k}.$$

Дальше работает теорема Эйлера: если $m$ и $n$ взаимно просты, то $m^{\varphi(n)} \equiv 1 \pmod{n}$. Скобка обращается в единицу, и справа остаётся само $m$. Никакой магии в схеме нет: закрытая экспонента просто «доводит» показатель до величины, кратной $\varphi(n)$, плюс один.

Отдельно стоит редкий случай, когда сообщение делится на $p$ или на $q$. Тогда теорема Эйлера напрямую не применима, но равенство всё равно выполняется - это проверяется малой теоремой Ферма по каждому простому множителю отдельно и китайской теоремой об остатках. Практического значения этот случай не имеет: угадать кратное $p$ сообщение не проще, чем разложить модуль.

Как выбирать открытую экспоненту

Требование к $e$ ровно одно: $1 < e < \varphi(n)$ и $\gcd(e, \varphi(n)) = 1$. Если общий делитель есть, обратного элемента не существует, и расширенный алгоритм Евклида честно вернёт вместо единицы этот делитель. Переключи график калькулятора в режим выбора экспоненты: зелёные столбики - кандидаты с НОД, равным единице, оранжевые не подходят.

Для $\varphi(n) = 2436 = 2^2 \cdot 3 \cdot 7 \cdot 29$ отпадают все чётные числа, а также кратные 3, 7 и 29. Поэтому популярное $e = 3$ здесь тоже пришлось бы отбросить: тройка делит 2436. Число 13 в этот список не попадает и годится.

На практике экспоненту не ищут перебором, а берут одну из двух: $e = 65537 = 2^{16} + 1$ почти всегда, реже $e = 3$. Причина простая: в двоичной записи 65537 всего две единицы, поэтому шифрование стоит семнадцать умножений независимо от длины ключа. А вот $d$ маленьким быть не должен - при $d < n^{1/4}$ ключ восстанавливается атакой Винера за считанные секунды.

Что меняется на настоящих ключах

Числа 43 и 59 годятся только для тетради. В боевом ключе $p$ и $q$ - случайные простые примерно по 1024 бита, чтобы модуль вышел на 2048 бит. Ищут их так: генерируют случайное нечётное число нужной длины и проверяют вероятностным тестом, а перебор делителей до корня, описанный в разборе как проверить число на простоту, для таких размеров не годится совсем.

Второе отличие - вместо $\varphi(n)$ чаще берут функцию Кармайкла $\lambda(n) = \operatorname{lcm}(p-1, q-1)$. Условие $ed \equiv 1 \pmod{\lambda(n)}$ слабее, поэтому $d$ ищется в меньшем диапазоне и в среднем выходит короче, а расшифровка быстрее. Для нашей пары $\lambda(2537) = \operatorname{lcm}(42, 58) = 1218$, и обратный к 13 по этому модулю - то же самое число 937: оно и так меньше 1218, выигрыша на учебных числах не видно. Третье - сообщение никогда не шифруют «как есть»: перед возведением в степень к нему добавляют случайное дополнение по схеме OAEP, иначе одинаковые сообщения давали бы одинаковые шифртексты.

Стойкость же целиком сводится к сложности разложения модуля. Зная $p$ и $q$, любой посчитает $\varphi(n)$ и повторит шаг 4 - наш $n = 2537$ раскладывается перебором за доли секунды, о чём подробно в разборе как найти простые множители. Для 2048 бит классических методов не хватает, но квантовый алгоритм Шора сводит факторизацию к поиску периода и решает задачу за полиномиальное время - поэтому RSA и считают схемой с ограниченным сроком годности.

До появления асимметричной криптографии стойкость искали в длине ключа: у шифра Виженера ключ-слово растягивали на весь текст, и именно повторяемость ключа его и погубила.

Частые ошибки

• Считают $\varphi(n)$ от произведения, а не от множителей. Формула $\varphi(n) = (p-1)(q-1)$ работает только для двух различных простых. Брать $n - 1 = 2536$ вместо 2436 - самая частая ошибка в контрольных, и дальше всё расчётное дерево уезжает.
• Берут $p = q$. При совпадении множителей формула другая: $\varphi(p^2) = p(p-1)$, а сам модуль раскладывается извлечением квадратного корня. Простые обязаны быть разными.
• Ищут $d$ по модулю $n$ вместо $\varphi(n)$. Обратный элемент к 13 берётся по модулю 2436, а не 2537. Число получится другое, и проверка расшифровкой не сойдётся.
• Не приводят отрицательный коэффициент. Расширенный алгоритм Евклида часто выдаёт $d$ со знаком минус; к нему нужно прибавить $\varphi(n)$, чтобы попасть в диапазон от 1 до $\varphi(n)$.
• Возводят в степень без приведения по модулю. Число $1234^{13}$ имеет 41 знак. Остаток берут после каждого умножения, иначе даже учебный пример не считается.
• Шифруют сообщение, большее модуля. Условие $m < n$ обязательно: при $m \ge n$ расшифровка вернёт остаток $m \bmod n$, а не исходное число. Длинные сообщения режут на блоки.

FAQ

Какие числа входят в открытый ключ, а какие в закрытый? Открытый ключ - пара $(n, e)$, её можно публиковать. Закрытый - пара $(n, d)$. Простые $p$, $q$ и значение $\varphi(n)$ уничтожают или хранят вместе с закрытым ключом: по любому из них $d$ восстанавливается за один прогон алгоритма Евклида.

Обязательно ли $e$ должно быть простым числом? Нет. Требуется только взаимная простота с $\varphi(n)$. Само $e$ может быть составным, например $e = 25$, если $\varphi(n)$ не делится на 5. Простые значения берут потому, что для них проверка НОД сводится к одному делению.

Почему нельзя вычислить $d$, зная только открытый ключ? Для поиска $d$ нужно $\varphi(n)$, а для него - разложение $n$ на множители. Обратная задача к умножению двух больших простых чисел и есть узкое место: перемножить их легко, разложить произведение обратно - вычислительно тяжело.

Что будет, если два человека случайно возьмут одно и то же простое? Их модули $n_1$ и $n_2$ получат общий делитель, и алгоритм Евклида найдёт его мгновенно, вскрыв оба ключа. Такие коллизии в реальных наборах ключей находили массово, поэтому качество генератора случайных чисел здесь важнее длины ключа.

Коротко

1. Взять два различных простых $p$ и $q$ и посчитать модуль $n = pq$: $43 \cdot 59 = 2537$.
2. Найти значение функции Эйлера $\varphi(n) = (p-1)(q-1) = 42 \cdot 58 = 2436$ и держать его в секрете.
3. Выбрать открытую экспоненту $e$ так, чтобы $\gcd(e, \varphi(n)) = 1$: для $e = 13$ алгоритм Евклида даёт единицу.
4. Вычислить закрытую экспоненту как обратный элемент: $d = e^{-1} \bmod \varphi(n) = 937$, проверка $13 \cdot 937 = 5 \cdot 2436 + 1$.
5. Шифровать как $c = m^e \bmod n$, расшифровывать как $m = c^d \bmod n$: сообщение 1234 превращается в 2391 и обратно.