быстрый доступ
9 марта 2022, 09:45
Количество просмотров 113

Постквантовая криптография. Готовимся сегодня?

Постквантовая криптография. Готовимся сегодня?
То, как могут повлиять на технологии криптографии и всей отрасли, базирующейся на их использовании, те новые возможности, которые могут открыться благодаря доступности квантовых вычислений, рассматривает Игорь Голдовский, директор Департамента инноваций, главный архитектор АО НСПК. Как и в своих предыдущих материалах, он выступает в качестве независимого эксперта в области платежных технологий, с чьим богатым опытом и всесторонней профессиональной экспертизой в области электронных платежей мы продолжаем знакомить наших читателей.

Предыдущие материалы: 1, 2.

Сегодня в СМИ, в том числе в профессиональных изданиях, периодически появляются материалы, посвященные вопросам создания и применения квантовых компьютеров. Все сходятся в том, что сегодняшние квантовые компьютеры, имеющие память в диапазоне от 50 до 100 кубитов, оказать заметного влияния на нашу повседневную жизнь не могут. Нужны машины, обладающие хотя бы несколькими тысячами кубитов памяти и работающие с невысокой вероятностью ошибки — не выше 0,5% на один кубит.

Никто не знает точного времени появления квантовых компьютеров с такими параметрами. Некоторые авторитетные эксперты утверждают, что это может случиться уже в 20-е годы нашего столетия. Другие специалисты говорят о том, что на достижение такого результата могут уйти десятилетия.

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

  • задачи факторизации целых чисел и логарифмирования в конечном поле (о них будет сказано ниже), при решении которых квантовые компьютеры дают экспоненциальное ускорение в сравнении с классическими компьютерами. Решение этих задач лежит в основе практически всех применяемых алгоритмов асимметричного шифрования;
  • задачи полного перебора: квантовый компьютер позволяет получить здесь квадратичное ускорение, что, например, потребует увеличения размера ключей в симметричных алгоритмах шифрования;
  • задачи моделирования физических и химических систем. Грубо говоря, квантовый вероятностный характер вычислений позволяет параллельно моделировать различные состояния подобных систем.

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

Что можно и что нельзя взломать с помощью квантовых вычислений?

Как будет рассказано ниже, для квантовых компьютеров были придуманы алгоритмы (алгоритмы Шора и Гровера (Shor Grover)), оказывающие существенное влияние на криптостойкость сегодняшних криптографических алгоритмов [Circuit for Shor’s algorithm using 2n+3 qubits. Stephane Beauregard, 2003; Shor’s discrete logarithm quantum algorithm for elliptic curves. John Proos, Christof Zalka, 2008]. В частности, наиболее широко используемые на практике алгоритмы асимметричного шифрования RSA, DSA, ECDSA, EdDSA, EC-SDSA перестают быть криптостойкими и взламываются (находится секретный ключ) за полиномиальное от размера публичного ключа время. Это утверждение верно для любых алгоритмов асимметричного шифрования, криптостойкость которых базируется на трудоемкости решения математических задач факторизации (разложения числа на простые сомножители) и дискретного логарифмирования в конечном поле или на множестве точек эллиптической кривой. Другими словами, все массово используемые алгоритмы асимметричного шифрования требуется менять на алгоритмы, криптостойкость которых базируется на трудоемкости решения неких иных математических задач!

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

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

01.jpg
Фото: businessfeed.ge

В то же время существуют алгоритмы шифрования, которые «ломаются» с помощью квантовых алгоритмов за полиномиальное время. В качестве примера можно привести варианты алгоритма DES: 2K-DES (выполняет 64 раунда шифрования 96 битным ключом, который представляется в виде двух 48 битных половинок, поочередно используемых в раундах алгоритма) и 4K-DES (то же количество раундов выполняется с уже 192 битным ключом, который представляется в виде четырех поочередно используемых 48 битных частей). С помощью квантового алгоритма Саймона (Simon) ключи этих алгоритмов находятся за полиномиальное время.

