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

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

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

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

Реклама на Компьютерре

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

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

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

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

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