Интересное исследование провели криптографы из Федеральной политехнической школы Лозанны в рамках проекта SSL Observatory. При помощи организации Electronic Frontier Foundation они собрали в открытой сети X.509 и другие сертификаты и составили базу из 11,4 млн RSA-модулей, из которых 7,1 млн имеют длину 1024 бита и меньше. Эта база данных была подвергнута анализу на предмет простых чисел, в результате чего удалось осуществить факторизацию 12720 модулей.
Анализ показал, что из 7,1 млн RSA-модулей 26444 являются уязвимыми 1024-битными модулями, ещё обнаружено 509 штук 512-битных и два 768-битных модуля. В общей сложности на всей выборке было использовано 31150 отдельных простых чисел.
Как известно, RSA-ключи генерируются следующим образом:
1. Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).
2. Вычисляется их произведение n = pq, которое называется модулем.
3. Вычисляется значение функции Эйлера от числа n:
φ(n) = (p − 1)(q − 1) .
4. Выбирается целое число e (1 < e < φ(n)), взаимно простое со значением функции φ(n). Число e называется открытой экспонентой (англ. public exponent).
5. При помощи расширенного алгоритма Евклида вычисляется число d, мультипликативно обратное к числу e по модулю φ(n). Число d называется секретной экспонентой.
6. Пара e, n публикуется в качестве открытого ключа RSA.
7. Пара d, n играет роль секретного ключа RSA.
Проблема в том, что для десятков тысяч сайтов при генерации ключей используются слишком малые значения e, что не обеспечивает практически никакой защиты. На общей выборке RSA-модулей количество незащищённых ключей составляет примерно 0,2%.
В восьми случаях обнаружены даже ключи, сгенерированные при e=1, а в двух случаях — при e=0, что вообще никуда не годится. В исследовании криптографов из Федеральной политехнической школы Лозанны (PDF) ещё много таких забавных фактов.
