Методи вибору параметрів скінченних полів матриць другого порядку та їх примітивних елементів для криптографічних застосувань у комп’ютерних системах і мережах

Abstract

Дисертацію присвячено розв’язанню актуального науково-прикладного завдання, що полягає в розробленні методів вибору параметрів скінченних полів матриць другого порядку та їх примітивних елементів для подальшого використання в криптографічних протоколах комп’ютерних систем і мереж. Актуальність теми зумовлена постійним зростанням обсягів інформації, що передається, обробляється та зберігається в електронному вигляді, а також підвищенням вимог до криптографічної стійкості засобів захисту даних в умовах розвитку розподілених обчислювальних середовищ, хмарних сервісів, мобільних мереж, вбудованих систем та Інтернету речей. За таких умов особливого значення набуває побудова нових математичних платформ для криптографії, які, з одного боку, спираються на строгий алгебраїчний апарат, а з іншого – дають змогу розширити простір криптографічних параметрів і підвищити обчислювальну складність несанкціонованого відновлення ключової інформації. У сучасній комп’ютерній криптографії скінченні поля є фундаментом багатьох класичних і сучасних алгоритмів, зокрема протоколів узгодження ключів, схем електронного цифрового підпису, симетричних шифрів та механізмів автентифікації. Водночас подальший розвиток криптографічних засобів потребує пошуку таких алгебраїчних конструкцій, які б дозволяли використовувати нові типи елементів і операцій без втрати математичної строгості. Одним із перспективних напрямів є використання матричних структур над простими полями. Проте практична цінність такого підходу визначається не лише самим фактом використання матриць, а насамперед можливістю конструктивно обирати параметри відповідного матричного середовища та примітивні елементи, придатні для побудови криптографічних перетворень. Саме цій задачі й присвячено дисертаційне дослідження. Об’єктом дослідження є процеси вибору параметрів скінченних полів матриць другого порядку та примітивних елементів у цих полях для криптографічного використання в комп’ютерних системах і мережах. Предметом дослідження є методи, моделі та алгоритми вибору параметрів скінченних полів матриць другого порядку, пошуку їх примітивних елементів, а також способи використання отриманих результатів у криптографічних протоколах узгодження ключів і електронного цифрового підпису. Метою дисертаційної роботи є підвищення криптографічної стійкості засобів захисту інформації в комп’ютерних системах і мережах за рахунок розроблення методів вибору параметрів скінченних полів матриць другого порядку та їх примітивних елементів, придатних для реалізації криптографічних протоколів. Для досягнення поставленої мети в роботі розв’язано такі основні завдання: проведено аналіз сучасного стану використання скінченних полів і матричних структур у криптографічних застосуваннях; визначено умови, яким мають задовольняти параметри матричних полів для їх практичного криптографічного використання; розроблено метод вибору примітивних елементів скінченних полів матриць другого порядку; розроблено метод вибору параметрів матричного поля та примітивного елемента в ньому; удосконалено реалізацію криптографічних протоколів узгодження ключів і електронного цифрового підпису шляхом перенесення відповідних операцій у матричне середовище; виконано дослідження статистичних властивостей і обчислювальної складності запропонованих рішень. У дисертації показано, що задача вибору примітивних елементів у скінченних полях матриць другого порядку не може ефективно розв’язуватися повним перебором усіх елементів, оскільки такий підхід є обчислювально витратним і малопридатним для практичних криптографічних застосувань. У зв’язку з цим розроблено метод вибору примітивних елементів, який базується на послідовній перевірці характеристик матриці-кандидата, аналізі її характеристичного полінома, умов досягнення максимального періоду та перевірці порядку визначника в базовому полі. Запропонований підхід дозволяє конструктивно формувати повну множину примітивних елементів без необхідності прямого перебору всіх можливих матриць. Такий результат має важливе прикладне значення, оскільки саме примітивні елементи є генераторами мультиплікативної групи та можуть бути використані як базові параметри у схемах узгодження ключів і підпису. Сутність розробленого методу полягає в тому, що для матриці-кандидата аналізуються її інваріантні характеристики, зокрема слід, визначник, а також дискримінант характеристичного полінома. На цій основі визначається, чи може така матриця бути кандидатом на примітивний елемент у відповідному матричному полі. Якщо для мультиплікативної групи порядок дорівнює p2 -1, то примітивний елемент повинен мати саме цей порядок. Для цього в роботі використано критерії, що зводять завдання перевірки примітивності до аналізу періоду матриці та порядку її визначника в базовому полі Zp. Такий підхід дозволяє перейти від загальної постановки завдання до ефективної обчислювальної процедури. Значну увагу приділено завданню одночасного вибору параметрів матричного поля та примітивного елемента в ньому. На відміну від традиційного підходу, коли спочатку фіксуються параметри поля, а потім окремо здійснюється пошук примітивних елементів, запропонований метод поєднує ці дві процедури. Це дозволяє отримувати параметри матричного поля й примітивний елемент у межах єдиної конструктивної схеми. Метод ґрунтується на використанні властивостей квадратичних лишків і нелишків у простому полі, аналізі нерозкладності характеристичного полінома, а також урахуванні зв’язку між параметрами матриці та властивостями її власних значень. Виділено спеціальний важливий випадок, коли порядок мультиплікативної групи має сприятливу факторизацію, зокрема пов’язану з числами Мерсенна або простими множниками спеціального вигляду, а також досліджено загальний випадок вибору параметрів. Наукова новизна одержаних результатів полягає в тому, що вперше розроблено та теоретично обґрунтовано методи вибору параметрів скінченних полів матриць другого порядку та їх примітивних елементів для криптографічних застосувань у комп’ютерних системах і мережах. Уперше запропоновано цілісний підхід, у межах якого задача вибору параметрів матричного поля поєднується із задачею вибору генератора його мультиплікативної групи. Представлено підходи до використання матричних алгебраїчних структур у протоколах узгодження ключів Діффі–Хеллмана та електронного цифрового підпису Ель-Гамаля. Практичне значення одержаних результатів полягає в тому, що розроблені методи можуть бути безпосередньо використані під час створення програмних і апаратних засобів криптографічного захисту інформації. Запропоновані алгоритмічні процедури дають змогу формувати параметри матричного поля та відповідні примітивні елементи для подальшого застосування в протоколах узгодження ключів, схемах електронного цифрового підпису, а також в інших криптографічних механізмах, що базуються на складності дискретного логарифмування. У роботі показано, що перенесення обчислень із класичного скалярного середовища до матричного дає змогу розширити множину допустимих криптографічних параметрів і створює передумови для підвищення криптографічної стійкості без принципового ускладнення базових арифметичних операцій. Одержані результати можуть бути використані в системах захищеного мережевого обміну, вбудованих пристроях, IoT-рішеннях, а також у спеціалізованих програмно-апаратних комплексах захисту інформації. У дисертації наведено приклади практичного застосування розроблених методів. Зокрема, досліджено реалізацію протоколу узгодження ключів у матричному середовищі, де відкриті та секретні параметри задаються елементами відповідного матричного поля. Розглянуто перенесення схеми електронного цифрового підпису Ель-Гамаля на випадок використання примітивних елементів скінченних полів матриць другого порядку. Показано, що в такому підході зберігається загальна логіка класичних криптографічних схем, але при цьому використовується ширший клас алгебраїчних об’єктів. Це відкриває можливість побудови нових модифікацій криптографічних протоколів, у яких параметри можуть бути додатково варійовані за рахунок матричного подання. Окрему увагу приділено дослідженню статистичних властивостей піднесення матриці до степеня та аналізу обчислювальної складності криптографічних перетворень у матричному полі. У роботі виконано порівняння запропонованих рішень із класичними реалізаціями над простим полем, проаналізовано вплив параметрів поля на кількість можливих примітивних елементів, а також показано, що коректний вибір параметрів має вирішальне значення для досягнення необхідного рівня криптографічної стійкості. Отримані результати підтверджують, що матричні поля можуть бути не лише теоретичною моделлю, а й практично придатною основою для розроблення криптографічних засобів. Результати дисертаційної роботи мають значення для подальшого розвитку математичного апарату криптографії та для створення нових підходів до побудови захищених систем передавання, зберігання та автентифікації інформації. Запропоновані методи забезпечують можливість систематичного вибору параметрів і примітивних елементів у матричних полях другого порядку та створюють наукове підґрунтя для подальших досліджень у напрямі вдосконалення асиметричних криптографічних протоколів, орієнтованих на використання спеціальних алгебраїчних структур. Практична орієнтованість одержаних результатів полягає в їх придатності до програмної реалізації, формалізації у вигляді алгоритмів та інтеграції в реальні системи захисту інформації. Основні результати дисертаційної роботи оприлюднено в 5 наукових публікаціях, серед яких 2 статті у виданнях, що індексуються в Scopus та/або Web of Science (одна з них у квартилі Q2), а також 3 доповіді на міжнародних науково-практичних конференціях. Це підтверджує апробацію основних положень дисертації та науковий інтерес до отриманих результатів.

