Методы повышения безопасности комбинированных схем аутентификации тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат наук Комарова Антонина Владиславовна

• Комарова Антонина Владиславовна
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Комарова Антонина Владиславовна

СОДЕРЖАНИЕ

РЕФЕРАТ

SYNOPSIS

СОКРАЩЕНИЯ

ОБОЗНАЧЕНИЯ

ВВЕДЕНИЕ

ГЛАВА 1. МЕХАНИЗМЫ АУТЕНТИФИКАЦИИ В СИСТЕМАХ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ

1.1 Идентификация и аутентификация пользователей

1.1.1 Методы аутентификации информации

1.1.2 Сравнительные характеристики рассматриваемых подходов

1.1.3 Результаты

1.1.4 Анализ научных публикаций

1.1.5 Анализ патентных исследований

1.2 Аутентификация посредством электронной подписи

1.2.1 Понятие и свойства двухключевой криптографии

1.2.2 Определение, параметры и задачи электронной подписи

1.2.3 Обоснование стойкости асимметричных алгоритмов

1.3 Существующие схемы электронной подписи, основанные на классической

асимметричной криптографии

1.3.1 Схемы электронной подписи, основанные на сложности задачи

факторизации

1.3.1.1 Алгоритм электронной подписи RSA

1.3.1.2 Схема электронной подписи Рабина

1.3.1.3 Оценка криптоаналитической сложности задачи факторизации

1.3.2 Схемы электронной подписи, основанные на сложности задачи дискретного логарифмирования в конечных полях

1.3.2.1 Схема электронной подписи Эль-Гамаля

1.3.2.2 Схема электронной подписи Шнорра

1.3.2.3 Оценка сложности задачи дискретного логарифмирования в конечных полях

1.3.3 Схемы электронной подписи, основанные на задаче дискретного логарифмирования на эллиптических кривых

1.3.3.1 Основные понятия эллиптических кривых

1.3.3.2 ГОСТ Р

1.3.3.3 Оценка сложности задачи дискретного логарифмирования в группе точек эллиптической кривой

1.4 Проблемы современных двухключевых криптосистем

1.5 Выводы к первой главе

ГЛАВА 2. ПОДХОДЫ И АЛГОРИТМЫ ПОСТКВАНТОВОЙ КРИПТОГРАФИИ

2.1 Квантовые вычисления и основная концепция

2.2 Классы постквантовых алгоритмов

2.2.1 Основные существующие постквантовые подходы

2.2.2 Кандидаты для новых постквантовых стандартов

2.2.3 Анализ постквантовых схем для комбинированной схемы

2.3 Криптография на решетках

2.3.1 Историческая справка, преимущества и недостатки теории решеток

2.3.2 Основные понятия и трудно решаемые задачи теории решеток

2.3.3 Схема электронной подписи FALCON

2.4 Проблемы существующих постквантовых подходов

2.5 Выводы ко второй главе

ГЛАВА 3. РАЗРАБОТКА КОМБИНИРОВАННЫХ СХЕМ АУТЕНТИФИКАЦИИ

3.1 Обоснование концепции

6

3.2 Механическое комбинирование нескольких схем электронной подписи

3.3 Модификация существующих схем электронной подписи

3.3.1 Комбинирование схемы Falcon и схемы Рабина

3.3.2 Комбинирование схемы Falcon и схемы RSA

3.3.3 Комбинирование схемы Falcon и схемы Эль-Гамаля

3.3.4 Комбинирование схемы Falcon и схемы Шнорра

3.3.5 Комбинирование схемы Falcon и ГОСТ Р

3.4 Оценка параметров разработанных схем

3.5 Выводы к третьей главе

ГЛАВА 4. МЕТОДЫ ПОВЫШЕНИЯ СТОЙКОСТИ СХЕМ ЭЛЕКТРОННОЙ ПОДПИСИ

4.1 Методы повышения стойкости схем электронной подписи на основе

индукционного вывода

4.1.1 Метод

4.1.2 Метод

4.1.3 Метод

4.1.4 Метод

4.2 Выводы к четвертой главе

ЗАКЛЮЧЕНИЕ

СПИСОК РИСУНКОВ

СПИСОК ТАБЛИЦ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

Приложение А. Программные коды

Приложение А.1. Алгоритм Falcon

Приложение А.2. Алгоритм Compress

Приложение А.3. Алгоритм ФАР

Приложение А.4. Алгоритм ФЭГ

Приложение А.5. Алгоритм ФАШ

Приложение А.6. Алгоритм ФАГО

7

Приложение В. Акты о внедрении

Приложение С. Основные публикации по теме диссертации

РЕФЕРАТ

Введение диссертации (часть автореферата) на тему «Методы повышения безопасности комбинированных схем аутентификации»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы диссертационного исследования

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

В настоящее время актуальной и прорывной темой многих исследований являются квантовые технологии. Не только в ведущих мировых научных изданиях, но и в средствах массовой информации все чаще появляются статьи, посвященные созданию квантового компьютера, способного решить задачи факторизации (ЗФ), дискретного логарифмирования в конечном простом поле (ЗДЛКПП) и дискретного логарифмирования в группе точек эллиптической кривой (ЗДЛЭК) за полиномиальное время. Некоторые учёные дают временную оценку в 20 лет для реализации полномасштабного квантового компьютера. Это означает, что криптографические механизмы, основанные на вышеперечисленных задачах, потеряют криптостойкость. К таким механизмам относятся и действующий стандарт Российской Федерации ГОСТ 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» и

действующий стандарт Соединенных Штатов Америки ECDSA, и многие другие протоколы.

В 2016 году Национальный институт стандартов и технологий США (NIST) объявил конкурс на создание новых постквантовых стандартов шифрования, ЭП и обмена ключами. Этот факт еще раз подчеркивает важность и актуальность данного направления исследований. Однако постквантовые подходы являются малоизученными и слабо проверенными на практике по сравнению с действующими асимметричными схемами.

Решением данного вопроса будут являться, так называемые, комбинированные схемы. Такого рода схемы предполагают двойную защиту: создание алгоритмов и протоколов, основанных одновременно на нескольких сложно вычислимых задачах, одна из которых принадлежит к постквантовой криптографии, а другая - к обычной ассиметричной криптографии.

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

Степень разработанности темы

В настоящее время в данной предметной области ведутся разработки следующих зарубежных ученых: I. Haviv, O. Regev, D. Micciancio, Xin Lu, Dengguo Feng, V. Lyubashevsky, C. Peikert, A. Chakrabarti. В работе также учтены результаты, полученные рядом отечественных авторов, в частности: В.И. Коржика, С.В. Беззатеева, Н.А. Молдовяна, А.А. Молдовяна, Е.С. Дерновой, Д.В. Захарова, И.А. Куприянова и других.

Целью диссертационной работы является повышение ИБ за счет

применения модифицированных схем ЭП, алгоритмов и протоколов

10

аутентификации.

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

Научная задача декомпозируется на следующие частные задачи:

1. Анализ известных постквантовых подходов и сложно вычислимых задач лежащих в их основе для выявления наиболее подходящей схемы ЭП для последующего комбинирования.

2. Анализ подходов на предмет синтеза алгоритмов и протоколов аутентификации.

3. Разработка схем и алгоритмов ЭП на основе вычисления нескольких трудно решаемых задач разного типа, стойких к атакам с помощью квантового компьютера.

4. Разработка протокола аутентификации, обеспечивающего повышенный уровень безопасности за счет использования постквантовой задачи поиска целочисленного решения.

5. Анализ разработанных алгоритмов и протокола на предмет их стойкости к потенциальным атакам.

6. Оценка параметров выработанных схем аутентификации.

7. Разработка обобщенных методов повышения стойкости схем ЭП.

Объектом исследования являются средства и системы аутентификации в

информационных системах.

Предметом исследования являются механизмы, методы, алгоритмы и протоколы аутентификации информации в системах ИБ.

Методы исследования. Для решения поставленных задач использовались аппарат и методы ИБ, линейной алгебры, теории чисел, теории вероятности, математической статистики, дискретной математики, теории сложности и криптографии.

Научная новизна диссертационного исследования заключается в следующем:

1. Разработаны комбинированные схемы ЭП, базирующиеся на нескольких трудно решаемых задачах, отличающиеся использованием аппарата теории чисел и теории решеток, за счет чего достигается повышение криптографической стойкости.

2. Разработаны алгоритмы ЭП, полученные методом встраивания элементов одной схемы ЭП в другую, за счет чего достигается относительное сокращение длины вырабатываемой подписи.

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

4. Предложены обобщенные методы комбинирования двух схем ЭП, одна из которых является асимметричной схемой из теории чисел, а другая -постквантовой схемой из теории решеток, за счет чего достигается повышение стойкости.

Основные положения, выносимые на защиту:

1. Алгоритмы ЭП, базирующиеся на нескольких трудно решаемых задачах разного типа, стойких к атакам с помощью квантового компьютера.

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

3. Методы повышения стойкости схем ЭП на основе индукционного вывода.

Соответствие паспорту специальности. Положения, выносимые на защиту,

соответствуют следующим пунктам паспорта специальности 05.13.19 - «Методы и системы защиты информации, информационная безопасность»:

• «5. Методы и средства (комплексы средств) информационного

противодействия угрозам нарушения информационной безопасности в открытых

12

компьютерных сетях, включая Интернет»;

• «11. Технологии идентификации и аутентификации пользователей и субъектов информационных процессов. Системы разграничения доступа»;

• «13. Принципы и решения (технические, математические, организационные и др.) по созданию новых и совершенствованию существующих средств защиты информации и обеспечения информационной безопасности».

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

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

Личный вклад автора. В диссертационной работе использованы результаты, в которых автору принадлежит определяющая роль. Автор лично участвовал в проведении теоретических и экспериментальных исследований по теме диссертации, их обсуждении, в анализе и интерпретации полученных результатов.

Апробация работы. Основные научные и практические результаты докладывались и обсуждались на следующих международных и всероссийских научно-технических конференциях:

1. «10Л, 12th International Conference On Security Of Information And Networks» (Джайпур, Индия, 2017 г.; Сочи, Россия, 2019 г.);

2. «II, III International Scientific Conference "Intelligent Information Technologies for Industry"» (IITI'17, Варна, Болгария, 2017 г.; IITI'18, Сочи, Россия, 2018 г.);

