Взлом криптосистемы RSA при неудачном выборе параметров криптосистемы

Само по себе использование RSA не обеспечивает безопасности. Дело еще в деталях реализации. Приведем ряд примеров. Для простоты вычислений будем работать с небольшими числами. Цель – показать особенности, не зависящие от размера.

Пример 4.

Пусть пользователь выбрал N = 2047, e = 179, d = 411.

Так как 2047 = 23× 89, а φ (23) =22, φ (89) =88 имеют наименьшее общее кратное 88, то любое число, обратное к 179 по модулю 88, например 59, будет действовать как d.

Пример 5.

Число N = 536813567 является произведением простого числа Мерсенна 8191 и простого числа Ферма 65537. Это очень плохой выбор.

Пример 6.

Число 23360947609 является очень плохим выбором для N из-за того, что два его простых делителя слишком близки друг к другу.

Пусть p > q, тогда имеем .

Обозначим: .

Так как S мало, то t – целое число, лишь немного большее причем t ² – N является полным квадратом.

Проверяем подряд целые числа В нашем примере t ₁ = 152843, t ₂ = 152844, t ₃ = 152845 и t ³ - N =804², тогда р = 152845 + 804, р = 152845 – 804. Таким образом, мы с третьей попытки нашли p и q.

Количество попыток, необходимых для факторизации N, можно при известных p и q вычислить по следующей формуле: , где [ x ] – операция округления x до ближайшего целого числа.