The dissertation is devoted to solving a relevant scientific and applied problem consisting in the development of methods for selecting the parameters of finite fields of matrices of order 2 and their primitive elements for subsequent use in cryptographic protocols of computer systems and networks. The relevance of the topic is due to the continuous growth in the volume of information transmitted, processed, and stored in electronic form, as well as by the increasing requirements for the cryptographic strength of data protection means under conditions of developing distributed computing environments, cloud services, mobile networks, embedded systems, and the Internet of Things. Under such conditions, the construction of new mathematical platforms for cryptography becomes particularly important; on the one hand, these platforms rely on a rigorous algebraic apparatus, and on the other hand, they make it possible to expand the space of cryptographic parameters and increase the computational complexity of unauthorized recovery of key information. In modern computer cryptography, finite fields constitute the foundation of many classical and contemporary algorithms, including key agreement protocols, digital signature schemes, symmetric ciphers, and authentication mechanisms. At the same time, the further development of cryptographic means requires the search for algebraic constructions that would allow the use of new types of elements and operations without loss of mathematical rigor. One promising area is the use of matrix structures over prime fields. However, the practical value of this approach is determined not merely by the very fact of using matrices, but primarily by the possibility of constructively selecting the parameters of the corresponding matrix environment and primitive elements suitable for building cryptographic transformations. It is precisely this problem that the dissertation research addresses. The object of the research is the processes of selecting parameters of finite fields of matrices order 2 and primitive elements in these fields for cryptographic use in computer systems and networks. The subject of the research is methods, models, and algorithms for selecting parameters of finite fields of matrices of order 2, finding their primitive elements, and determining ways to use the obtained results in cryptographic key agreement protocols and digital signature schemes. The aim of the dissertation is to increase the cryptographic strength of information protection means in computer systems and networks through the development of methods for selecting the parameters of finite fields of matrices of order 2 and their primitive elements suitable for the implementation of cryptographic protocols. To achieve this aim, the following main tasks were solved in the study: an analysis of the current state of the use of finite fields and matrix structures in cryptographic applications was carried out; the conditions to be satisfied by the parameters of matrix fields for their practical cryptographic use were determined; a method for selecting primitive elements of finite fields of matrices of order 2 was developed; a method for selecting parameters of a matrix field and a primitive element in it was developed; the implementation of cryptographic key agreement protocols and digital signatures was improved by transferring the corresponding operations into the matrix environment; and a study of the statistical properties and computational complexity of the proposed solutions was performed. The dissertation demonstrates that the problem of selecting primitive elements in finite fields of second-order matrices cannot be effectively solved by exhaustive enumeration of all elements, since such an approach is computationally expensive and of limited suitability for practical cryptographic applications. Accordingly, a method for selecting primitive elements was developed that is based on the successive verification of the characteristics of a candidate matrix, analysis of its characteristic polynomial, the conditions for attaining the maximum period, and verification of the order of the determinant in the base field. The proposed approach makes it possible to constructively form the complete set of primitive elements without the need for direct exhaustive enumeration of all possible matrices. This result has important practical significance, since primitive elements are generators of the multiplicative group and may be used as basic parameters in key agreement and signature schemes. The essence of the developed method lies in the fact that, for a candidate matrix, its invariant characteristics are analyzed, in particular the trace, determinant, and the discriminant of the characteristic polynomial. On this basis, it is determined whether such a matrix can be a candidate primitive element in the corresponding matrix field. If the order of the multiplicative group is equal to p2 -1, then the primitive element must have exactly this order. For this purpose, the study employs criteria that reduce the problem of verifying primitiveness to an analysis of the period of the matrix and the order of its determinant in the base field Zp. Such an approach makes it possible to move from a general formulation of the problem to an efficient computational procedure. Considerable attention is paid to the problem of simultaneously selecting the parameters of the matrix field and a primitive element in it. Unlike the traditional approach, in which the field parameters are first fixed and the search for primitive elements is then carried out separately, the proposed method combines these two procedures. This makes it possible to obtain the parameters of the matrix field and a primitive element within a single constructive scheme. The method is based on the use of the properties of quadratic residues and non-residues in a prime field, analysis of the irreducibility of the characteristic polynomial, and consideration of the relationship between the matrix parameters and the properties of its eigenvalues. A special important case is distinguished, in which the order of the multiplicative group has a favorable factorization, in particular one associated with Mersenne numbers or prime factors of a special form; the general case of parameter selection is also investigated. The scientific novelty of the obtained results lies in the fact that, for the first time, methods for selecting the parameters of finite fields of matrices of order 2 and their primitive elements for cryptographic applications in computer systems and networks have been developed and theoretically substantiated. For the first time, an integral approach has been proposed in which the problem of selecting the parameters of a matrix field is combined with the problem of selecting a generator of its multiplicative group. Approaches to the use of matrix algebraic structures in the Diffie–Hellman key agreement protocol and the ElGamal digital signature scheme are presented. The practical significance of the obtained results lies in the fact that the developed methods may be directly used in the creation of software and hardware means for cryptographic information protection. The proposed algorithmic procedures make it possible to form the parameters of a matrix field and the corresponding primitive elements for further application in key agreement protocols, digital signature schemes, as well as in other cryptographic mechanisms based on the difficulty of the discrete logarithm problem. The study shows that transferring computations from the classical scalar environment to the matrix one makes it possible to expand the set of admissible cryptographic parameters and creates the prerequisites for increasing cryptographic strength without fundamentally complicating the basic arithmetic operations. The obtained results may be used in secure network exchange systems, embedded devices, IoT solutions, as well as in specialized software and hardware complexes for information protection. The dissertation provides examples of the practical application of the developed methods. In particular, the implementation of a key agreement protocol in a matrix environment is investigated, where public and secret parameters are specified by elements of the corresponding matrix field. The transfer of the ElGamal digital signature scheme to the case of using primitive elements of finite fields of second-order matrices is considered. It is shown that, within this approach, the general logic of classical cryptographic schemes is preserved, while a broader class of algebraic objects is employed. This opens up the possibility of constructing new modifications of cryptographic protocols in which parameters may be additionally varied through matrix representation. Particular attention is paid to the study of the statistical properties of matrix exponentiation and to the analysis of the computational complexity of cryptographic transformations in a matrix field. The study compares the proposed solutions with classical implementations over a prime field, analyzes the influence of field parameters on the number of possible primitive elements, and shows that the correct selection of parameters is of decisive importance for achieving the required level of cryptographic strength. The obtained results confirm that matrix fields can serve not only as a theoretical model but also as a practically suitable basis for the development of cryptographic means. The results of the dissertation are significant for the further development of the mathematical apparatus of cryptography and for the creation of new approaches to the construction of secure systems for the transmission, storage, and authentication of information. The proposed methods provide the possibility of systematic selection of parameters and primitive elements in second-order matrix fields and create a scientific foundation for further research aimed at improving asymmetric cryptographic protocols oriented toward the use of special algebraic structures. The practical orientation of the obtained results lies in their suitability for software implementation, formalization in the form of algorithms, and integration into real information protection systems. The main results of the dissertation have been published in 5 scientific publications, including 2 articles in journals indexed in Scopus and/or Web of Science (one of them in the Q2 quartile), as well as 3 papers presented at international scientific and practical conferences. This confirms the approbation of the main provisions of the dissertation and the scientific interest in the obtained results.