Модели и методы использования электронной подписи в доверенных системах хранения данных тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Давыдов Вадим Валерьевич

• Давыдов Вадим Валерьевич
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Давыдов Вадим Валерьевич

Реферат

Synopsis

Введение

Глава 1. Метод постквантовой пороговой подписи, основанной на математической задаче поиска изогений между

эллиптическими кривыми

1.1 Алгоритмы Шора и Гровера как угроза современной криптографии

1.2 Выбор математического аппарата для построения криптографических алгоритмов подписи

1.2.1 Криптография, основанная на кодах, исправляющих ошибки

1.2.2 Криптография, основанная на решётках

1.2.3 Криптография, основанная на многомерных уравнениях

1.2.4 Криптография, основанная на хэш-функциях

1.2.5 Криптография, основанная на изогениях эллиптических кривых

1.2.6 Выбор математической задачи

1.3 Математический аппарат

1.4 Построение пороговой подписи на изогениях эллиптических кривых

1.4.1 Схема подписи CSI-FiSh, построенная на изогениях

1.4.2 Пороговый вариант подписи CSI-FiSh

1.4.3 Описание предлагаемого решения

1.4.4 Безопасность схемы

1.4.5 Экспериментальные результаты

1.5 Выводы по главе

Глава 2. Метод разделения секрета с возможностью

эффективного изменения порога

2.1 Интерполяционные формулы

2.1.1 Определение интерполяции

2.1.2 Интерполяционная формула Ньютона

2.1.3 Интерполяционная формула Лагранжа

2.1.4 Связь между формулой Лагранжа и Ньютона

2.2 Схемы разделения секрета

2.2.1 Схема Миньотта

2.2.2 Схема Шамира

2.3 Описание предлагаемого решения

2.3.1 Метод разделения секрета, использующий интерполяционный многочлен Ньютона

2.3.2 Пример

2.4 Сравнение использования полиномов Лагранжа и Ньютона для сборки секрета

2.4.1 Оценка эффективности при использовании полиномов Ньютона и Лагранжа

2.4.2 Пример использования предлагаемой схемы в реальных системах

2.4.3 Пример сборки секрета с помощью интерполяционного многочлена Лагранжа при изменении порога

2.4.4 Пример сборки секрета с помощью интерполяционного многочлена Ньютона при изменении порога

2.5 Выводы по главе

Глава 3. Модели использования электронной подписи в доверенных системах хранения данных с

использованием технологии блокчейн

3.1 Краткая история и определение технологии блокчейн

3.2 Работа с блоками в блокчейн

3.2.1 Устройство блока на примере криптовалют

3.2.2 Правила добавления блоков в сети

3.2.3 Доказательство выполнения работы (Proof-of-Work) и другие механизмы добавления блоков

3.3 Разновидности блокчейн

3.4 Модели использования блокчейн технологии в доверенных системах хранения данных для регистрации событий

3.5 Использование криптографических примитивов в системах с блокчейн

3.6 Выводы по главе

Глава 4. Практическое применение разработанных методов в доверенных системах хранения данных на примере модели регистрации дорожных инцидентов

4.1 Модель системы регистрации дорожных инцидентов

4.1.1 Система онлайн-регистрации

4.1.2 Система оффлайн-регистрации

4.2 Распределение ключей в системе регистрации дорожных инцидентов

4.2.1 Работа PKI при различных сценариях возникновения автомобильных инцидентов

4.2.2 Использование ID-based и Attribute-based криптографии

в модели регистрации дорожных инцидентов

4.2.3 Работа Private Key Generator (PKG)

4.3 Методы обеспечения анонимности пользователей в полученной модели

4.4 Выводы по главе

Заключение

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

Список рисунков

Список таблиц

Приложение А. Свидетельства о регистрации программ для

ЭВМ

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

Приложение В. Тексты публикаций по теме исследования

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

Реферат Общая характеристика работы

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

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

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

Технология была впервые формально описана Сатоши Накамото в 2008 году в статье про первую криптовалюту биткоин, однако, похожие идеи высказывались гораздо раньше (Д. Чаум, Р. Меркл, 1979; С. Хабер, В. Сторнетта, 1990).

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

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

торую вычислительно трудную задачу, решение которой требует большого количества энергии и мощностей. Такой подход называется доказательством выполнения работы (Proof-of-work - PoW), и в качестве бонуса за решение задачи узлы получают вознаграждение в виде криптовалюты. В настоящее время также набирает популярность доказательство доли владения (Proof-of-Stake -PoS), где не требуется больших вычислительных мощностей; тот пользователь, у которого больше баланс счёта, с большей вероятностью сгенерирует новый блок.

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

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

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

логарифмирования. Это означает, что такие системы уязвимы к квантовому алгоритму Шора, и их использование несёт угрозу вскрытия в ближайшем будущем. В конце 2022 года была опубликована работа «Factoring integers with sublinear resources on a superconducting quantum processor», в которой предложен квантовый алгоритм, позволяющий вскрыть RSA-2048, используя всего 372 физических кубита, что говорит об острой необходимости перестраивать системы, используя постквантовые алгоритмы и протоколы.

В связи с вышеизложенным тема данного исследования является актуальной.

Целью данной работы является разработка методов использования электронной подписи в доверенных системах хранения данных.

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

1. Провести анализ схем распределённой подписи и схем разделения секрета, определить основные достоинства и недостатки.

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

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

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

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

1. Метод постквантовой пороговой подписи, основанной на математической задаче поиска изогений между эллиптическими кривыми.

2. Метод разделения и сборки секрета на основе интерполяционного многочлена Ньютона.

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

Научная новизна:

1. Разработан метод пороговой подписи на основе алгоритма CSI-FiSh со свойством быстрой сборки секрета. Отличительными особенностями та-

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

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

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

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

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

Диссертационное исследование было выполнено при поддержке следующих научно-исследовательских проектов:

1. НИР Университета ИТМО №718546: «Управление киберфизическими системами»;

2. НИР Университета ИТМО №619296: «Разработка методов создания и внедрения киберфизических систем»;

3. НИР Университета ИТМО №620164: «Методы искусственного интеллекта для киберфизических систем»;

4. НИР с компанией TOGA №77043: «Исследование моделей и методов многофакторной аутентификации»;

5. Федеральная программа академического лидерства Приоритет-2030: «Технология комплексирования математического и алгоритмического

базиса для решения задач информационной безопасности в сетях будущих поколений».

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

1. The 12th International Congress on Ultra Modern Telecommunications and Control Systems (ICUMT). Конференция проходила онлайн.

2. International Conference on Information Networking 2020 (ICOIN). Барселона, Испания.

3. IX, XI Конгресс Молодых Учёных Университета ИТМО. Санкт-Петербург, Россия.

4. Пятьдесят первая, пятьдесят вторая научная и учебно-методическая конференция Университета ИТМО. Санкт-Петербург, Россия.

Публикации. Основные результаты по теме диссертации изложены в 8 печатных изданиях, 6 из которых изданы в журналах, индексируемых Scopus и Web of Science [1—6], 2 изданы в журналах, рекомендованных ВАК [7; 8]. Получено свидетельство о государственной регистрации программ для ЭВМ.

Личный вклад. Разработка моделей и методов, представленных в настоящей диссертации, выполнена автором лично. Постановка цели и задач, обсуждение планов исследований и полученных результатов выполнены автором совместно с научным руководителем. В работе [7] вклад автора заключается в том, что автором была найдена проблема последовательной сборки секрета и предложен способ решения проблемы; совместно с Хуцаевой А.Ф., Иогансо-ном И.Д., Дакуо Ж.-М. Н. и Беззатеевым С.В. проводились многочисленные обсуждения предложенного решения, решение было программно реализовано и усовершенствовано. В остальных работах, выполненных в соавторстве с научным руководителем Беззатеевым С.В., Давыдову В.В. принадлежат соответствующие основные результаты; вклад научного руководителя заключался в постановке задачи и консультировании; также проводились многочисленные обсуждения полученных результатов.

Содержание диссертации

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

Первая глава посвящена построению улучшенной схемы пороговой подписи, устойчивой к атакам на квантовом компьютере. Для построения такой схемы за основу была выбрана математическая задача поиска изогений между эллиптическими кривыми. Были проанализированы алгоритм подписи CSI-FiSh (Бейленс и др., 2019), основанный на преобразовании Фиата-Шамира, его пороговый вариант (Де Фео, Мейер, 2020), и предложена улучшенная версия пороговой подписи, дающая выигрыш по времени на этапе подписи, а также предусматривающая механизм защиты от недобросовестного дилера.

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

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

Алгоритм Шора на квантовом компьютере решает две математические задачи, не решаемые за полиномиальное время на классическом компьютере: задачу факторизации (эквивалентная задаче нахождения корня по модулю составного числа) и задачу дискретного логарифмирования. Алгоритм Гровера на квантовом компьютере решает задачу поиска строки в списке, состоящем из п строк, за временную сложность 0(у/п).

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

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

В разделе 1.3 кратко описывается математический аппарат изогений.

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

