Квантовый компьютер и криптоанализ симметричных шифров

Прямое и универсальное использование квантового компьютера для “взлома” симметричных шифров сводится к (квантовому) поиску при помощи алгоритма Гровера (это аналог полного перебора вариантов). Из-за квадратичного выигрыша, который даёт данный алгоритм относительно перебора на классическом вычислителе, симметричные шифры для сохранения практической стойкости должны использовать ключи в два раза большей разрядности. Но квантовый компьютер может быть использован и для криптоанализа, направленного на тот или иной конкретный шифр, то есть, для снижения стойкости конкретного шифра, а не для простого перебора: успешный криптоанализ – позволяет существенно снизить “мощность перебора”. При этом универсальный квантовый компьютер можно применить для реализации уже наработанных классических техник криптоанализа (с тем или иным выигрышем в производительности, либо без выигрыша), а можно разработать некие новые квантовые методы криптоанализа, что гораздо интереснее.

Эти квантовые методы должны использовать какие-то свойства взламываемого шифра, которые хорошо проецируются именно на возможности квантовых вычислений. Пример. Предположим, что для для заданного шифра можно построить некоторую периодическую функцию, разбивающую всё пространство ключей на интервалы. Период этой функции может эффективно определить квантовый компьютер (это типичная задача, так, на поиске периода основан квантовый алгоритм Шора факторизации чисел). Знание периода позволяет путём анализа нескольких пар, состоящих из открытого текста и соответствующего ему шифротекста, определить, в какой именно из интервалов попадает секретный ключ, а дальше уже перебирать значения только из этого интервала, который, предположим, невелик. (Можно переформулировать: пусть обнаруживается период функции, определяющей возможные ключи – в таком случае, зная период, можно будет проверить только их, прыгая по значениям.) Пары открытых текстов и шифротекстов часто известны на практике. Скажем, HTTPS, использующий TLS в качестве транспорта, подразумевает передачу куки-файлов или известных заголовков запросов. При этом режим счётчика (GCM и пр.) основан на зашифровании последовательных значений. Это грубое изложение, но оно математически сходно с атаками, которые уже несколько лет обсуждаются в публикациях, применительно к различным режимам симметричных шифров.

Другими словами, алгоритм Гровера, “грубый поиск”, является универсальным. Если он будет реализован (а для реализации, применительно к шифрам, потребуется сложный квантовый компьютер с тысячами кубитов), то это затронет стойкость всех симметричных шифров, но приведёт “всего лишь” к росту разрядности ключей в два раза. Однако неверно полагать, что не существует куда более эффективных квантовых методов криптоанализа, которые, в случае появления мощного квантового компьютера, снизят до уровня непригодности стойкость если не самих используемых сейчас симметричных шифров, то их повсеместно применяемых режимов работы.

Адрес записки: https://dxdt.ru/2017/04/10/8320/

Похожие записки:



Далее - мнения и дискуссии

(Сообщения ниже добавляются читателями сайта, через форму, расположенную в конце страницы.)

1 комментарий от читателей

  • 1. 22nd April 2017, 00:47 // Читатель Сергей Виноградов написал:

    Интересно, возможно ли защититься от этого уже сейчас, не зная, что именно будет???