Постквантовая криптография, возможно, не будет стойкой
Как известно, продолжается конкурс NIST (Национальный институт стандартизации США) по разработке алгоритмов постквантовой криптографии. Слово "постквантовая" означает, что алгоритмы будут стойкими для взлома с помощью квантовых компьютеров.
За более чем 5 лет конкурса пали десятки претендентов (из 69-ти). В июне NIST объявил о том, что выбирает 4 алгоритма-финалиста и 4 альтернативных алгоритма. В августе один из 4 альтернативных алгоритмов (SIKE) был взломан.
Забавно, но, как минимум, несколько алгоритмов, включая SIKE, были взломаны без каких-либо ссылок на квантовые компьютеры. То есть имели самые обычные уязвимости, буквально, позволявшие сломать шифрование на обычном домашнем компьютере.
Кажется, это первый случай, когда финалиста (пусть и альтернативного списка) конкурса NIST сломали. Обычно, финалисты считаются очень надёжными шифрами.
В чём причина таких провалов?
1. Для построения постквантовых алгоритмов используются математические задачи, которые считаются сложными до неразрешимости. Однако, многие из этих задач просто недостаточно изучены. Кроме этого, эти задачи очень сложны даже для математиков.
Поэтому, там много нюансов и при достаточной подготовке и мотивации часто находятся проблемы, которых не ждали.
В SIKE, кстати, способ взлома алгоритмов родом из 90-х годов. Но разработчики алгоритма, видимо, просто не учли его или даже не знали о существовании нужной теоремы.
2. Сложность самих квантовых вычислений.
Квантовые алгоритмы, сами по себе, сложны и плохо изучены. В том числе и потому, что, собственно, квантовых компьютеров нет и практиков по таким алгоритмам тоже нет. А значит, мало кто вообще понимает, что там происходит и как создавать алгоритмы.
Стоит ожидать, что с появлением реальных и полезных квантовых компьютеров, мы увидим рост числа математиков-практиков, хорошо знающих квантовые алгоритмы. После чего постквантовые алгоритмы начнут падать ещё интенсивнее.
Что делать?
Чем нам это грозит?
Обычным людям - практически ничем. Владельцы квантовых компьютеров, возможно, смогут взломать ключи шифрования от вашей переписки и платёжных систем.
Однако, такая информация, обычно, быстро устаревает и не очень ценна. К тому же, мошенники вряд ли смогут позволить себе нужные квантовые мощности (хотя это тоже ещё вопрос). Так что ломать, в основном, будут спецслужбы.
В данном случае, лучше будет обновлять пароли от сайтов (от почты) хотя бы раз в несколько лет, а лучше раз в год (лучше, конечно, ещё чаще :)) ), чтобы их было тяжелее украсть в случае чего.