Взлом криптосистемы 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 – целое число, лишь немного большее Проверяем подряд целые числа Количество попыток, необходимых для факторизации N, можно при известных p и q вычислить по следующей формуле:
|
.
.
причем t 2 – N является полным квадратом.
В нашем примере t 1 = 152843, t 2 = 152844, t 3 = 152845 и t 3 - N =8042, тогда р = 152845 + 804, р = 152845 – 804. Таким образом, мы с третьей попытки нашли p и q.
, где [ x ] – операция округления x до ближайшего целого числа.
