Роман Душкин - Криптографические приключения: таинственные шифры и математические задачи

Вместе с тем отец продолжал:

— Вы хорошо знаете, что в информатике и теории информации используется понятие «бит». Это единица количества информации, и один бит представляет собой количество актов выбора между двумя альтернативами. Если у нас есть два различных предмета, то для того, чтобы выбрать между ними, требуется один бит. Если есть четыре предмета, то для выбора одного требуется два бита. Для восьми предметов требуется три бита. Ну и так далее, вы уже должны это прекрасно понимать. Традиционно для представления битов используются две цифры — 0 и 1. Так и выглядит альтернатива между двумя предметами: 0 или 1. Если у нас четыре предмета, то требуется два бита, которые дают четыре варианта: 00, 01, 10 и 11. Вспомнили?

Мы с Катей дружно кивнули. Отец улыбнулся и продолжил лекцию:

— А теперь представьте, что мы оперируем не чёткими битами, а некоторой их нечёткой комбинацией. В физике это называется «суперпозицией», но мне не очень нравится это слово, так как оно не отражает сущности. Возьмём один бит. В обычной математике он может принимать значение 0 или 1, да? А в квантовых вычислениях один бит может принимать бесконечное количество значений, каждое из которых равно сумме значений 0 и 1 с некоторыми коэффициентами, причём сами коэффициенты являются комплексными числами, а сумма их квадратов должна равняться 1. Понятно? Конечно же, непонятно.

Мы с Катей опять кивнули, потом замотали головами, а потом рассмеялись. Отец воздел руки к небу, но потом сосредоточился и сказал:

— Ладно, про комплексные числа говорить не будем. В целом для решения задачи они не требуются. Просто надо помнить, что наша реальность, похоже, устроена так, что в ней используются именно комплексные числа. Но это я вам потом еще напомню. Итак, пусть это будут действительные коэффициенты. Каждая единица информации в модели квантовых вычислений представляет собой сумму битов 0 и 1 с действительными коэффициентами, сумма квадратов которых равна 1. Выглядит это так.

Отец записал формулу:

a | 0 > + b | 1>, a 2 + b 2 = 1

— Так понятно?

Мы с Катей опять синхронно покачали головами. Я не выдержал и сказал:

— Ну послушай. Мне кажется, что ты хочешь объяснить что-то слишком сложное. Ты можешь рассказать самыми простыми словами, как можно взломать шифр? Не важно, какие там формулы. Главное для нас сейчас — понять, как это может быть.

Отец тяжело вздохнул. Потом подумал и сказал:

— Ну ладно. Это действительно высшая математика, и если вдаваться в тонкости, то мы просидим здесь неделю, а то и больше. Я просто расскажу вам, как квантовые компьютеры решают задачи и как этот способ решения можно применить для взлома метода RSA.

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

Другими словами, если взять атом и представить его в качестве кубита, то он будет находиться в суперпозиции двух состояний. Если к нему добавить второй атом, то они оба уже будут находиться в суперпозиции четырёх состояний. Три атома находятся в суперпозиции восьми состояний. Десять атомов — в суперпозиции одной тысячи двадцати четырёх состояний. Число состояний в суперпозиции трёхсот атомов больше, чем число атомов и других частиц во всей Вселенной.

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

И это свойство квантовых вычислений можно взять за основу очень эффективных алгоритмов, которые могут быстро решить те задачи, которые не решаются обычными алгоритмами. Проблема в том, что после применения преобразований все кубиты всё равно остаются в суперпозиции своих состояний. А как именно выглядит такая суперпозиция? Это понять очень сложно, практически невозможно. Можно измерить состояние набора кубитов, но сам факт измерения как бы «схлопытает» суперпозицию в определенное состояние, и вероятность получения этого состояния равна квадрату коэффициента, с которым оно находится в суперпозиции. Если много раз делать измерения над одинаковыми суперпозициями, то можно оценить коэффициенты, но чаще всего это просто невозможно.

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

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

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

Оказалось, что есть и алгоритм для взлома протокола Диффи — Хеллмана, и это вообще привело меня в уныние — получается, всё то, чему учил нас отец этим летом, можно взломать. Но я вспомнил, как мы проделали эксперимент по передаче информации при помощи квантового протокола, абсолютно стойкого к простым атакам. Так что я вновь приободрился.