Компьютерра - Компьютерра PDA N161 (25.02.2012-02.03.2012)

Кстати, пуштунская жаба уже не одинока. Мои коллеги из Санкт-Петербурга нашли подобный вид на Памире, а в прошлом году - ещё одинв Западных Трансгималаях. Подождём, что станет известно о способах размножения новых находок...

Автор: Киви Берд

Опубликовано 01 марта 2012 года

В августе нынешнего года в калифорнийском городке Санта-Барбара пройдёт международная криптографическая конференция CRYPTO 2012, дающая своего рода срез текущего состояния дел в этой области прикладной математики. И хотя до начала мероприятия остаётся ещё полгода, уже сегодня можно с уверенностью сказать, какая из тем обсуждения будет среди самых горячих.

Прогнозировать это несложно, потому что одна из исследовательских работ, намеченных для доклада на CRYPTO, опубликована уже сейчас и сразу же вызвала заметный резонанс. Ибо то, что исследователям – команде криптографов из Европы и США – удалось обнаружить, для большинства специалистов от академической науки оказалось, выражаясь поделикатнее, сильной неожиданностью.

Для начала имеет смысл подоходчивее объяснить, что же за результаты удалось получить команде исследователей, которую возглавляли известный голландский математик-криптограф Арьен Ленстра (Arjen K. Lenstra) и независимый калифорнийский криптоэксперт Джеймс Хьюз (James P. Hughes). В настоящее время Ленстра является профессором Лозаннского федерального политехникума (École Polytechnique Fédérale de Lausanne), так что все остальные криптографы - соавторы этой большой работы также представляют данный швейцарский вуз.

Целью исследования, занявшего в общей сложности около трёх лет, являлся тщательный аналитический обзор той необъятной массы криптоключей, что повсеместно применяются ныне в реальной жизни. То есть учёные кропотливо собрали из интернет-баз все те ключи и сертификаты, что по определению предполагаются общедоступными и составляют основу криптографии с открытым ключом.

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

Именно RSA используется для генерации сертификатов протокола SSL, повсеместно применяемого для шифрования соединений в интернете. Для того чтобы вся эта система работала, лежащий в основе стойкости RSA ключевой элемент под названием "модуль" должен быть произведением двух очень больших простых чисел, причём для каждого конкретного ключа эти числа должны быть строго уникальными.

После анализа 7,1 миллиона ключей аналитиками было установлено, что сравнительно небольшая их доля – 27 тысяч, или примерно 0,4 процента, – имеют общий простой "фактор" или делитель с другими ключами-числами. Это означает, что с криптографической точки зрения числа оказываются очень слабыми. Иначе говоря, выявившие такого рода ключи аналитики могут их быстро взломать, а значит, то же самое способен сделать и кто угодно ещё.

Выходит, что стойкость криптографии с открытым ключом составляет не 100процентов, а лишь 99,6. Казалось бы, не такой уж плохой результат для реальной защиты информации. Но аналитики оценивают этот итог существенно иначе. Потому что, согласно теоретическим расчётам, 0,4 процента никудышных ключей не должны были появиться.

Цитируем одно из интервью Джеймса Хьюза: "Факт заключается в том, что если бы эти числа-ключи имели ту энтропию, которая для них предполагается в теории, то вероятность даже одного-единственного из такого рода событий (совпадение факторов) для семи миллионов ключей должна быть ничтожно малой... Мы считаем, что всё это довольно необычно"...

По свидетельству Хьюза, в тех случаях, когда генерация ключей делается правильно, для случайного числа-ключа длиной 1024 бита теоретически понадобилось бы сгенерировать ещё 2 200других ключей, прежде чем будут исчерпаны прочие множители-факторы и появится повторение. Гигантское количество 2 200, для сравнения и примерного представления о его размерах, можно иначе (приближённо) записать как 10 60. Если же для каждого из семи миллиардов жителей планеты ежесекундно вырабатывать по одному такому ключу, то даже за сто лет общее число сгенерированных ключей будет измеряться числом с шестнадцатью нулями. А здесь этих нулей шестьдесят.

Это странно с математической точки зрения, но в действительности дело обстоит, похоже, даже круче. Хотя основная масса всех аналитических усилий команды была сосредоточена на (общераспространённых ныне) ключах длиной 1024 бита, в поле их зрения попадали и более длинные 2048-разрядные ключи. И хотя в теории столь огромные числа должны предоставлять просто-таки невообразимо гигантское пространство энтропии, напрочь исключающее возможности повторения множителей, многочисленные ключи с общими факторами выявлены и здесь.

Но и это ещё не всё. Аналогичные нынешним исследования проводились и ранее, правда, на меньшем количестве ключей. Исследованный ныне массив из семи миллионов – это тоже далеко не все применяемые в мире ключи. Очень важным новым открытием стал такой факт: процентная доля ключей, для которых установлено, что они сгенерированы с помощью неуникальных множителей, скорее всего, будет возрастать и далее по мере того, как будут становиться доступными для анализа ещё большие количества ключей.

Доля 0,4 (точнее - 0,38) процента дефективных ключей была обнаружена в условиях, когда исследователи просмотрели в общей сложности 7,1 миллиона ключей, в то время как выявленная в более раннем исследовании доля дефективных ключей в размере 0,26 процента соответствовала проанализированному числу из 4,7 миллиона модулей RSA. Иначе говоря, как результат такой зависимости, подлинное количество ключей, которые на самом деле можно было бы вскрыть, используя данный подход, может оказаться даже выше, чем показывает нынешнее исследование.

Пытаясь логически осмыслить полученные результаты, учёные пришли к выводу, что кто-то наверняка уже знает об этом. Непосредственно в их статье данная мысль сформулирована следующим образом: "Учитывая отсутствие в наших методах анализа каких-то хитрых и сложных приёмов, а также последовавшие за этим открытия, очень трудно поверить, будто представленная нами работа является чем-то совершенно новым. Особенно принимая во внимание, что существуют организации, известные обострённым любопытством к подобного рода делам".