Отец смотрел на нас, но ничего не говорил. А мы, откровенно говоря, не знали, что сказать в ответ. Через минут пять отец решил нам помочь:
— Ну что нужно для расшифровки?
Я ответил сразу же:
— Закрытая экспонента.
— А как она вычисляется?
Хм-м. Это обратный элемент для открытой экспоненты по модулю, равному функции Эйлера для произведения двух простых чисел. Я сказал:
— Нам надо уметь вычислять обратный элемент.
Но отец парировал:
— Это очень просто. Это несложная задача. Её можно решить хотя бы перебором. Подумайте. Ты уже сказал про функцию Эйлера. Для чего она нужна?
— Это модуль, по которому делаются вычисления.
И тут Катя воскликнула:
— Я поняла! Функция Эйлера равна произведению двух простых множителей, из которых сначала вычли по единице. И если мы знаем простые множители, то можем легко подсчитать функцию Эйлера. Но мы этих множителей не знаем, а потому расшифровать зашифрованное этим алгоритмом сообщение очень сложно.
— Всё правильно. Именно на гипотезе, что разложить очень большое число на простые множители крайне сложно, и основана криптографическая сложность этого алгоритма. Но я хочу вам сказать, что это только гипотеза. Пока что нет алгоритма разложения, который работал бы за приемлемое время на современных компьютерах. Но есть понимание того, как эту задачу можно решить быстро и просто. И сейчас я вам про это расскажу…
Я спросил:
— Погоди-ка. Если ты говоришь, что есть метод быстрого взлома этого алгоритма RSA, но при этом на нем основана вся криптозащита в мире, то не собираешься ли ты нам рассказать страшную тайну, за которую могут и чикнуть?
— Ну что это за выражения: «чикнуть»? Нет, не собираюсь, поскольку расскажу только про абстрактную математическую модель. Она ещё не реализована, и когда мы сможем её реализовать — вообще непонятно. Но фундаментальных ограничений нет, так что когда-нибудь мы сможем создать компьютер, подходящий для этой цели, и вы будете к этому готовы.
Отец немного поразмыслил, а потом сказал:
— Итак, давайте с самого начала. Кто мне скажет, как при помощи двух простых множителей взломать шифрограмму RSA?
Я, не дожидаясь разрешения, выпалил:
— Надо от каждого простого числа отнять единицу, а результаты перемножить. Это получится значение функции Эйлера. Оно берётся в качестве модуля, по которому надо найти обратный элемент для открытой экспоненты. Этот обратный элемент и будет закрытой экспонентой. Зная её, мы сможем расшифровать сообщение.
Отец похвалил меня, а потом обратился к Кате:
— Катерина, скажи теперь ты, что такое «обратный элемент»?
— Это такое число, которое, если его перемножить с заданным, даст единицу по некоторому модулю.
— Отлично! Никак не думал, что вы сможете так просто оперировать математическими понятиями, которые изучаются на специальных курсах абстрактной алгебры. Теперь давайте поговорим о новой математической модели, про которую я обещал вам рассказать. Она называется «квантовые вычисления».
Я даже выдохнул от таких известий. Дело в том, что я точно знал: в научной лаборатории у отца уже сейчас проходит испытания прототип квантового компьютера. При его разработке использовались те же самые технологии, которые он применял ко мне для создания искусственной памяти. Неужели теперь он посвятит меня в тайну этих методов?
Вместе с тем отец продолжал:
— Вы хорошо знаете, что в информатике и теории информации используется понятие «бит». Это единица количества информации, и один бит представляет собой количество актов выбора между двумя альтернативами. Если у нас есть два различных предмета, то для того, чтобы выбрать между ними, требуется один бит. Если есть четыре предмета, то для выбора одного требуется два бита. Для восьми предметов требуется три бита. Ну и так далее, вы уже должны это прекрасно понимать. Традиционно для представления битов используются две цифры — 0 и 1. Так и выглядит альтернатива между двумя предметами: 0 или 1. Если у нас четыре предмета, то требуется два бита, которые дают четыре варианта: 00, 01, 10 и 11. Вспомнили?
Мы с Катей дружно кивнули. Отец улыбнулся и продолжил лекцию:
— А теперь представьте, что мы оперируем не чёткими битами, а некоторой их нечёткой комбинацией. В физике это называется «суперпозицией», но мне не очень нравится это слово, так как оно не отражает сущности. Возьмём один бит. В обычной математике он может принимать значение 0 или 1, да? А в квантовых вычислениях один бит может принимать бесконечное количество значений, каждое из которых равно сумме значений 0 и 1 с некоторыми коэффициентами, причём сами коэффициенты являются комплексными числами, а сумма их квадратов должна равняться 1. Понятно? Конечно же, непонятно.
Мы с Катей опять кивнули, потом замотали головами, а потом рассмеялись. Отец воздел руки к небу, но потом сосредоточился и сказал:
— Ладно, про комплексные числа говорить не будем. В целом для решения задачи они не требуются. Просто надо помнить, что наша реальность, похоже, устроена так, что в ней используются именно комплексные числа. Но это я вам потом еще напомню. Итак, пусть это будут действительные коэффициенты. Каждая единица информации в модели квантовых вычислений представляет собой сумму битов 0 и 1 с действительными коэффициентами, сумма квадратов которых равна 1. Выглядит это так.
Отец записал формулу:
a | 0 > + b | 1>, a2 + b2 = 1
— Так понятно?
Мы с Катей опять синхронно покачали головами. Я не выдержал и сказал:
— Ну послушай. Мне кажется, что ты хочешь объяснить что-то слишком сложное. Ты можешь рассказать самыми простыми словами, как можно взломать шифр? Не важно, какие там формулы. Главное для нас сейчас — понять, как это может быть.
Отец тяжело вздохнул. Потом подумал и сказал:
— Ну ладно. Это действительно высшая математика, и если вдаваться в тонкости, то мы просидим здесь неделю, а то и больше. Я просто расскажу вам, как квантовые компьютеры решают задачи и как этот способ решения можно применить для взлома метода RSA.
Отец начал рассказ. Если взять некоторое количество квантовых битов, или кубитов, то общее число возможных их состояний вычисляется как двойка в степени этого количества. Добавляя один кубит, мы увеличиваем число состояний в два раза. И, самое главное, все эти состояния находятся в суперпозиции друг с другом с такими же коэффициентами, сумма квадратов которых равна 1. Это было бы простой и интересной математической абстракцией, если бы не оказалось, что элементарные частицы, из которых состоит всё в нашем мире, не ведут себя именно так.
Другими словами, если взять атом и представить его в качестве кубита, то он будет находиться в суперпозиции двух состояний. Если к нему добавить второй атом, то они оба уже будут находиться в суперпозиции четырёх состояний. Три атома находятся в суперпозиции восьми состояний. Десять атомов — в суперпозиции одной тысячи двадцати четырёх состояний. Число состояний в суперпозиции трёхсот атомов больше, чем число атомов и других частиц во всей Вселенной.
А самое главное — с такими суперпозициями можно осуществлять преобразования. Это как будто бы передача битов в функции, но тут суперпозиции состояний кубитов изменяются. Самая главная особенность заключается в том, что есть взять десять кубитов и их суперпозицию 1024 состояний и применить к ним преобразование, то оно сразу же будет применено ко всем 1024 состояниям. Вот это и отличает модель квантовых вычислений от обычных компьютеров. Представить себе это очень сложно, но похоже, что наша реальность работает именно так.
И это свойство квантовых вычислений можно взять за основу очень эффективных алгоритмов, которые могут быстро решить те задачи, которые не решаются обычными алгоритмами. Проблема в том, что после применения преобразований все кубиты всё равно остаются в суперпозиции своих состояний. А как именно выглядит такая суперпозиция? Это понять очень сложно, практически невозможно. Можно измерить состояние набора кубитов, но сам факт измерения как бы «схлопытает» суперпозицию в определенное состояние, и вероятность получения этого состояния равна квадрату коэффициента, с которым оно находится в суперпозиции. Если много раз делать измерения над одинаковыми суперпозициями, то можно оценить коэффициенты, но чаще всего это просто невозможно.
Однако раз после применения преобразований мы получаем суперпозицию состояний результата, то по ней можно делать некоторые заключения о свойствах проведённых преобразований. Последовательность преобразований — это функция, и именно определённые свойства этой функции можно понять. И получается занимательная вещь. Взяв нужное число кубитов, составив из них равновероятностную суперпозицию и совершив преобразование, мы получаем суперпозицию результата работы функции на всех возможных аргументах. Ещё раз — за один прогон функции мы получаем суперпозицию результатов для всех возможных значений её аргументов. Вот в этом и заключается сила квантовых вычислений.
К взлому метода RSA это имеет прямое отношение. При помощи такой методики можно составить специальный вид квантовых преобразований, который как бы решает задачу разложения на множители. Как сказал отец, при помощи одного прогона такого квантового алгоритма можно найти подсказки для нахождения простых множителей. А найти сами простые множители по этим подсказкам — дело техники. Он не стал посвящать нас в детали этого сложного алгоритма, но сказал, что он в своей лаборатории смог с его помощью разложить на простые множители небольшое число — меньше сотни. Мы с Катей поверили на слово.
Итак, оказалось, что метод шифрования RSA не такой уж и стойкий. Правда, по словам отца, до сих пор квантового компьютера, на котором можно было бы выполнять такой алгоритм, не существует. Но он должен появиться в ближайшее время.
Оказалось, что есть и алгоритм для взлома протокола Диффи — Хеллмана, и это вообще привело меня в уныние — получается, всё то, чему учил нас отец этим летом, можно взломать. Но я вспомнил, как мы проделали эксперимент по передаче информации при помощи квантового протокола, абсолютно стойкого к простым атакам. Так что я вновь приободрился.