О квантовых компьютерах говорят еще с восьмидесятых годов. И хотя с ними до сих пор мало кто сталкивался, они все же постепенно становятся реальностью и начинают угрожать традиционной криптографии. В ответ на это появились постквантовые алгоритмы шифрования. В статье я покажу, как они используются в OpenVPN, а заодно обсудим общее положение дел в мире квантовых технологий.
Всякий, кто желает обеспечить защиту своих данных дольше десяти лет, должен сейчас перейти на альтернативные формы шифрования.
Арвинд Кришна, директор исследовательского подразделения IBM (в настоящее время президент и генеральный директор IBM)
В марте 2018 года ученые из Google объявили о создании 72-кубитного компьютера Bristlecone. Параметры компьютера точно неизвестны. Видимо, они были неидеальны, потому что о квантовом превосходстве в Google заговорили лишь в октябре 2019 года, а достичь его удалось на 53-кубитном компьютере Sycamore.
Квантовым превосходством называют ситуацию, когда квантовый компьютер решает такую задачу, которая простому компьютеру не по зубам.
За 200 секунд Sycamore получил результат, который классический суперкомпьютер искал бы 10 тысяч лет. Хотя в Intel компьютерное превосходство Google оспорили и в целом оказалось, что задача была искусственно составлена под результат, стало ясно, что в районе 50+ кубит находится граница, за которой квантовый компьютер может «побить» классический. Правда, только в узком классе специфических задач.
В конце 2020 года китайские исследователи из Научно‑технического университета Китая объявили о решении на их квантовом компьютере задачи, которая в принципе не может быть решена на классическом компьютере, поскольку для этого потребовалось бы время, равное половине жизни Земли.
Исследователи из IBM в то же время заявили, что уже в 2021 году планируют построить квантовый компьютер с 127 кубитами, в 2022 году они надеются иметь 433 кубита, в 2023 году 1121 кубит, а далее они видят перспективу дойти аж до миллиона кубитов и более. Планов громадье!
Проблема, однако, не только в количестве кубитов. При работе квантовых вентилей, то есть при выполнении унитарных операций над кубитами, неизбежно возникают ошибки. Их вероятность невелика, но не нулевая. В процессе вычислений ошибки накапливаются, и без коррекции трудно получить правильный результат. Под действием окружающей среды происходит декогеренция системы, то есть разрушение ее квантового состояния (состояния запутанности кубитов изолированной системы).
Время декогеренции, то есть время поддержания системы кубитов изолированной от окружающей среды, — принципиальный фактор при построении большого квантового компьютера. Если это время меньше времени, необходимого для квантовых вычислений, в системе при вычислении возникают ошибки и в результате вычислений мы получим только рандомизированный шум. Изоляция системы, уменьшение уровня ошибок на вентилях и создание эффективных алгоритмов, корректирующих ошибки, — эти направления работы становятся в последнее время приоритетными и активно разрабытываются в ведущих исследовательских центрах.
Чтобы корректировать ошибки, в квантовых алгоритмах применяются логические кубиты, состоящие из нескольких физических кубитов. Состояние единичного кубита кодируется в перепутанных состояниях нескольких кубитов. Поэтому в квантовом компьютере с коррекцией ошибок реальных кубитов потребуется намного больше. Например, один из первых предложенных для коррекции ошибок 7-кубитовый код Стина (Stean) использует семь кубитов для хранения одной единицы (кубита) квантовой информации.
Параллельно с работой над физической реализацией квантового компьютера разрабатываются квантовые алгоритмы. На прилавках уже появились научно‑популярные брошюры, помогающие всем желающим начать изучать основы квантового программирования. Особое место занимает проект IBM Quantum Experience, позволяющий создавать квантовые алгоритмы и запускать их на квантовых компьютерах IBM и симуляторах.
От себя порекомендую упомянутый фундаментальный труд Нильсена и Чанга, насчитывающий уже десяток переизданий. Есть перевод на русский язык одного из первых изданий, книга называется «Квантовые вычисления и квантовая информация».
В России тоже есть специалисты, готовые к созданию большого квантового компьютера. В МГУ готовят магистров по программе «Квантовые вычисления», есть программы по квантовой криптографии и связи, по квантовым оптическим технологиям. В МФТИ читают лекции по квантовой теории информации, в других университетах есть похожие курсы.
Квантовый компьютер рационально использовать для решения очень небольшого класса задач. Это моделирование квантовых систем. Например, в химии это расчеты химических реакций или расчеты пространственной структуры молекул при создании новых материалов или лекарств. Это задачи оптимизации, например в расчетах сложной логистики (типа задачи коммивояжера). Это криптоанализ существующих шифров.
Именно публикация алгоритма Шора (Shor) в 1994 году, использующего быстрое квантовое преобразование Фурье для факторизации больших чисел, подогрела интерес к квантовому компьютеру, вызвала бум исследований в этой области и направила на их развитие огромные ресурсы.
Есть американская организация ASC X9, где разрабатывают глобальные финансовые стандарты, в том числе в области криптографической защиты финансовых данных. Членами этой организации являются Bank of America, Citigroup, JPMorgan Chase, Федеральная резервная система, платежная система VISA и Агентство национальной безопасности США. Фирма веников не вяжет, как говорят в народе. И вот в январе 2018 года эта структура озаботилась рисками для финансовых организаций от квантового компьютера и в начале 2019 года выпустила информационный отчет ASC X9 IR 01—2019. Отчет приводит такую логику: если предположить, что к 2028 году ожидается появление квантового компьютера, способного взломать защиту, например, пластиковых карт, рассчитанных на пять лет использования, то применение классической криптографии должно быть прекращено и защита переведена на квантово устойчивую криптографию как минимум за пять лет до потенциальной атаки. Если учесть время на переход от классики к постквантовой криптографии, то переход должен быть начат уже сейчас.
С оговорками и без окончательных выводов, в информационном отчете оценивается ежегодный прирост числа кубитов в 35%. Не закон Мура, но все же. Такими темпами тысячекубитный квантовый компьютер может быть сделан через семь‑восемь лет. Но на самом деле для обоснованного прогноза пока очень мало данных.
Примечательно, что в АНБ изменили рекомендации по шифронаборам для защиты информации. Из так называемого Suite B (сейчас это CNSA Suite) исчезла Curve P-256 для ECDH и ECDSA, хотя модули 3072 bit для RSA остались.
А ведь всегда считалось, что по криптостойкости P-256 и RSA-3072 равны и соответствуют стойкости симметричного алгоритма AES-128.
Но AES-128 хотя бы для SECRET в обновленном Suite B тоже нет, только AES-256 для TOP SECRET. В FAQ АНБ и Центральной службы безопасности (CSS) Минобороны США по CNSA Suite и квантовым вычислениям MFQ-U-OO-815099-15 четко разъяснено, что в национальных системах безопасности (NSS) следующие алгоритмы, ранее одобренные для SECRET, не должны использоваться:
Таким образом, CNSA Suite сейчас включает в себя следующие алгоритмы (отдельно подчеркнуто, что до момента, когда будут разработаны квантово устойчивые алгоритмы).
Если это связать с оптимистичными прогнозами о разработке квантовых компьютеров, то можно построить правдоподобную версию. Так, в 2017 году исследователи из Microsoft Research опубликовали статью, в которой дали следующую оценку: для вычисления дискретного логарифма на стандартной эллиптической кривой P-256 над конечным полем достаточно 2330 кубитов, в то время как для факторизации RSA с модулем 3072 необходимо 6146 кубитов, то есть почти в три раза больше.
Получается, что для квантовых вычислений P-256 и RSA-3072 по криптографической стойкости совсем не равны. В АНБ, вероятно, могли получить аналогичные данные ранее, при этом мы не можем исключить существование более глубокой оптимизации алгоритма Шора для эллиптических кривых.
Если в течение десяти лет будет построен квантовый компьютер с 2300+ кубитами, он, предположительно, сможет с помощью алгоритма Шора взломать короткие ключи ECC, начиная с 256-битовых ключей, а с помощью алгоритма Гровера (Grover), решающего задачу перебора, ослабить примерно в два раза симметричные ключи AES. То есть криптостойкость AES-128 уменьшится до 264 операций, что в обозримом будущем может оказаться неприемлемым, криптостойкость же AES-256, снизившись до 2128 операций, останется достаточной, поскольку сегодня считается, что выполнение 2128 операций недостижимо.
Вот любопытный пример того, как идет работа над совершенствованием квантовых алгоритмов. В конце 2015 года вышла статья «Оценка квантовых ресурсов для применения алгоритма Гровера к AES», и расчеты авторов показывали, что для взлома AES-128 необходимо 2953 кубита (второй столбец таблицы ниже).
А в 2019-м исследователи из солнечной Флориды оптимизировали квантовый алгоритм и рассчитали, что для взлома AES-128 необходимо лишь 865 кубитов (третий столбец таблицы).
Представляется, однако, что, даже когда будет тысячекубитный квантовый компьютер, необходимое для атаки огромное количество вычислений окажется пока практически неподъемным. И понятно, почему АНБ оставило RSA-3072: такой длины ключ пока также будет стойким.
Но самый любопытный и интригующий пассаж в отчете ASC X9 следующий. На момент публикации отчета самый большой квантовый компьютер имел 72 кубита. Однако, как указывают авторы отчета, есть мнение, что более мощные квантовые компьютеры существуют, но информация о них не опубликована. Авторы полагают, что могут существовать квантовые компьютеры примерно со 100 кубитами!
Материалы из последних выпусков становятся доступны по отдельности только через два месяца после публикации. Чтобы продолжить чтение, необходимо стать участником сообщества «Xakep.ru».
Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», позволит скачивать выпуски в PDF, отключит рекламу на сайте и увеличит личную накопительную скидку! Подробнее
1 год9300 р. |
1 месяц870 р. |
Я уже участник «Xakep.ru»
Читайте также
Последние новости