3. «The 20 th Conference of Open Innovations Association FRUCT and ISPIT 2017 seminar» (Санкт-Петербург, Россия, 2017 г.);

4. «VII, VIII Международная научно-техническая и научно-методическая конференция "Актуальные проблемы инфокоммуникаций в науке и образовании" при поддержке Федерального агентства связи, Правительства Санкт-Петербурга и Ленинградской области» (Санкт-Петербург, Россия, 2018 - 2019 гг.);

5. «Международный конгресс по интеллектуальным системам и информационным технологиям IS&IT'2018» (Геленджик, Россия, 2018 г.);

6. «XX, XXI Международная объединенная конференция "Интернет и современное общество" Internet and Modern Society - IMS» (Санкт-Петербург, Россия, 2017 - 2018 гг.);

7. «I, II Всероссийский студенческий форум «Инженерные кадры - будущее инновационной экономики России» (Йошкар-Ола, Россия, 2015 - 2016 гг.);

8. «VIII Научно-практическая конференция молодых ученых «Вычислительные системы и сети (Майоровские чтения)»» (Санкт-Петербург, Россия, 2016 г.);

9. «IV, V, VI, VII, VIII Всероссийский конгресс молодых ученых» (Санкт-Петербург, Россия, 2015-2019 гг.);

10. «XLIV, XLV, XLVI, XLVII, XLVIII Научная и учебно-методическая конференция Университета ИТМО» (Санкт-Петербург, Россия, 2015 - 2019 гг.).

Внедрение результатов

Результаты диссертационной работы были внедрены и использовались при проведении прикладных научных исследований:

• В федеральном государственном бюджетном учреждении науки «Институт Земного магнетизма, ионосферы и распространения радиоволн им. Н.В. Пушкова» Российской Академии наук (СПбФ ИЗМИРАН).

• В федеральном государственном автономном образовательном учреждении высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики»:

o НИР № 619296 «Разработка методов создания и внедрения киберфизических систем»;

o НИР № 617026 «Разработка методов интеллектуального управления киберфизическими системами с использованием квантовых технологий»; o НИР № 615878 «Проектирование методов создания безопасных технологических и информационных систем»;

o учебная дисциплина «Современные криптографические алгоритмы в киберфизических системах», «Постквантовая криптография».

• OOO «ЛЕНГИПРОРЕЧТРАНС».

• ООО «ИНТЭК».

Публикации по теме диссертации. Результаты диссертационной работы отражены в 19 публикациях, в том числе 9 публикациях в рецензируемых журналах из перечня ВАК и 2 публикациях в рецензируемых журналах из перечня Scopus.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 104 наименований, 3 приложений. Общий объем работы составляет 228 страниц, в том числе 30 рисунков и 14 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Далее проведен анализ существующих в настоящее время схем ЭП и синтез

основных сложно вычислимых задач теории чисел, лежащих в их основе.

Отмечено, что наиболее широко используемыми в современных информационных

системах являются задачи факторизации (ЗФ) и дискретного логарифмирования в

16

конечном простом поле (ЗДЛКПП) и в группе точек эллиптической кривой (ЗДЛЭК). На сложности решения первой, основана криптосистема RSA, а также схема ЭП Рабина, базирующаяся на трудности задачи извлечения корней по простому модулю. Сложность данной задачи считается сравнимой со сложностью решения задачи факторизации. Сложность решения ЗДЛКПП положена в основу схем ЭП Эль-Гамаля и Шнорра, а трудность вычисления ЗДЛЭК является основой безопасности действующего стандарта ЭП РФ ГОСТ 34.10.2012. Приведена оценка стойкости данных схем.

Выявлены основные проблемы современных криптосистем: с ростом возможностей вычислительной техники вероятность взлома существующих схем увеличивается, а время, потраченное на этот процесс, уменьшается, следовательно, возникает постоянная потребность в увеличении размеров ключей, что отрицательно сказывается на производительности. Другой очень важной проблемой является потенциальная возможность появления квантового компьютера. При появлении квантового противника с огромными вычислительными мощностями велика вероятность и тотального взлома существующих криптосистем путём полного перебора по всему пространству ключей.

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

Таким образом, поднимаются вопросы, связанные с повышением безопасности существующих криптосистем. Данную задачу предлагается решать путем синтеза ассиметричных и постквантовых алгоритмов и протоколов аутентификации информации.

Вторая глава диссертации посвящена текущему состоянию дел в области

постквантовой криптографии. В данной главе рассмотрены существующие

17

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

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

Требование компактности, то есть сумма длин открытого ключа и подписи (| pk | +1 Sign |), выявлено как определяющее требование к построению комбинированной схемы ЭП. Показано, что данному критерию решеточная схема Falcon, базирующаяся на сложности решения задачи с коротким целочисленным решением (SIS), является наиболее перспективной для дальнейшего использования в комбинированной схеме ЭП.

В данной главе приводятся основные положение и определения теории решеток для более детального понимания сути представленных далее сложно вычислимых криптографических задач. К ним относятся: задача поиска кратчайшего вектора решетки (SVP), задача поиска ближайшего вектора решетки (CVP), задача декодирования ограниченного расстояния (BDD), задача с коротким целочисленным решением (SIS), задача обучения с ошибками (LWR).

В данной главе раскрыта структура схемы Falcon. В оригинальной схеме используется большое количество специфических алгоритмов, таких как алгоритм быстрого преобразования Фурье, алгоритм (Compress(s)), принимающий

на вход многочлен s и выводящий его сжатое представление в виде битовой строки, алгоритм (Decompress (s)), производящий обратное действие и др. Данные алгоритмы делают схему более безопасной к атакам разного рода, но не влияют на базовую суть. Рассмотрим основную структуру Falcon. Она выглядит следующим образом. Открытым ключом является полно ранговая матрица

A е Zqnxn (m > n) генерирующая g-арную решетку Lq (A) . Закрытым ключом

является матрица B е Z^xm, генерирующая решетку Lq (B), такую что для

х е L (A) и y е Lqq (B) выполнено условие (x, y) = 0mod q. Следовательно, строки

матриц A и B попарно ортогональны: B х Aт = 0. Матрица B состоит из практически ортогональных векторов с малыми коэффициентами, а матрица A -из не ортогональных векторов с большими коэффициентами. Все процедуры

выполняются в фактор кольце R = Zq [ x] / (xn +1) усеченных многочленов.

Процедура генерации подписи к сообщению Mтакова:

• генерируется битовая строка r = {0,1}320 из некоторого случайного равномерного распределения;

• используя хэш-функцию SHAKE-256 вычисляется h = H(m || r);

• вычисляется значение с, такое что выполняется сАт = h;

• с помощью матрицы B вычисляется у е Lq (B), близкий к с;

• вычисляется разность s = c - v. Подписью к сообщению Mявляется пара (r, s). Процедура проверки подписи (r, s) к сообщению M:

• вычисляется значение h = H(m || r);

• проверяется выполнимость условия ||s|| < [5, где параметр Р выбирается в зависимости от требуемого уровня безопасности;

• вычисляется значение h' = sAr. Если h' = h, то подпись признается подлинной.

Корректность проверки: h' = sAT = (с - v)AT = cAT - vAT = h - 0 = h .

19

К преимуществам данной схемы можно отнесены: компактность, стойкость, как к классической модели случайного оракула, так и к квантовой модели случайного оракула, конвертируемость, экономичность, быстроту, резистентность к атакам на основе предварительно найденных коллизий. В качестве недостатков Falcon отмечены: необходимость использования арифметики с плавающей запятой, отсутствие изученных методов противодействия атакам по побочным каналам связи, нетривиальная реализация некоторых процедур.

В конце второй главы делаются соответствующие выводы и ставятся новые возникающие задачи, которые необходимо решить в дальнейшем, но не в рамках данного диссертационного исследования.

В третьей главе диссертационного исследования обоснована концепция построения комбинированных схем ЭП. Обозначены подходы по синтезу алгоритмов и протоколов аутентификации информации, основанных на задачах разного типа. К таким подходам можно отнести:

1. Механическое комбинирование двух схем в одной. В этом случае сообщение M сначала подписывается одной подписью ^, затем второй подписью . Итоговой подписью к документу M будет являться пара подписей (^ || ). Однако недостаток такого механизма комбинирования очевиден: при комбинировании N схем в одной схеме, временные параметры и длины ключей и подписи, возрастут в N раз, что является неприемлемым с точки зрения практического использования в реальных информационно-телекоммуникационных системах.

2. Встраивание элементов одной схемы ЭП в другую. Таким образом, повышается уровень безопасности и, соответственно, понижается вероятность взлома модифицированных схем ЭП. Подобный подход не является новым, однако возможность комбинирования постквантовых схем с классическими асимметричными схемами не была предложена. Рассмотрим варианты комбинирования различных схем ЭП, упомянутых в 1 главе, со схемой Falcon.

Комбинирование схемы Falcon и схемы ЭП Рабина. Предлагается схема и алгоритм ЭП, который далее будем называть ФАР, созданные путем встраивания схемы ЭП Рабина в схему Falcon. В диссертации Е.С. Дерновой был предложен подход по модификации параметров схемы Рабина для того, чтобы добиться выигрыша в скорости. Используем этот подход при генерации модуля n в схеме ФАР. Также в модифицированной схеме будут использоваться алгоритм Compress, принимающий на вход многочлен и выводящий его числовое представление, и алгоритм Decompress, производящий обратное действие к алгоритму Compress (т.е. Decompress ° Compresses) = s ).

Процедура генерации ключей состоит из следующих шагов:

• генерируются две матрицы A и B так же, как в схеме Falcon;

• формируется модуль n=pq;

• выбирается число У такое, что у = p'q' и p' = 3mod4, q' = 3mod4, p' | (p -1), q' | (q -1) и p' не делит (q-1), а q' не делит (p -1).

Открытым ключом в модифицированной схеме будет являться пара (A, n).

Закрытым ключом - тройка (B, q, p).

Процедура генерации подписи к сообщению М в этом случае несколько изменится:

• генерируется битовая строка r = {0,1}320 из некоторого случайного равномерного распределения;

• с использованием криптографически стойкой хэш-функции SHAKE-256 вычисляется значение h = H (М || г);