Пусть К - конечное поле, Ех - эллиптическая кривая, заданная над К. Изогенией между двумя эллиптическими кривыми Ех и Е2 называется нетривиальный гомоморфизм

' : Ех ! Е2-'(Ое) = ОЕ2, (1)

где О - точка на бесконечности на кривых Ех и Ес1 соответственно.

Множество точек на кривой Е\(К) (К - алгебраическое замыкание поля К), отображающееся изогенией ' в точку Ое2 на кривой Е2, называется ядром изогении и обозначается как кег(').

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

Известно, что для суперсингулярной эллиптической кривой Е' кольцо эндоморфизмов EndFp (Е') над полем Fp изоморфно порядку мнимого квадратичного поля. Пусть О - порядок мнимого квадратичного поля, а также существу-

ет элемент ж 2 O, являющийся F^-эндоморфизмом Фробениуса на кривой E0. Обозначим Ellp(O,/K) как набор суперсингулярных эллиптических кривых E, заданных над конечным полем Fp с кольцом эндоморфизмов EndFp(E) = O.

Действием группы классов идеалов Cl(O) для порядка O на множество Ellp(O,n) является отображение:

Cl(O) х Ellp(O, ж) ! Ellp(O, ж),

([a],E)! E/a, (2)

Пусть генераторный идеал в группе классов идеалов обозначается как g, g 2 Cl(O), пусть a 2 Z, Eo,Ei 2 Ellp(O^) - эллиптические кривые. Вводится следующее обозначение

Ei = ga ? Eo , Ei = [a]Eo, (3)

где ? - операция группового действия.

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

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

1. Обратная задача группового действия (СЛ1Р)

Пусть задана кривая Е, Еп^Е) = О. Необходимо найти идеал а С О такой, что Е = а ? Е0.

2. Обратная задача многоцелевого группового действия (ЫТ-СЛ1Р) Пусть заданы кривые Е1,..., Е^, Еп^Е^ = ••• = Еп^Е^) = О. Необ-

ходимо найти идеал а С О такой, что Е,ь = a?Ej для г] 2 {0, ...,к},г = 3.

В разделе 1.4 предлагается построение нового варианта пороговой подписи, основанной на схеме СБЛИЗЬ.

В начале подробно описывается оригинальная схема подписи СБЛИЗЬ (Бейленс и др., 2019) и преобразование Фиата-Шамира, лежащее в основе данной схемы. Далее описывается пороговый вариант СБЛИЗЬ (де Фео, Мейер, 2020). В результате анализа порогового варианта подписи были выявлены две основные проблемы.

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

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

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

Для 10 пользователей схемы при пороге в 7 участников с параметрами безопасности алгоритма Б = 8, £ = 7 предложенная схема работает почти в 3,5 раза быстрее оригинальной.

Для решения проблемы компроментации дилера, когда он не забывает секрет, предлагается следующее решение. Пусть дилер генерирует набор секретных чисел {ах,а2, ..., а в-1}, считает тени для каждого из них с помощью схемы разделения секрета Шамира, а затем передаёт полученные тени sij каждому из участников соответственно. После этого системой выбирается случайный участник, который генерирует набор случайных значений соли

(заН^,эаН^, ..., эаН^-1} 2 , «делит» каждый элемент набора с помощью схемы разделения секрета Шамира, обновляет набор публичных ключей и отправляет каждому другому участнику Pj доли ва1Ц-, г 2 (1, ..., £ — 1}, ] 2 (1, ..., п}, где п - общее количество участников. Выбор случайного участника можно осуществлять с помощью специальных протоколов, например, схемы электронной лотереи Пэйе.

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

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

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

В разделе 2.1 подробно рассматриваются интерполяционные формулы Ньютона и Лагранжа.

Как правило, интерполяция - это метод поиска нового решения с использованием предопределённого набора результатов или значений функции. Пусть известен набор точек X = ((х0, х1, ..., хп)}, а также соответствующие им значения функций ^ = {(/(ж0),/(ж1), ..., /(хп)}. Одной из задач интерполяции является нахождение хотя бы приблизительного значения функции ](х^) для точки х^, не представленной в известном наборе X.

Формула Ньютона - это интерполяционный многочлен, использующийся для заданного набора точек. Пусть задано (п + 1) точек: ((х0,у0),... (xj,yj),..., (хп,уп)}. Значения по координате х называются интерполяционными точками, а значения по у - интерполяционными значениями.

Для интерполяции функции / значения интерполяции определяются как

Уз = /(X),Ч? = 0, (4)

Базисные многочлены Ньютона определяются следующим образом

¿-1

Пг(х) = Ц(Ж - Хз), (5)

3=1

где г = 1, ...,п и (х) = 1.

Интерполяционная формула Ньютона задаётся как

(6)

Рп(х) = ^ К • Пг(х) = Ко + К1(х - Хо) + К2(х - Х0)(Х - Х1) + ...

¿=0

... + Кп(х - Хо) ... (х - Хп-1), где Рп(х3-) = f (х3-), У? =0, ..., п; К может быть записана как

_ / [х1,...,хг] - / [х0 ,...,Х(г-1) ] К = -—-, (7)

хг х0

где /[х1,..., х^] - разделённая разность порядка п.

Формула Лагранжа традиционно представляется в виде многочлена, где для (п + 1) пар чисел (х0,у>), (хьу1),..., (хп,Уп), где хг = Х3 для всех г = ] существует единственный полином Ь(х) степени п, для которого Ь(х3-) = у3- для всех ^ = 0,...,п:

п

¿(х) = X У Мх), (8)

п

;х' = X У» ^»(х]

¿=0

п

где /¿(х) = ГГ ^ 3 - базисные полиномы со следующими свойствами:

1. deg/¿(х) = п;

2. /¿(х^) — 1;

3. /¿(х3-) = 0 если ^ = г.

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

В разделе 2.2 описаны схемы разделения секрета. Первые пороговые (t,n)-cxeMbi разделения секрета были опубликованы в 1979 году Шамиром и Блэкли, которые работали независимо друг от друга. Чуть позже, в 1982 году французский учёный Миньотт опубликовал схему разделения секрета, основанную на китайской теореме об остатках.

Схемы таких типов традиционно состоят из двух этапов: раздача долей и сборка секрета. Пусть S - секрет, который нужно разделить между n участниками, выдав каждому одну долю секрета из набора S = {si, , ..., sn}. Необходимо соблюдение двух условий:

1. S может быть легко вычислен, если известно t и более долей секрета;

2. S не может быть получен, если известно (t — 1) и менее долей.

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

Далее в диссертационной работе рассмотрены схемы Миньотта и Шами-ра. Схема Шамира состоит из двух этапов: разделение секрета и сборка секрета.

Разделение секрета

Пусть задано простое число p > S, которое известно всем участникам обмена. Строится полином из кольца Fp[x] степени (t — 1) со случайными коэффициентами, кроме a0, который задаётся равным S:

L(x) = at—1 • xt—1 + at—2 • xt—2 + ••• + a1 • x + S mod p. (9)

Тени секрета могут быть вычислены следующим образом:

Уо = L(1),

yi = L(2),

... (10) Уп—i = L(n).

В результате выполнения фазы каждый участник получает свою тень секрета, а также число, которое использовалось при вычислении значения тени

(параметр ж), то есть пару значений (ж^у). Сборка секрета

Для восстановления секрета используется интерполяционная формула Лагранжа. После фазы раздачи имеются t долей - пар чисел {(-о,Уо), (-i,Vi), (xt-i,yt-i)}, где жг = -j для всех i = j, а также

единственный полином L(-) степени (t — 1), для которого L(-j) = у для всех j = 0, ...,t — 1. Для вычисления (сборки) исходного секрета используются следующие уравнения:

t—i

S = L(0) = X Vi • li(0) mod p

¿=0

t—i

li(0) = (—1)t—i П mod p (11)

X i j

j=0,j=i

В разделе 2.3 предлагается метод разделения секрета с использованием полинома Ньютона вместо полинома Лагранжа на этапе сборки секрета.

Фаза разделения секрета ничем не отличается от исходной. После фазы разделения имеются t долей и единственный полином L(-) степени (t — 1). Для вычисления исходного секрета используются следующие уравнения:

t—i

S = L(0) = Ко + X Kini(0)

i i=i (12) ni(0) = П(—-j)

j =о

Далее в разделе показан пример разделения и сборки секрета на основе многочленов Лагранжа и Ньютона.

В разделе 2.4 анализируется предлагаемое решение и проводится его сравнение со схемой Шамира.

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Давыдов Вадим Валерьевич, 2023 год

Литература

1. Goldfeder S. et al. Securing bitcoin wallets via threshold signatures. 2014.

2. Stathakopoulou C., Cachin C. Threshold signatures for blockchain systems //Swiss Federal Institute of Technology. 2017. V. 30. P. 1.

3. Johnson D., Menezes A., Vanstone S. The elliptic curve digital signature algorithm (ECDSA) // International journal of information security. 2001. V. 1, № 1. P. 36-63.

