Квантовые вычисления продолжают занимать туманное пространство между практическим применением и теоретическими размышлениями, но они приближаются к реальному использованию. Одним из наиболее интересных вариантов использования квантовых компьютеров является современная интернет-криптография.
Квантовые вычисления и кубиты
Квантовые вычисленияНазвание происходит от того факта, что оно основано на свойствах субатомных частиц, управляемых законами, которые кажутся странными тем из нас, кто укоренен в макромире. В частности, квантовые компьютеры используют кубиты (квантовые биты) вместо двоичных цифр (битов), которые мы знаем из традиционных компьютерных систем.
Кубиты имеют вероятностную природу, тогда как биты детерминированы. А кусочек в конечном итоге сводится к физическому переключателю, хотя и очень маленькому, измеряемому несколькими нанометрами. Биты двоичные: включено или выключено, истинно или ложно, 0 или 1.
С кубитами дело обстоит иначе.
Физической основой кубита могут быть многочисленные явления, такие как вращение электрона или поляризация фотонов. Это увлекательная тема: царство линейных уравнений, соединяющих воображение и реальность. Квантовая механика считается интерпретацией лежащей в основе реальности, а не ее описанием, и она является домом для очень сложных вычислений.
Состояние кубита описывается как линейная суперпозиция двух возможных состояний. После наблюдения состояние определяется как истинное или ложное. Однако одни и те же входные данные не обязательно приводят к одному и тому же выходному сигналу, и состояние, когда оно не наблюдается, может быть описано только в вероятностных терминах.
С точки зрения классической физики еще более удивительным является то, что кубиты в квантовом компьютере могут находиться в нескольких состояниях одновременно. Когда компьютер определяет состояние кубита, оно превращается в одно «или-или» (так называемое коллапс волновой функции).
Квантовые вычисления в криптографии
Все это весьма интересно с научной и философской точки зрения. Например, функциональность квантовых компьютеров подтверждает влияние наблюдения на частицы и предполагает, что Бог действительно играет в кости со Вселенной. Но здесь нас интересуют практические аспекты растущей мощности квантовых вычислений в нашей повседневной жизни. В ближайшие годы наиболее глубокое влияние, вероятно, окажет на криптографию.
Самый известный путь от квантовых вычислений к криптографии — это теоретический прорыв, произошедший в 1994 году: алгоритм Шора. Теоретически этот алгоритм показал способность квантовой машины Тьюринга эффективно решать класс задач, которые было невозможно решить с помощью традиционных компьютеров: факторизацию больших целых чисел.
Если вы знакомы с алгоритмами асимметричной криптосистемы, такими как Диффи-Хеллман и RSA, вы знаете, что они основаны на сложности решения коэффициентов для больших чисел. Но что произойдет, если квантовые вычисления решат эту проблему?
Взлом больших целых чисел с помощью квантовой механики
Алгоритм Шора и несколько других алгоритмов используют квантовую механику для взлома односторонних функций, лежащих в основе асимметричной криптографии. Адиабатические квантовые вычисления также использовались для атаки на факторизацию.
Алгоритмы Шора и другие алгоритмы рассчитывают на способность квантового компьютера обитать во множестве состояний благодаря кубитам. Затем они выбирают эти кубиты (что разрушает их состояние) таким образом, чтобы обеспечить высокую степень вероятности выборки. По сути, мы передаем вопрос «Каковы множители данного числа» в таинственный невидимый мир, где свойства частиц могут существовать в нескольких состояниях. Затем мы запрашиваем эти свойства для наиболее вероятного ответа. (Да, это действительно работает.)
Наибольшее число, учтенное алгоритмом Шора, равно 21. Адиабатические квантовые вычисления успешно уложили 143.
Эти алгоритмы сложны и впечатляющи, но пока их количество ничтожно. Текущий стандарт RSA — 2048 бит, то есть 617 цифр! Однако, атакуя число 143, исследователи по незнанию обнаружили подход, который позволяет использовать большие числа, по крайней мере теоретически. Одним из примеров является 56 153, что все еще относительно небольшое число по сравнению с тем, что потребуется для компрометации реальных криптосистем. Это также зависит от редуктивного трюка, который нельзя использовать для всех чисел.
Угроза инфраструктуре веб-безопасности
На данный момент мы знаем, что фундаментальные аспекты квантовой атаки на асимметричные алгоритмы устраняются. Насколько быстро технология продвинется до такой степени, что сможет приблизиться к значительно большим цифрам?
Интересно, что симметричные алгоритмы, которые мы используем каждый день (например, AES), не слишком уязвимы для квантовых алгоритмов. Здесь применяется алгоритм Гровера. Даже теоретически невозможно сократить время, необходимое для атаки этих алгоритмов, намного больше, чем классические алгоритмы, при условии использования 256-битных ключей.
Однако в большинстве случаев симметричной защищенной связи ключи устанавливаются посредством асимметричного обмена. Таким образом, большая часть веб-трафика сегодня уязвима для атак на основе современных квантовых вычислений. Если злоумышленник сможет обнаружить ключ, установленный в начале взаимодействия, никакое симметричное шифрование будет бесполезным.
Таким образом, угроза инфраструктуре веб-безопасности реальна. Давайте на минутку задумаемся о динамике игры. Первое, что следует учитывать, — это чистая экономика и доступ. Сейчас только организации, у которых много денег, могут позволить себе возиться с такими вещами. IBM, Google и ученые-исследователи в Китае соперничают за лидерство в создании жизнеспособных систем, а также за участие в ряде университетских усилий. За кулисами правительственные учреждения, такие как Агентство национальной безопасности США, конечно же, не бездействуют. На самом деле у АНБ есть собственный взгляд на проблему публичной криптографии и квантовых вычислений.
Развитие безопасности квантовых вычислений
Маловероятно, что мелкие субъекты достигнут возможностей квантовых вычислений, достаточных для атаки на современные асимметричные ключи, пока это не сделают крупные организации. Это означает, что мы переживаем длительный период времени, когда инфраструктура безопасности может развиваться в ответ на динамику квантовых вычислений.
Никто не знает, когда появятся по-настоящему криптоопасные квантовые машины, но вполне вероятно, что это произойдет. Двумя критериями, позволяющими разобраться в этом вопросе, являются количество кубитов в системе и долговечность этих кубитов.
Кубиты подчиняются тому, что называется декогеренция. Энтропия всегда уносит хрупкие ансамбли электронов и фотонов. Проблема в том, что количество и долговечность кубитов сложно измерить количественно. Сколько кубитов необходимо для практической воспроизводимой атаки на ключ RSA 2048? Кто-то говорит десятки, кто-то миллионы. Насколько необходима согласованность? Кто-то говорит, что это сотни наносекунд, кто-то — минуты.
И все это можно перевернуть с помощью таких методов, как вышеупомянутое хитрое использование алгоритмов предварительной обработки. Кто знает, какой изобретательный студент сейчас придумывает новый подход. Люди, которые разложили 143 на квантовой машине, даже не осознали, что им удалось разгадать и 56 153, пока два года спустя.
Постквантовая криптография
Все дороги ведут в постквантовый мир, и многие люди уже усердно над ним работают. Национальный институт стандартов и технологий США прямо сейчас проводит конкурсы на разработку квантовоустойчивых алгоритмов. Некоторые из этих усилий приносят результаты.
В конечном счете, основываясь на все более реальных результатах, мы можем сказать, что квантовая угроза криптографии реальна. Но на данный момент это более чем уравновешивается противодействующими силами. Возможно, со временем нам придется попрощаться с некоторыми из наших старых любимых алгоритмов, но их место займут новые.
За этим танцем будет интересно наблюдать в течение следующего десятилетия.