• вычисляется значение с, такое чтоб выполнялось условие сАт = h;

• с помощью матрицы B вычисляется у е Lq (B), близкий к с ;

• вычисляется разность s = c - v;

• вычисляется значение a = (Compress(s)), a <n;

p-1 q-1

• проверяется выполнение сравнений a 2 = 1mod p и a 2 = 1mod q;

Если одно из соотношений не выполняется, то генерируется новое случайное число r и процедура повторяется до тех пор, пока не будет найдено такое значение r, для которого оба условия выполняются, т. е. получено a, являющееся квадратичным вычетом по модулю п.

1

• по китайской теореме об остатках вычисляется s ' = a2 mod n.

Подписью к сообщению M является пара чисел (r, s').

Процедура проверки модифицированной подписи (r, s') к сообщению m:

• вычисляется значение h = H (М || r ) ;

• вычисляется значение a': a ' = s '2 mod n ;

• вычисляется значение s : s = (Decompress(a ')) ;

• проверяется выполнимость условия |s|| < [ ;

• вычисляется значение h ' = sAr. Если h ' = h, то подпись признается подлинной.

Блок-схемы разработанного алгоритма представлены на рисунках 1 и 2.

Можно показать, что предложенная схема действительно основывается на сложности решения двух трудных математических задач. Для того чтобы злоумышленник мог подделать элемент подписи s', ему потребуется вычислить квадратный корень по составному модулю п, а без знания чисел p и q это является трудной математической задачей - задачей вычисления корней по составному модулю. В случае если злоумышленник умеет находить квадратные корни по модулю п, он все равно не сможет взломать схему, так как предварительно ему следует найти вектор v достаточно близкий к вектору с, а это значит, что злоумышленник должен уметь решать задачу SIS. В настоящий момент успешных методов решения данной задачи за полиномиальное время найдено не было.

Рисунок 1 - Алгоритм формирования подписи Рисунок 2 - Алгоритм проверки подписи ФАР ФАР

Таким образом, для того, чтобы можно было на практике осуществить

1

процесс вычисления параметра я' (б' = а2modп), необходимо, чтобы число (р(п) имело структуру: (р(п) =щ, где числа гид являются большими простыми числами. В этом случае можно добиться наибольшей в данных условиях мощности множества QRn, которая будет составлять четвертую часть элементов

группы 2п: #QRn е^"(#). Так как параметр я' зависит от случайно

генерируемой битовой строки г, то подбирая значение г, можно получить

значение s'являющееся квадратичным вычетом по модулю n. Однако, так как лишь четвертая часть элементов будет удовлетворять накладываемым условиям, производительность схемы снижается в среднем в 4 раза. Данный факт свидетельствует о необходимости поиска других вариантов комбинирования для устранения этого недостатка.

Список литературы диссертационного исследования кандидат наук Комарова Антонина Владиславовна, 2019 год

Литература

1. Коробейников А.Г., Кутузов И.М. Алгоритм обфускации//Кибернетика и программирование. 2013. № 3. С. 1-8.

2. FALCON. - Режим доступа: https://falcon-sign.info, свободный (дата обращения: 05.06.2019).

3. Gentry C., Peikert C., Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, p. - 197-206, Victoria, British Columbia, Canada, May 17-20, 2008. ACM Press. 7, 8, 11, 12, 13, 14.

4. Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1985. — Vol. 31, Iss. 4. — P. 469-472. — ISSN 0018-9448 — doi:10.1109/TIT.1985.1057074.

5. Schnorr C.P. Efficient Identification and Signatures for Smart Cards.Advances in Cryptology -CRYPTO'89. Lecture Notes in Computer Science 435. — 1990. — С. 239 - 252.

6. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. ГОСТ 34.10-2012. - Госстандарт России. М., Стан-дартинформ. - 2013. - 18с.

References

1. Korobeynikov A. G., Kutuzov I. M. Obfuscation Algorithm [Algoritm obfuskacii] // Cybernetics and programming, 2013, № 3, P. 1-8.

2. FALCON. Available at: https://falcon-sign.info, free (accessed: 05.06.2019).

3. Gentry C., Peikert C., Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, p. - 197-206, Victoria, British Columbia, Canada, May 17-20, 2008. ACM Press. 7, 8, 11, 12, 13, 14.

4. Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1985. — Vol. 31, Iss. 4. — P. 469-472. — ISSN 0018-9448 — doi:10.1109/TIT.1985.1057074.

5. Schnorr C.P. Efficient Identification and Signatures for Smart Cards.Advances in Cryptology -CRYPTO'89. Lecture Notes in Computer Science 435. — 1990. — C. 239 - 252.

6. Information technology. Cryptographic protection of information. Processes of formation and verification of electronic digital signature. GOST 34.10-2012 [Informacionnaya tekhnologiya. Kriptograficheskaya zashchita informacii. Processy formirovaniya i proverki elektronnoj cifrovoj podpisi. GOST 34.10-2012]. Gosstandart Rossii. M., Standartinform, 2013, p. 18.

КОМАРОВА Антонина Владиславовна, аспирант факультета безопасности информационных технологий, Федерального государственного автономного образовательного учреждения высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики», 197101, г. Санкт-Петербург, Кронверкский проспект, 49, E-mail: [e-mail]

КОРОБЕЙНИКОВ Анатолий Григорьевич, доктор технических наук, профессор, заместитель директора по науке, Санкт-Петербургский филиал Федерального государственного бюджетного учреждения науки Института земного магнетизма, ионосферы и распространения радиоволн им. Н.В.Пушкова Российской академии наук. 199034, г. Санкт-Петербург, Менделеевская линия, 3, E-mail: [e-mail]

KOMAROVA Antonina, postgraduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics. 197101, St. Petersburg, Russia. Kronverksky pr., 49. E-mail: [e-mail]

KOROBEYNIKOV Anatoly, Dr.Sc., Professor, Deputy Director for Science, Pushkov Institute of Terrestrial Magnetism, Ionosphere and Radio Wave Propagation of the Russian Academy of Sciences (IZMIRAN). 199034, St. Petersburg, Russia, Mendeleevskaya liniya, 3, E-mail: [e-mail]

05.13.19

А.В. Комарова, А.Г. Коробейников д-р техн. наук

Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики», факультет безопасности информационных технологий Санкт-Петербург, piter-ton@mail. ru

МОДИФИЦИРОВАННАЯ СХЕМА ЭЛЕКТРОННОЙ ПОДПИСИ, СТОЙКАЯ К КВАНТОВОМУ КОМПЬЮТЕРУ

В статье представлена схема электронной подписи, построенная путем комбинирования пост-квантовой схемы Falcon и схемы электронной подписи Рабина. Показано, что предлагаемая схема основывается на сложности решения двух трудных задач одновременно: задачи извлечения корней по составному модулю и задачи поиска короткого целочисленного решения. Приведены оценки трудоемкости полученной схемы, а также оценки длин ключей и подписи.

Ключевые слова: схема Falcon, пост-квантовая криптография, электронная подпись, теория решеток, задача извлечения корней по составному модулю, задача поиска короткого целочисленного решения.

Одной из важных проблем для современной криптографии в настоящий момент является потенциальная возможность появления квантового компьютера. В этом случае из всех возможных криптографических приложений особенно остро данная проблема скажется на схемах электронной подписи (ЭП). Они становятся небезопасными [1]. Существует большое количество пост-квантовых подходов и схем ЭП, однако, по мнению авторов, наибольшего внимания заслуживает теория решеток, в частности схема Falcon [2]. Трудоемкость схемы основывается на сложности поиска короткого целочисленного решения в решетке [3-4].

Основная структура схемы Falcon выглядит так. Открытым ключом является полно

ранговая матрица A е Z^ x n (m > n) генерирующая g-арную решетку Lq (A) . Закрытым

ключом является матрица B е zm^m, генерирующая решетку L^ (B), такую что для

х е L (A) и у е Lq (B) выполнено условие (x, y) = 0mod q . Следовательно строки

матриц A и B попарно ортогональны: B х Аг = 0. Матрица B состоит из практически ортогональных векторов с малыми коэффициентами, а матрица A - из не ортогональных векторов с большими коэффициентами. Все процедуры выполняются в фактор кольце

R = Zq[ x\/(xn +1) усеченных многочленов.

Процедура генерации подписи к сообщению Mтакова:

1. генерируется битовая строка r = 1}32° из некоторого случайного равномерного распределения;

2. используя хэш-функцию SHAKE-256 вычисляется h = H(m || r) ;

3. вычисляется значение с, такое что выполняется eAr = h;

4. с помощью матрицы B вычисляется v е L^(B) , близкий к с;

5. вычисляется разность s = c - v .

Подписью к сообщению M является пара (r, s).

Процедура проверки подписи (r, s ) к сообщению M:

1. вычисляется значение h = H(m || r) ;

2. проверяется выполнимость условия ||s|| < Р, где параметр Р выбирается в зависимости от требуемого уровня безопасности;

3. вычисляется значение h ' = sAT.

Если h ' = h, то подпись признается подлинной.

Корректность проверки: h ' = sAT = (с — v)AT = cAT — vAT = h — 0 = h .

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

Разработанная авторами схема, которую далее будем называть ФИКК, создана путем встраивания схемы ЭП Рабина [7] в схему Falcon [2]. В выработанной схеме алгоритм Compress принимает на вход многочлен и выводит его сжатое представление в виде числовой строки, а алгоритм Decompress производит обратное действие к алгоритму Compress (т.е. Decompress ° Compressas) = s )\ принимает на вход строку и выводит многочлен. В диссертации [5] был предложен подход по модификации параметров схемы Рабина для того, чтобы добиться выигрыша в скорости. Используем этот подход при генерации модуля n в схеме ФИКК.

Процедура генерации ключей состоит из следующих шагов:

1. генерируются две матрицы A и B так же, как в схеме Falcon;

2. формируется модуль n=pq;

3. выбирается число у такое, что у = p ' q ' и p ' = 3mod4, q ' = 3mod4, p ' |( p — 1), q ' | (q — 1) и p ' не делит (q— 1), а q ' не делит (p — 1) .

Открытым ключом в модифицированной схеме будет являться пара

( A, n). Закрытым ключом - тройка ( B, q, p).

Процедура генерации подписи в этом случае несколько изменится:

4. генерируется битовая строка r = 1}32° из некоторого случайного равномерного распределения;

5. с использованием криптографически стойкой хэш-функции SHAKE-256 вычисляется значение h = H (m || r ) ;

6. вычисляется значение с, такое чтоб выполнялось условие сАТ = h ;

7. с помощью матрицы B вычисляется v е L(B) , близкий к с ;

8. вычисляется разность s = c - v ;

9. вычисляется значение a = (Compress(s)), a <n ;

p—1 q—1

10. проверяется выполнение сравнений a 2 = 1modp и a 2 = 1modq ;

Если одно из соотношений не выполняется, то генерируется новое случайное число r и процедура повторяется до тех пор, пока не будет найдено такое значение r, для которого оба условия выполняются, т. е. получено a, являющееся квадратичным вычетом по модулю n.

1

11. По китайской теореме об остатках вычисляется s ' = a2 mod n .

Подписью к сообщению M является пара чисел (r, s').

Процедура проверки модифицированной подписи (r, s') к сообщению M:

1. вычисляется значение h = H (m || r ) ;

2. вычисляется значение a': a' = s,2modn ;

3. вычисляется значение s : s = (Decompress(a ')) ;

4. проверяется выполнимость условия |s| < ß ;

5. вычисляется значение h ' = sAT.

Если h ' = h, то подпись признается подлинной.

Можно показать, что предложенная схема действительно основывается на сложности решения двух трудных математических задач. Для того чтобы злоумышленник мог подделать элемент подписи s', ему потребуется вычислить квадратный корень по составному модулю n, а без знания чисел p и q это является трудной математической задачей - задачей вычисления корней по составному модулю. В случае если злоумышленник умеет находить квадратные корни по модулю n, он все равно не сможет взломать схему, так как предварительно ему следует найти вектор v достаточно близкий к вектору с, а это значит, что злоумышленник должен уметь решать задачу SIS. В настоящий момент успешных методов решения данной задачи за полиномиальное время найдено не было.

Проведем оценку трудоемкости выработанной схемы ЭП. По сравнению с исходными схемами время и количество операций, требуемых для создания подписи ФИКК, увеличились, однако, за счет использования модуля специальной структуры, они стали меньше суммы обозначенных параметров каждой схемы. Длины ключей также увеличились, но длина подписи осталась неизменной.

Разработанная модифицированная схема может быть внедрена в различные системы криптографической защиты информации. Интересным и актуальным продолжением исследований в данной области является комбинирование схемы Falcon с другими известными асимметричными схемами, такими как схемы ЭП Шнорра, Эль-Гамаля, RSA. Предлагаемая модифицированная схема может быть реализована в MATLAB [В].

Список литературы

1. Chen L., Jordan S., Liu Y.K., Moody D., Peralta R., Perlner R., Smith-tone D. Report on PostQuantum Cryptography, NISTIR B105, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2016, 10pp. https://doi.org/10.602B/NIST.IR.B105.

2. FALCON. - Режим доступа: https://falcon-sign.info, свободный (дата обращения: 03.06.2019).

3. Пискова, А.В. Теория решеток в постквантовой криптографии / А.В. Пискова,

A.Г. Коробейников // Сборник трудов V Всероссийского конгресса молодых ученых (Санкт-Петербург, 12-15 апреля 2016 г.). - 2016. - Т. 2. - С. 91-93.

4. Коробейников А.Г., Пискова А.В., Менщиков А.А. Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности // Вопросы кибербезопасности. 2016. № 1. С. 47-52.

5. Дернова Е.С. Механизмы аутентификации информации, основанные на двух вычислительно трудных задачах: дис. ... канд. тех. наук: 05.13.19 / Дернова Евгения Сергеевна. - СПб., 2009. - 162 с.

6. Дернова Е.С., Нгуен Ле Минь, Костина А.А., Щербаков В.А. Схемы цифровой подписи, взлом которых требует решения двух трудных задач в одной конечной группе // XI Санкт-Петербургская международная крнференция Региональная информатика-2008 ^^200B) СПб, 22-24 октября 2008г. Материалы конференции. СПб, 2008. C97-9B.

7. Rabin M..О. Digitalized signatures and public-key functions as intractable as factorization, Technical report MIT / LCS/ TR-212, MIT Laboratory for Computer Science. - 1979.

B. Коробейников А.Г., Гришенцев А.Ю. Разработка и исследование многомерных математических моделей с использованием систем компьютерной алгебры. - СПб: НИУ ИТМО, 2014. - 100 с.

I АНАЛИЗ ОСНОВНЫХ СУЩЕСТВУЮЩИХ ПОСТ-КВАНТОВЫХ ПОДХОДОВ И СХЕМ ЭЛЕКТРОННОЙ ПОДПИСИ1

Комарова А.В.2, Коробейников А.Г.3

Цель статьи: освещение последних тенденций развития пост-квантовой криптографии, в частности, схем электронной подписи, путем рассмотрения кандидатов, прошедших во второй тур конкурса стандартов Национального Института Стандартов и Технологий США (NIST).

Метод: анализ и синтез существующих пост-квантовых подходов, сравнительный анализ некоторых характеристик наиболее перспективных, по мнению авторов, схем электронной подписи.

Полученный результат: рассмотрены существующие пост-квантовые подходы и синтезированы наиболее перспективные из них. Проведено сравнение некоторых параметров схем электронной подписи, прошедших во второй тур конкурса пост-квантовых стандартов Национального Института Стандартов и Технологий США (NIST). Сделан вывод о том, что для построения схем электронной подписи наиболее перспективным подходом из всех предложенных является теория решеток, в частности схема FALCON. Данная схема обеспечивает наивысший уровень «компактности» по сумме длин открытого ключа и подписи среди всех представленных на конкурсе NIST пост-квантовых схем электронной подписи при сопоставимых уровнях безопасности и временных параметрах.

Ключевые слова: пост-квантовая криптография, квантовый компьютер, теория решеток, многомерные квадратичные системы, электронная подпись на хэш-функциях, теория алгебраического кодирования, изогении эллиптических кривых, теория кос, схема FALCON.

1. Введение

В настоящее время в быстроразвивающемся технологическом мире появление квантового компьютера все больше становится реальностью [1]. Для некоторых областей знаний создание такого устройства позволит обрабатывать данные на порядок быстрее, чем это делают современные машины [2], что станет прорывом, но для современной криптографии - угрозой взлома всех существующих криптосистем.

Ведущими мировыми научными коллективами постоянно ведутся разработки по построению квантового вычислителя [3]. Некоторые учёные дают временную оценку в 20 лет для реализации полномасштабного квантового компьютера. Если вычислительные возможности нарушителя возрастут в десятки, сотни, тысячи раз, то это приведёт к резкой необходимости увеличения длины ключей до критического уровня, не пригодного для их успешной эксплуатации в реальных информационных системах. Также, необходимо отметить, что при появлении квантового противника с огромными вычислительными мощностями велика вероятность и тотального взлома существующих криптосистем путём полного перебора по всему пространству ключей [2].

Данную проблему можно решить путем использования примитивов пост-квантовой криптографии, сравнительно новой отрасли криптографии, призванной противостоять квантовым вычислениям.

Р01:10.21681/2311-3456-2019-2-58-68

Еще одним путем решения обозначенной выше проблемы, является использование квантовой криптографии. В отличие от асимметричной криптографии (и постквантовой, и классической), основанной на условно однонаправленных математических функциях, квантовая криптография основывается на принципах квантовой механики и квантовой теории информации, гарантирующих физическую однонаправленность. Однако существует ряд проблем, связанных со сложностью реализации и высокой стоимостью оборудования. При длине канала передачи данных более 100 км, скорость передачи значительно снижается (до нескольких битов в секунду) [4]. Данный факт пока не позволяет реализовать полноценный защищенный обмен критически важной информацией. В силу этого, авторам видится, что на данный момент пост-квантовая криптография является более реализуемой для использования в существующих системах.

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

За последние пять лет количество публикуемых работ по данной тематике, как зарубежных, так и российских, значительно возросло [5-10]. Этот факт подчеркивает актуальность данной проблемы и вызывает интерес к дальнейшим исследованиям в этой области.

1 Работа выполнена при поддержке НИР Университета ИТМО №619296 «Разработка методов создания и внедрения киберфизических систем».

2 Комарова Антонина Владиславовна, аспирант, Университет ИТМО, Санкт-Петербург, Россия. E-mail: [e-mail]

3 Коробейников Анатолий Григорьевич, доктор технических наук, профессор, институт земного магнетизма, ионосферы и распространения радиоволн имени Н. В. Пушкова РАН, Санкт-Петербург, Россия. E-mail: [e-mail]

Таблица 1.

Влияние квантового компьютера на существующие криптосистемы

Криптографический Тип Применение Влияние полномасштабного квантового компьютера алгоритм

ГОСТ Р 34.12-2015, AES Симметричный Шифрование Необходимы более длинные ключи

ГОСТ Р 34.11-2012, SHA-2, SHA-3 - Хэш-функции Необходимы более длинные выходные значения хэш-функции

RSA Асимметричный Электронная подпись, Генерация ключей Становится небезопасным

DSA Асимметричный Электронная подпись, Обмен ключами Становится небезопасным

ГОСТ Р 34.10-2012, ECDH, ECDSA Асимметричный Электронная подпись, Обмен ключами Становится небезопасным

2. Постановка задачи

В 1994 году американский ученый П. Шор (P. W. Shor) предложил квантовый алгоритм, способный решать задачи факторизации и дискретного логарифмирования за полиномиальное время . Это означает, что криптографические механизмы, основанные на вышеперечисленных задачах, потеряют свою криптостой-кость. К таким механизмам относятся и действующий стандарт Российской Федерации ГОСТ 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи» и действующий стандарт Соединенных Штатов Америки ECDSA, и многие другие протоколы.

Существует ещё один квантовый алгоритм - алгоритм Л. Гровера (L.Grover), сложность которого оценивается в , но он не дает столь большой выигрыш в скорости по сравнению с алгоритмом Шора и больше подходит для взлома симметричных криптосистем и хэш-функций. Как можно видеть, алгоритм Гровера квадратично повышает скорость вычислений по сравнению с классическими компьютерами.

В отчете Национального Института Стандартов и Технологий США (The National Institute of Standards and Technology, NIST) [11] (апрель 2016 года) отмечается, что большинство асимметричных криптографических примитивов, широко используемых сегодня в разных сферах общественной жизни, и которые базируются на задачах факторизации и дискретного логарифмирования в разных группах, будут скомпрометированы, что показано в Таблице 1.

Не смотря на то, что уже происходит переход от хэш-алгоритмов MD5 и SHA-1 к SHA-2 и SHA-3 [12], как видно из Таблицы 1, то появление квантового компьютера повлечёт за собой необходимость многократного увеличения длины ключей для симметричного шифрования, а для хэш-функций - многократного увеличения длины хэша. Такие длины становятся неприемлемыми для практического использования симметричных алгоритмов и существующих хэш-функций в будущем.

Считается, что 2048-битовые ключи RSA будут обеспечивать достаточный уровень безопасности до 2030 года, а 3072 битовые ключи будут безоговорочно безопасными в обозримом будущем [12], однако, согласно отчету NIST [11], в случае реализации полномасштабного квантового компьютера, и RSA и ECDSA станут небезопасными. Некоторые учёные дают временную оценку в 20 лет для реализации такого полномасштабного устройства.

Для решения поднятой выше проблемы, в 2016 году NIST объявил о старте открытого конкурса на создание новых пост-квантовых алгоритмов и стандартов.

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

Таким образом, в рамках проводимого исследования была поставлена задача по анализу и синтезу существующих пост-квантовых подходов, а также кандидатов второго тура конкурса стандартов NIST среди схем электронной подписи для выявления наиболее перспективной, по мнению авторов, схемы.

3. Существующие пост-квантовые подходы

Пост-квантовая криптография на данный момент включает в себя следующие основные подходы:

• теория решеток;

• многомерные квадратичные системы;

• электронные подписи на хэш-функциях;

• теория алгебраического кодирования;

• изогении эллиптических кривых;

• теория кос.

Рассмотрим кратко преимущества и недостатки каждого подхода, приведем примеры конкретных реализаций.

Криптография на решётках. Данный раздел криптографии начал активно развиваться с 1990-х годов

и включает в себя большое количество трудно вычислительных задач, некоторые из которых считаются NP-полными [13]. Большинство схем просты в понимании, обеспечивают хорошее быстродействие и обладают свойством распараллеливания вычислений. Помимо шифрования и подписи, на решётках могут быть построены другие интересные приложения (полностью гомоморфное шифрование [14], шифрование и подпись с использованием атрибута [15], обфускация кодов и другие). Некоторые системы из этого раздела обладают сложностью в наихудшем случае, а не в среднем, как большинство криптосистем. К минусам можно отнести отсутствие точного метода оценки сложности алгоритмов на решетках к существующим видам атак [16]. Наиболее известной схемой является криптосистема NTRU (Nth-degree TRUncated polynomial ring), предложенная в 1998 году. На базе криптосистемы NTRU можно реализовать алгоритмы шифрования и электронной подписи. Модифицированная версия данного алгоритма была взята за основу стандарта для финансовых организаций ANSI X9.98-2010 «Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry». В 2008 году криптосистема NTRU была включена в стандарт IEEE 1363.1 «Lattice-based public-key cryptography».

Криптография, основанная на многомерных квадратичных системах. Стойкость этого раздела криптографии основывается на сложности решения системы многомерных квадратичных многочленов над конечным полем [17]. Данная задача считается NP-полной. Системы из этого раздела обладают хорошей скоростью и небольшими требованиями к вычислительным ресурсам, однако, длины открытых ключей довольно большие. Наиболее известным примером является криптосистема HFE (Hidden Fields Equations), основанная на скрытых уравнениях поля и предложенная Ж. Патариным (J.Patarin) в 1996 году.

Криптография, основанная на хэш-функциях. В данный раздел входят электронные подписи, построенные с помощью хэш-функций, в силу чего обеспечивается их стойкость к квантовым вычислениям [18]. С помощью этого подхода можно выработать лишь ограниченное количество подписей на одном ключе. Также, к недостаткам системы относится тот факт, что подписанту необходимо записывать точное количество уже подписанных сообщений. Ошибка в этой записи приведёт к уязвимо-стям системы. Классическим примером является подпись Р. Меркла (R. Merkle), предложенная в 1979 году.

Криптография на кодах, исправляющих ошибки (теория алгебраического кодирования [19]). К плюсам такого рода систем можно отнести скорость вычислений. К минусам - слишком большую длину ключей [20]. На теории алгебраического кодирования базируются классические криптосистемы McEliece и Niederreiter. McEliece была предложенная Р. Мак-Элисом (R. Mac-Eliece) в 1978 году. Niederreiter была разработана Х. Нидеррай-тером (H. Niederreiter) в 1986 году.

Изогении суперсингулярной эллиптической кривой. Наиболее популярный протокол SIDH (Supersingular isogeny Diffie-Hellman, SIDH) позволяет произвести об-

мен ключами по незащищенному каналу связи. Этот факт и является его отличительной особенностью, гарантирующей совершенную секретность [21]. С учётом сжатия SIDH имеет наименьшую длину ключа из всех постквантовых протоколов обмена ключами. Однако полноценной криптосистемы на изогениях пока реализовано не было.

Криптосистемы, основанные на группах кос. Основы теории кос были введены в 20-х годах 19 века немецким математиком Э. Артином (Е. Агйп). Криптографические примитивы, основанные на группах кос, могут решать большой спектр задач информационной безопасности (обеспечение целостности, подлинности, неотказуемо-сти, конфиденциальности передаваемой информации, осуществление протоколов обмена ключами, шифрования и электронной подписи) [22]. Также они обладают свойством быстрой генерации ключей, но время шифрования или подписания документа оставляет желать лучшего. В качестве примера, можно привести схему электронной подписи WalnutDSA.

Обобщение вышеупомянутых подходов приведено в Таблице 2.

Как и в классических асимметричных криптографических алгоритмах и схемах электронной подписи, трудность взлома которых основывается на сложности вычисления какой-либо «трудной» односторонней математической задачи (функции), в пост-квантовой криптографии стойкость основывается также на сложности вычисления некоторой трудно решаемой задачи.

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

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

В дальнейшем, при рассмотрении схем электронной подписи, также будет видно, что при сопоставимом уровне криптостойкости, схемы на основе теории решеток являются наиболее интересными и «компактными».

4. Кандидаты на новый пост-квантовый стандарт

Как уже было сказано ранее, в 2016 году Национальный Институт Стандартов и Технологий США объявил о тарте конкурса на создание новых пост-квантовых алгоритмов и стандартов взамен старых [11]. Всего было представлено 82 заявки. Подача заявок на участие в первом туре конкурса закончилась 30 декабря 2017 года. Всего было допущено 69 алгоритмов, из них 49 алгоритмов шифрования с открытым ключом и 20 схем электронной подписи. Результаты первого тура

Таблица 2.

Сравнение пост-квантовых подходов

Вид Обоснование сложности Скорость Преимущества Недостатки

Теория решеток Шифрование ЭП Хэш-функции Обмен ключами Полностью гомоморфное шифрование Протоколы «забывчивой передачи» Протоколы с использованием атрибута Шифрование, основанное на идентификации Нахождение «хорошего» базиса решетки Решение задач теории решеток в особых решетках Хорошо реализуется на специальном ПО Обоснование сложности в наихудшем случае Множество сфер применения Повышенная длина ключей по сравнению с ЭК Отсутствие точного метода оценки сложности

Многомерные квадратичные системы Многомерные квадратичные системы Шифрование ЭП Обмен ключами Решение систем многомерных квадратичных уравнений Хорошо реализуется на аппаратных средствах Быстрота Малая длина ключей даже в сравнении с ЭК Несостоятельность обоснования безопасности Большое количество систем было взломано Повышенная длина открытого ключа

ЭП на хэш-функциях ЭП Сопротивление коллизиям Зависит от используемой хэш-функции Сравнительная быстрота Возможность реализации только протоколов ЭП Ограниченное количество подписей на одном ключе Безопасность зависит от выбираемой хэш-функции Большая длина подписи

Теория алгебраического кодирования Шифрование ЭП Хэш-функции Обмен ключами Декодирование полных линейных кодов Хорошо реализуется на аппаратных средствах Хорошая скорость вычислений Слишком большая длина ключей Большие требования к памяти устройства Большое количество систем было взломано

Изогении эллиптических кривых Обмен ключами Задача нахождения изогенных отображений между двумя суперсингулярными эллиптическими кривыми Хорошо реализуется на специальном ПО Совершенно прямая секретность Наименьшая длина ключа Отсутствие полноценной криптосистемы

Теория кос Шифрование ЭП Обмен ключами Решение проблемы поиска сопряжений Хорошо реализуется на аппаратных средствах Решают большой спектр задач Быстрая генерация ключей Медленные процессы генерации и проверки ЭП

были объявлены 30 января 2019 года. Во второй тур прошли 26 кандидатов [23]: 17 алгоритмов шифрования и распределения ключей и 9 схем электронной подписи.

Среди схем электронной подписи во второй тур прошли:

• Схемы на решетках:

o CRYSTALS-DILITHIUM; o FALCON; o qTESLA;

• Многомерные квадратичные системы: o GeMSS;

o LUOV; o MQDSS; o Rainbow;

• Электронные подписи на хэш-функциях: o Picnic;

o SPHINCS+.

В сжатые сроки, до 15 марта 2019 года разработчики этих систем должны были внести требующиеся корректировки и обновить заявки. Организаторами планируется, что срок рассмотрения претендентов во втором туре продлится приблизительно год-полтора, после чего будут объявлены победителя конкурса, либо, по необходимости, будет назначен третий тур.

Конкурс является полностью открытым. Организаторы призывают все криптографическое научное сообщество, включая уже выбывших кандидатов принять участие в рассмотрении оставшихся заявок, для более скрупулезного выявления недостатков.

Три основных критерия, по которым производилась оценка кандидатов, были следующие: безопасность, быстродействие и использование ресурсов памяти, характеристики алгоритмов и нюансы реализаций.

• Безопасность является важнейшим требованием. NIST планирует использовать новый пост-квантовый стандарт для широкого ряда задач. Оценка кандидатов будет происходить именно по их способности обеспе-

чения безопасности в этих криптографических задачах. Схемы электронной подписи должны быть стойкими к атакам при адаптивно выбираемом шифртексте (adaptive chosen cipher text attack), атакам на основе известных сообщений, к экзистенциальной подделке и другим видам атак. [11]

NIST определяет 5 уровней стойкости: o 1 уровень - «вероятно, безопасные алгоритмы в обозримом будущем (если не окажется, что КК будут работать быстрее, чем ожидается)»; o 2, 3 уровни - «вероятно, безопасные алгоритмы

в обозримом будущем»; o 4, 5 уровни - «вероятно, чрезмерные по стойкости алгоритмы»;

Также одним из требований для кандидатов было предоставление информации для обобщения об известных криптоаналитических атаках на предлагаемые схемы, и оценка сложности этих атак.

• Второе по значимости требование - требование к эффективности выполнения и использованию ресурсов памяти. Сюда относятся: размеры ключей, размеры подписи; время, затраченное на генерацию ключей и подписи; время, требуемое на проверку подписи; а также доля возможных ошибок при работе алгоритмов. Требования по размеру памяти относятся как к программному, так и к аппаратному обеспечению.

• Критерий «характеристики алгоритмов и нюансы реализаций» заключаются в каких-либо специфических возможностях каждого алгоритма, например, в хорошей способности эффективно работать на различных платформах, или в возможности распараллеливания вычислений для достижения большего быстродействия.

Рассмотрим кандидатов второго тура среди схем электронной подписи более подробно (Таблица 3). Параметры, по которым производится сравнительный анализ следующие: длина закрытого ключа, длина открытого ключа,длина подписи.

Таблица 3.

Схемы электронной подписи, прошедшие во второй тур конкурса пост-квантовых стандартов \IIST

Алгоритм Конкретная реализация Пост-квант. подход Закрытый ключ, байт Открытый ключ, байт Длина подписи, байт Категория безопасности

Dilithium_ medium 2 800 1 184 2 044 1

CRYSTALS-Dilithium Dilithium_ recommended 3 504 1 472 2 701 2

Dilithium_ very_high (Л ю ic ti t 3 856 1 760 3 366 3

falcon1024 te _J 8 193 1 793 1 330 5

Falcon falcon512 R 4 097 897 690 1

falcon768 е 3 6 145 1 441 1 077 3

qTesla_128 е я 2 112 4 128 3 104 1

qTESLA qTesla_192 и о £ 8 256 8 224 6 176 3

qTesla_256 8 256 8 224 6 176 5

GeMSS GeMSS128 Многомерные квадратичные системы (Multivariate) 14 208 417 408 48 1

GeMSS192 39 440 1 304 192 88 3

GeMSS256 82 056 3 603 792 104 5

LUOV luov-48-49-242 32 7 536 1 746 2

luov-64-68-330 32 19 973 3 184 4

luov-80-86-399 32 40 248 4 850 5

luov-8-117-404 32 100 989 521 5

luov-8-63-256 32 15 908 319 2

luov-8-90-351 32 46 101 441 4

MQDSS mqdss-48 32 62 32 882 2

mqdss-64 48 88 67 800 4

Rainbow la 100 209 152 097 64 1

lb 114 308 163 185 78 1

Ic 143 385 192 241 104 1

lllb 409 463 564 535 112 3

lllc 537 781 720 793 156 3

IVa 376 141 565 489 92 4

Vc 1 274 317 1 723 681 204 5

Vla 892 079 1 351 361 118 5

Vlb 1 016 868 1 456 225 147 5

Picnic picnicllfs Подписи на основе хэш-функций (Hash) 49 33 34 004 1

picnicllur 49 33 53 933 1

picnicl3fs 73 49 76 744 3

picnicl3ur 73 49 121 817 3

picnicl5fs 97 65 132 828 5

picnicl5ur 97 65 209 478 5

Sphincs+ sphincs-sha256-128f 64 32 16 976 1

128s 64 32 8 080 1

192f 96 48 35 664 3

192s 96 48 17 064 3

256f 128 64 49 216 5

256s 128 64 29792 5

Различные криптографические схемы, помимо обеспечения должного уровня безопасности, могут оцениваться по другим разным параметрам, например, по быстродействию (то есть по скорости выполнения процедур, как на стороне отправителя, так и на стороне получателя), по требуемой памяти обрабатывающего устройства (как отправителя, так и получателя), по длинам закрытых ключей, которые необходимо хранить, и по некоторым другим параметрам.

Для схем подписи, по понятным причинам, определяющим параметром является длина подписи, а также длина открытого ключа подписывающего, поэтому при дальнейшем анализе будем особое внимание уделять

следующему параметру: |рк| + |Sign|, где |рк| - длина открытого ключа, |Sign| - длина подписи.

Из основных классов пост-квантовой криптографии, наиболее перспективными являются схемы на основе решеток, многомерных квадратичных многочленов и схемы на основе хэш-функций. Каждая из схем имеет различные реализации в зависимости от обеспечиваемого уровня безопасности согласно требованиям конкурса.

Для схем электронной подписи определяющими параметрами являются длины ключей (особенно открытого ключа) и подписи. В меньшей степени - время генерации, подписания и проверки. Поэтому, предлагается «от-

Таблица 4.

Первый уровень безопасности

Алгоритм Конкретная реализация Подход Закрытый ключ, байт Открытый ключ, байт Длина подписи, байт

CRYSTALS-Dilithium Dilithium_ medium Подписи на основе теории решеток (Lattices) 2 800 1 184 2 044

Falcon falcon512 4 097 897 690

qTesla qTesla_128 2 112 4 128 3 104

бросить» схемы GeMSS и Rainbow, так как длины ключей в этих схемах достигают нескольких сотен Кбайт. Также, предлагается исключить подписи, основанные на хэш-функциях - Picnic и Sphincs+ - в силу их ограниченности по количеству генерируемых подписей на одной паре ключей.

Для дальнейшей выборки рассмотрим параметры оставшихся схем (CRYSTALS-DILITHIUM, FALCON, qTESLA, LUOV, MQDSS) для разных уровней безопасности: первого уровня (Таблица 4), второго-третьего уровней (Таблица 5) и четвертого-пятого уровней (Таблица 6).

Первый уровень безопасности из оставшихся кандидатов обеспечивают только схемы на решетках. Многомерные квадратичные схемы обладают более высокими уровнями безопасности, но конкретных реализаций для первого уровня не имеют. По тактовым затратам наиболее интересным является схема qTesla_128. Что касается параметра , то явно выигрывает Falcon512 (Рис. 1).

Среди схем второго-третьего уровней наибольшим быстродействием обладает CRYSTALS-Dilithium. Наименьшим - MQDSS. MQDSS-48 имеет короткие ключи,

но слишком большую длину подписи, что совершенно неприемлемо для гибридных систем.

По параметру снова явное преимущество имеют схемы на решетках, в частности, схема Ра1соп768 (Рис. 2).

На четвертом - пятом уровнях безопасности многомерные квадратичные схемы 1иоу-80-86-399, 1иоу-8-117-404 и 1иоу-8-90-351 обладают слишком большими длинами открытых ключей. Схема mqdss-64 - большой длиной подписи. Среди остальных схем наибольшее быстродействие обеспечивает qTesla_256, относящаяся к криптографии на решетках. По сумме длин открыто-

го ключа и подписи снова побеждает схема falcon1024 (Рис. 3), также относящаяся к криптографии на решетках.

Проведенный сравнительный анализ пост-квантовых схем электронной подписи выявил наиболее перспективного кандидата - схему FALCON, которая при всех уровнях безопасности обеспечивала наименьшую длину ключей и подписи. При первом уровне значение |pk| + |Sign| равно 1587 байт, на третьем - 2518 байт, на пятом - 3123 байт. Эти цифры сопоставимы с аналогичными параметрами схемы RSA.

Закрытый ключ Открытый ключ подпись

Dîlîthîum medium

falcon512

qTesla_128

Рис. 1. Длины ключей и подписи при первом уровне безопасности

Таблица 5.

Второй-третий уровни безопасности

Алгоритм Конкретная реализация Пост-квантовый класс Закрытый ключ, байт Открытый ключ, байт Длина подписи, байт

CRYSTALS-Dilithium Dilithium_ recommended Подписи на основе теории решеток 3 504 1 472 2 701

Dilithium_ very_ high 3 856 1 760 3 366

Falcon falcon768 6 145 1 441 1 077

qTesla qTesla_192 8 256 8 224 6 176

LUOV luov-48-49-242 Многомерные квадратичные системы 32 7 536 1 746

luov-8-63-256 32 15 908 319

MQDSS mqdss-48 32 62 32 882

Рис. 2. Длины ключей и подписи при втором и третьем уровнях безопасности

Таблица 6.

Четвертый-пятый уровни безопасности

Алгоритм Конкретная реализация Пост-квантовый класс Закрытый ключ, байт Открытый ключ, байт Длина подписи, байт

Falcon falcon1024 Подписи на основе теории решеток 8 193 1 793 1 330

qTesla qTesla_256 8 256 8 224 6 176

LUOV luov-64-68-330 Многомерные квадратичные системы 32 19 973 3 184

luov-80-86-399 32 40 248 4 850

luov-8-117-404 32 100 989 521

luov-8-90-351 32 46 101 441

MQDSS mqdss-64 48 88 67 800

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

Рис. 3. Длины ключей и подписи при четвертом и пятом уровнях безопасности

5. Выводы

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

Показано, что по требованию компактности, то есть по сумме длин подписи и открытого ключа схе-

ма на основе теории решеток FALCON (во всех трех конкретных реализациях) имеет наименьшую длину из всех представленных выше алгоритмов при сопоставимом времени работы и уровне безопасности.

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

В дальнейшем предполагается подробнее изучить схему электронной подписи FALCON: процедуры генерации ключей, генерации подписи, проверки подписи, рекомендуемые разработчиками параметры, положительные и отрицательные стороны.

Рецензент: Исмагилов Валерий Сарварович, кандидат физико-математических наук, ученый секретарь Санкт-Петербургского филиала Федерального государственного бюджетного учреждения науки Института земного магнетизма, ионосферы и распространения радиоволн им. Н.В. Пушкова РАН, Санкт-Петербург, Россия. E-mail: [e-mail]

Литература

1. Ллойд С. Программируя вселенную. Квантовый компьютер и будущее науки. - М. : Альпина нон-фикшн, 2014. - 256 с.

2. Душкин Р.В. Обзор текущего состояния квантовых технологий // Компьютерные исследования и моделирование. 2018. Т. 10. № 2. С. 165-179.

3. Соловьев В. М. Квантовые компьютеры и квантовые алгоритмы. Часть 1. Квантовые компьютеры // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2015. Т. 15, вып. 4. С. 462-477.

4. Филиппов М.А., Кротова Е.Л. Квантовая криптография. Преимущества и недостатки // Вестник УрФО. Безопасность в информационной сфере. 2017. № 4 (26). С. 25-27.

5. Bernstein DJ, Lange T. Post-quantum cryptography: dealing with the fallout of physics success, IACR, 2017. 20 p.

6. Кравченко В.О., Черкесова Л.В. Обзор постквантовых криптографических алгоритмов // Аллея науки. 2019. Т. 3. № 1 (28). С. 966974.

7. Михайличенко Д.А., Егорова А.А. Основные направления развития постквантовой криптографии // Труды Ростовского государственного университета путей сообщения. 2016. № 2. С. 41-45.

8. Березовский Г.Ю., Гущина О.М. Исследование постквантовой криптографии // Прикладная математика и информатика: современные исследования в области естественных и технических наук: материалы III научно-практической

всероссийской конференции (школы-семинара) молодых ученых 24-25 апреля 2017 г. - Тольятти: Издатель Качалин Александр Васильевич, 2017. 2017. С. 71 - 73.

9. Рябый М.А. Обзор современных методов квантовой и пост-квантовой криптографии // Безпека шформацМ. 2014. Т. 20. № 3. С. 236-241.

10. Горбенко И. Пономарь В. Исследование возможности использования и преимуществ постквантовых алгоритмов в зависимости от условий применения // Восточно-Европейский журнал передовых технологий. 2017. Т. 2. № 9 (86). С. 21-32.

11. Chen L., Jordan S., Liu Y.K., Moody D., Peralta R., Perlner R., Smith-tone D. Report on Post-Quantum Cryptography, NISTIR 8105, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2016, 10pp. https://doi.org/10.6028/NIST.IR.8105.

12. Семенов Ю.А. Квантовая криптография [Электронный ресурс]. - Режим доступа: http://book.itep.ru/6/q_crypt.htm, свободный. - Заголовок с экрана (дата обращения: 28.04.2019).

13. Пискова А.В., Коробейников А.Г. Теория решеток в постквантовой криптографии // Сборник трудов V Всероссийского конгресса молодых ученых материалы конгресса : в 2 т. Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики. 2016. С. 91-93.

14. Александрова Е.Б., Шенец Н.Н. Применение постквантовой и гомоморфной криптографии в задачах кибербезопасности // Неделя науки СПбПУ. Материалы научного форума с международным участием. Междисциплинарные секции и пленарные заседания институтов. 2015. С. 9-17.

15. Taeho Jung, Xiang-Yang Li, Zhiguo Wan, and Meng Wan. ODntrol cloud data access privilege and anonymity with fully anonymous attribute-based encryption, IEEE transactions on information forensics and security, 2010, P. 190-199.

16. Кузнецов А.А., Горбенко Ю.И. Исследование криптографических атак на схемы электронной цифровой подписи в фактор-кольце усеченных полиномов // Захист шформацМ. 2016. Т. 18. № 4. С. 293-300.

17. Жаткин А.В. Применение систем квадратных уравнений многих переменных в асимметричной криптографии // Безопасность информационных технологий. 2013. Т. 20. № 1. С. 98-99.

18. Батенко К.Е., Прокудин А.Н. Пост-квантовый алгоритм электронно-цифровой подписи на основе дерева Меркла и ГОСТ РФ 34.11-12 «СТРИБОГ» // Молодой ученый. 2017. № 23 (157). С. 100-103.

19. Завгородний С.Д. Криптография на основе кодов исправления ошибок // Научные исследования и разработки студентов Сборник материалов VI Международной студенческой научно-практической конференции. Редколлегия: О.Н. Широков [и др.]. 2018. С. 96-98.

20. Кузнецов А.А., Киян А.С., Деменко Е.Е. Схемы электронной цифровой подписи на основе алгебраического кодирования // Актуальные научные исследования в современном мире. 2017. № 11-9 (31). С. 57-60.

21. Александрова Е.Б., Пендрикова О.Н. Применение графов изогений для проверки суперсингулярности эллиптических кривых // Проблемы информационной безопасности. Компьютерные системы. 2018. № 3. С. 63-69.

22. Shpilrain V., Zapata G. Combinatorial group theory and public key cryptography, Appl. Algebra Eng. Commun. Comput, 17 (2006), no. 3-4, 291-302.

23. Alagic J., Alperin-Sheriff J., Apon D., Cooper D., Dang Q., Yi-Kai Liu., Miller C., Moody D., Peralta R., Perlner R., Robinson A., SmithTone D. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process, NISTIR 8240, National Institute of Standards and Technology, Gaithersburg, Maryland, January 2019, 27 pp. http://dx.doi.org/10.6028/NIST.IR.8240.

THE ANALYSIS OF EXISTING POST-QUANTUM APPROACHES AND ELECTRONIC SIGNATURE SCHEMES

Komarova A.V.4, Korobeynikov A.G.5

The purpose of the article is to highlight the latest trends in the post-quantum cryptography development, in particular, in electronic signature schemes. The goal is achieved by considering the second round candidates of the National Institute of Standards and Technology (NIST) competition.

Method: analysis and synthesis of existing post-quantum approaches, comparative analysis of the most promising electronic signature schemes, according to the authors point of view, and its characteristics.

The result: the existing post-quantum approaches are considered and the most promising of them are synthesized. The comparison of some second round electronic signature scheme parameters is held. It is concluded that for the construction of electronic signature schemes the most promising approach of all proposed is the lattice theory, in particular the FALCON scheme. This scheme provides the highest level of«compactness»in the sum of the public key and signature lengths among all the post-quantum electronic signature schemes presented at the NIST competition with comparable levels of security and time parameters.

4 Antonina Komarova, postgraduate student, St. Petersburg National Research University of Information Technologies, Mechanics and Optics, St. Petersburg, [e-mail]

5 Anatoly Korobeynikov, Dr.Sc., Professor, Pushkov institute of terrestrial magnetism, ionosphere and radio wave propagation of the Russian Academy of Sciences St.-Petersburg Filial, St. Petersburg, [e-mail]

Keywords: post-quantum cryptography, quantum computer, lattice theory, multivariate quadratic equations, hash-

based signatures, code-based signatures, isogenies of elliptic curves, braid theory.

Reference

1. Lloid S. Programmiruia vselennuiu Kvantovyi kompiuter i budushchee nauki. - M.: Alpina non-fikshn, 2014. - 256 p.

2. Dushkin R. V. Obzor tekushchego sostoianiia kvantovykh tekhnologii // Kompiuternye issledovaniia i modelirovanie [Computer research and modeling]. 2018. V. 10. № 2. P. 165-179.

3. Solovev V. M. Kvantovye kompiutery i kvantovye algoritmy. Chast 1. Kvantovye kompiutery // Izv. Sarat un-ta Nov. ser. Ser. Matematika Mekhanika Informatika. [News Sarat. Un. New ser. Ser. Mathematics. Mechanics. Informatics]. 2015. V. 15. № 4. P. 462-477.

4. Filippov M.A., Krotova E.L. Kvantovaya kriptografiya. Preimushchestva i nedostatki // Vestnik UrFO. Bezopasnost' v informacionnoj sfere [Herald UrFO. Information security]. 2017. № 4 (26). P. 25-27.

5. Bernstein DJ, Lange T. Post-quantum cryptography: dealing with the fallout of physics success, IACR, 2017. 20 p.

6. Kravchenko V.O., Cherkesova L.V. Obzor postkvantovyh kriptograficheskih algoritmov // Alleya nauki [Alley of science]. 2019. V. 3. № 1 (28). P. 966-974.

7. Mihajlichenko D.A., Egorova A.A. Osnovnye napravleniya razvitiya postkvantovoj kriptografii // Trudy Rostovskogo gosudarstvennogo universiteta putej soobshcheniya [Proceedings of Rostov state University of railway engineering]. 2016. № 2. P. 41-45.

8. Berezovskij G.Yu., Gushchina O.M. Issledovanie postkvantovoj kriptografii // Prikladnaya matematika i informatika: sovremennye issledovaniya v oblasti estestvennyh i tekhnicheskih nauk: materialy III nauchno-prakticheskoj vserossijskoj konferencii (shkoly-seminara) molodyh uchenyh 24-25 aprelya 2017 g. [Applied mathematics and Informatics: modern research in the field of natural and technical Sciences: materials of the III scientific-practical all-Russian conference (school-seminar) of young scientists 24-25 April 2017] - Tol'yatti: Izdatel' Kachalin Aleksandr Vasil'evich, 2017. 2017. P. 71 - 73.

9. Ryabyj M.A. Obzor sovremennyh metodov kvantovoj i post-kvantovoj kriptografii // Bezpeka informacii [Information security]. 2014. V. 20. № 3. P. 236-241.

10. Gorbenko I. Ponomar' V. Issledovanie vozmozhnosti ispol'zovaniya i preimushchestv postkvantovyh algoritmov v zavisimosti ot uslovij primeneniya // Vostochno-Evropejskij zhurnal peredovyh tekhnologij. 2017. V. 2. № 9 (86). P. 21-32.

11. Chen L., Jordan S., Liu Y.K., Moody D., Peralta R., Perlner R., Smith-tone D. Report on Post-Quantum Cryptography, NISTIR 8105, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2016, 10pp. https://doi.org/10.6028/NIST.IR.8105.

12. Semenov Yu.A. Kvantovaya kriptografiya [electronic resource]. - Mode of access: http://book.itep.ru/6/q_crypt.htm, free. - The title screen (accessed date: 28.04.2019).

13. Piskova A.V., Korobejnikov A.G. Teoriya reshetok v postkvantovoj kriptografii // Sbornik trudov V Vserossijskogo kongressa molodyh uchenyh materialy kongressa: v 2 t. [Proceedings of the V all-Russian Congress of young scientists materials of the Congress: in 2 v]. Sankt-Peterburgskij nacional'nyj issledovatel'skij universitet informacionnyh tekhnologij, mekhaniki i optiki. 2016. P. 91-93.

14. Aleksandrova E.B., Shenec N.N. Primenenie postkvantovoj i gomomorfnoj kriptografii v zadachah kiberbezopasnosti // Nedelya nauki SPbPU. Materialy nauchnogo foruma s mezhdunarodnym uchastiem. Mezhdisciplinarnye sekcii i plenarnye zasedaniya institutov [The week of science of SPbSPU. Materials of the scientific forum with international participation. Interdisciplinary sections and plenary sessions of the institutes.]. 2015. P. 9-17.

15. Taeho Jung, Xiang-Yang Li, Zhiguo Wan, and Meng Wan. Control cloud data access privilege and anonymity with fully anonymous attribute-based encryption, IEEE transactions on information forensics and security, 2010, P. 190-199.

16. Kuznecov A.A., Gorbenko Yu.I. Issledovanie kriptograficheskih atak na skhemy elektronnoj cifrovoj podpisi v faktor-kol'ce usechennyh polinomov // Zahist informacii [Information protection]. 2016. V. 18. № 4. P. 293-300.

17. Zhatkin A.V. Primenenie sistem kvadratnyh uravnenij mnogih peremennyh v asimmetrichnoj kriptografii // Bezopasnost' informacionnyh tekhnologi [Information technology security]. 2013. V. 20. № 1. P. 98-99.

18. Batenko K.E., Prokudin A.N. Post-kvantovyj algoritm elektronno-cifrovoj podpisi na osnove dereva Merkla i GOST RF 34.11-12 «STRIBOG» // Molodoj uchenyj [Young scientist]. 2017. № 23 (157). P. 100-103.

19. Zavgorodnij S.D. Kriptografiya na osnove kodov ispravleniya oshibok // Nauchnye issledovaniya i razrabotki studentov Sbornik materialov VI Mezhdunarodnoj studencheskoj nauchno-prakticheskoj konferencii [Research and development of students Collection of materials VI International student scientific-practical conference]. Redkollegiya: O.N. Shirokov [i dr.]. 2018. P. 96-98.

20. Kuznecov A.A., Kiyan A.S., Demenko E.E. Ckhemy elektronnoj cifrovoj podpisi na osnove algebraicheskogo kodirovaniya // Aktual'nye nauchnye issledovaniya v sovremennom mire [Actual research in the modern world]. 2017. № 11-9 (31). P. 57-60.

21. Aleksandrova E.B., Pendrikova O.N. Primenenie grafov izogenij dlya proverki supersingulyarnosti ellipticheskih krivyh // Problemy informacionnoj bezopasnosti. Komp'yuternye sistemy [Problems of information security. Computer systems]. 2018. № 3. P. 63-69.

22. Shpilrain V., Zapata G. Combinatorial group theory and public key cryptography, Appl. Algebra Eng. Commun. Comput, 17 (2006), no. 3-4, 291-302.

23. Alagic J., Alperin-Sheriff J., Apon D., Cooper D., Dang Q., Yi-Kai Liu., Miller C., Moody D., Peralta R., Perlner R., Robinson A., SmithTone D. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process, NISTIR 8240, National Institute of Standards and Technology, Gaithersburg, Maryland, January 2019, 27 pp. http://dx.doi.org/10.6028/NIST.IR.8240.

Analysis and Comparison of Electronic Digital Signature State Standards GOST R 34.10-1994, GOST R 34.10-2001

and GOST R 34.10-2012

Antonina Komarova Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia [e-mail]

Anatoly Korobeynikov Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia [e-mail]

Alexander Menshchikov Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia menshikov@ corp.ifmo.ru

Yurij Gatchin Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg,Russia [e-mail],

Alexander Negols Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia [e-mail]

Nina Tishukova Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia, nina.tishukova@ mail.ru

ABSTRACT

These days information systems that use asymmetric cryptography or public key cryptography are widely spread all over the world. The reason of this fact is a rather high reliability of existing algorithms. In terms of information security, we can distinguish the following important tasks: ensuring the availability of information, its authenticity and confidentiality. All these problems can be solved with the help of electronic digital signature (hereinafter-EDS). It ensures the integrity of information, its confidentiality, authenticity and the origin. EDS is widely used in various commercial and governmental organizations that are obliged to follow the state standard GOST R 34.10-2012 "Information technology. Cryptographic protection of information. The processes of forming and checking electronic digital signature". In the view of the above we perform a comparative analysis of the state standard GOST R 34.10-2012 with the state standards GOST R 34.10-2001 and R 34.10-1994 to find their relevance, reliability and complexity. Due to the fact that EDS is based on a special hash function, the authors of this article have also reviewed the state standards GOST R 34.11 -2012 and GOST R 34.11-1994. To estimate hash function generation time, the Python Code which uses the Pygost Library has been written. Furthermore, hacking complexity assessments of the algorithms themselves have been realized. Therefore, estimations of speed and performance procedures generation and signature verification have been made and the hacking complexity assessments of the Russian state standards are realized. The approximate durations of forced entry are calculated and the advantage of the new state standard GOST R 34.10-2012 is justified. As a result of the analysis the relevance, the reliability and the complexity of the state standard GOST R 34.10-2012 have been turned out. In spite of all the strength benefits the new standard requires more time effort for hash-function formation and for the digital signature formation.

CCS Concepts

• Security and privacy^ Cryptography^ Public key (asymmetric) techniques^ Digital signatures

Keywords

"State Standard", "Digital Signature", "Hash function", "Discrete Logarithm", "Elliptic Curve"

1. INTRODUCTION

These days information technologies are of a great importance for the enterprises functioning [1]. Secure information technology is applied in such areas as production, economy, financing, military [2]. All the information processed in computer networks and on the Internet should be well protected. This fact requires continuous improvement of information security mechanisms.

Public-key cryptosystems are the most demanded today. Among them elliptic curve (hereinafter-EC) cryptosystems are the most persistent and time-consuming according to scientists [3]. This fact was one of the reasons to change state standard GOST R 34.10-1994 «Information technology. Cryptographic data security. Formation and verification processes of electronic digital signature» with its equivalent in 2001 and then later with more advanced analogue in 2012. Digital signature algorithms state standards GOST R 34.10-2001 and GOST R 34.10-2012 are the improvement of digital signature algorithm state standard GOST R 34.10-1994. Unlike the old standard which is based on the discrete logarithm in finite simple field complexity, new algorithms are built on the basis of the mathematical apparatus of EC.

2. ALGORITHM DESCRIPTION

In this chapter we look at step-by-step algorithms according to each state standard.

2.1 The State Standard GOST R 34.11-1994

2.1.1 The generation of signature parameters Getting primes is performed using (xn = bxn_^ + c) linear

congruent detector with 216 or 232 modules. The user needs to specify initial condition x0 and c detector parameter. Specified values should be fixed (to remember) for the possibility of verifying that prime numbers were obtained according to the established procedure.

2.1.2 Signature generation algorithm to M message

• Step 1 - Calculate the hash function value as h(M),

if h(M) mod q = 0 then h(M) = 0255 ;

• Step 2 - Generate k random integer, 0<k<q;

• Step 3 - Calculate two values:

r = ak mod p and r = r mod q,

if r = 0 , then return to step 2 and generate another k value;

• Step 4 - Calculate s with the help of x secret key:

5 = (xr + kh(M))mod q ,

if s=0 then return to step 2;

• Signature to Mmessage is (r ^ H^^ vect°r-

The sender transmits to recipient a digital sequence of characters which consists of the binary text message representation and attached EDS. The recipient should verify the message authenticity and authenticity of EDS, performing a number of operations (calculations). This is possible if recipient knows the sender' public key.

2.1.3 Verification of the signature algorithm

• Step 1 - Check if 0<s<q and 0<r'<q then the signature is considered invalid;

• Step 2 - Calculate the hash function value for received M message h(Mi) , if h(Mi)modq = 0 then h(M) = 0255 ;

• Step 3 - Compute v value as

v = (h (M1 ))q—2(mod q);

• Step 4 - Compute Zj and Z2 values as

z1 = sv(mod q) , z2 = (q— r )v(mod q);

• Step 5 - Compute u value as

u = ((aS 1 yS2 )(modp))(mod q) ;

• Step 6 - Check if r = u .

If r and u values are coincidence then recipient decides that received message was transmitted by the sender. The transmission process was not violated message integrity, i.e. M =M. Otherwise, the signature is considered invalid [4].

2.2 The State Standard GOST R 34.11-2001

2.2.1 The generation of signature parameters

• Step 1 - Generate prime r number which is EC module and satisfies the inequality p > 2255 ;

• Step 2 - Choose E elliptic curve with its J(E) invariant or with coefficients a, b e GF(p) ;

• Step 3 - Choose an integer m number which is the order of elliptic curve E;

• Step 4 - Choose a prime q number which is order of cyclic subgroup of the E EC for which the following conditions are performed:

m = nq,n e Z ,1 < n 1

254 -,256 | ;

2 < q < 2 J

• Step 5 - Choose P e E point with its coordinates P(x , y ) such that P * 0, q * P = 0 ;

• Step 6 - Select a secret key d, 0 < d < q;

• Step 7 - Calculate Q e E public key point with coordinates

P(xq, y q ) which satisfies q * P = Q equality;

• Public key is a pair of points (P, Q), the secret key is d.

2.2.2 Signature generation algorithm to M message

• Step 1 - Calculate the hash function value as h=H(M) binary vector;

• Step 2 - Compare h binary vector with a number and calculate e number:

e = a mod q, if e=0 then e=1;

• Step 3 - Generate k random number, 0<k<q;

• Step 4 - Compute the EC point C = k* P with coordinates

C (x,, );

• Step 5 - Calculate r = xc mod q . If r=0 then return to step 3;

• Step 6 - Calculate s parameter as

s = (rd + ke~) mod q,

if s=0 then return to step 3;

• Step 7 - Calculate r and s binary vectors which correspond respectively to parameters r and 5;

• Signature to M message is ^ = (r || 5) vector.