4. Zhang F., Safavi-Naini R., Susilo W. An efficient signature scheme from bilinear pairings and its applications // International workshop on public key cryptography. Springer, Berlin, Heidelberg, 2004. P.277-290.

5. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM review. 1999. V. 41, № 2. P. 303-332.

6. Ростовцев А. Г., Маховенко Е. Б. Криптосистема на категории изогенных эллиптических кривых // Проблемы информационной безопасности. Компьютерные системы. 2002. № 3. С. 74.

7. Jao D. et al. SIKE: Supersingular isogeny key encapsulation // HAL. 2017.

8. Computer Security Division I. T. L. Post-Quantum Cryptography | CSRC | CSRC // CSRC | NIST [Электронный ресурс]. URL: https://csrc.nist.gov/projects/post-quantum-cryptography (accessed: 04.12.2022).

9. Castryck W., Decru T. An efficient key recovery attack on SIDH (preliminary version) // Cryp-tology ePrint Archive. 2022.

10. Is SIKE broken yet? // Is SIKE broken yet? [Электронный ресурс]. URL: https://issikebrokenyet.github.io/ (accessed: 04.12.2022).

11. De Feo L., Galbraith S. D. SeaSign: compact isogeny signatures from class group actions // Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2019. P. 759-789.

12. Beullens W., Kleinjung T., Vercauteren F. CSI-FiSh: efficient isogeny based signatures through class group computations // International Conference on the Theory and Application of Cryptol-ogy and Information Security. Springer, Cham, 2019. P. 227-247.

13. De Feo L. et al. SQISign: compact post-quantum signatures from quaternions and isogenies // International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2020. P. 64-93

14. Castryck W. et al. CSIDH: an efficient post-quantum commutative group action // International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2018. P. 395-427.

15. De Feo L., Meyer M. Threshold schemes from isogeny assumptions // IACR International Conference on Public-Key Cryptography. Springer, Cham, 2020. P. 187-212.

16. Cozzo D., Smart N. P. Sashimi: cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol // International Conference on Post-Quantum Cryptography. Springer, Cham, 2020. P. 169-186.

17. Vélu J. Isogénies entre courbes elliptiques // CR Acad. Sci. Paris, Séries A. 1971. V. 273. P. 305-347.

18. Silvermann J. H. The arithmetic of elliptic curves // Graduate Texts in Mathematics. 1986. V. 106.

19. Alamati N. et al. Cryptographic group actions and applications // International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2020. P. 411439.

20. Sotakova J. Elliptic curves, isogenies, and endomorphism rings. P. 17.

21. Stolbunov A. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves // Advances in Mathematics of Communications. 2010. V. 4, № 2. P. 215.

22. Couveignes J. M. Hard homogeneous spaces // Cryptology ePrint Archive. 2006.

23. Shamir A. How to share a secret // Communications of the ACM. 1979. V. 22, № 11. P. 612-613.

24. Paillier P. Public-key cryptosystems based on composite degree residuosity classes // International conference on the theory and applications of cryptographic techniques. Springer, Berlin, Heidelberg, 1999. P. 223-238.

25. Paverd A., Martin A., Brown I. Modelling and automatically analysing privacy properties for honest-but-curious adversaries // Tech. Rep. 2014.

Давыдов Вадим Валерьевич

аспирант 4 года обучения факультета безопасности информационных технологий, преподаватель, Университет ИТМО (НИУ ИТМО,197101, Санкт-Петербург, Кронверкский пр., д. 49, лит. А.), e-mail: vvdavydov@itmo. ru, ORCID ID: 0000-0002-5544-2434.

Хуцаева Алтана Феликсовна

инженер, магистрант 2 курса факультета безопасности информационных технологий, Университет ИТМО (НИУ ИТМО, 197101, Санкт-Петербург, Кронверкский проспект, д. 49, лит. А.), e-mail: [e-mail], ORCID ID: 0000-0001-5494-7142.

Иогансон Иван Дмитриевич

инженер, аспирант факультета безопасности информационных технологий, Университет ИТМО (НИУ ИТМО, 197101, Санкт-Петербург, Кронверкский проспект, д.49, литер А.), e-mail: [e-mail], ORCID ID: 0000-0002-0856-2249.

Дакуо Жан-Мишель Никодэмович

инженер, аспирант факультета безопасности информационных технологий, Университет ИТМО (НИУ ИТМО, 197101, Санкт-Петербург, Кронверкский проспект, д.49, литер А.), e-mail: [e-mail], ORCID ID: 0000-0002-4084-8829.

Беззатеев Сергей Валентинович

заведующий кафедрой информационной безопасности, Санкт-Петербургский государственный университет аэрокосмического приборостроения (190000, Санкт-Петербург, ул. Большая Морская, д. 67, лит. А);

директор лаборатории криптографических методов защиты информации, Университет ИТМО (НИУ ИТМО, 197101, Санкт-Петербург, Кронверкский проспект, д.49, литер А.), e-mail: [e-mail], ORCID ID: 0000-0002-0924-6221.

Авторы прочитали и одобрили окончательный вариант рукописи. Авторы заявляют об отсутствии конфликта интересов.

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

90

B. B. ,3,aBbigoB, A. Хуцаева, H. HoraH50H, ®.-M. H. AaKyo, C. B. Ee33aTeeB

Improved Threshold Signature Scheme CSI-FiSh with Fast Secret Recovery

Vadim V. Davydov1, Altana F. Khutsaeva1, Ivan D. Ioganson1, Zhan-Mishel N. Dakuo1,

Sergey V. Bezzateev1,2

1 ITMO University (ITMO) 2 Saint Petersburg State University of Aerospace Instrumentation (SUAI)

Abstract: The paper presents an improved version of the CSI-FiSh threshold signature offered by L. De Feo and M. Meyer in 2020. In the proposed scheme, public and private keys are additionally updated avoiding the case of compromising a dealer. It is also proposed to eliminate the sequential information transfer between participants when signing and replace it with an assembly with the participation of the dealer. Experimental results showing the effectiveness of the proposed approach and the assessment of the resulting scheme safety are presented.

Keywords: isogeny-based cryptography, post-quantum cryptography, digital signature, threshold signature, secret sharing schemes.

For citation: Davydov V. V., Khutsaeva A. F., Ioganson I. D., Dakuo Z.-M. N., Bezzateev S. V. Improved threshold signature scheme CSI-Fish with fast secret recovery (in Russian). Vestnik SibGUTI, 2023, vol. 17, no. 1. pp. 76-91. https://doi.org/10.55648/1998-6920-2023-17-1-76-91.

Content is available under the license © Davydov V. V., Khutsaeva A. F.,

Creative Commons Attribution 4.0 Ioganson I. D., Dakuo Z.-M. N.,

License Bezzateev S. V., 2023

The article was submitted: 05.12.2022;

revised version: 25.01.2023; accepted for publication 04.02.2023. References

1. Goldfeder S. et al. Securing bitcoin wallets via threshold signatures. 2014.

2. Stathakopoulou C., Cachin C. Threshold signatures for blockchain systems. Swiss Federal Institute of Technology, 2017, vol. 30, pp. 1.

3. Johnson D., Menezes A., Vanstone S. The elliptic curve digital signature algorithm (ECDSA). International journal of information security, 2001, vol. 1, no. 1, pp. 36-63.

4. Zhang F., Safavi-Naini R., Susilo W. An efficient signature scheme from bilinear pairings and its applications. International workshop on public key cryptography, Springer, Berlin, Heidelberg, 2004, pp. 277290.

5. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 1999, vol. 41, no. 2, pp. 303-332.

6. Rostovcev A. G., Mahovenko E. B. Kriptosistema na kategorii izogennyh ellipticheskih krivyh [Cryptosystem on the category of isogenic elliptic curves] Problemy informacionnoj bezopasnosti. Komp'yuternye sistemy, Saint-Petersburg, 2002, no. 3, p. 74.

7. Jao D. et al. SIKE: Supersingular isogeny key encapsulation. HAL, 2017, vol. 2017.

8. Computer Security Division I. T. L. Post-Quantum Cryptography | CSRC | CSRC. CSRC | NIST, [Research and analysis of computer network monitoring tools and methods], available at: https://csrc.nist.gov/projects/post-quantum-cryptography (accessed: 04.12.2022).

9. Castryck W., Decru T. An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, 2022.

10. Is SIKE broken yet? Is SIKE broken yet? [Research and analysis of computer network monitoring tools and methods], available at: https://issikebrokenyet.github.io/ (accessed: 04.12.2022).

11. De Feo L., Galbraith S. D. SeaSign: compact isogeny signatures from class group actions. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Cham, 2019, pp. 759-789.

12. Beullens W., Kleinjung T., Vercauteren F. CSI-FiSh: efficient isogeny based signatures through class group computations. International Conference on the Theory and Application of Cryptology and Information Security, Springer, Cham, 2019, pp. 227-247.

13. De Feo L. et al. SQISign: compact post-quantum signatures from quaternions and isogenies. International Conference on the Theory and Application of Cryptology and Information Security, Springer, Cham, 2020, pp.64-93

