512-разрядный ключ шифрования удалось разложить на множители

Группе исследователей из шести стран мира под руководством Датча Хермана те Рейля из голландского Национального института математики и информатики (CWI, www.cwi.nl) удалось разложить на сомножители 512-разрядное число. Именно такую длину имеют многие ключи, используемые для обеспечения безопасности систем электронной коммерции в Internet.

Датч Херман те Рейль: «Вот число
и его найденные сомножители»

По словам Франса Снийдерса из CWI, используется бесчисленное количество различных 512-разрядных ключей, а разложить на множители удалось лишь один. «Но с помощью опробованной нами технологии мы теперь потенциально можем взломать любой ключ», — считает он.

Исследование, носившее недвусмысленное название RSA Factoring Challenge, финансировала компания RSA Data Security. Цель исследования — выяснить реальный уровень защиты, обеспечиваемый ключами различной длины. В конце августа компания сообщила, что группе ученых потребовалось семь месяцев на то, чтобы определить сомножители одного из 512-разрядных ключей, используемых алгоритмом RSA. Эти данные могут быть использованы для декодирования зашифрованной информации. RSA опубликовала заявление, в котором говорится, что «результаты исследования подтвердили рекомендации RSA о необходимости для обеспечения надежной защиты использовать ключ длиной не менее 768 разрядов».

Брюс Шнайер, президент консалтинговой компании Counterpane Systems, занимающейся вопросами криптографической защиты, заявил, что подобный вывод можно было сделать задолго до завершения исследования.

Разложение ключа на сомножители — математическая модель так называемого «открытого ключа» в хорошо известной системе шифрования RSA, которая была разработана Ривестом, Шамиром и Эдлеманом в середине 70-х в Массачусетсском технологическом институте. Сейчас 512-разрядное шифрование широко используется в аппаратном и программном обеспечении для защиты трафика электронной коммерции, в частности в интернациональной версии коммуникационного протокола SSL.

Разложенное на сомножители число, названное RSA-155, было взято из RSA Challenge List, своеобразного мерила безопасности в криптосистеме RSA.

Для того чтобы найти сомножители RSA-155, использовались 292 компьютеров в 11 различных офисах, расположенных по всему миру. 160 рабочих станций SGI и Sun Microsystems, а также 120 персональных компьютеров с процессорами Pentium II работали в параллель непрерывно в течение семи месяцев.

Шнайер отметил, что та же самая задача могла бы быть решена буквально за неделю, если бы исследователи предложили инструментарий для организации работы над ней множества машин, подключенных к Internet, как это было сделано во время взлома DES.