Материал из РУВИКИ — свободной энциклопедии

Постквантовая криптография

Постквантовая криптография
Краткое имя/название PQC
Против криптоанализ

Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми для криптографических атак. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора[1][2]. Многие криптографы в настоящее время ведут разработку алгоритмов, независимых от квантовых вычислений, то есть устойчивых к квантовым атакам.

Существуют классические криптосистемы, которые опираются на вычислительно сложные задачи и имеют ряд существенных отличий от указанных выше систем, из-за чего их гораздо сложнее решить. Эти системы независимы от квантовых вычислений, и, следовательно, их считают квантово-устойчивыми (quantum-resistant), или «постквантовыми» криптосистемами.

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

Алгоритмы[править | править код]

Постквантовые криптографические конструкции способны спасти криптографический мир от квантовых атак. Хотя квантовый компьютер и уничтожит большинство традиционных алгоритмов (RSA, DSA, ECDSA), но сверхбыстрыми вычислениями не получится полностью избавиться от криптографии, так как постквантовая криптография, в основном, сосредоточена на пяти различных подходах, решающих проблему квантовых атак[2][3].

Криптография, основанная на хеш-функциях[править | править код]

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

Криптография, основанная на кодах исправления ошибок[править | править код]

Является одним из наиболее перспективных кандидатов на пост-квантовые криптосистемы. Классическим примером является схемы шифрования McEliece и Niederreiter.

Криптография, основанная на решётках[править | править код]

Классическим примером схем шифрования являются Ring-Learning with Errors[4][5][6][7] или более старые NTRU, GGH и криптосистема Миччанчо.

Криптография, основанная на многомерных квадратичных системах[править | править код]

Одной из самых интересных схем является подпись с открытым ключом Жака Патарина HFE, предложенная им в 1996 году как обобщение предложений Matsumoto и Imai[2].

Шифрование с секретным ключом[править | править код]

Ярким примером является шифр Rijndael, предложенный в 1998 году, впоследствии переименованный в AES (Advanced Encryption Standard).

Шифрование с использованием суперсингулярной изогении[править | править код]

Это аналог протокола Диффи-Хеллмана, основанный на блуждании в суперсингулярном изогенном графе, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищённый от прослушивания канал связи[8].

Примеры криптографических атак на RSA[2][править | править код]

В 1978 году документ, опубликованный разработчиками криптографического алгоритма с открытым ключом RSA (аббревиатура от фамилий Rivest, Shamir и Adleman), упоминал новый алгоритм Ричарда Шреппеля «linear sieve», который факторизовал любой RSA модуль длины бит, используя простых операций. Таким образом, для того чтобы этот алгоритм требовал по меньшей мере простых операций, необходимо выбирать длины по крайней мере не меньше чем бит. Так как означает, что что-то сходится к при , то для выяснения правильного размера при конечном требуется более тщательный анализ скорости «linear sieve».

В 1988 году Джон Поллард предложил новый алгоритм факторизации, который называется Общий метод решета числового поля. Этот алгоритм факторизовал RSA-модуль размерности бит, используя простых операций. Таким образом, требуется выбирать длины не меньше чем бит, чтобы алгоритму потребовалось как минимум простых операций.

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

В 1994 году Питер Шор предложил алгоритм, который факторизовал любой RSA-модуль размерности бит, используя (точнее ) кубитовых операций на квантовом компьютере размера порядка кубит (и небольшого количества вспомогательных вычислений на классическом компьютере). Пользуясь алгоритмом Шора, необходимо по крайней мере выбирать модуль битовым размером не меньше чем бит, что является слишком большим числом для любого интересующего нас [9].

Практические применения криптографических конструкций[2][править | править код]

Примеров алгоритмов, устойчивых к квантовым атакам, крайне мало. Но несмотря на больший уровень криптографической устойчивости, постквантовые алгоритмы неспособны вытеснить современные криптосистемы (RSA, DSA, ECDSA и др.).

Рассмотрим нападения на криптосистему с открытым ключом, а именно на алгоритм шифрования McEliece, который использует двоичные коды Гоппы. Первоначально Роберт Мак-Элис представил документы, в которых коды длиной взламываются за простых операций. Таким образом, требуется выбирать не меньше чем бит, чтобы алгоритму потребовалось как минимум простых операций. Несколько последующих работ сократили количество операций атаки до , но значительно меньше , если большое. Поэтому улучшенные атаки до сих пор используют простых операций. Что касается квантовых компьютеров, то их использование приведёт лишь к уменьшению константы , что совсем незначительно сократит количество операций, необходимых для взлома этого алгоритма.

Если система шифрования McEliece так хорошо защищена, то почему она не приходит на смену RSA? Всё дело в эффективности — в частности, в размере ключа. Открытый ключ McEliece использует примерно бит, в то время как открытому ключу RSA достаточно около бит. Если , то бит для McEliece, будет меньше бит для RSA, но реальные уровни безопасности, такие как , позволяют RSA иметь открытый ключ в несколько тысяч бит, в то время как для McEliece размер ключа приближается к миллиону бит.

Конференция PQCrypto[править | править код]

С 2006 года проводится серия конференций, посвящённых постквантовой криптографии.

См. также[править | править код]

Примечания[править | править код]

  1. Peter Shor (1995-08-30), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, arΧiv:quant-ph/9508027. 
  2. 1 2 3 4 5 Daniel J. Bernstein. Introduction to post-quantum cryptography (неопр.) // (Introductory chapter to book "Post-quantum cryptography"). — 2009.
  3. Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding, IEEE Spectrum (1 ноября 2008). Архивировано 8 октября 2015 года. Дата обращения: 26 ноября 2014.
  4. рус. обучение с ошибками
  5. Peikert, Chris Lattice Cryptography for the Internet. IACR (2014). Дата обращения: 10 мая 2014. Архивировано 12 мая 2014 года.
  6. Guneysu, Tim Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. INRIA (2012). Дата обращения: 12 мая 2014. Архивировано 18 мая 2014 года.
  7. Zhang, jiang Authenticated Key Exchange from Ideal Lattices. iacr.org. IACR (2014). Дата обращения: 7 сентября 2014. Архивировано 7 сентября 2014 года.
  8. Протокол Диффи-Хеллмана с использованием суперсингулярной изогении.
  9. http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf Архивная копия от 15 декабря 2017 на Wayback Machine стр 9
  10. официальный сайт PQCrypto 2006. Дата обращения: 19 ноября 2014. Архивировано 26 октября 2014 года.
  11. официальный сайт PQCrypto 2008. Дата обращения: 19 ноября 2014. Архивировано из оригинала 19 октября 2014 года.
  12. официальный сайт PQCrypto 2010. Дата обращения: 19 ноября 2014. Архивировано 9 октября 2014 года.
  13. официальный сайт PQCrypto 2011. Дата обращения: 19 ноября 2014. Архивировано 27 декабря 2014 года.
  14. официальный сайт PQCrypto 2013. Дата обращения: 19 ноября 2014. Архивировано 23 декабря 2014 года.
  15. официальный сайт PQCrypto 2014. Дата обращения: 19 ноября 2014. Архивировано из оригинала 26 октября 2014 года.

Ссылки[править | править код]