ИнформатикаТеория · RSA
SilverTests.ru · УчебникМодульная арифметика: нахождение ключа d
Алгоритм RSA
Формула для закрытого ключа d
1Что дано в задаче
Даны два простых числа \(p\) и \(q\), а также число \(e\) (открытая экспонента). Нужно найти число \(d\) (закрытая экспонента), удовлетворяющее условию:
\( (d \cdot e) \bmod f(n) = 1 \), где \( f(n) = (p - 1)(q - 1) \)
Операция % (или mod) — остаток от деления. Запись выше означает: произведение \(d \cdot e\) при делении на \(f(n)\) даёт остаток 1. Другими словами, \(d \cdot e = k \cdot f(n) + 1\) для некоторого целого \(k\).
2Алгоритм решения
Шаг 1. Вычислить \(f(n) = (p-1) \cdot (q-1)\).
Шаг 2. Найти наименьшее \(d\), при котором \((d \cdot e) \bmod f(n) = 1\).
Шаг 3. Все остальные подходящие значения получаются прибавлением \(f(n)\):
\( d, \quad d + f(n), \quad d + 2f(n), \quad d + 3f(n), \quad \ldots \)
Способ 1 — прямой перебор d
Подставляем \(d = 1, 2, 3, \ldots\) и считаем \((d \cdot e) \bmod f(n)\), пока не получим 1. Надёжный способ, но при больших \(f(n)\) может быть долгим.
Способ 2 — перебор множителя k (быстрее)
Из равенства \(d \cdot e = k \cdot f(n) + 1\) выражаем:
\( d = \dfrac{k \cdot f(n) + 1}{e} \)
Перебираем \(k = 0, 1, 2, \ldots\) и берём первое \(k\), при котором выражение делится нацело. Как правило, нужное \(k\) находится очень быстро.
3Разбор задачи из демоварианта
\(p = 5,\ q = 7,\ e = 11\). Найти наибольшее \(d < 40\).
Шаг 1. \(f(n) = (5-1)(7-1) = 4 \cdot 6 = 24\).
Шаг 2. Ищем способом 2: \(d = (24k + 1) \,/\, 11\).
| k |
24k + 1 |
÷ 11 |
|
| 0 |
1 |
0,09… |
— |
| 1 |
25 |
2,27… |
— |
| 2 |
49 |
4,45… |
— |
| 3 |
73 |
6,63… |
— |
| 4 |
97 |
8,81… |
— |
| 5 |
121 |
11 |
✓ |
Наименьшее \(d = 11\).
Шаг 3. Все подходящие \(d\): 11, 35, 59, 83, … (шаг 24). Наибольшее при \(d < 40\): 35.
Проверка: 35 × 11 = 385 = 16 × 24 + 1. Остаток от деления на 24 равен 1 ✓
4Типичные вариации вопросов
| Формулировка |
Что делать |
| Наименьшее d |
Найти первое d (способом 1 или 2) |
| Наибольшее d < X |
Первое d, затем прибавлять f(n), пока < X |
| d ближайшее к X |
Найти два соседних d вокруг X, взять ближнее |
| Сколько d в [A; B] |
Перечислить d₀, d₀+f(n), d₀+2f(n)… подсчитать |
| d в [1; f(n)] |
Ровно одно значение — наименьшее d |
Самопроверка: всегда умножайте найденное \(d\) на \(e\) и проверяйте, что остаток от деления на \(f(n)\) равен 1. Занимает 5 секунд и страхует от арифметических ошибок.