14. Castryck W. et al. CSIDH: an efficient post-quantum commutative group action. International Conference on the Theory and Application of Cryptology and Information Security, Springer, Cham, 2018, pp. 395-427.

15. De Feo L., Meyer M. Threshold schemes from isogeny assumptions. IACR International Conference on Public-Key Cryptography, Springer, Cham, 2020, pp. 187-212.

16. Cozzo D., Smart N. P. Sashimi: cutting up CSI-FiSh secret keys to produce an actively secure distributed signing protocol. International Conference on Post-Quantum Cryptography, Springer, Cham, 2020, pp. 169-186.

17. Vélu J. Isogénies entre courbes elliptiques. CR Acad. Sci. Paris, Séries A, 1971, vol. 273, pp. 305-347.

18. Silvermann J. H. The arithmetic of elliptic curves. Graduate Texts in Mathematics, 1986, vol. 106.

19. Alamati N. et al. Cryptographic group actions and applications. International Conference on the Theory and Application of Cryptology and Information Security, Springer, Cham, 2020, pp. 411-439.

20. Sotakova J. Elliptic curves, isogenies, and endomorphism rings. p. 17.

21. Stolbunov A. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, vol. 4, no. 2, p. 215.

22. Couveignes J. M. Hard homogeneous spaces. Cryptology ePrint Archive, 2006.

23. Shamir A. How to share a secret. Communications of the ACM, 1979, vol. 22, no. 11, pp. 612-613.

24. Paillier P. Public-key cryptosystems based on composite degree residuosity classes. International conference on the theory and applications of cryptographic techniques, Springer, Berlin, Heidelberg, 1999, pp. 223-238.

25. Paverd A., Martin A., Brown I. Modelling and automatically analysing privacy properties for honest-but-curious adversaries. Tech. Rep., 2014.

Vadim V. Davydov

4th year PhD student of the Department of Information Security, lecturer, ITMO University (ITMO, Kron-verksky Pr. 49, bldg. A, St. Petersburg, 197101, Russia), e-mail: [e-mail], ORCID ID: 00000002-5544-243.

Altana F. Khutsaeva

Engineer, 2nd year master's degree student of the Department of Information Security, ITMO University (ITMO, Kronverksky Pr. 49, bldg. A, St. Petersburg, 197101, Russia), e-mail: [e-mail], ORCID ID: 0000-0001-5494-7142.

Ivan D. Ioganson

Engineer, PhD student of the Department of Information Security, ITMO University (ITMO, Kronverksky Pr. 49, bldg. A, St. Petersburg, 197101, Russia), e-mail: [e-mail], ORCID ID: 0000-00020856-2249.

Zhan-Mishel N. Dakuo

Engineer, PhD student of the Department of Information Security, ITMO University (ITMO, Kronverksky Pr. 49, bldg. A, St. Petersburg, 197101, Russia), e-mail: [e-mail], ORCID ID: 0000-0002-40848829.

Sergey V. Bezzateev

Head of Information Security Department, Saint-Petersburg State University of Aerospace Instrumentation (190000, Saint-Petersburg, Bolshaya Morskaya str. 67, lit. A); Director of Cryptographic Methods of Information Security Laboratory, ITMO University (197101, Saint-Petersburg, Kronverksky prospekt 49, lit. A), e-mail: [e-mail], ORCID ID: 0000-0002-0924-6221.

УДК 004.057.4 DOI: 10.55648/1998-6920-2022-16-2-33-39

Криптографический протокол поиска места встречи участников со свойством конфиденциальности

И. Д. Иогансон, А. А. Голованов, Ж.-М. Н. Дакуо, В. В. Давыдов1

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

Ключевые слова: криптографический протокол, свойство конфиденциальности, протоколы конфиденциального вычисления.

1. Введение

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

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

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

В данной работе уделено внимание протоколам, которые позволяют вычислить сумму секретных значений нескольких пользователей. В работе [4] приведён пример простейшего варианта такого протокола. Он имеет следующую структуру:

1. Пользователям присваиваются номера от 1 до k .

2. Пользователь 1 генерирует случайное число т0 .

3. Далее, начиная с пользователя 1, каждый пользователь / получает значение — от пользователя / — 1 (или в случае пользователя 1 это будет просто сгенерированное им значение

1 Работа выполнена при поддержке программы «Приоритет 2030».

Wq ) и отправляет пользователю i +1 (пользователь k отправит свое значение пользователю 1) значение mi = mi_i + Xi, где x^ - входное значение пользователя i.

4. В конце пользователь 1 вычисляет значение mk _ Wq , равное искомой сумме, и отправляет его остальным пользователям.

В статье [5] описан так называемый «k-Secure Sum Protocol». Этот протокол для n пользователей выглядит следующим образом:

1. Пусть k - целое число, обозначающие параметр безопасности.

2. Пусть пользователи пронумерованы от 0 до n _1.

3. Пусть Di - входное значение, принадлежащее пользователю i.

к _1

4. Разобьём Di на к сегментов D;q,Di(k_1) таким образом, что Dt = ^ Dj .

5. Пусть Sqq = 0.

6. Для j от 0 до к _1:

а. Для i от 0 до n _1:

i. Пользователь i посылает пользователю (( + 1)modn:

S(i+1)j = Sij + Dij . b S0(j+1)= Snj .

7. Пользователь 0 публикует значение Sq£ .

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

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

каждого пользователя выражено числом Xj el, где / е [l...А'}, которое является координатой в некоторой системе координат. Требуется найти координату встречи у, наиболее удобную для всех участников, что в данной работе понимается как среднее арифметическое значение:

у = Й=£1 (1) к '

При этом предлагаемый протокол обладает следующими свойствами:

1. Значение xi не раскрывается пользователем Pi ни на одном из этапов.

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

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

2. Описание протокола

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

1. Инициализация.

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

допустимое количество значащих цифр после запятой. Далее каждый пользователь формирует обязательство, подобное тому, что использовал П. Фельдман в своей проверяемой схеме разделения секрета [6], для своего значения х^: С\ = х^ ■ G, где О - генераторная точка на эллиптической кривой (ЭК) Е над полем Fq, где д - простое. ЭК Е и точка О известны всем

пользователям. Обязательства С .--Ск публикуются в свободном доступе для каждого пользователя.

Рис. 1. Общий вид схемы

2. Первый круг.

Каждый пользователь выбирает случайное значение 5г- е^ Ъ. Далее начинается передача сообщений. Обозначение Ра ^ Р^ : обозначает, что пользователь Ра передаёт информацию пользователю РЬ, после двоеточия описана передаваемая информация. Также будем считать,

что Рк+1 = Р1.

Передаваемая информация вычисляется по правилу:

р ^ р+1: ш1, / = ш1, / -1 + х1 + Ъ,

где ш10 = 0.

3. Второй круг. Пусть

ш2,0 = ш1,к =Е?=1(х + Ъ )■

Тогда правила вычисления передаваемой информации на данном круге:

р ^ р+1 : ш2,/ = ш2л -1 " " х/.

(2)

(3)

4. Третий круг.

Пусть

т3,0 = т2, к .

Тогда правила вычисления передаваемой информации на данном круге:

Ц ^ Ц+1:т3, / = т3, / -1 + ^ •

(6)

Если в конце протокола пользователь Ц получил значение тз к • Если тз, к = 0, то протокол считается корректно выполненным, и Ц рассылает сообщение о корректном окончании протокола. Иначе - во время работы протокола возникла ошибка, и Ц рассылает сообщение о том, что протокол окончился с ошибкой.

5. Завершение.

Каждый пользователь Ц обладает набором значений {т^-,т2 ',тз г-}, полученных им на кругах 1, 2 и 3 соответственно. Далее он вычисляет:

Данное значение и является координатой сбора.

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

ЕС =(к■ У)■ G • (8)

'=1

3. Доказательства корректности и безопасности 3.1. Доказательство корректности

На конце 1-го и 2-го кругов пользователь Ц получает значения:

У =

т1,' + т2,' + т3,' к

(7)

т1, к = Е(( + sj);

(9)

j=1

к

т2,к = -Е] =1^' •

(10)

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

(11)

т2,= Е^=1 ( + sj ) -Е|=! ( + ) = £)=+! ( + ^ ) -Е)=^ ; т3 =-Е7=& + Е|=^ =-Ек=+ ^ •

(12)

Тогда

У = 1 (, г + т2,г + т3,г ) =

1 ■ 1 (14)

= £(Гу=1( + ^ ) + Ък]=г +1( + ^ =Ъ— Е/=| +1*; ) = 1к=1х; .

3.2. Доказательство безопасности

Каждый пользователь г знает следующий набор значений: [к, хг-, $1, тц, т2/,т3г-, у}. Обозначим:

Ха = Г /=1х]' , хь = Г к =1х] ;

-к=г ]

Хг —1 „ х-'к „

/=1*/ , =Г /=^.

(15)

Тогда сообщения т1 т2 т3 ^:

т1 г = ха + 5а ; т2г = хЬ + ^ — *а; т3 г =—.

Система из четырёх уравнений с четырьмя переменными ха, хь, , :

"ха + 8а = т1 г хЬ + ^ — 8а = т2 г

