Идёт гонка за создание новых способов защиты данных и коммуникаций от угроз, исходящих от сверхмощных квантовых компьютеров

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

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

Как работает цифровое шифрование?

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

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

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

Хакеры могут попытаться взломать код, подбирая все возможные варианты ключа. Но защищающиеся стороны очень усложняют им эту задачу, используя пары очень длинных ключей – как в 2048-битной RSA, использующей ключи длиной в 617 десятичных чисел. Перебор всех возможных вариантов приватных ключей займёт тысячи – если не миллионы – лет у обычных компьютеров.

Почему квантовые компьютеры несут угрозу шифрованию?

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

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

Хакеры также, скорее всего, попытаются использовать во вред алгоритмы оптимизации определенных задач. Один из таких алгоритмов, опубликованный Ловом Гровером из AT&T Bell Labs, помогает квантовым компьютерам гораздо быстрее искать варианты. Другой алгоритм, опубликованный в 1994 году Питером Шором, тогда также работавшим в Bell Labs, а теперь профессором в MIT, помогает квантовым компьютерам невероятно быстро находить простые множители целых чисел.

Алгоритм Шора угрожает таким системам с публичным ключом, как RSA, чья математическая защита в частности зависит от того, насколько сложно провести обратный инжиниринг результата перемножения очень больших простых чисел (разложение на множители). В отчёте по квантовым вычислениям, опубликованном в прошлом году национальной академией наук, инженерного дела и медицины США, предсказывается, что мощный квантовый компьютер, на котором работает алгоритм Шора, сможет взламывать 1024-битные варианты RSA менее, чем за день.

Смогут ли квантовые компьютеры взламывать криптографическую защиту в ближайшее время?

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

Однако, год, в котором квантовый взлом кодов станет серьёзной головной болью – который некоторые исследователи безопасности окрестили Y2Q – может подобраться неожиданно быстро. В 2015 году исследователи заключили, что для достаточно быстрого взлома 2048-битного RSA шифрования квантовому компьютеру понадобится миллиард кубитов. В более современной работе указывается, что компьютер с 20 млн кубитов сможет справиться с этой задачей всего за 8 часов.

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

Любое предприятие или правительство, рассчитывающее хранить данные несколько десятилетий, должно уже сейчас задуматься над тем, какие риски несёт в себе новая технология, поскольку используемое ими сегодня шифрование может быть взломано в будущем. На перекодирование огромных объёмов исторических данных в более надёжный вид могут уйти года, поэтому лучше будет применять надёжное кодирование сегодня. Отсюда проистекает запрос на постквантовую криптографию.

Какой будет постквантовая криптография?

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

Одна из линий обороны – увеличение размеров цифровых ключей для значительного увеличения количества вариантов, в которых нужно будет вести поиск перебором. К примеру, простое удвоение размера ключа с 128 до 256 бит учетверяет количество возможных вариантов, которые придётся перебрать квантовой машине, использующей алгоритм Гровера.

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

Цель исследований – выбрать один или несколько методов, которые затем можно будет широко применять. Национальный институт стандартов и технологий США запустил в 2016 году разработку стандартов постквантового шифрования для правительственного использования. Он уже сузил изначальный набор заявок с 69 до 26, но говорит, что первые черновики стандартов, скорее всего, появятся не ранее 2022 года.

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