Чип от D-Wave Systems с квантовыми возможностями

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

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

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

Американский математик Питер Шор известен своими работами в области геометрии, теории вероятностей, комбинаторики, теории алгоритмов и квантовой информатики. А наибольшую известность ему принесли работы по теории квантовых вычислений. В 1994 году он опубликовал работу, в которой представил алгоритм, потенциально способный взломать криптографию с открытым ключом. Для этого вам потребуется «всего лишь» квантовый компьютер с несколькими сотнями логических кубитов.

К примеру, RSA использует открытый ключ размера M, который представляет собою произведение двух больших простых чисел. Один из способов взломать шифр RSA — найти множители M. Самый лучший классический алгоритм их поиска отработает на обычном компьютере за время M^1/3. Алгоритм Шора, используя возможности квантовых компьютеров, способен сделать это не сильно медленнее, чем вычисление произведения этих чисел – то есть очень быстро.

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

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

«Что АНБ хочет сказать этим обращением, так это выразить свою обеспокоенность квантовыми компьютерами, достаточную для приложения огромных усилий, необходимых для переключения с шифрования с открытыми ключами на постквантовую криптографию,- поясняет Надя Хенинджер (Nadia Heninger), ассистент-профессор информатики Пенсильванского университета. – Это сильно отразится на индустрии информационной безопасности, поскольку всем компаниям, работающим по контракту с правительством, придётся внедрять новые алгоритмы в своих продуктах».

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