Ь = т3 г „ ха + хЬ = У * к

является линейно зависимой, так как сумма первых трех уравнений равна четвертому:

(16)

(17)

ха + 8а = т1г хЬ +Ь — 8а = т2г —8Ь = т3 г

(18)

ха + хЬ = т1 + т21 + т31 = У * к Следовательно, данная система не имеет единого решения относительно этих переменных. Таким образом, из имеющегося набора значений пользователь не может получить информацию об хк других пользователей (кроме у).

Применяемая схема обязательств основана на проблеме дискретного логарифмирования [7] и не позволяет злоумышленнику раскрыть значение секрета. Также в представленной схеме обязательств отсутствует возможность подмены значения секрета создателем этого обязательства.

4. Оценки протокола 4.1. Обобщение

Данный протокол в базовом варианте работает в 1 -мерном пространстве, однако его очевидным образом можно обобщить на п-мерное пространство, где координаты каждого пользователя г задаются п-мерным вектором X^ =(хг1,х^,...,х1п). В таком случае необходимо

просто произвести данный протокол для каждой из координат по отдельности и на выходе получить у = (yl,y2,., Уп ) •

4.2. Ограничения

Данный протокол проводится для к участников. Однако при к = 2 оба пользователя очевидным образом, зная у = Х1 +Х2 и свой X', могут найти Х3-' другого пользователя. Поэтому

число к участников протокола всегда должно быть больше 2^

Также в случае, если у пользователя ' были скомпрометированы оба ключа К( _ 1)) и К1 ((+1), то злоумышленник, перехватив сообщения, которые пользователь принимает

и посылает в процессе действия протокола, сможет однозначно установить значение X'. Аналогичное действие могут совершить пользователи ' + 1 и ' -1, если сговорятся и поделятся друг с другом сообщениями, которые они посылали и принимали от пользователя ' •

Литература

1. Yao A. C. Protocols for secure computations // 23rd IEEE Annual symposium on foundations of computer science (SFCS), 1982. P. 160-164.

2. Dugan T., Zou X. A survey of secure multiparty computation protocols for privacy preserving genetic tests // 2016 IEEE First International Conference on Connected Health: Applications, Systems and Engineering Technologies (CHASE), 2016. P. 173-182.

3. Lapets A. et al. Secure MPC for analytics as a web application // 2016 IEEE Cybersecurity Development (SecDev), 2016. P. 73-74.

4. Clifton C. et al. Tools for privacy preserving distributed data mining // ACM Sigkdd Explorations Newsletter. 2002. V. 4, №. 2. P. 28-34.

5. Sheikh R., Kumar B., Mishra D. K. Privacy preserving k secure sum protocol // arXiv preprint arXiv:0912.0956. 2009.

6. Feldman P. A practical scheme for non-interactive verifiable secret sharing // 28th IEEE Annual Symposium on Foundations of Computer Science (SFCS), 1987. P. 427-438.

7. Silverman J. H., Pipher J., Hoffstein J. An introduction to mathematical cryptography. Springer New York, 2008.

Статья поступила в редакцию 25.04.2022; переработанный вариант - 01.05.2022.

Иогансон Иван Дмитриевич

инженер факультета безопасности информационных технологий Университета ИТМО (197101, Санкт-Петербург, Кронверкский просп., д. 49, литер А), e-mail: ivan.iogan-

son@yandex. ru.

Голованов Андрей Андреевич

инженер факультета безопасности информационных технологий Университета ИТМО, e-mail: agolovanov2403@gmail. com.

Дакуо Жан-Мишель Никодэмович

инженер факультета безопасности информационных технологий Университета ИТМО, e-mail: [e-mail]. .

Давыдов Вадим Валерьевич

преподаватель факультета безопасности информационных технологий Университета ИТМО, e-mail: [e-mail].

Cryptographic protocol for finding the meeting place of participants with confidentiality property Ivan D.Ioganson

Engineer, ITMO University (St. Petersburg, Russia), ivan. ioganson@yandex. ru. Andrei A. Golovanov

Engineer, ITMO University (St. Petersburg, Russia), agolovanov2403@gmail. com. Zhan-Mishel N. Dakuo

Engineer, ITMO University (St. Petersburg, Russia), jeandakuo@mail. ru. Vadim V. Davydov

Lecturer, ITMO University (St. Petersburg, Russia), vvdavydov@itmo .ru.

In this paper a new cryptographic protocol for finding the meeting place of participants is proposed. This protocol allows several participants to choose the meeting place closest to their locations not revealing the coordinates of each of the participants. The protocol also allows to detect an error occurring during the transfer of information between participants. The correctness and security of the used approach are proved, and the main advantages and disadvantages are determined.

Keywords: cryptographic protocol, confidentiality property, secure multi-party computation. References

1. Yao A. C. Protocols for secure computations. 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 1982, pp. 160-164. DOI: 10.1109/SFCS.1982.38.

2. Dugan T., Zou X. A survey of secure multiparty computation protocols for privacy preserving genetic tests. 2016 IEEE First International Conference on Connected Health: Applications, Systems and Engineering Technologies (CHASE), 2016, pp. 173-182. DOI: 10.1109/CHASE.2016.71.

3. Lapets A., Volgushev N., Bestavros A., Jansen F. and Varia M. Secure MPC for analytics as a web application. 2016 IEEE Cybersecurity Development (SecDev), 2016, pp. 73-74. DOI: 10.1109/SecDev.2016.027.

4. Clifton C., Kantarcioglu M., Jaideep V., Lin X. and Zhu M. Y. Tools for privacy preserving distributed data mining. ACMSIGKDD Explorations, 2003, vol. 4, pp. 28-34.

5. Sheikh R., Kumar B., Mishra D. K. Privacy preserving k secure sum protocol. International Journal of Computer Science and Information Security, 2009, vol. 6.

6. Feldman P. A practical scheme for non-interactive verifiable secret sharing. 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), 1987, pp. 427-438. DOI: 10.1109/SFCS.1987.4.

7. Silverman J. H., Pipher J., Hoffstein J. An introduction to mathematical cryptography, Springer New York, 2008. vol 1.

УНИВЕРСИТЕТ итмо

НАУЧНО-ТЕХНИЧЕСКИЙ ВЕСТНИК ИНФОРМАЦИОННЫХ ТЕХНОЛОГИИ, МЕХАНИКИ И ОПТИКИ март-апрель 2022 Том 22 № 2 http://ntv.ifmo.ru/

SCIENTIFIC AND TECHNICAL JOURNAL OF INFORMATION TECHNOLOGIES, MECHANICS AND OPTICS March-April 2022 Vol. 22 No 2 http://ntv.ifmo.ru/en/

ISSN 2226-1494 (print) ISSN 2500-0373 (online)

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

doi: 10.17586/2226-1494-2022-22-2-324-331 УДК 004.056.55

Современные вариации криптосистем Мак-Элиса и Нидеррайтера

Вадим Валерьевич Давыдов1®, Владислав Владиславович Беляев2, Елизар Филаретович Кустов3, Антон Георгиевич Леевик4, Сергей Валентинович Беззатеев5

1,2,3,4,5 Университет ИТМО, Санкт-Петербург, 197101, Российская Федерация

5 Санкт-Петербургский государственный университет аэрокосмического приборостроения, Санкт-Петербург, 190000, Российская Федерация

1 [e-mail]и, https://orcid.org/0000-0002-5544-2434

2 [e-mail], https://orcid.org/0000-0002-1067-7483

3 [e-mail], https://orcid.org/0000-0002-0191-1178

4 [e-mail], https://orcid.org/0000-0003-1823-7877

5 [e-mail], https://orcid.org/0000-0002-0924-6221

Аннотация

Предмет исследования. Исследованы классические криптосистемы, предложенные Робертом Мак-Элисом в 1978 году и Гарольдом Нидеррайтером в 1986 году и их современные вариации. Метод. Выполнен детальный обзор пяти кодовых криптосистем с открытым ключом. Основные результаты. Показано, что некоторые из современных интерпретаций классических систем Мак-Элиса и Нидеррайтера имеют значительные недостатки. Установлено, что допущен ряд неточностей в описании криптосистемы XGRS на расширенных кодах Рида-Соломона, которая не обеспечивает заявленного уровня безопасности к атаке по информационным совокупностям. Продемонстрировано, что время генерации ключей и время расшифрования в современных кодовых криптосистемах достаточно велико, а открытый и секретный ключи занимают большой объем памяти. Практическая значимость. Выявленные неточности в рассмотренных схемах могут быть учтены при их улучшении и коррекции, а также при построении более точной оценки их уровня безопасности и эффективности. Представленные в работе кодовые криптосистемы могут рассматриваться как стандарты постквантовой криптографии и использоваться для защиты данных после появления мощного квантового компьютера. Ключевые слова

постквантовая криптография, криптосистема Мак-Элиса, криптосистема Нидеррайтера, двоичные коды Гоппы,

расширенные коды Рида-Соломона

Благодарности

