Ответы на контрольные вопросы
1. Почему числа p и q в RSA должны быть простыми и различными?
· Простыми — чтобы легко вычислить функцию Эйлера φ(n) = (p-1)(q-1). Для составных чисел её вычисление требует факторизации, что сложно.
· Различными — если p = q, то n = p², и φ(n) = p(p-1). Зная n, злоумышленник легко извлекает √n = p и получает φ(n), а значит и d. Кроме того, для n = p² снижается стойкость.
2. Почему сообщение M должно быть меньше модуля n?
Потому что операция M^e mod n определена для M < n. Если M ≥ n, то при расшифровании мы получим M mod n, а не исходное M — информация будет потеряна. На практике сообщение разбивают на блоки, каждый из которых < n.
3. Для чего в RSA используется функция Эйлера?
Функция Эйлера φ(n) определяет количество чисел, взаимно простых с n и меньших n. Она нужна для:
· Выбора e, взаимно простого с φ(n);
· Вычисления d из условия e*d ≡ 1 mod φ(n).
Это следует из теоремы Эйлера: M^φ(n) ≡ 1 mod n для НОД(M, n) = 1, что гарантирует корректность расшифрования.
4. Как с помощью расширенного алгоритма Евклида находится d?
Расширенный алгоритм Евклида для чисел e и φ(n) находит такие x и y, что:
e*x + φ(n)*y = НОД(e, φ(n)) = 1
Отсюда e*x ≡ 1 mod φ(n), значит x — это и есть искомая секретная экспонента d. Если x < 0, к нему прибавляют φ(n), чтобы получить положительное значение в диапазоне [0, φ(n)-1].
5. В чём основная вычислительная сложность для злоумышленника?
Злоумышленник знает открытый ключ (e, n), но не знает p и q. Чтобы найти d, ему нужно знать φ(n) = (p-1)(q-1), а для этого — разложить n на простые множители (задача факторизации). Для больших n (2048 бит и более) лучшие известные алгоритмы (общий метод решета числового поля) требуют экспоненциального времени. Именно на сложности факторизации больших чисел и основана криптостойкость RSA.
