Последние дни RSA

Евгений Firstborn Рогов

Спецвыпуск: Хакер, номер #055, стр. 055-016-1

(jevgenijsr@gmail.com)

Новейшие квантовые технологии - в массы, или почему классические криптосистемы отживают свое

У тебя есть что-то сокровенное, что очень хотелось бы скрыть от чужих глаз или даже от любых, кроме собственных? Всем известно, что самым адекватным способом скрыть какую-либо ценную информацию является шифрование. Однако можно ли доверять широко используемым сейчас алгоритмам?

Информация в тени

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

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

Классика взлома

Итак, с какой же стороны можно подойти к такой непростой проблеме, как взлом криптосистемы класса RSA? Конечно, нет ничего, что было бы невозможно взломать. В системе всегда найдется слабое место: может, навредит человеческий фактор, может, техническая тонкость, но без слабого звена просто никуда! В отчете ФБР США за 2003 год указывается, что ущерб от взломов компьютерных систем составил $200 млрд.! И это только в США, и только за один год!

Где же искать "слабое" звено многократно проверенной криптосистемы? На самом деле вариантов несколько. Для начала необходимо ответить на вопрос о том, от чего зависит надежность криптоалгоритма? Вот современные варианты ассиметричной криптосистемы. Они построены таким образом, что стойкость системы, то есть трудность расшифровки секретного сообщения без соответствующего ключа, напрямую зависит от степени сложности эффективного вычислительного решения некоторых математических задач. На практике это означает всего лишь то, что если некто умеет за обозримое время раскладывать на простые множители тысячезначные числа, то этот хитрый некто сможет и расшифровать сообщение, зашифрованное с помощью RSA. Как? Очень просто! Можно перехватить передаваемый по каналам связи публичный ключ, выудить из него число N, являющееся произведением простых чисел P и Q (см. врезку). Далее, используя алгоритм факторизации (собственно - разложения на простые множители), найти эти два числа. Зная их, можно запросто реконструировать оба ключа: публичный и секретный. Проблемка остается в том, что если число N достаточно велико, то решить задачу факторизации за приемлемое время просто не получится даже задействовав вычислительную мощность всех существующих компьютеров. И именно для того чтобы поддерживать невозможность практического решения такой задачи, постоянно наращивается длина ключей (а следовательно, и увеличиваются числа N, P и Q). Вот если бы можно было кардинально ускорить процесс факторизации...