Национальный институт стандартов и технологий США (NIST) опубликовал отчёт о постквантовой криптографии. В нём обсуждается подготовка к появлению квантовых компьютеров, с лёгкостью взламывающих любые современные криптосистемы. Эксперты NIST полагают, что принимать меры нужно уже сейчас, иначе будет поздно.
О квантовых компьютерах читайте здесь, здесь и здесь.
Национальный институт стандартов и технологий – это организация при министерстве торговли США. Он занимается стандартизацией различных технологий, в том числе криптографических алгоритмов. Именно этот институт утвердил алгоритм AES и следит за регулярным увеличением длины ключей шифрования, применяемых государственными учреждениями в США.
Большинство распространённых криптографических алгоритмов, используемых при шифровании и работе с электронными подписями, основаны на том, что разложение чисел на простые множители, дискретное логарифмирование и некоторые другие математические задачи имеют очень высокую сложность. Обычные компьютеры принципиально не способны выполнить необходимые вычисления за разумное время.
В 1994 году учёный Питер Шор из исследовательского центра Bell Labs обнаружил, что универсальные квантовые компьютеры способны решать эти задачи за полиномиальное время. Иными словами, так быстро, что популярные алгоритмы шифрования с открытым ключом утрачивают смысл. Спустя два года американский математик Лов Гровер изобрёл квантовый алгоритм поиска, который значительно ускоряет расшифровку симметричных криптоалгоритмов.
Изобретения Шора и Гровера не уничтожили современную криптографию по единственной причине: квантовых компьютеров достаточной мощности пока не существует. Ключевое слово – "пока". Недавно корпорация IBM открыла доступ к экспериментальному пятикубитовому квантовому компьютеру и планирует в течение 10-ти лет увеличить количество кубитов в 10-20 раз.
Многие эксперты полагают, что квантовые компьютеры, способные взламывать любые современные криптосистемы с открытым ключом, появятся в течение ближайших 20-ти лет. По оценке специалистов NIST, к 2030 году взлом алгоритма RSA с ключом длиной 2000 бит будет занимать считанные часы. Это будет недёшево (понадобится не менее миллиарда долларов), но вполне реально.
Алгоритм AES можно будет спасти, существенно удлинив ключ, но алгоритмы RSA, ECDSA, ECDH, DSA и многие другие станут небезопасны. В NIST считают, что с этим нужно что-то делать, и как можно скорее.
Известно несколько криптоалгоритмов, основанных на математических проблемах, которые пока не выходит упростить за счёт применения квантовых компьютеров. В NIST высоко оценивают алгоритмы асимметричного шифрования, основанные на решётках: они просты, эффективны и хорошо параллелизуются.
Кроме того, стоит обратить внимание на криптосистемы с открытым ключом, основанные на сложности декодирования полных линейных кодов (одна из них изобретена математиком Робертом Мак-Элисом ещё в конце 70-х г.г.), и на криптосистемы, использующие NP-сложность решения системы полиномиальных уравнений с несколькими переменными.
Авторы отчёта напоминают, что на внедрение современных криптографических алгоритмов ушло почти 20 лет, и нет никаких оснований полагать, что квантовоустойчивое крипто распространится быстрее. Готовиться к появлению мощных квантовых компьютеров нужно уже сейчас, иначе есть риск остаться у разбитого корыта в самый неподходящий момент.
Источник: xakep.ru
Комментариев нет:
Отправить комментарий