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

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

Вы можете оставить комментарий, или ссылку на Ваш сайт.

Оставить комментарий