Атака повторным шифрованием

Строим последовательность: .

, а так как НОД (e, φ (N)), то существует такое натуральное число m, что e^m º 1(mod φ (N)). Но тогда , отсюда следует, что , значит, y ^m-1 – решение сравнения y = x^e (mod N).

Пример 7.

Пусть имеется открытый ключ N =84517, e = 397 и зашифрованное им сообщение y = 8646. Необходимо найти исходный текст x.

Возведем y в степень e и получим y ² = 37043. Будем повторять операцию до тех пор, пока не получим yⁿ = y. y^{n -1} – искомое сообщение: y ³ = 5569, y ⁴ = 61833, y ⁵ = 83891, y ⁶ = 16137, y ⁷ = 8646. y ⁶ является решением сравнения y = x^e (mod N), а, следовательно, искомым сообщением x.

Замечание. Анализ метода повторного шифрования хорошо показывает необходимость соблюдения требований на выбор p и q для обеспечения стойкости. В данном примере d = 82 225. Неудачный выбор криптосистемы привел к тому, что атака методом повторного шифрования дала результат почти сразу, тогда как нахождение d потребовало бы на порядок больших вычислений.