Группа криптографов и математиков из Европы и США выявила серьёзную уязвимость в криптоалгоритме RSA, который повсеместно применяется в электронной коммерции, в банковской среде и для шифрования в интернете.
Система RSA, описание которой приводится здесь, предполагает генерацию двух ключей — открытого и закрытого, что и осуществляется путём нескольких математических операций, включающих в том числе получение произведения двух простых чисел, которые держатся в секрете. Эти числа должны, в свою очередь, предварительно генерироваться случайным образом.
Как выяснилось, на этапе генерации этих чисел и таится уязвимость: генераторы простых чисел не всегда работают так, как следовало бы, так что исследователи, собрав обширную коллекцию открытых (опубликованных в Сети) ключей безопасности, обнаружили довольно существенное количество неэффективных.
Применив алгоритм Евклида, позволяющий отыскивать наибольший общий делитель двух чисел, группе исследователей во главе с почтенным голландским математиком Арьеном К. Ленстрой удалось выяснить, что небольшое количество исходных чисел «не было по-настоящему случайным» и что можно было вычислить применявшиеся для генерации открытого ключа числа.
0,2 процента, или 27 тысяч из проанализированных ключей, по утверждению исследователей, совершенно «не обеспечивали защиты». Проблема касалась как 1024-битных, так и 2048-битных ключей RSA. До сих пор шифрование с 1024-битным и тем более 2048-битным ключом считалось неуязвимым. Лобовая атака на такой шифр требует многолетних вычислений на пределе возможностей современных компьютеров.
Ключи для анализа выбирались из нескольких баз данных; одна из них принадлежит Массачуссетскому технологическому институту, другая — SSL Observatory («SSL-обсерватория») — Фонду электронного фронтира (EFF).
«SSL-обсерватория» создавалась именно с целью исследования эффективности SSL-сертификатов в Сети. Вскоре после публикации выводов Арьена Ленстры и его коллег Фонд выразил обеспокоенность недостаточной защищённостью ключей шифрования: в теории это позволяет перехватывать транзакции, которые с точки зрения их участников кажутся защищёнными от вторжения, незаметно вклиниваться в защищённые интернет-соединения и предпринимать прочие злонамеренные действия.
Ещё один интересный выводи из этого исследования: однофакторные алгоритмы шифрования, требующие только одного исходного числа — такие, как ElGamal, DSA и ECDSA, оказываются более надёжными, чем многофакторные, то есть подобные RSA.
Подробнее: академический доклад Ленстры и его соратников с формальным описанием уязвимости.