Группа криптографов и математиков из Европы и США выявила серьёзную уязвимость в криптоалгоритме RSA, который повсеместно применяется в электронной коммерции, в банковской среде и для шифрования в интернете.

Система RSA, описание которой приводится здесь, предполагает генерацию двух ключей – открытого и закрытого, что и осуществляется путём нескольких математических операций, включающих в том числе получение произведения двух простых чисел, которые держатся в секрете. Эти числа должны, в свою очередь, предварительно генерироваться случайным образом.

Как выяснилось, на этапе генерации этих чисел и таится уязвимость: генераторы простых чисел не всегда работают так, как следовало бы, так что исследователи, собрав обширную коллекцию открытых (опубликованных в Сети) ключей безопасности, обнаружили довольно существенное количество неэффективных.

Применив алгоритм Евклида, позволяющий отыскивать наибольший общий делитель двух чисел, группе исследователей во главе с почтенным голландским математиком Арьеном К. Ленстрой удалось выяснить, что небольшое количество исходных чисел “не было по-настоящему случайным” и что можно было вычислить применявшиеся для генерации открытого ключа числа.

0,2 процента, или 27 тысяч из проанализированных ключей, по утверждению исследователей, совершенно “не обеспечивали защиты”. Проблема касалась как 1024-битных, так и 2048-битных ключей RSA. До сих пор шифрование с 1024-битным и тем более 2048-битным ключом считалось неуязвимым. Лобовая атака на такой шифр требует многолетних вычислений на пределе возможностей современных компьютеров.

Ключи для анализа выбирались из нескольких баз данных; одна из них принадлежит Массачуссетскому технологическому институту, другая – SSL Observatory (“SSL-обсерватория”) – Фонду электронного фронтира (EFF).

“SSL-обсерватория” создавалась именно с целью исследования эффективности SSL-сертификатов в Сети. Вскоре после публикации выводов Арьена Ленстры и его коллег Фонд выразил обеспокоенность недостаточной защищённостью ключей шифрования: в теории это позволяет перехватывать транзакции, которые с точки зрения их участников кажутся защищёнными от вторжения, незаметно вклиниваться в защищённые интернет-соединения и предпринимать прочие злонамеренные действия.

Ещё один интересный выводи из этого исследования: однофакторные алгоритмы шифрования, требующие только одного исходного числа – такие, как ElGamal, DSA и ECDSA, оказываются более надёжными, чем многофакторные, то есть подобные RSA.

Подробнее: академический доклад Ленстры и его соратников с формальным описанием уязвимости.