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

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

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

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 24-41-04006

НазваниеТеоретические основы параметризуемых унифицированных способов задания конечных ассоциативных алгебр и разработка постквантовых криптографических алгоритмов с открытым ключом

Руководитель Молдовян Николай Андреевич, Доктор технических наук

Организация финансирования, регион Федеральное государственное бюджетное учреждение науки "Санкт-Петербургский Федеральный исследовательский центр Российской академии наук" , г Санкт-Петербург

Конкурс №96 - Конкурс 2024 года «Проведение фундаментальных научных исследований и поисковых научных исследований международными научными коллективами» (VAST)

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-216 - Математические модели и методы защиты, преобразования и передачи информации

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

Код ГРНТИ49.33.35

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Заявленный проект ориентирован на развитие фундаментальных основ постквантовых криптографических алгоритмов с открытым ключом, использующих вычислительную трудность решения систем многих степенных уравнений с многими неизвестными, включая 1) алгоритмы электронной цифровой подписи (ЭЦП) со скрытой группой и 2) криптоалгоритмы , основанные на трудно обратимых нелинейных отображениях с секретной лазейкой. Алгоритмы ЭЦП первого типа используют в качестве своего алгебраического носителя конечные некоммутативные ассоциативные алгебры (КНАА) и способы параметризации унифицированных способов задания КНАА позволят построить КНАА достаточно больших размерностей, необходимых для достижения заданного уровня стойкости. Криптосистемы второго типа относятся к многомерной криптографии (МК). Последняя считается одной из перспективных областей постквантовой криптографии, в рамках которой могут быть разработаны практичные постквантовые алгоритмы открытого шифрования и алгоритмы ЭЦП. Однако в настоящее время не устранен основной недостаток алгоритмов МК, заключающийся в том, что при требуемом уровне стойкости размер открытого ключа в известных алгоритмах МК является чрезвычайно большим - от десятков Килобайт при 80-битной стойкости до нескольких Мегабайт при 256-битной стойкости. Для устранения этого недостатка развивается новая парадигма многомерной криптографии, отличающаяся от традиционного подхода тем, что в качестве базового нелинейного отображения, вычисляемого как нахождение значений множества степенных многочленов (представляющих собой открытый ключ) над конечным полем GF(n) сравнительно малого порядка, используется операция экспоненцирования в поле GF(n^k), заданном в форме конечной k-мерной алгебры над полем GF(n) с многими независимыми структурными константами из поля GF(n). Конкретная модификация расширенного поля задается секретными значениями структурных констант, являющихся элементами секретного ключа, поэтому обратное отображение при известном открытом ключе не может быть выполнено непосредственно как операция извлечения корня в конечном поле. Восстановление поля GF(n^k) по открытому ключу представляет собой основную структурную атаку на алгоритмы МК, построенные в рамках предлагаемой парадигмы. При этом данная структурная атака связана с решением большой системы степенных уравнений над полем GF(n). Прямые атаки на алгоритмы МК, в том числе и построенные в соответствии с новой парадигмой, хорошо изучены за последние 30 лет с момента появления МК. В отличии от известных алгоритмов МК, в которых типы структурных атак отличны от прямых атак, состоящих в решении системы многих степенных уравнений с многими неизвестными, основные структурные атаки для разрабатываемых алгоритмов относятся к тому же типу, что и прямые атаки. Это в принципе позволит дать оценку стойкости с единых позиций, учитывая при этом и другие возможные варианты атак. Одной из проблем в направлении развития новой парадигмы МК является то, что разработка таблиц умножения базисных векторов, с помощью которых задается ассоциативная операция умножения векторов, в настоящее время носит в основном эвристический характер. Для завершения формирования новой парадигмы создание теоретических основ параметризации унифицированных способов задания коммутативных ассоциативных алгебр, в том числе и векторных конечных полей, имеет важнейшее значение и обеспечит возможность их задания для случая достаточно больших размерностей с большим числом независимых структурных констант. В рамках новой парадигмы будут разработаны постквантовые алгоритмы ЭЦП нового типа, отличающиеся тем, что для их взлома требуется по открытому ключу вычислить секретные параметры задания векторного конечного поля, используемого в качестве алгебраического носителя. Указанные теоретические основы также существенно расширят возможности реализации постквантовых алгоритмов ЭЦП со скрытой группой за счет появления возможности использования КНАА существенно увеличенных размерностей.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Аннотация результатов, полученных в 2024 году
1. Разработаны три способа унифицированного задания конечных коммутативных ассоциативных алгебр (ККАА), параметризуемых по распределению базисных векторов и по распределению структурных констант по ячейкам таблиц умножения базисных векторов (ТУБВ). Каждый из разработанных способов состоят в формировании единой математической формулы, в качестве параметров которой выступают значения m и d. Размерность задаваемой алгебры m принимает различные последовательности натуральных значений в каждом из способов. Значение d задает параметризацию распределения базисных векторов. Для получения достаточного разнообразия различных распределений базисных векторов по ячейка ТУБВ были разработаны формулы с дополнительным параметром d, принимающим значения от 1 до m, для каждого из которых формируется уникальное распределение базисных векторов при обеспечении свойств комутативности и ассоциативности операции умножения векторов. Разработаны три различных типа таких генерирующих формул: 1) для размерностей m =2^z - 1 при произвольной натуральной степени z; 2) для размерностей m, таких, что число m+1 является простым; 3) для произвольных размерностей m>1. Каждый из трех разработанных способов унифицированной генерации ТУБВ для одинакового значения размерности задает множества ТУБВ с уникальными распределениями базисных векторов, которые определяются значением параметра d из области допустимых значений. Для первого способа d=1,2,...2^z-1; для второго d=1,2,...m и для третьего d=0,1,...m-1. 2. Для каждого из трех способов унифицированного задания ТУБВ с возможностью параметризации распределения базисных векторов разработаны расширенные генерирующие формулы, включающие дополнительный параметр t (Для первого способа t=2,3...2^z-1; для второго t=2,3...m и для третьего t=1,2,...m-1), определяющий распределение по ячейкам ТУБВ одной структурной константы или двух структурных сопряженных констант. Разработанные расширенные генерирующие формулы с двумя сопряженными константами при фиксированных значениях размерности m и параметров d и t задают уникальную ТУБВ с двумя независимыми константами. При фиксированных значениях m и d для каждого из возможных значений параметра t (имеем m-1 различных значений t) имеем уникальную пару распределений двух структурных констант в ТУБВ-таблицах с одинаковым распределением базисных векторов, которое задано зафиксированными значениями m и d. Доказано утверждение о сохранении свойства ассоциативности при наложении всех распределений, задаваемых различными параметрами t при фиксированном распределении базисных векторов па ячейкам ТУБВ заданной размерности. Благодаря этому утверждению можно построить ТУБВ с 2(m-1) различными распределениями структурных констант, которая определяет операцию умножения векторов, обладающую свойствами коммутативности и ассоциативности. 3. Разработаные унифицированные способы задания ТУБВ реализуют три необходимых требования для задания векторных конечных полей - наличие свойств коммутативности и ассоциативности и существование глобальной двухсторонней единицы. Следующее требуемое для целей проекта условие состоит в выполнении делимости порядка (равного p^s-1) мультипликативной группы поля, над которым задается конечная алгебра на размерность векторов Это требование реализуется выбором соответствующих значений m, p и s. При наличии всех указанных условий кольцо, которым является ККАА, заданная по разработанным генерирующим формулам, становится полем только при соответствующей комбинации значений структурных констант, присутствующих в ТУБВ. Выполненное большое число вычислительных экспериментов позволило установить, что известные различные ТУБВ, включая генерируемые по разработанным унифицированным формулам, которые задают коммутативное и ассоциативное умножение векторов, могут быть разделены на два больших класса: 1) ТУБВ, которые при всех возможных наборах значений структурных констант задают ККАА, являются конечными кольцами и 2) ТУБВ, которые при некоторых наборах значений структурных констант задают ККАА, являются конечными кольцами, а при некоторых других наборах значений структурных констант задают ККАА, являются векторными конечными полями. Установлено, что все ТУБВ генерируемые по разработанным унифицированным формулам относятся ко второму типу ТУБВ. 4. При задании векторных конечных полей над конечным полем GF(2^s) имеется суженное пространство выбора соотношения значений размерности векторного конечного поля и степени s, при которых может быть сформировано векторное конечное поле путем подбора определенных комбинаций значений структурных констант. Разработан алгоритм, реализующий генерацию ТУБВ, пригодную для задания векторных конечных полей над полями GF(2^s). Для различных наборов значений m и s, сгенерированных по этому алгоритму была выполнена экспериментальная проверка возможности формирования векторных конечных полей для ТУБВ сгенерированных по каждой из трех разработанных унифицированных формул. Эти эксперименты подтвердили возможность формирования наборов структурных констант, задающих формирование алгебры, являющейся векторным конечным полем. 5. Для выполнения вычислительных экспериментов, описанных выше, и практической проверке полученных теоретических результатов разработаны компьютерные программы, с помощью которых были выполнены эксперименты, подтвердившие на практике корректность полученных теоретических результатов. 6. Используя в качестве аналогов известные алгебраические алгоритмы с многократным вхождение подписи в проверочное уравнение, известный способ усиления рандомизации ЭЦП и конечные некоммутативные ассоциативные алгебры, заданные над конечными полями вида GF(2^s), с глобальной двухсторонней единицей, были разработаны алгебраические алгоритмы ЭЦП, основанные на вычислительной трудности решения больших систем степенных уравнений, и обладающие сравнительно малым размером открытого ключа. 7. Разработан способ построения многомерных алгоритмов ЭЦП нового типа -- требующих для подделки подписи восстановления секретной модификации векторного конечного поля, в котором задано кубическое уравнение верификации подписи, проверяемое по открытому ключу, заданному в виде набора многочленов, описывающих операцию возведения в куб в векторном конечном поле. Разработан конкретный алгоритм данного типа и получена общая оценка его параметров при реализации на векторных конечных полях характеристики два. 8. Выполнен анализ стойкости разработанных алгоритмов ЭЦП со скрытой группой, основанных на вычислительной трудности решения систем многих квадратных уравнений с многими неизвестными и использующих КНАА над конечными полями GF(2^s) четной характеристики в качестве алгебраического носителя.

