Национальный институт стандартов и технологий США (NIST) опубликовал отчёт о постквантовой криптографии. В нём обсуждается подготовка к появлению квантовых компьютеров, с лёгкостью взламывающих любые современные криптосистемы. Эксперты NIST полагают, что принимать меры нужно уже сейчас, иначе будет поздно.

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

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

В 1994 году учёный Питер Шор из исследовательского центра Bell Labs обнаружил, что универсальные квантовые компьютеры способны решать эти задачи за полиномиальное время. Иными словами, так быстро, что популярные алгоритмы шифрования с открытым ключом утрачивают смысл. Спустя два года американский математик Лов Гровер изобрёл квантовый алгоритм поиска, который значительно ускоряет расшифровку симметричных криптоалгоритмов.

Изобретения Шора и Гровера не уничтожили современную криптографию по единственной причине: квантовых компьютеров достаточной мощности пока не существует. Ключевое слово — «пока». На днях корпорация IBM открыла доступ к экспериментальному пятикубитовому квантовому компьютеру и планирует в течение десяти лет увеличить количество кубитов в 10-20 раз.

Многие эксперты полагают, что квантовые компьютеры, способные взламывать любые современные криптосистемы с открытым ключом, появятся в течение ближайших двадцати лет. По оценке специалистов NIST, к 2030 году взлом алгоритма RSA с ключом длиной 2000 бит будет занимать считанные часы. Это будет недёшево (понадобится не менее миллиарда долларов), но вполне реально.

Алгоритм AES можно будет спасти, существенно удлинив ключ, но алгоритмы RSA, ECDSA, ECDH, DSA и многие другие станут небезопасны. В NIST считают, что с этим нужно что-то делать, и как можно скорее.

Известно несколько криптоалгоритмов, основанных на математических проблемах, которые пока не выходит упростить за счёт применения квантовых компьютеров. В NIST высоко оценивают алгоритмы асимметричного шифрования, основанные на решётках: они просты, эффективны и хорошо параллелизуются.

Кроме того, стоит обратить внимание на криптосистемы с открытым ключом, основанные на сложности декодирования полных линейных кодов (одна из них изобретена математиком Робертом Мак-Элисом ещё в конце семидесятых), и на криптосистемы, использующие NP-сложность решения системы полиномиальных уравнений с несколькими переменными.

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



8 комментариев

  1. h0lera

    09.05.2016 at 19:28

    стеганография в помощь. иногда информацию можно представить в таком виде что сам автор затруднится вспомнить что он имел ввиду.
    до сих пор винда глючит как и четверть века назад. значит до сих пор не научились прямыми руками писать код для настольных ПК. каким образом они собираются писать софт для кубита, который есть и true и false в один и тот же самый момент? на каком языке будет if statement? хотел бы увидеть этот синтакс. уже пудряд мозг этим квантом как и псевдоанонимным биткоионом с вымогателями пять лет подряд. это наверно мода такая сейчас на мистику или дурь в редакции хакера забористая. может грибами позавтракали?
    так или иначе. чтоб они там не придумали дабы освоить бюджет налогоплательщика. всё равно кашерный бэкдорчик прямо на железе будет стоять, не зависимо от для длины и непубличности ключей.

  2. h0lera

    09.05.2016 at 22:51

    самый верный способ обхода шифрования это утюг и паяльник

  3. baho1991

    10.05.2016 at 19:02

    «Ассиметричного» режет глаз. Исправьте пожалуйста

  4. VlS

    10.05.2016 at 21:33

    Все это чушь. Кто-то там что-то сказал. На рен-тв каждый день «эксперты» разоблачения гонят. В реальности квантовый компьютер (которого по сути еще и нет, а есть лишь простые логические ячейки) может выполнять лишь очень узкий круг задач быстрее обычного и перебор паролей в этот круг не входит. Попробуйте к примеру найти описание как же он это будет делать. Простой раскрут на бабло правительств и инвесторов через общественное мнение. Чем то напоминает кипиш вокруг «проблемы 2000»

    • va-dudnikov

      11.05.2016 at 01:38

      Да что вы говорите. Алгоритм Гровера перебирает решения за O(sqrt(N/l)), N — размерность, l — количество корней (в нашем случае l=1). Алгоритм Шора позволяет факторизовать число M за O(lg^3(M)). Вопрос только в том, когда получится увеличить число кубитов до нужных размерностей.
      Если IBM планирует увеличить число кубитов в 10-20 раз, то, скорее всего, у них уже есть основания так говорить.
      Думаю из-за такой кампании увеличится количество исследований в этой области, что в свою очередь поспособствует развитию квантовых вычислений. Лично я начал изучать культуру функционального программирования хотя бы для того, что бы написать «Hello, World!» на 5-ти кубитном квантовом компьютере.

  5. Int

    11.05.2016 at 01:07

    > Он занимается стандартизаций

  6. devbutch

    11.05.2016 at 13:30

    параллелизуются — может всё же распараллеливаются?

Оставить мнение