Следует отметить, что эти алгоритмы относительно просто вскрываются и с помощью классических компьютеров с использованием так называемой сдвиговой атаки, изобретенной Алексом Бирюковым (Alex Biryukov) и Дэвидом Вагнером (David Wagner). Для вскрытия 2K-DES с помощью этой атаки требуется всего 232 известных открытых текстов и 233 операций шифрования. Однако тот же алгоритм Саймона позволяет вскрыть российский алгоритм шифрования, определенный в стандарте ГОСТ Р28147–89, используя 2114.8 квантовых запросов, что в 213.2 раз быстрее, чем вскрытие этого алгоритма шифрования с помощью алгоритма Гровера (квантового перебора ключей).

Еще меньшее влияние появление квантовых компьютеров окажет на стойкость хэш-функций (под стойкостью в данном случае понимается трудоемкость решения задачи поиска коллизии хэш-функции). Асимптотически потребуется увеличить длину значения хэш-функции в полтора раза. Например, вместо функции SHA-256 потребуется применять функцию SHA-384.

Что делать?

Как мы видим, последствия от появления квантовых компьютеров значительные, а поскольку криптография сегодня используется массово (достаточно в качестве примера привести протокол TLS, практически постоянно используемый пользователями интернета), то готовиться к их появлению нужно уже сегодня. Именно так рассудил Национальный институт по стандартизации США (NIST), который еще в 2016 году запустил проект PQC (Post-Quantum Cryptography) Standardization.

У проекта PQC (Post-Quantum Cryptography) Standardization три задачи:

  1. Заменить схемы создания цифровой подписи, определенные в стандарте FIPS 186–4 (RSA, DSA, ECDSA)
  2. Заменить протокол шифрования данных при передаче ключей, определенный в SP 800–56B и основанный на использовании RSA
  3. Заменить протокол согласования ключей, определенный в SP 800–56A, в основе которого лежит алгоритм Диффи- Хеллмана (Diffie- Hellman).

В конце 2016 года NIST выпустил сообщение (Federal Notice) о сборе предложений по решению перечисленных задач до конца 2017 г. В 2018 г. NIST приступил к анализу полученных многочисленных предложений и планирует до конца 2023 г. завершить выбор алгоритмов, решающих поставленные задачи. При этом допускается выбор нескольких победителей. Из сообщения NIST: We may not be able to select one single winner for each function (signature, encryption, key agreement).

02.jpg

NIST также внимательно изучает процесс миграции со старых алгоритмов на новые. Речь идет о работе в т. н. гибридной моде, когда какие-то пользователи пока поддерживают только старые алгоритмы. Предполагается, что наряду с поддержкой новых алгоритмов пользователи должны будут в течение какого-то времени поддерживать и старые алгоритмы. Такие продвинутые пользователи будут генерировать подпись документа с использованием старого и нового алгоритмов, и продвинутым пользователем подпись будет признаваться при наличии двух подписей сообщения и только когда обе подписи верны.

NIST предполагает, что миграция на постквантовые криптографические алгоритмы начнется в 2030 году. До этого времени ожидается использование в основном сегодняшних стандартов FIPS.

Состояние дел с построением квантовых компьютеров

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

Сегодняшними мировыми лидерами в построении универсальных квантовых компьютеров являются компании Google, IBM и Intel. В марте 2018 года компания Google объявила, что ей удалось построить 72 кубитный квантовый процессор Bristlecone, имеющий низкую вероятность ошибок в вычислениях: вероятность ошибки в 2 кубитном логическом элементе процессора Bristlecone составляет 0,6%, что чуть выше уже упоминавшегося нами значения (0,5%), установленного в техническом задании на разработку. Компания не раскрыла подробных характеристик своего устройства, однако утверждает, что оно позволяет достичь «квантового превосходства».


magazine-green
Полный текст доступен только по подписке
Если у вас есть аккаунт, авторизуйтесь
Подписаться
Рубрика:
{}Безопасность