Криптография на решётках
жүктеу/скачать 16.24 Kb.
|
- Бұл бет үшін навигация:
- Криптография с открытым ключом или асимметричная криптография
|
Анализ известных постквантовых подходов Криптография на решётках — подход к построению алгоритмов асимметричного шифрования с использованием задач теории решёток, то есть задач оптимизации на дискретных аддитивных подгруппах, заданных на множестве . Наряду с другими методами постквантовой криптографии, считается перспективным в связи с возможностями квантового компьютера взламывать широко используемые асимметричные системы шифрования, основанные на двух типах задач теории чисел: задачах факторизации целых чисел и задачах дискретного логарифмирования. Сложность взлома алгоритмов, построенных на решётках, крайне велика, самые лучшие алгоритмы могут решить эту задачу с трудом за экспоненциальное время. По состоянию на середину 2010-х годов неизвестно ни одного квантового алгоритма, способного справиться лучше обычного компьютера. Криптография, основанная на многомерных квадратичных системах. Криптография, основанная на хеш-функциях. Классическим примером такого подходя является подпись Меркла – алгоритм многоразовой цифровой подписи, основанный на использовании дерева Меркла, и любой одноразовой подписи, основанной на криптостойкой хеш-функции. Хеш-функция (англ. hash function от hash — «превращать в фарш», «мешанина»), или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. паарпрпавр Эллиптическая криптография — раздел криптографии, который изучает асимметричные криптосистемы, основанные на эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день неизвестны субэкспоненциальные алгоритмы дискретного логарифмирования. Обобщение вышеупомянутых подходов приведено в Таблице 6. Как и в классических криптографических алгоритмах и схемах ЭП, трудность взлома которых основывается на сложности вычисления какой-либо «трудной» односторонней математической задачи функции Аутентификации подтверждение подлинности Криптография с открытым ключом или асимметричная криптография — это криптографическая система, использующая пары ключей. Каждая пара состоит из открытого ключа (который может быть известен другим) и закрытого ключа (который может быть не известен никому, кроме владельца). В 1995 году сотрудник компании AT&T Питер Шор опубликовал отрезвляющую статью, озаглавленную «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer»1 . Алгоритм Шора – это квантовый алгоритм, который приводит к экспоненциальному ускорению при решении задач факторизации, дискретного логарифмирования (DLP) и дискретного логарифмирования на эллиптических кривых (ECDLP). На классическом компьютере эти задачи неразрешимы, но на квантовом их вполне можно решить. А следовательно, квантовый компьютер можно использовать для вскрытия любого криптографического алгоритма, зависящего от сложности этих задач, включая RSA, протокол Диффи–Хеллмана, эллиптическую криптографию и все применяемые в настоящее время криптографические механизмы. Иными словами, безопасность RSA или эллиптической криптографии оказывается не выше, чем у шифра Цезаря. (Шор мог с тем же успехом назвать свою статью «Взлом всей криптографии с открытым ключом на квантовом компьютере».) жүктеу/скачать 16.24 Kb. Достарыңызбен бөлісу:
|