Публикации

1. Молдовян Н.А. Parameterized method for specifying vector finite fields of arbitrary dimensions Quasigroups and related systems, Quasigroups and related systems. 2024. Vol. 32. No. 2, pp. 299-312 (год публикации - 2024)
10.56415/qrs.v32.21

2. Молдовян А.А., Молдовян Н.А. Parameterized unified method for setting vector for multivariate cryptography Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления, Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2024. Т. 20. № 4. С. 479-486 (год публикации - 2024)
10.21638/spbu10.2024.404

3. Захаров Д.В., Костина А.А., Морозова Е.В., Молдовян Д.Н. Алгоритм ЭЦП на алгебре матриц 3х3, использующий две скрытые группы Вопросы кибербезопасности, Вопросы кибербезопасности. 2025. № 3(67). С. 45-54. (год публикации - 2025)
10.21681/2311-3456-2025-3-45-54

4. Молдовян А.А.. Молдовян Н.А. A method for enhancing randomization in algebraic signature algorithms on non-commutative algebras Quasigroups and related systems, Moldovyan A.A., Moldovyan N.A. A method for enhancing randomization in algebraic signature algorithms on non-commutative algebras // Quasigroups and related systems. 2025. Vol. 33. No. 1, pp.71-83 (год публикации - 2025)
10.56415/qrs.v33.06

