Криптография перед эпохой квантовых вычислений
Недавно мы провели встречу экспертного сообщества по криптографии и квантовым технологиям, в которой приняли участие ведущие российские компании данной отрасли — «Российский квантовый центр», QApp, «Криптонит», «КриптоПро», «ЭЛВИС-ПЛЮС» и другие. На мероприятии обсудили развитие квантовых и гибридных вычислительных алгоритмов, разработку квантовых компьютеров и связанные с этим вызовы для криптографии. Эксперты обозначили ряд принципиальных моментов, подробнее о которых мы расскажем в этой статье.
Какие бывают квантовые компьютеры?
В России ведётся разработка квантовых компьютеров всех основных типов: на ионах (ионных ловушках), на холодных атомах (в оптических ловушках), на сверхпроводниках и фотонных чипах. Как и во всём мире, пока это штучные экспериментальные установки, далёкие от практического применения. На них отрабатывают различные инженерные подходы, тестируют алгоритмы и принципы дальнейшего масштабирования.
В то же время существует альтернативный подход к архитектуре квантовых процессоров, основанный на полупроводниковых технологиях. Он может оказаться востребованным уже на следующем этапе — промышленного производства квантовых компьютеров.
Где актуальны квантовые алгоритмы?
«Какими бы ни были по своей природе компьютеры будущего, сейчас нужно разрабатывать универсальные квантовые алгоритмы, без которых вычислительная система с любым количеством кубитов окажется дорогой и бесполезной железкой. В своей практике мы часто сталкиваемся с задачами комбинаторной оптимизации. Именно на них мы таргетируем свои исследования и разработку своих алгоритмов», — сказал эксперт компании QBoard Антон Божедаров.
Участники встречи отметили, что также важно разрабатывать гибридные алгоритмы для гетерогенных вычислительных систем. В них квантовый процессор или его эмулятор ускоряют отдельные операции, на которые компьютеры классической архитектуры потратили бы слишком много времени. Уже существует целый ряд «квантово-вдохновлённых» архитектур и алгоритмов, которые помогают решать некоторые практические задачи. В качестве примера можно обратиться к опыту D-Wave.
В 2017 году канадская компания D-Wave Systems совместно с мюнхенской лабораторией Volkswagen решила задачу оптимизации городских маршрутов в Пекине. Для этого специалисты проанализировали GPS-треки 418 такси с помощью квантового (точнее, квантово-вдохновлённого) компьютера D-Wave 2X. Исследователи выполнили квадратичную бинарную оптимизацию треков, что позволило рассчитать оптимальные маршруты движения.
Интересно, что при решении этой задачи физические ограничения архитектуры D-Wave 2X были успешно преодолены за счёт оригинального алгоритмического подхода. Квантовый процессор D-Wave 2X представляет собой решётку, содержащую 1135 функциональных кубитов с ограниченной связанностью (принципиальный момент). При этом для оптимизации трафика требовалось закодировать 1 254 логических переменных. Ограничение удалось обойти с помощью минорного встраивания — метода, при котором одна структура графа отображается на другую, а также с помощью гибридного инструмента qbsolv, позволяющего часть промежуточных вычислений выполнять на обычном процессоре.
Чисто квантовые алгоритмы эффективны в решении задач дискретной оптимизации (с квадратичными функциями) и смешанного программирования (MIP, где целевая функция состоит из вещественных и бинарных, либо целочисленных переменных). Также квантовые алгоритмы дают существенный выигрыш по скорости в задачах квадратичной бинарной оптимизации (QUBO) и смешанного квадратичного программирования (MIQP).
Сейчас больше всего разговоров о том, что появление квантовых компьютеров (и соответствующих квантовых алгоритмов) создаст серьёзные проблемы современной криптографии. Эти опасения обоснованы, правда — лишь отчасти.
Что такое CRQC?
Ключевое понятие для оценки квантовых угроз механизмам шифрования и электронной подписи —криптографически-релевантный квантовый компьютер, или CRQC. Это универсальный (способный взламывать актуальные криптографические алгоритмы) и достаточно мощный компьютер с квантовым процессором. В нём будут (как минимум) тысячи логических кубитов и межкубитных соединений, но главное — он сможет стабильно работать. Для этого потребуется разработать и реализовать алгоритмы коррекции ошибок, учитывающие аппаратную специфику конкретной квантовой платформы.
В настоящее время CRQC не существует. Его появление аналитики Gartner прогнозируют примерно в 2030 году, при условии сохранения тенденции к увеличению объёмов инвестиций в разработку квантовых компьютеров. С момента появления CRQC многие популярные криптографические алгоритмы, включая RSA, ECDSA, ГОСТ Р 34.10–2012 и схемы обмена ключами на основе протокола Диффи — Хеллмана, окажутся уязвимыми. Поэтому замену им нужно разрабатывать уже сейчас.
Криптографические механизмы постквантовой эры
Сейчас в криптографии наступает интересный период развития: разрабатываются новые криптографические механизмы, которые призваны защитить от «квантовой угрозы», которая неизвестно когда явится и в каком обличии.
Так, на проходившем в 2016–2022 годах конкурсе NIST рассматривалось 69 постквантовых алгоритмов инкапсуляции ключа и электронной подписи. Все они были основаны на одном из классов математических задач, которые останутся вычислительно сложными после появления CRQC:
на основе хеш-функций (например — SPHINCS+, в разработке которого принял участие Михаил Кудинов, на тот момент являвшийся сотрудником российской компании QApp);
на основе кодов, исправляющих ошибки (Classic McEliece);
на основе алгебраических решёток (CRYSTALS-Dilithium, Falcon);
на основе систем квадратичных полиномов (частично взломаны);
на основе изогений эллиптических кривых (взломаны);
Одним из перспективных типов постквантовых алгоритмов являются схемы, построенные на основе вычислительно сложных задач из теории кодов, исправляющих ошибки. На момент начала конкурса NIST в научном сообществе даже не было понимания того, какой должна быть электронная подпись (ЭП) на кодах. Все представленные на конкурс алгоритмы подписи на основе кодов, исправляющих ошибки, не прошли даже его первый раунд. Как отметил руководитель лаборатории криптографии компании «Криптонит» Василий Шишкин, в «Криптоните» решили не ориентироваться на NIST, а проводить собственные исследования. Результатом стала постквантовая схема ЭП «Шиповник», для которой коллегами из QApp уже подготовлена открытая быстрая реализация.
Также в «Криптоните» ведётся разработка постквантового протокола инкапсуляции ключа на кодовой криптосистеме с открытым ключом типа Мак-Элиса.
«Мы создаём пул алгоритмов, который закроет основные проблемы в криптографии после появления квантового компьютера», — сказал зам. руководителя лаборатории криптографии по научной работе компании «Криптонит», кандидат физико-математических наук Иван Чижов.
В свою очередь, исследователи компании QApp, опираясь на экспертизу, полученную при анализе схемы SPHINCS+, разработали собственную схему ЭП «Гиперикум», основанную на хеш-функциях. Как подчеркнул ведущий разработчик этой схемы Олег Турченко, использование в схеме «Гиперикум» отечественной хеш-функции «Стрибог» даёт возможность использовать уже имеющиеся аппаратные средства для её ускорения.
Интересно, что «Гиперикум» и «Шиповник» — это не конкуренты, а дополняющие друг друга в разных сценариях использования решения.
Угрозы будущего в настоящем
Системный архитектор компании «ЭЛВИС-ПЛЮС» Валерий Смыслов рассказал в своём докладе, что в настоящее время в России отсутствуют стандартизированные постквантовые механизмы обмена ключами. При этом постквантовые алгоритмы целесообразно внедрять ещё до появления CRQC, поскольку срок секретности для коммерческой и государственной тайны исчисляется годами (даже десятками лет). Новая атака Harvest and Decrypt (известная также как Harvest Now, Decrypt Later или Store Now, Decrypt Later) предполагает возможность перехвата зашифрованного сетевого трафика уже сейчас и сохранение его до момента появления CRQC, который даст возможность быстро его расшифровать. Чем раньше мы уйдём от квантово-уязвимых схем, тем больше сможем сохранить в секрете.
Валерий Смыслов отметил, что в настоящее время известны четыре основных способа противодействия «квантовой угрозе». Это отказ от асимметричных схем при выработке сеансовых ключей, квантовое распределение ключей, использование комбинированных схем с дополнительным симметричным ключом и применение для вычисления сеансовых ключей постквантовых криптографических механизмов.
Инженерный совет интернета (IETF) ориентируется на два последних способа при модификации протоколов для защиты от квантовой угрозы. При этом комбинированные схемы с дополнительным симметричным ключом считаются краткосрочным решением, позволяющим получить защиту прямо сейчас, а использование постквантовых криптографических механизмов — перспективным решением. В последнем случае классические механизмы с открытым ключом, используемые для вычисления общего ключа, заменяются в протоколах на их постквантовые функциональные аналоги.
В IETF как один из способов внедрения постквантовых механизмов в существующую инфраструктуру рассматривается гибридная схема постквантового обмена ключами. Это метод вычисления общего секрета, в котором используется комбинация из классического протокола (например, Диффи — Хеллмана на эллиптических кривых — ECDH) и одного или нескольких постквантовых алгоритмов, базирующихся на разных математических принципах. В гибридной схеме общий секрет зависит от всех задействованных механизмов. Делается это для того, чтобы минимизировать риски перехода на малоизученные криптографические механизмы, в то же время, обеспечив стойкость на фоне растущей «квантовой угрозы».
«На сегодня крайне важным направлением в контексте обеспечения массовой защиты от квантовой угрозы является встраивание постквантовых алгоритмов в протоколы TLS и IPsec, а также проработка инфраструктуры открытых ключей (PKI). Мы занимаемся практической реализацией этих задач. Одним из открытых вопросов, требующих тщательной проработки, является создание средств криптографической защиты информации (СКЗИ), защищённых от атак по побочным каналам», — сказал Евгений Алексеев, кандидат физико-математических наук, начальник отдела криптографических исследований «КриптоПро».
На программном уровне замена криптографических алгоритмов на постквантовые может быть выполнена хоть сейчас.
«У нас есть готовое решение для доставки российских и зарубежных постквантовых алгоритмов в конечные продукты. Это PQLR SDK — переносимый на все актуальные вычислительные архитектуры набор средств разработки, поддерживающий интеграцию с различными крипто-провайдерами (OpenSSL, Java JCA, Android Conscrypt)», — отметил Сергей Гребнев, руководитель группы прикладных исследований QApp.
Эмулируй это!
Для разработки и проверки квантовых алгоритмов сегодня применяются эмуляторы квантовых вычислителей, построенные на графических процессорах (ГП) и ПЛИС. Они же используются для обучения работе с квантовыми алгоритмами.
Например, подразделение Российского квантового центра QBoard предоставляет удалённый доступ к образовательному эмулятору 30-кубитного компьютера «Телеквант». В нём можно решать задачи из области моделирования, оптимизации и машинного обучения, описывая их на языке OpenQASM.
Также в РКЦ разработан и доступен через облачную платформу программный эмулятор SimCim, основанный на моделировании когерентной машины Изинга. Он применяется для решения задач из области дискретной оптимизации, позволяя одновременно использовать до 5 000 переменных.
Ожидания и реальность
В России приказом Минцифры от 31.07.2020 утверждена дорожная карта развития квантовых вычислений до 2024 года. Согласно этому документу, до конца 2023 года планировалось создание квантового компьютера минимум на 30 кубит и разработка не менее пяти квантовых алгоритмов. Из-за пандемии и ряда других событий фактические сроки сдвинулись. На сегодня продемонстрирован лишь 16-кубитный квантовый компьютер, созданный в лаборатории ФИАН. Однако в части написания алгоритмов результат превзошёл ожидания. Исследователи «МИСиС» и Российского квантового центра создали целую библиотеку алгоритмов для разработки квантовых программ.
«Часто спрашивают о том, когда мы сможем пользоваться постквантовой криптографией. Я уже пользуюсь! Могу на смартфоне включить постквантовое шифрование и позвонить в офис, в том числе по видеосвязи», — сказал Сергей Гребнев, демонстрируя новое мобильное приложение, разрабатываемое в QApp.
Сергей напомнил, как в 2022 году китайские коллеги сделали вид, что нашли эффективный подход к взлому RSA. Они опубликовали об этом статью «Factoring integers with sublinear resources on a superconducting quantum processor». Коллектив российских учёных, объединивший специалистов из QApp, QBoard и Сбера, провёл исследование и выяснил, что авторы очень сильно завысили оценку эффективности метода. На данный момент общепринято, что для факторизации ключа RSA длиной 2048 бит потребуется компьютер с миллионами физических кубитов, а не с 372-мя, как утверждалось в статье.
Мифы постквантовой криптографии
«В любой новой области появляются мифы, связанные с недостатком информации. Их важно развенчивать в ходе публичной дискуссии, чтобы мы могли лучше понимать друг друга и вырабатывать эффективные стратегии взаимодействия», — сказал Станислав Смышляев, доктор физико-математических наук, заместитель генерального директора «КриптоПро».
Среди наиболее распространённых заблуждений Станислав Смышляев отметил следующие:
Чтобы защищаться от квантовых угроз в криптографии, нужен квантовый компьютер?
Нет, не нужен. В качестве меры противодействия уже разрабатываются принципиально другие криптографические алгоритмы, взлом которых будет не по силам квантовым компьютерам.
Квантовые компьютеры и квантовые угрозы — никому не нужная абстракция?
В реальности это уже технология уровня прототипа и угроза для целого ряда криптографических алгоритмов, основанных на задачах факторизации и дискретного логарифмирования.
Квантовый компьютер появится со дня на день, а может и уже появился в какой-нибудь секретной лаборатории. Получается, что постквантовые алгоритмы нужно было внедрять ещё вчера?
Прогресс в разработке квантовых компьютеров действительно впечатляет, но до появления криптографически-релевантной модификации потребуется преодолеть целый ряд проблем, связанных со временем удержания когерентного состояния, устранением шумов и связанных с ними ошибок, необходимым числом логических кубитов и связей между ними. При самом благоприятном сценарии это займёт годы.
Переход на постквантовые алгоритмы обойдётся в триллионы рублей?
Вовсе нет. Замена классических алгоритмов на постквантовые — наименее затратный путь предотвращения «квантовой угрозы». Он обойдётся гораздо дешевле создания «квантового интернета», поскольку не потребует ничего менять физически. Смена основных криптографических алгоритмов производилась и ранее, в том числе и в нашей стране. Это требует исследований, разработок и вложений средств, но этот путь уже был пройден не раз. Все замены пройдут на уровне стандартов, протоколов и реализаций криптографических средств, а конечные пользователи даже не заметят этого.
Выводы
Появление мощного квантового компьютера теоретически несёт угрозу некоторым криптографическим алгоритмам, применяющимся в основном для защиты данных, передаваемых через интернет. Поэтому разработка постквантовых схем электронной подписи и протоколов инкапсуляции ключа является актуальной задачей. Это не означает, что мы должны срочно внедрять хоть что-нибудь и как-нибудь. Есть процедуры экспертной оценки новых алгоритмов, их отбора и стандартизации, которые необходимо соблюдать для создания надёжного криптографического фундамента.
При этом симметричные алгоритмы шифрования с достаточной длиной ключа будет сложно взломать и в эпоху доступных квантовых вычислений, следовательно — острой необходимости искать им альтернативу сейчас нет.
«Есть математические предпосылки считать, что квантовый компьютер никогда не научится быстро решать вычислительные задачи определённого типа. В частности, квантовому компьютеру не под силу быстро находить корни нелинейного уравнения над конечным полем. Поэтому основные криптографические стандарты, описывающие хеш-функции (ГОСТ 34.11–2018 «Стрибог», SHA-3) и блочные шифры (ГОСТ 34.12–2018 «Магма», «Кузнечик» и AES) останутся актуальными и после появления CRQC», — пояснил Иван Чижов.
Самым простым способом подготовиться к «квантовой» угрозе будет замена потенциально уязвимых классических алгоритмов шифрования и электронной подписи на постквантовые. Сделать это нужно как можно быстрее из-за возможности атаки типа harvesting decrypt в ближайшем будущем, но без ущерба для полноты экспертного анализа стойкости предлагаемых на замену алгоритмов.
