Атака повторным шифрованием
Строим последовательность:
Пример 7. Пусть имеется открытый ключ N =84517, e = 397 и зашифрованное им сообщение y = 8646. Необходимо найти исходный текст x. Возведем y в степень e и получим y 2 = 37043. Будем повторять операцию до тех пор, пока не получим yn = y. yn -1 – искомое сообщение: y 3 = 5569, y 4 = 61833, y 5 = 83891, y 6 = 16137, y 7 = 8646. y 6 является решением сравнения y = xe (mod N), а, следовательно, искомым сообщением x. Замечание. Анализ метода повторного шифрования хорошо показывает необходимость соблюдения требований на выбор p и q для обеспечения стойкости. В данном примере d = 82 225. Неудачный выбор криптосистемы привел к тому, что атака методом повторного шифрования дала результат почти сразу, тогда как нахождение d потребовало бы на порядок больших вычислений.
|
.
, а так как НОД (e, φ (N)), то существует такое натуральное число m, что em º 1(mod φ (N)). Но тогда 
, отсюда следует, что 
, значит, y m-1 – решение сравнения y = xe (mod N).