5. Дуонг М.Т., Молдовян А.А., Молдовян Д.Н., Нгуен М.Х., До Б.Т. Structure of quaternion-type algebras and a post-quantum signature algorithm International Journal of Electrical and Computer Engineering, May Thu Duong, A.A. Moldovyan, D.N Moldovyan, Minh Hieu Nguyen, Bac Thi Do, “Structure of quaternion-type algebras and a post-quantum signature algorithm,” International Journal of Electrical and Computer Engineering (IJECE), vol. 15, no. 3, pp. 2965–2976, June 2025 (год публикации - 2025)
10.11591//ijece.v15i3.pp2965-2976

6. Молдовян А.А., Молдовян Д.Н., Молдовян Н.А. Постквантовые двухключевые криптосхемы на конечных алгебрах Информатика и автоматизация, Информатика и автоматизация. 2024. Т. 23. № 4. С. 1246-1276. (год публикации - 2024)
10.15622/ia.23.4.12

7. Молдовян Н.А, Петренко А.С. Алгебраический алгоритм ЭЦП с двумя скрытыми группами Вопросы кибербезопасности, Вопросы кибербезопасности. 2024. № 6(64). С. 98-107. (год публикации - 2024)
10.21681/2311-3456-2024-6-98-107

8. Дуонг М.Т., Молдовян А.А., Молдовян Н.А., Нгуен М.Х., До Б.Т. Structure of 6-dimensional finite non-commutative algebras with many single-sided units Bulletin of Electrical Engineering and Informatics, Structure of 6-dimensional finite non-commutative algebras with many single-sided units // Bulletin of Electrical Engineering and Informatics. 2025. V. 14. No. 3. P. 2017-2030 (год публикации - 2025)
10.11591/eei.v14i3.9064

9. Петренко А. С ПАРАМЕТРИЗАЦИЯ ПОСТКВАНТОВОЙ ЭЛЕКТРОННОЙ ПОДПИСИ КНАА-2-ЭЦП Вопросы кибербезопасности, Вопросы кибербезопасности. – 2025. – № 5(69). – С. 88-95 (год публикации - 2025)
10.21681/2311-3456-2025-5-88-95