Работа выполнена в рамках НИР № 620164 Университета ИТМО. Работа частично финансировалась Федеральной программой академического лидерства Приоритет 2030. Выражается благодарность Жан-Мишелю Дакуо за помощь в программной реализации.

Ссылка для цитирования: Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В. Современные вариации криптосистем Мак-Элиса и Нидеррайтера // Научно-технический вестник информационных технологий, механики и оптики. 2022. Т. 22, № 2. С. 324-331. doi: 10.17586/2226-1494-2022-22-2-324-331

Modern variations of McEliece and Niederreiter cryptosystems Vadim V. Davydov1®, Vladislav V. Beliaev2, Elizar F. Kustov3, Anton G. Leevik4,

Sergey V. Bezzateev5

1,2,3,4,5 ITMO University, Saint Petersburg, 197101, Russian Federation

5 Saint Petersburg State University of Aerospace Instrumentation, Saint Petersburg, 190000, Russian Federation

1 [e-mail], https://orcid.org/0000-0002-5544-2434

2 [e-mail], https://orcid.org/0000-0002-1067-7483

3 [e-mail], https://orcid.org/0000-0002-0191-1178

4 [e-mail], https://orcid.org/0000-0003-1823-7877

5 [e-mail], https://orcid.org/0000-0002-0924-6221

© Давыдов В.В., Беляев В.В., Кустов Е.Ф., Леевик А.Г., Беззатеев С.В., 2022

Abstract

Classical cryptosystems proposed by Robert McEliece (1978) and Harold Niederreiter (1986) and their modern variations are studied. A detailed review of five code-based public key cryptosystems has been presented. It is shown that some of the modern interpretations of the classical McEliece and Niederreiter cryptosystems have significant issues. In particular, it has been established that the XGRS cryptosystem based on extended Reed-Solomon codes does not provide the declared level of security against the information set decoding attack, and also has a number of inaccuracies. It is shown that the time of key generation and decryption in modern cryptosystems is quite large, and the public and private keys take up a large amount of memory. The inaccuracies of the considered schemes revealed in this work can be used to improve and adjust the systems, as well as to build a more accurate assessment of their security level and efficiency. The presented cryptosystems can be considered as standards for post-quantum cryptography and can be used to protect data after development of powerful quantum computers. Keywords

post-quantum cryptography, McEliece cryptosystem, Niederreiter cryptosystem, binary Goppa codes, generalized

Reed-Solomon codes

Aknowledgements

The work is made as a part of research work no. 620164 at ITMO University. This project has received financial support from the Priority 2030 Federal Academic Leadership Program. We thank Jean-Michelle Dakuo for his help in programming implementation.

For citation: Davydov V.V., Beliaev V.V., Kustov E.F., Leevik A.G., Bezzateev S.V. Modern variations of McEliece and Niederreiter cryptosystems. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2022, vol. 22, no. 2, pp. 324-331 (in Russian). doi: 10.17586/2226-1494-2022-22-2-324-331

Введение

В настоящее время ведется активная разработка систем постквантовой криптографии. Это связано с появлением квантового компьютера и изобретением Питером Шором квантового алгоритма [1], позволяющего решать задачи факторизации и дискретного логарифмирования за полиномиальное время. Одним из разделов постквантовой криптографии в целом является криптография, основанная на кодах, исправляющих ошибки. Впервые такая система была построена Робертом Мак-Элисом в 1978 году [2] на основе нового класса двоичных кодов, предложенных В.Д. Гоппой в 1971 году [3]. Через 8 лет, в 1986 году, Гарольд Нидеррайтер [4] предложил одноименную криптосистему, построенную на обобщенных кодах Рида-Соломона [5]. В 1992 году В.М. Сидельников и С.О. Шестаков [6] опубликовали атаку на криптосистему Нидеррайтера, приводящую к вскрытию данной системы.

Впоследствии исследователи занимались разработкой различных модификаций схем, использующих помехоустойчивые коды. Сегодня также продолжаются исследования, связанные с поисками улучшений в оригинальных системах Мак-Элиса и Нидеррайтера. Основные идеи состоят в снятии ограничения на вес вектора ошибки, использование кодов, отличных от кодов Гоппы, а также увеличение стойкости системы к различным атакам, в частности к атаке по информационным совокупностям («information set decoding») [7].

В последних опубликованных работах описаны новые криптосистемы, основанные на оригинальных идеях Мак-Элиса и Нидеррайтера, однако все они были успешно вскрыты. В 1994 году В.М. Сидельниковым была предложена криптосистема, основанная на кодах Рида-Маллера [8], однако в 2007 году был представлен ее криптоанализ, показывающий вскрытие системы за полиномиальное время [9]. В 1995 году представлена криптосистема на кодах ранговой метрики Э.М. Габидулина [10], которая была взломана

в 2008 году в работе [11]. В 2007 году предложена криптосистема на кодах с малой плотностью проверок (Low-Density Parity-Check, LDPC-кодах) [12], а в 2008 году в [13] — взлом системы. Использование ал-гебро-геометрических кодов также оказалось ненадежным [14, 15]. Попытки модифицировать криптосистему Мак-Элиса с тем, чтобы сделать ее более стойкой к различным атакам, также не увенчались успехом [16, 17].

Из представленного обзора видно, что оригинальные идеи Мак-Элиса и Нидеррайтера на сегодняшний день являются наиболее актуальными, а код, который до сих пор оказался устойчивым к различного вида атакам, — двоичный код Гоппы [18].

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

Рассмотрим три новые криптосистемы, на примере которых продемонстрированы существующие подходы и актуальное состояние постквантовой криптографии, использующей помехоустойчивые коды. Криптосистема «Classic McEliece» [19] была предложена международной группой авторов и приняла участие в конкурсе NIST (National Institute of Standards and Technology) на включение в стандарт постквантовой криптографии.

В схеме XGRS (extended Generalized ReedSolomon), опубликованной в 2021 году [20], использованы расширенные коды Рида-Соломона [21]. По мнению авторов, данная схема устойчива к атакам Сидельникова-Шестакова и к атаке по информационным совокупностям. В настоящей работе выполнен подробный анализ безопасности и эффективности схемы XGRS. Впервые продемонстрирована ее неустойчивость к атаке по информационным совокупностям и доказано, что уровень ее безопасности к данной атаке не соответствует заявленному авторами оригинальной работы.

На примере схемы IKKR (Ivanov-Kabatiansky-Krouk-Rumenko), предложенной в [22] и основанной на результатах работы [23], продемонстрирована неэффективность идеи увеличения маскирующего векто-

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

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

Классические криптосистемы Мак-Элиса и Нидеррайтера

В 1978 году в работе [2] была предложена Робертом Мак-Элисом криптосистема, где в качестве кодов, исправляющих ошибки, выбраны двоичные коды Гоппы [3]. Также Гарольд Нидеррайтер в 1984 году в работе [6] предложил использовать обобщенные коды Рида-Соломона.

Данные криптосистемы являются классическими, так как впервые для шифрования были использованы идеи применения NP-полной задачи синдромного декодирования, сложность которой была доказана в работе [23]. Несмотря на то, что работа Нидеррайтера вышла через 8 лет после публикации Мак-Элиса, в ней использована более простая идея — математическая проблема синдромного декодирования случайного кода. Основным отличием криптосистем является случайность шифрования. В криптосистеме Мак-Элиса шифрование зависит от вектора ошибки, который выбирается случайным образом, в то время как в криптосистеме Нидеррайтера целенаправленно выбирается сообщение с определенными ограничениями.

Атакующий, стремясь взломать криптосистему Мак-Элиса или Нидеррайтера, должен решить NP-полную задачу синдромного декодирования [24], найти ближайшее кодовое слово линейного кода C к вектору в окружении пространства C, зная, что такое слово единственно. Злоумышленник не знает секретного кода, поэтому должен решать задачу для случайного кода без какой-либо специальной структуры.

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

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

Для многих кодов из-за их структуры основной является атака Сидельникова-Шестакова. В 1992 году В.М. Сидельников и С.О. Шестаков показали возможность вскрытия системы Нидеррайтера из-за особенностей обобщенного кода Рида-Соломона [6]. Как утверждали авторы, их атака может быть применена и к двоичным кодам Гоппы. Впоследствии оказалось, что это не так, и система, построенная на двоичных кодах Гоппы, устойчива к данной атаке. В то же время структура обобщенного кода Рида-Соломона позволяет эффективно, за полиномиальное время, решить для них задачу синдромного декодирования, что делает невозможным их применение в системах шифрования с открытым ключом. Отметим, что идея Нидеррайтера нашла свое применение практически во всех современных криптосистемах, участвующих в конкурсе на

стандартизацию, проводимом NIST. В частности, система «Classic McEliece» использует идею Нидеррайтера, но названа в честь Роберта Мак-Элиса из-за использования двоичных кодов Гоппы, устойчивых к атаке Сидельникова-Шестакова.

Самой опасной и универсальной является атака по информационным совокупностям, описанная в работах [7, 25].

