NIST: Квантовые компьютеры сломают современное крипто, и к этому пора готовиться

[Сталкер 7 081]

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

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

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

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

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

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

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

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

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

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

https://xakep.ru/2016/05/06/quantum-nist/