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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми к криптографическим атакам. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора.[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).

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

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

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

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

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

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

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

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

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

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

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

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

  1. Peter W. 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 (2009). «Introduction to post-quantum cryptography».
  3. Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding, IEEE Spectrum (1 ноября 2008).
  4. рус. обучение с ошибками
  5. Peikert, Chris Lattice Cryptography for the Internet. IACR (2014). Проверено 10 мая 2014. Архивировано 31 января 2014 года.
  6. Guneysu, Tim Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. INRIA (2012). Проверено 12 мая 2014.
  7. Authenticated Key Exchange from Ideal Lattices. iacr.org. IACR (2014). Проверено 7 сентября 2014. Архивировано 17 августа 2014 года.
  8. официальный сайт PQCrypto 2006.
  9. официальный сайт PQCrypto 2008.
  10. официальный сайт PQCrypto 2010.
  11. официальный сайт PQCrypto 2011.
  12. официальный сайт PQCrypto 2013.
  13. официальный сайт PQCrypto 2014.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]