Во многих современных научных работах данные системы шифрования модифицированы, использованы иные подходы к шифрованию и расшифрованию. Но все построенные системы сводятся к базовым идеям классических схем [2, 4]. Рассмотрим подробнее три системы, которые наиболее полно отражают текущее положение дел в области кодовой криптографии и дают представление о попытках улучшить системы Мак-Элиса и Нидеррайтера путем снятия некоторых ограничений (например, увеличение веса вектора ошибки).

Современный вариант криптосистемы Мак-Элиса на кодах Гоппы

Криптосистема на кодах Гоппы «Classic McEliece» представлена в работе [19]. В отличие от классической системы Нидеррайтера, где открытый ключ получается перемножением матриц, в современном варианте криптосистемы открытый ключ определяется представлением проверочной матрицы H в систематическом виде. Поскольку такое представление матрицы является односторонней функцией, т. е. нельзя произвести обратную операцию перевода матрицы из систематического вида к исходному, матрицу T, которая является урезанной версией матрицы H без единичной матрицы слева, используют как открытый ключ. Умножение матрицы H на дополнительные матрицы не требуется, так как это увеличивает время выполнения процедур шифрования и расшифрования, а также увеличивается размер ключей, а выигрыш в стойкости алгоритма совсем невелик. Отметим, что получение из матрицы Н, приведенной к систематическому виду, секретных параметров кода Гоппы является сложной задачей, и на данный момент не существует таких алгоритмов, которые делали бы это за полиномиальное время.

Криптосистема XGRS на расширенных кодах Рида-Соломона

Криптосистема XGRS на расширенных кодах Рида-Соломона представлена в работе [20], где авторам удалось уменьшить размер открытого ключа по сравнению с криптосистемой в [19] и сохранить требуемый уровень безопасности к атаке по информационным совокупностям. Также авторы утверждают, что данная криптосистема устойчива к атаке Сидельникова-Шестакова и к атаке на основе произведения Шура [26] благодаря расширению и последующему за ним выкалыванию позиций исходного кода, которое приводит к изменению его структуры.

Заметим, что в [20] присутствуют некоторые неточности. В частности, на этапе генерации ключа нет информации о том, что результирующая матрица при-

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

Авторы работы [20] утверждают, что при параметрах кода Рида-Соломона над конечным полем Fqm при q = 13, m = 3, где q — характеристика поля, m — степень расширения и, соответственно, длиной кода n = 1258 и числом информационных символов k = 1031 достигается 256-битный уровень безопасности к атаке по информационным совокупностям.

Такой же уровень достигается для двоичных кодов Гоппы в криптосистеме «Classic McEliece» с параметрами n = 6960, k = 5413, q = 2, m = 13 [19, 20]. Для проверки этого утверждения был выполнен пересчет вероятности успешной атаки при использовании кодов Рида-Соломона в криптосистеме XGRS [20] и двоичных кодов Гоппы в криптосистеме «Classic McEliece» по следующей формуле:

Cn-t

P

успеха

а

(1)

где С* — биномиальный коэффициент из n по k; t — количество ошибок, исправляемых кодом.

Отметим, что полученные результаты дают грубую наглядную и вычислительно простую оценку вероятности реализации атаки по информационным совокупностям, поскольку в настоящей работе задачей является сравнительная оценка соотношения уровня безопасности системы «Classic McEliece» и системы на кодах Рида-Соломона [20]. Более точные формулы для оценки вероятности реализации атаки по информационным совокупностям представлены в работе [27]. Так как в криптосистеме XGRS на кодах Рида-Соломона шифрование ведется поблочно, рассчитаем общее количество блоков на длине кода (n), число информационных блоков (k) и кодовое расстояние (d).

Избыточность кода Рида-Соломона с параметрами n = 1258 и k = 1031 равна: r = n - k = 227. Получим минимальное расстояние такого кода d = r + 1 = 228,

d- 1

а число исправляемых ошибок кодом: t = = 113.

Вычислим количество информационных блоков длины 1 для расширенного кода Рида-Соломона [20]:

k' =

тк-(т-Х)п 3-1031-1258

= 611.

Общее количество блоков длины 1 на длине n = 2516 расширенного кода совпадает с длиной кода и равно 1258. Для таких параметров вероятность успешной атаки по информационным совокупностям для криптосистемы на кодах Рида-Соломона приблизительно равна 5,9 х 10-36. Воспользуемся параметрами для кода Гоппы [20] для «Classic McEliece» с 256-битным уровнем безопасности: n = 6960, k = 5413, t = 119. В соответствии с формулой (1), получим, что вероятность успешной атаки приблизительно равна 4,9 х 10-80, что примерно соответствует 256-битному уровню безопасности.

Таким образом, очевидна неточность в расчетах безопасности системы, изложенная авторами в [20], и, соответственно, утверждение о выигрыше представленной системы по размеру открытого ключа в сравнении с «Classic McEliece» неверно.

Несмотря на то, что рассматриваемая система [20] на кодах Рида-Соломона не может быть вскрыта с помощью атаки Сидельникова-Шестакова, она неустойчива к атаке по информационным совокупностям и не может быть использована на практике в текущей редакции. Важно отметить, что использование кодов Рида-Соломона без их расширения также невозможно, так как в этом случае система становится уязвимой к атаке Сидельникова-Шестакова.

Криптосистема IKKR, использующая маскирующие вектора большого веса

Модификация современной криптосистемы Мак-Элиса на кодах Гоппы представлена в работе [22]. В работе рассмотрено повышение стойкости криптосистемы путем исключения обязательного ограничения на вес вектора ошибки. В отличие от оригинальной системы, где вес вектора обязательно должен быть меньше либо равен значению количества ошибок, исправляемых кодом, в системе [22] данное ограничение нивелируется применением линейных преобразований к вектору ошибки и введением кодовых слов в качестве «засаливающих» элементов.

В криптосистеме IKKR акцент сделан на увеличение веса вектора ошибок e, что может улучшить криптостойкость системы к атакам по информационным совокупностям. В криптосистеме вектор e умножен на матрицу

Epub = W х D х (Сл + P) х M,

где W, M — случайные невырожденные матрицы размера n х n; P — перестановочная матрица размера n х n; D — диагональная матрица с t ненулевыми элементами на диагонали; Cn — матрица кодовых слов; Epub — открытый ключ.

После расчета получим:

e х Epub = e х W х D х (Cn + P) х M = = (e х W х D х Cn + e х W х D х P) х M.

Первое слагаемое — кодовое слово, так как матрица Cn — матрица, строки в которой — это кодовые слова. Второе слагаемое — вектор ошибки веса не более t. Данное условие получается из-за умножения на матрицу D. При умножении на данную матрицу ненулевыми остаются только те позиции вектора, которые соответствуют ненулевым ее столбцам. В итоге шифртекст будет представлять некое кодовое слово с ошибкой, но, в отличие от современной криптосистемы Мак-Элиса, если злоумышленник найдет алгоритм, по которому он правильно произведет декодирование, то он не сможет найти открытый текст, не зная остальных частей закрытого ключа.

Несмотря на устойчивость к атаке по информационным совокупностям, криптосистема IKKR оказалась

подвержена другим атакам. Криптоанализ системы описан в работе [28]. В работе показан алгоритм атаки, работающий за полиномиальное время, который позволяет найти открытый текст на основе шифртекста, а также приведена ссылка на программную реализацию данной атаки с помощью системы компьютерной алгебры Sagemath. Атака использует факт линейности шифрования в системе и строится на решении системы линейных уравнений, которая имеет решение, эквивалентное открытому тексту. Кроме того, время работы алгоритма атаки меньше времени, требуемого на сам процесс расшифрования.

Заметим, что данная атака является частной для криптосистемы IKKR и не применима для систем, рассмотренных выше.

Параметры криптосистем

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

Оценим размеры ключей для рассмотренных криптосистем: оригинальной системы Мак-Элиса, «Classic McEliece» и XGRS на расширенных кодах Рида-Соломона. Допустим, что один элемент матрицы представляет один бит (за основу взяты двоичные коды).

Для оригинальной системы Мак-Элиса и системы «Classic McEliece» примем за основу код Гоппы с параметрами m = 13, n = 6960, k = 5413, t = 119. Для криптосистемы XGRS на расширенных кодах Рида-Соломона параметры кода: q = 13, nRS = 1258, kRS = 1031, tRS = 114, а также дополнительные параметры X = 2, mRS = 3.

Результаты расчетов представлены в табл. 1.

В табл. 1 используются следующие обозначения: S(k х k) — случайная невырожденная матри-

ца; G(k х n) — порождающая матрица кода Гоппы; P ( n х n ) — случайная перестановочная матрица; G (k х n ) — произведение матриц S х G х P; T(mt х k) — матрица-открытый ключ для системы «Classic McEliece»; s(n) — случайная строка длины n; L(n) — множество локаторов для кода Гоппы; H'(m^ х х (nRS - kRs) х XnRs) х [log2q] — матрица-открытый ключ для системы XGRS; H((nRS - kRS) х nRS) х [log2qmRS] — порождающая матрица для расширенного кода Рида-Соломона; Q(nRSl х nRSl) х [log2q] — матрица-секретный ключ для криптосистемы XGRS; у — примитивный

