Квантово-устойчивые криптографические алгоритмы
Синонимы: Постквантовые алгоритмы
Коротко
- Квантово-устойчивые (постквантовые) криптографические алгоритмы — это семейство асимметричных криптографических алгоритмов, стойких как относительно классических атак, так и атак с использованием квантового вычислителя (квантовых атак);
- Наиболее распространенные в настоящее время асимметричные криптографические алгоритмы, такие как RSA, DSA, ГОСТ Р 34.10-2012, не являются квантово-устойчивыми, поскольку уже сейчас известны эффективные квантовые алгоритмы (метод Шора для факторизации и дискретного логарифмирования) для их анализа. В то же время, симметричным криптографическим алгоритмам, таким как блочные шифры ГОСТ Р 34.12-2015, AES и хэш-функции ГОСТ Р 34.10-2012, SHA-3, квантовый компьютер угрожает в меньшей степени, поскольку, хотя известные квантовые методы и понижают оценку трудоемкости их анализа, анализ по-прежнему нереализуем в обозримое время;
- Таким образом, для достижения квантовой устойчивости асимметричных криптографических схем, понадобилось обратиться к новым классам вычислительно сложных задач. Известные на данный момент классы таких задач включают в себя задачи теории решеток, теории кодов, исправляющих ошибки, многочленов от многих переменных, криптографических хэш-функций и другие.
Подробно
Основные направления синтеза квантово-устойчивых алгоритмов включают:
«Экзотика»:
На примере алгоритмов-финалистов конкурса NIST и разработок команды QApp — библиотеки квантово-устойчивых алгоритмов PQLR SDK — можно видеть как современные синтезные концепции находят реализацию в конкретных криптографических схемах.
Так, задачи теории решеток лежат в основе алгоритмов-финалистов конкурса NIST: CRYSTALS-KYBER, NTRU, SABER (реализован в нашем продукте PQLR SDK), CRYSTALS-DILITHIUM и FALCON, альтернативных алгоритмов-финалистов FrodoKEM и NTRU Prime.
Задачи теории кодирования обеспечивают стойкость таких алгоритмов-финалистов конкурса NIST, как Classic McEliece (реализован в нашем продукте PQLR SDK) и альтернативных алгоритмов-финалистов BIKE, HQC.
На основе многочленов от многих переменных строятся финалист конкурса NIST Rainbow и альтернативный алгоритм-финалист GeMSS.
Большое внимание уделяется криптографическим алгоритмам на основе хэш-функций. Так, алгоритм-финалист конкурса NIST XMSS и альтернативный алгоритм-финалист SPHINCS+ реализованы в PQLR SDK. Команда QApp активно сотрудничает с разработчиками алгоритма XMSS в части обоснования криптостойкости алгоритма, а также принимает участие в деятельности рабочей группы РГ 2.5 «Постквантовые криптографические механизмы» ТК 26 «Криптографическая защита информации» с целью стандартизации в России схемы цифровой подписи, основанной на хэш-функциях.
Алгоритмы на основе изогений суперсингулярных эллиптических кривых представлены в финале конкурса NIST схемой SIKE. Специалисты команды QApp активно участвуют в работе РГ 2.5 «Постквантовые криптографические механизмы» ТК 26 в части стандартизации отечественного алгоритма «Форзиция», основанного на сложных задачах из этого класса.
Наконец, единственный альтернативный финалист конкурса NIST из класса «экзотических» — схема цифровой подписи Picnic — основана на доказательствах с нулевым разглашением. Можно отметить, что на алгоритмы из этого класса пришлось наибольшее количество успешных атак среди всех 69 участников конкурса NIST.
Основные направления синтеза квантово-устойчивых алгоритмов включают:
- Использование теории целочисленных решеток (lattice-based cryptography): задача поиска кратчайшего вектора решетки и ее варианты, задача обучения с ошибкой;
- Использование кодов, исправляющих ошибки (code-based cryptography): задача декодирования случайного кода;
- Использование многочленов от многих переменных (multivariate cryptography): задача решения нелинейной системы уравнений;
- Использование криптографических хэш-функций (hash-based cryptography): задачи поиска коллизии/прообраза/второго прообраза для криптографических хэш-функций;
- Использование изогений суперсингулярных эллиптических кривых (supersingular isogeny-based cryprography): задача поиска пути в графе изогений.
«Экзотика»:
- проблемы сопряженного поиска (search problem);
- операции в группах кос (braid groups);
- алгебра октонионов;
- многочлены Чебышёва;
- и так далее.
На примере алгоритмов-финалистов конкурса NIST и разработок команды QApp — библиотеки квантово-устойчивых алгоритмов PQLR SDK — можно видеть как современные синтезные концепции находят реализацию в конкретных криптографических схемах.
Так, задачи теории решеток лежат в основе алгоритмов-финалистов конкурса NIST: CRYSTALS-KYBER, NTRU, SABER (реализован в нашем продукте PQLR SDK), CRYSTALS-DILITHIUM и FALCON, альтернативных алгоритмов-финалистов FrodoKEM и NTRU Prime.
Задачи теории кодирования обеспечивают стойкость таких алгоритмов-финалистов конкурса NIST, как Classic McEliece (реализован в нашем продукте PQLR SDK) и альтернативных алгоритмов-финалистов BIKE, HQC.
На основе многочленов от многих переменных строятся финалист конкурса NIST Rainbow и альтернативный алгоритм-финалист GeMSS.
Большое внимание уделяется криптографическим алгоритмам на основе хэш-функций. Так, алгоритм-финалист конкурса NIST XMSS и альтернативный алгоритм-финалист SPHINCS+ реализованы в PQLR SDK. Команда QApp активно сотрудничает с разработчиками алгоритма XMSS в части обоснования криптостойкости алгоритма, а также принимает участие в деятельности рабочей группы РГ 2.5 «Постквантовые криптографические механизмы» ТК 26 «Криптографическая защита информации» с целью стандартизации в России схемы цифровой подписи, основанной на хэш-функциях.
Алгоритмы на основе изогений суперсингулярных эллиптических кривых представлены в финале конкурса NIST схемой SIKE. Специалисты команды QApp активно участвуют в работе РГ 2.5 «Постквантовые криптографические механизмы» ТК 26 в части стандартизации отечественного алгоритма «Форзиция», основанного на сложных задачах из этого класса.
Наконец, единственный альтернативный финалист конкурса NIST из класса «экзотических» — схема цифровой подписи Picnic — основана на доказательствах с нулевым разглашением. Можно отметить, что на алгоритмы из этого класса пришлось наибольшее количество успешных атак среди всех 69 участников конкурса NIST.
Как уже сегодня использовать постквантовую криптографию для защиты данных вашего бизнеса?
Для того, чтобы использовать постквантовую криптографию уже сегодня, вы можете воспользоваться нашим программным решением — библиотекой квантово-устойчивых алгоритмов PQLR SDK.
Библиотека решает задачу не только реализации, но и упрощения интеграции постквантовых алгоритмов в существующую инфраструктуру защиты информации. Для этого в состав нашего решения включена модифицированная версия открытой библиотеки OpenSSL. Используя ее вместо оригинальной версии OpenSSL, приложения могут быть переведены на использование постквантовых алгоритмов с минимальными трудозатратами.
Наша библиотека реализует алгоритмы распределения ключа и алгоритмы электронно-цифровой подписи, основанные на различных криптографических схемах. При выборе и реализации конкретных алгоритмов мы ориентируемся как на экспертную оценку со стороны международного криптографического сообщества, так и на опыт лидеров индустрии по внедрению перспективных криптографических решений, а также на собственную валидацию стойкости и производительности алгоритмов.
Для того, чтобы использовать постквантовую криптографию уже сегодня, вы можете воспользоваться нашим программным решением — библиотекой квантово-устойчивых алгоритмов PQLR SDK.
Библиотека решает задачу не только реализации, но и упрощения интеграции постквантовых алгоритмов в существующую инфраструктуру защиты информации. Для этого в состав нашего решения включена модифицированная версия открытой библиотеки OpenSSL. Используя ее вместо оригинальной версии OpenSSL, приложения могут быть переведены на использование постквантовых алгоритмов с минимальными трудозатратами.
Наша библиотека реализует алгоритмы распределения ключа и алгоритмы электронно-цифровой подписи, основанные на различных криптографических схемах. При выборе и реализации конкретных алгоритмов мы ориентируемся как на экспертную оценку со стороны международного криптографического сообщества, так и на опыт лидеров индустрии по внедрению перспективных криптографических решений, а также на собственную валидацию стойкости и производительности алгоритмов.