10. Молдовян А.А. ПОСТКВАНТОВЫЙ АЛГЕБРАИЧЕСКИЙ АЛГОРИТМ ЭЦП С ТРЕМЯ СКРЫТЫМИ ГРУППАМИ Вопросы кибербезопасности, Вопросы кибербезопасности 2025 № 5 (69), с.78-87 (год публикации - 2025)
10.21681/2311-3456-2025-5-78-87

11. К.-Л. Динь, Л.-Г. Нгуен, Х.-М. Нгуен, Т.-Б. До, Молдовян А.А., Молдовян Д.Н. Post-Quantum Signature Algorithm on Finite matrix Algebras, using Three hidden Groups IEEE, Dinh K.-L., Nguyen L.-G., Nguyen L.-G., Do T.-B., Moldovyan A.A., Moldovyan D.N., Kostina A.A. Post-Quantum Signature Algorithm on Finite matrix Algebras, using Three hidden Groups,"2025 2nd International Conference On Cryptography And Information Security (VCRIS)”, Hanoi, Vietnam, October 30-31, 2025, pp. 1-8, doi: 10.1109/VCRIS68011.2025.11250573 (год публикации - 2025)
10.1109/VCRIS68011.2025.11250573

12. К.-Л. Динь, Л.-Д. Нгуен, Т.-Б. До, Молдовян А.А., Молдовян Д.Н. Костина А.А. Defining High-Dimensional Non-Commutative Algebras as Carriers for Post-Quantum Digital Signature Algorithms IEEE, 2024 1st International Conference On Cryptography And Information Security (VCRIS), Hanoi, Vietnam, 2024, pp. 1-5, doi: 10.1109/VCRIS63677.2024.10813386 (год публикации - 2024)
10.1109/VCRIS63677.2024.10813386

Аннотация результатов, полученных в 2025 году
В ходе выполнения проекта на этапе 2025 года была рассмотрена задача формирования векторных конечных полей четной характеристики и сформулированы требования к выбору параметров задания конечных ассоциативных коммутативных алгебр над конечными полями GF(2^s) для формирования в них мультипликативной группы с циклическим строением и порядком, равным значению 2^{sm} – 1. Выполнены вычислительные эксперименты, показывающие, что реализация сформулированных требований задает формирование конечных алгебр частного вида, являющихся векторными конечными полями. Сформулировано и доказано расширенное утверждение о мультипликативной суперпозиции распределений структурных констант при фиксированном распределении базисных векторов в таблице умножения базисных векторов (ТУБВ), сохраняющей свойство ассоциативности операции умножения векторов. Утверждение обеспечивает возможность одновременно параметризовать распределение базисных векторов и структурных констант в ТУБВ. В соответствии с расширенным утверждением обеспечивается увеличение числа потенциально возможных модификаций векторного конечного поля, что имеет существенное значение при их использовании в качестве элементов секретного ключа. Утверждение показывает возможность комбинирования формализованных способов задания многих распределений структурных констант с распределениями, установленными эвристическим путем. Выведены общие формулы описывающие трудно обратимое отображение с секретной лазейкой, задаваемое операцией экспоненцирования в сравнительно малые степени в векторных конечных полях и описываемые наборами степенных многочленов от многих переменных, которыми являются координаты отображаемого (входного) вектора. Значения многочленов задают координаты выходного вектора. Показано, что для случая задания векторного конечного поля над конечными полями характеристики два компактные наборы многочленов могут описывать операцию экспоненцирования сравнительно большой степени. Для частных случаев выведены наборы многочленов, описывающие операцию экспоненцирования в степени z= 4, 5, 16, 17, 128, 129 в векторных конечных полях GF((2^8)^5), заданных над полями GF(2^8). Выполнены вычислительные эксперименты, подтвердившие на практике корректность полученных формул для наборов многочленов, описывающих операции экспоненцирования в степени, взаимно простые с порядком мультипликативной группы векторного конечного поля. Совместно с вьетнамской стороной разработан ряд постквантовых алгебраических алгоритмов электронной цифровой подписи (ЭЦП) со скрытой группой, основанных на вычислительной сложности решения больших систем степенных уравнений, которые обладают малым суммарным размером открытого ключа и подписи и благодаря этому представляют интерес как прототипы практичных постквантовых стандартов ЭЦП. Разработан способ оценивания стойкости предложенных алгебраических алгоритмов подписи, отличающийся описанием координат векторов, входящих в скрытую группу, по координатам вектора-представителя этой группы. По результатам выполненных исследований в 2025 году опубликовано 8 научных статей в ведущих рецензируемых изданиях входящих в базы научного цитирования RSCI, Scopus, Web of Science, в том числе 4 статьи совместно с вьетнамскими исполнителями проекта.

Публикации