элемент поля Fqm.

ч

Из полученных результатов (табл. 1) видно, что оптимальным решением с точки зрения памяти является криптосистема XGRS на расширенных кодах Рида-Соломона. Однако, из-за наличия выявленных в настоящей работе проблем устойчивости криптосистемы XGRS к атаке по информационным совокупностям, использовать ее не рекомендуется. Из рассмотренных систем наиболее приближенная к оптимальной для использования - криптосистема «Classic McEliece».

Моделирование криптосистем

Для моделирования рассмотренных криптосистем разработаны программы на языке программирования Python с использованием программного обеспечения SAGE на персональном компьютере со следующими характеристиками: процессор Intel Core i5-8300H CPU 2.30 GHz, оперативная память 8 GB 2667 MHz.

Для каждой криптосистемы проведено измерение значения времени выполнения процессов генерации ключей tGen, шифрования tEnc и расшифрования tDec. Для криптосистем Мак-Элиса и «Classic McEliece» использован алгоритм декодирования Паттерсона [29], для криптосистемы XGRS — алгоритм декодирования Берлекэмпа-Месси [30].

Входные параметры для моделирования криптосистем: n — длина кода, k — длина кодируемого сообщения, t — количество исправляемых ошибок.

Заметим, что при моделировании криптосистемы XGRS на обобщенных кодах Рида-Соломона исполь-

Таблица 1. Оценка размеров ключей криптосистем Table 1. Cryptosystems key sizes estimation

Криптосистема Вид ключа Размер открытого ключа, бит Размер секретного ключа, бит Приблизительный общий размер ключей, МБ

Открытый Секретный

Оригинальная система Мак-Элиса G(k х n) t S(k х k) G(k х n) P(n х n) 3/77-107 1,15108 18

«Classic McEliece» T(mt х k) s(n) G(k х n) L(n) 8,37-106 3,77-107 5,5

XGRS на расширенных кодах Рида-Соломона H'OrsORS - kRS) х х ÏMrs^ riog2ql tRS 1 H((nRS - kRS) х х nRS) х riog2imRSl Q(nRS^ х nRSl) х х riog2ql Y 6,85106 2,87-107 4,2

Таблица 2. Экспериментальные значения исследуемых параметров рассмотренных криптосистем Table 2. Experimental values of the studied parameters of the considered cryptosystems

Параметры

q n k t m X tGen, отн. ед. tEnc, отн. ед. tDec, отн. ед.

Оригинальной криптосистемы Мак-Элиса

— 2304 1280 64 — — 1 0,00026 0,347

— 3584 1536 128 — — 2,06 0,00026 0,784

— 4096 2048 128 — — 3,73 0,00026 1,390

— 6912 2816 256 — — 3,94 0,00035 4,070

Криптосистемы «Classic McEliece»

— 2304 1280 64 — — 12,07 0,066 0,790

— 3584 1536 128 — — 49,71 0,214 2,523

— 4096 2048 128 — — 67,11 0,237 3,091

— 6912 2816 256 — — 484,07 0,842 12,301

Криптосистемы XGRS на обобщенных кодах Рида-Соломона

13 1258 1031 113 3 2 17,24 0,00023 20,470

13 1382 829 276 3 2 38,21 0,00065 25,390

7 1770 1539 115 4 2 36,94 0,00051 55,570

7 2024 1841 91 4 2 38,40 0,00034 87,750

зованы следующие дополнительные параметры: q — характеристика поля, m — расширение поля, 1 — коэффициент сокращения.

Результаты моделирования представлены в табл. 2.

Для оценки параметров целесообразно использовать относительные единицы, так как на устройствах с разными мощностями возможен большой разброс полученных результатов. Примем за относительную единицу по времени время генерации ключей для оригинальной системы Мак-Элиса с параметрами n = 2304, k = 1280, t = 64.

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

В криптосистеме «Classic McEliece» время генерации увеличивается по сравнению с оригинальной системой из-за расширения проверочной матрицы кода и последующего ее приведения к систематическому виду.

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

Заключение

В работе выполнен обзор оригинальных криптосистем Мак-Элиса и Нидеррайтера и их современных модификаций. Рассмотрены пять различных криптосистем, для трех из которых было проведено моделирование. Продемонстрировано, что попытки улучшения кодовых схем с открытым ключом путем использования других классов кодов (не двоичных кодов Гоппы) и снятия ограничений на вес вектора ошибки не увенчались успехом. Получены важные теоретические и практические результаты. В рассмотренной криптосистеме XGRS было выявлено несоответствие реального уровня безопасности к атаке по информационным совокупностям заявленному авторами, что делает ее неприменимой с учетом современных реалий, а также отмечены неточности при подсчете размеров ключей. Сравнительный анализ представленных криптосистем показал, что криптосистема «Classic McEliece» на сегодняшний день является наиболее приближенной к оптимальному решению по уровню безопасности и производительности среди рассмотренных в работе криптосистем. Оценка результатов моделирования трех представленных криптосистем показала, что, помимо больших размеров ключей, процессы генерации ключа и декодирования на компьютере со средними характеристиками занимают достаточно большое время — их уменьшение остается на сегодняшний момент актуальной задачей для дальнейших исследований.

Литература

1. Shor P.W. Algorithms for quantum computation: discrete logarithms and factoring // Proc. of the 35th IEEE Annual Symposium on Foundations of Computer Science (FOCS). 1994. P. 124-134. https:// doi.org/10.1109/SFCS.1994.365700

2. McEliece R.J. A public-key cryptosystem based on algebraic coding theory // DSN Progress Report 42-44, 1978. P. 114-116.

3. Гоппа В.Д. Рациональное представление кодов и (L^-коды // Проблемы передачи информации. 1971. Т. 7. № 3. С. 41-49.

4. Niederreiter H. Knapsack-type cryptosystems and algebraic coding theory // Problems of Control and Information Theory. 1986. V. 15. N 2. P. 159-166.

5. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. С. 506-507.

6. Сидельников В.М., Шестаков С.О. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона // Дискретная математика. 1992. Т. 4. № 3. С. 57-63.

7. Peters C. Information-set decoding for linear codes over Fq // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2010. V. 6061. P. 81-94. https://doi.org/10.1007/978-3-642-12929-2_7

8. Sidelnikov V.M. A public-key cryptosystem based on binary Reed-Muller codes // Discrete Mathematics and Applications. 1994. V. 4. N 3. P. 191-207. https://doi.org/10.1515/dma.1994.4.3.191

9. Minder L., Shokrollahi A. Cryptanalysis of the Sidelnikov cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2007. V. 4515. P. 347-360. https://doi. org/10.1007/978-3-540-72540-4_20

10. Gabidulin E.M. Public-key cryptosystems based on linear codes: Report 95-30 / Delft University of Technology, Faculty of Technical Mathematics and Informatics, 1995. P. 17-31.

11. Overbeck R. Structural attacks for public key cryptosystems based on Gabidulin codes // Journal of Cryptology. 2008. V. 21. N 2. P. 280301. https://doi.org/10.1007/s00145-007-9003-9

12. Baldi M., Chiaraluce F. Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes // Proc. of the IEEE International Symposium on Information Theory (ISIT). 2007. P. 2591-2595. https://doi.org/10.1109/ISIT.2007.4557609

13. Otmani A., Tillich J.P., Dallot L. Cryptanalysis of McEliece cryptosystem based on quasi-cyclic LDPC codes // Proc. of the First International Conference on Symbolic Computation and Cryptography. LMIB Beihang University, 2008. P. 69-81.

14. Janwa H., Moreno O. McEliece public key cryptosystems using algebraic-geometric codes // Designs, Codes and Cryptography. 1996. V. 8. N 3. P. 293-307. https://doi.org/10.1023/A:1027351723034

15. Faure C., Minder L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes // Proc. of the 11th International Workshop on Algebraic and Combinatorial Coding Theory. 2008. P. 99-107.

16. Loidreau P. Strengthening McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2000. V. 1976. P. 585-598. https://doi.org/10.1007/3-540-44448-3_45

17. Kobara K., Imai H. On the one-wayness against chosen-plaintext attacks of the Loidreau's modified McEliece PKC // IEEE Transactions on Information Theory. 2003. V. 49. N 12. P. 3160-3168. https://doi.org/10.1109/TIT.2003.820016

18. Bernstein D.J., Lange T., Peters C. Attacking and defending the McEliece cryptosystem // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2008. V. 5299. P. 31-46. https:// doi.org/10.1007/978-3-540-88403-3_3

19. Bernstein D.J. et al. Classic McEliece: conservative code-based cryptography / NIST. 2017.

20. Khathuria K., Rosenthal J., Weger V. Encryption scheme based on expanded reed-solomon codes // Advances in Mathematics of Communications. 2021. V. 15. N 2. P. 207-218. https://doi. org/10.3934/amc.2020053

21. Reed I.S., Solomon G. Polynomial codes over certain finite fields // Journal of the Society for Industrial and Applied Mathematics. 1960. V. 8. N 2. P. 300-304. https://doi.org/10.1137/0108018