Криптоанализ RSA - Элементарные атаки

Интернет магазин китайских планшетных компьютеров

Компьютеры - Криптоанализ RSA - Элементарные атаки

29 мая 2011

Оглавление:
1. Криптоанализ RSA
2. Элементарные атаки
3. Малые значения секретной экспоненты

Рассмотрим несколько атак связанных с неправильным использованием алгоритма RSA.

Генерация простых чисел

На случайные простые числа $p\,$ и $q\,$ накладывается следующее дополнительное ограничение:

$p\,$ и $q\,$ не должны быть слишком близки друг к другу, иначе можно будет их найти, используя метод факторизации Ферма. Однако, если оба простых числа $p\,$ и $q\,$ были сгенерированы независимо, то это ограничение с огромной вероятностью автоматически выполняется.

Схема с общим модулем n

Начальные данные: Чтобы избежать генерирования различных модулей $n=p*q \,$ для каждого пользователя, защищённый сервер использует единый n для шифрования всех сообщений. Сторона $A \,$ использует этот сервер для получения сообщения $M \,$

Задача: противник хочет расшифровать сообщение стороны $A \,$ .

Казалось бы, шифротекст $C= M^{e_a} \mod n ,\,$ отправленный стороне $A \,$ , не может быть расшифрован стороной $B \,$ , если она не обладает секретным ключом $d_{a} \,$ . Однако сторона $B \,$ может использовать свои экспоненты $e_b , d_b \,$ , чтобы разложить модуль $n \,$ , и после этого, зная $e_a \,$ , вычислить секретную экспоненту $d_a \,$ .