Рассмотрим классическую задачу криптографии

  • Алиса отправляет шифрсообщение Бобу с использованием публично известного алгоритма шифрования и ключа известного Бобу

  • Эвил перехватила шифрсообщение и хочет прочитать его содержимое

Как квантовые вычисления помогут Эвил с её задачей?

Если множество открытых текстов, где текст - последовательность символов, является значительно меньшим подмножеством множества последовательности символов, то классическим является атака грубой силы - то есть перебор всех возможных ключей и проверка полученной последовательности символов на принадлежность множеству открытых текстов.

Допустим, что у нас имеется

  • программная реализация функции DECRYPT(key, ciphertext) возвращающая последовательность символов полученных при расшифровании шифрсообщения ciphertext на ключе key

  • программная реализация функции ISPLAINTEXT(text) = 0 если text является принадлежит множеству открытых текстов и != 0 в противном случае

NB. если алгоритм шифрования реализован на основе блочного шифра, то достаточно иметь реализации расшифрования блока DECRYPT, а реализацию функции ISPLAINTEXT выполнять в цикле по блокам символов с накоплением результата.

Сам алгоритм грубой силы выглядит так:

for each key
text = DECRYPT(key, ciphertext)
if ISPLAINTEXT(text) == 0 then return (key,text)
end for

Как мы делаем сейчас

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

Чему нас учит наука

Как, с точки зрения теории информации, можно оценить вероятность правильного дешифрования сообщения:

  1. Будем считать, что шифр является моноалфавитным (например, современные компьютеры обрабатывают данные представленные байтами на бинарной логике)

  2. Пусть

  • LENGTH(plaintext) - длина сообщения выраженная в битах

  • LENGTH(key) - длина ключа выраженная в битах

  • LENGTH(ciphertext ) - длина шифрсообщения выраженная в битах

  • ENTROPY(plaintext) - энтропия сообщения выраженная в битах (в терминах Клода Шеннона)

Очевидно, что

  • LENGTH(plaintext)<=LENGTH(ciphertext )

  • априорная вероятность, что случайный неправильный ключ key пройдёт проверку на открытый текст составит 2**-(LENGTH(plaintext)-ENTROPY(plaintext))

  • если LENGTH(plaintext)-ENTROPY(plaintext) > LENGTH(key) то ключ будет определён

NB. Часто алгоритмы шифрования сохраняют длину исходного сообщения и имеют ключи фиксированной длины, а значит, при выполнении условия LENGTH(ciphertext )-ENTROPY(plaintext) >= LENGTH(key) ключ будет определён

Посмотрим теперь на квантовые вычисления

В основе квантовых вычислений лежит возможность использования запутанного состояния частиц и возможность менять вероятности этих запутанных состояний. Если рассматривать массив запутанных между собой частиц, как регистр вычислительной системы, то можно легко увидеть, что над этим регистром можно легко реализовать базовые арифметические операции, такие как сложение, вычитание, умножение, деление, сдвиг и так далее с использованием базового набора квантовых вентилей. То есть при достаточном количестве поддерживаемых квантовой системой связанных частиц можно трансформировать обычную программную реализацию функции над регистром детерминированного компьютера в набор квантовых вентилей преобразования массива запутанных частиц.

Примеры таких трансформаций массивов кубитов, которые являются аналогами арифметических операций классического компьютера над регистром вы можете найти в моих более ранних публикациях

Таким образом

  1. в квантовой системе мы сформируем неопределённое состояние в массиве K длины LENGTH(key)

  2. над массивом K выполним трансформацию U(K) которая будет соответствовать преобразованию ISPLAINTEXT(DECRYPT(K, ciphertext )) для имеющегося шифротекста ciphertext

  3. и нам надо найти такое состояние регистра K, при котором U(K) == 0 а это является классической задачей в квантовых вычислениях именуемой поиск по словарю, которые сейчас публично решаются через различные алгоритмы усиления амплитуды и алгоритм Гровера сейчас наиболее известен среди них.

  4. Применяем известные нам методы решения задачи поиска по словарю на квантовых машинах (возможно использование библиотечных функций) и золотой ключик у нас в кармане (в финальном состоянии массива запутанных частиц)

Всем спасибо!