Факторизация при известном значении р{т

Наиболее простой задачей является определение простых делителей числа т по известным значениям т и р (т).

Поскольку ip{m) — (р — l)(g — 1) — т — (p + q) + 1, то мы можем рассмотреть систему уравнений относительно неизвестных целых чисел р и q

Согласно теореме Виета получаем, что искомые значения р и q являются корнями трехчлена.

Следовательно, информация о точном значении <�р (т) сразу приводит пас к разложению числа т на множители.

Факторизация при известном значении d

Легко показать, что знание секретного ключа d схемы RSA также приводит к разложению модуля схемы т на простые множители. Прежде чем привести вероятностный полиномиальный алгоритм, который находит разложение числа т на множители, нам потребуется следующая лемма.

Лемма 10.1 (см. [3 ]). Пусть т — нечетное составное число, раскладывающееся в произведение двух простых чисел р и q. Представим р (гп) в виде <�р{гп) = 2ⁿt. Обозначим символом S множество вычетов а € Z_m таких, что НОД (a, m) — Yu выполнено одно из двух условий:

• 1. а¹ = 1 (modm),
• 2. а²'⁴ = — 1 {modm) для некоторого целого к, 0 ^ к ^ п, тогда мощность множества S не превосходит .

Утверждение леммы позволяет нам построить простой алгоритм факторизации числа т, основанный на следующей идее. Пусть a g S, то есть а — вычет, который не удовлетворяет условиям леммы. Тогда.

для любого к = 0,1,…, п — 1.

Выберем в качестве к минимальное из всех возможных значений таких, что a^2k+lt = 1 (modm). Такое к всегда найдется, поскольку в силу теоремы Эйлера выполнено сравнение 2^2>ч = = 1 (mod т).

Обозначим и = a^[1][2]*^[3] (modm) и v = а^2к+'^г (modm). Тогда Таким образом мы получаем сравнения.

которые позволяют найти делитель числа т, поскольку либо р (и — 1), либо q (q — 1). Изложим сказанное выше в виде алгоритма разложения числа т на множители.

Алгоритм 10.1 (Факторизация модуля схемы RSA).

Вход: Целое составное число гп — модуль схемы RSA и значения секретного d и открытого е ключей схемы RSA.

Выход: Простой делитель р числа т.

• 1. Определить w = ed — 1 и представить w = 2ⁿt.
• 2. Выбрать случайное значение Ь, 0 < b < т.
• 3. Вычислить р = НОД (Ь, т). Если р > 1, завершить алгоритм.
• 4. Вычислить v = Ь¹ (mod га).
• 5. Если v = 1 (mod га), то вернуться на шаг 2. Иначе — определить к = 0.
• 6. Пока к < п, выполнять
• 6.1. Если v = -1 (mod га), вернуться на шаг 2.
• 6.2. Вычислить и = v, v = и² (mod га), к = к + 1.
• 6.3. Если v = 1 (mod га), перейти к шагу 8.
• 7. Вернуться на шаг 2.
• 8. Вычислить р = НОД (и — 1. га).
• 9. Если р > 1, то закончить алгоритм. Иначе — вернуться к шагу 2. ?

Согласно утверждению данной леммы, с вероятностью ^ вычет 6 даст нам разложение числа т на простые сомножители. Если же мы вычислим вычет b несколько, скажем г, раз, то вероятность разложения числа на множители будет равна (1 — 2~^г).

• [1] Ключи схемы RSA удовлетворяют сравнению ed = 1 (mod m), следовательно, на первом шаге алгоритма выполнено равенствоw = s (j>(m) для некоторого натурального s. Таким образом, вычет Ь, вычисляемый случайным образом на втором шаге алгоритма, удо
• [2] влетворяет сравнению b = as (mod m), где, а — вычет, участвующий
• [3] в утверждении леммы 10.1.