Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

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

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

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

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

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

Если система шифрования 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". arXiv: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. Архивировано 20 сентября 2009 года.
  3. "Q&A With Post-Quantum Computing Cryptography Researcher Jintai Ding". IEEE Spectrum. 2008-11-01. Архивировано из оригинала 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. http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf Архивная копия от 15 декабря 2017 на Wayback Machine стр 9
  9. официальный сайт PQCrypto 2006. Дата обращения: 19 ноября 2014. Архивировано 26 октября 2014 года.
  10. официальный сайт PQCrypto 2008. Дата обращения: 19 ноября 2014. Архивировано из оригинала 19 октября 2014 года.
  11. официальный сайт PQCrypto 2010. Дата обращения: 19 ноября 2014. Архивировано 9 октября 2014 года.
  12. официальный сайт PQCrypto 2011. Дата обращения: 19 ноября 2014. Архивировано 27 декабря 2014 года.
  13. официальный сайт PQCrypto 2013. Дата обращения: 19 ноября 2014. Архивировано 23 декабря 2014 года.
  14. официальный сайт PQCrypto 2014. Дата обращения: 19 ноября 2014. Архивировано из оригинала 26 октября 2014 года.

Ссылки

Эта страница в последний раз была отредактирована 10 марта 2024 в 15:37.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).