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

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

Пример 4. Пусть пользователь выбрал N = 2047, e = 179, d = 411. Так как 2047 = 2389, а имеют наименьшее общее кратное 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 и тогда
р = 152845 – 804. Таким образом, мы с третьей попытки нашли p и q. Количество попыток, необходимых для факторизации N, можно при известных p и q вычислить по следующей формуле: , где [ x ] – операция округления x до ближайшего целого числа.