Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа
| dc.contributor.advisor | Марковський, Олександр Петрович | |
| dc.contributor.author | Нікольський, Сергій Сергійович | |
| dc.date.accessioned | 2026-07-07T11:27:14Z | |
| dc.date.available | 2026-07-07T11:27:14Z | |
| dc.date.issued | 2026 | |
| dc.description.abstract | Нікольський С.С. Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 123 – Комп’ютерна інженерія з галузі знань 12 – Інформаційні технології. – Національний Технічний Університет України «Київський Політехнічний Інститут імені Ігоря Сікорського», Київ, 2026. Дисертаційна робота присвячена розвитку технологій організації обчислень мультиплікативних операцій алгебри скінчених полів Галуа GF(2n) для прискорення реалізації криптографічних механізмів захисту інформації з відкритим ключем в системах дистанційного контролю та управління об’єктами реального часу з застосуванням технологій ІоТ, шляхом розробки методів прискореної комп’ютерної реалізації базової операції такої криптографії – експоненціювання на скінчених полях Галуа. що здійснюється над числами, довжина яких на порядки перевищує розрядність процесора. Мета і завдання дослідження. Мета дослідження полягає в прискоренні комп’ютерної реалізації експоненціювання на скінчених полях Галуа – базової операції сучасних механізмів криптографічного захисту інформації з відкритим ключем в системах дистанційного управління на базі технологій ІоТ. Для досягнення мети дослідження поставлено і вирішено такі задачі: 1. Аналіз використання криптографічних механізмів захисту даних, в яких використовується алгебра скінчених полів Галуа, обґрунтування критеріїв ефективності засобів обчислювальної реалізації базової операції над полями Галуа, що використовується в цих механізмах – експоненціювання над числами, довжина яких значно перевищує розрядність процесора; огляд, з позицій цих критеріїв існуючих методів та алгоритмів обчислення експоненти на полях Галуа, визначення можливостей підвищення швидкодії її обчислювальної реалізації. 2. Теоретичне обґрунтування, розробка та дослідження методу прискореного експоненціювання, який організує обробку бітів коду експоненти в напрямку від старших до молодших групами по h розрядів, при цьому всі операції множення в рамках групи заміняються однією такою операцією з використанням передобчислень, що здійснюється перед кожнім експоненціювання, а група з h операцій піднесення до квадрату заміняється на одну операцію піднесення в ступінь 2h з використанням передобчислень, яка виконуються при зміні утворюючого поліному поля Галуа, що дозволяє зменшити кількість мультиплікативних операцій. 3. Теоретичне обґрунтування, розробка та дослідження методу прискорення обчислення експоненти на полях Галуа за рахунок організації суміщення в часі виконання двох операцій на полі Галуа – піднесення до квадрату та множення на постійне число, за рахунок чого забезпечується прискорення виконання важливої для криптографічних застосувань операції обчислення експоненти. 4. Теоретичне обґрунтування, розробка та дослідження методу прискорення обчислення експоненти на полях Галуа шляхом організації обробки коду експоненти зі старших розрядів по групам, що складаються з одиниці та передуючим їй нулям і здійснюється для кожної з них у вигляді однієї суміщеної операції множення на полях Галуа з використанням передобчислень, за рахунок чого досягається зменшення кількості операцій множення і, відповідно, прискорення обчислення експоненти на полі Галуа. 5. Теоретичне обґрунтування, розробка та дослідження методу прискорення обчислення експоненти на полях Галуа шляхом організації паралельного обчислення експоненти на кінцевих полях Галуа, яка відрізняється тим, що в рамках кожного із k обчислювальних процесів здійснюється піднесення числа в ступінь, код якої містить n/k значущих бітів експоненти, розділених k-1 нульовими бітами, за рахунок чого кількість операцій множення і піднесення в ступінь двійки на полі Галуа зменшується в k раз. 6. Теоретичне обґрунтування, розробка та дослідження методу прискорення обчислення експоненти на полях Галуа шляхом організації паралельного обчислення експоненти на скінчених полях Галуа, яка відрізняється тим, що в рамках кожного із k обчислювальних процесів здійснюється піднесення числа в ступінь числа два з отриманням стартового значення для обчислення часткової експоненти, що містить в собі n/k суміжних розрядів коду експоненти, що дозволяє прискорити процес обчислення експоненти на полях Галуа в k раз. 7. Теоретичне обґрунтування, розробка та дослідження методу прискорення обчислення експоненти на полях Галуа шляхом організації паралельного обчислення експоненти на скінчених полях Галуа, яка відрізняється тим, що в кожному із паралельних процесів оброблюється група фрагментів коду експоненти для яких попередньо обраховано значення експонент-шаблонів, які підносять в ступінь двійки з застосуванням інших передобчислень, за рахунок чого досягається прискорення обчислення на багатоядерних процесорних платформах експоненти на полях Галуа. 8. Створення програмних засобів для експериментального дослідження ефективності запропонованих методів та підходів до прискорення реалізації базової для криптографічних протоколів операції експоненціювання на скінчених полях Галуа. Об’єкт дослідження – процеси обчислення базової для криптографічних застосувань операції експоненціювання на скінчених полях Галуа, яка виконується над числами, довжина яких значно перевищує розрядність процесора. Предмет дослідження – методи організації обчислювального процесу експоненціювання на скінчених полях Галуа GF(2n). Методи досліджень базуються на базових засадах теорії скінчених полів Галуа, теорії рекурсивних функцій, теорії ймовірності, а також на основних положеннях статистичного та імітаційного моделювання. Наукова новизна одержаних результатів роботи полягає у наступному: 1. Вперше розроблено та досліджено метод експоненціювання на скінчених полях Галуа GF(2n), який відрізняється тим, що біти коду експоненти оброблюються в напрямку від старших до молодших групами по h розрядів, при цьому всі операції множення в рамках групи заміняються однією такою операцією з використанням передобчислень, що здійснюється перед кожнім експоненціювання, а група з h операцій піднесення до квадрату заміняється на одну операцію піднесення в ступінь 2h з використанням передобчислень, яка виконуються при зміні утворюючого поліному поля Галуа, що дозволяє зменшити кількість мультиплікативних операцій на полі Галуа для реалізації експоненціювання. 2. Вперше розроблено та досліджено метод прискореного обчислення експоненти на полях Галуа, якій відрізняється від відомих тим, що організується суміщення в часі виконання двох мультиплікативних операцій на полі Галуа – піднесення до квадрату та множення на постійне число, за рахунок чого забезпечується прискорення виконання цієї важливої для криптографічних застосувань операції. Теоретично доведено та експериментально підтверджено, що запропонований метод дозволяє в 4.5 рази прискорити комп’ютерну реалізацію експоненціювання на полях Галуа в порівнянні з відомими методами. 3. Вперше обґрунтовано, розроблено і досліджено метод обчислення експоненти на полях Галуа GF(2n), який відрізняється тим, що обробка коду експоненти виконується зі старших розрядів і організується по групам, що складаються з одиниці та передуючим їй нулям і здійснюється для кожної з них у вигляді однієї суміщеної операції множення на полях Галуа з використанням передобчислень, за рахунок чого досягається зменшення кількості операцій множення. 4. Вперше теоретично обґрунтовано, запропоновано та досліджено підхід до паралельного обчислення експоненти на скінчених полях Галуа, який базується на табличному методі швидкого піднесення в довільну ступінь двійки, що дозволяє практично одночасно визначити стартові значення k незалежних обчислювальних процесів. Запропонований підхід конкретизовано у вигляді трьох методів паралельного обчислення експоненти на скінчених полях Галуа, перший з який вирізняється тим, що в рамках кожного із k обчислювальних процесів здійснюється піднесення числа в ступінь, код якої містить n/k значущих бітів експоненти, розділених k-1 нульовими бітами; другий з яких вирізняється тим, що в рамках кожного із k обчислювальних процесів здійснюється піднесення числа в ступінь числа два з отриманням стартового значення для обчислення часткової експоненти, що містить в собі n/k суміжних розрядів коду експоненти; відмінність третього методу полягає в тому, що в кожному із k паралельних процесів оброблюється група фрагментів коду експоненти для яких попередньо обраховано значення експонент-шаблонів, які підносять в ступінь двійки з застосуванням спеціальних передобчислень. Запропонований підхід дозволяє прискорити експоненціювання за полях Галуа дією двох складових: одночасного виконання k незалежних обчислювальних процесів та передобчислень, що дозволяє, в підсумку досягти прискорення більш ніж в k раз в залежності від методу організації розпаралелювання. | |
| dc.description.abstractother | Nikolsky S.S. Methods for acceleration of data protection cryptographic mechanisms based on the algebra of Galois fields computer implementation. – Qualifying scientific work on manuscript rights. Thesis for a Ph.D. degree by specialty 123 - Computer engineering from the field of knowledge 12 - Information technologies. - National Technical University of Ukraine "Ihor Sikorsky Kyiv Polytechnic Institute", Kyiv, 2026. Thesis is devoted to the development of the organization of multiplicative operations of the Galois algebra of finite fields GF(2n) calculations to accelerate the implementation of public key cryptographic data protecting mechanisms in systems of remote real-time control of real word objects using IoT technologies. This goal is archived by developing methods of accelerated computer implementation of the basic operation of such cryptography - exponentiation on finite Galois fields by numbers whose length is orders of magnitude greater than the processor's bit rate. The goal and tasks of the research. The goal of the research is to accelerate the computer implementation of exponentiation on finite Galois fields - the basic operation of modern open key cryptographic mechanisms for data protection in system for remote control based on IoT technologies. To achieve the goal of the research, the following tasks were set and solved: 1. Analysis of the application of cryptographic data protection mechanisms, which use the algebra of finite Galois fields. Substantiation of the criteria for the effectiveness of means of computational implementation of the basic operation on Galois fields used in these mechanisms - exponentiation over numbers, the length of which significantly exceeds the processor's bit capacity; a review, from the standpoint of these criteria, of the existing methods and algorithms for calculating the exponent on Galois fields, determining the possibilities of increasing the speed of its computational implementation. 2. Theoretical justification, development and research of the method of accelerated exponentiation, which organizes the processing of code bits, exponents are processed in the direction from the highest to the lowest in groups of h digits, while all multiplication operations within the group are replaced by one such operation using recalculations, which is performed before each exponentiation, and a group of h operations of raising to the square is replaced by one operation of raising to the power of 2 h using precomputations , which are performed when changing the forming Galois polynomial field, which allows to reduce the number of multiplicative operations. 3. Theoretical substantiation, development and research of the method of speeding up the calculation of the exponent on Galois fields due to the organization of the combination in time of the execution of two operations on the finite Galois field - squaring and multiplication by a constant number, due to which the acceleration of important for cryptographic applications operation of exponentiation on Galois fields is ensured. 4. Theoretical substantiation, development and research of the method of speeding up the calculation of the exponent on Galois fields by organizing the processing of the code of the exponent from the higher orders in groups consisting of a unit and the sequence of zeros, whose preceding it and carried out for each of them in the form of one combined operation of multiplication on Galois fields using precomputations, due to which a reduction in the number of multiplication operations and, accordingly, an acceleration of the calculation of the exponent on the finite Galois field is achieved. 5. Theoretical substantiation, development and research of the method of speeding up the calculation of the exponent on Galois fields by organizing the parallel calculation of the exponent on finite Galois fields, which is distinguished by the fact that within each of the k calculation processes, a number is raised to a power, the code of which contains n/k significant bits of the exponent, divided by k-1 zero bits, due to which the number of operations of multiplication and raising to the power of two on the Galois field is carried out decreases by k times. 6. Theoretical substantiation, development and research of the method of speeding up the calculation of the exponent on the Galois fields by organizing the parallel calculation of the exponent on the finite Galois fields, which is distinguished by the fact that within each of the k calculation processes, the number is raised to the power of two to obtain the starting value for the calculation of the partial exponent, which contains n/k adjacent digits of the exponent code, which allows to speed up the process of calculating the exponent on the fields Galois k times. 7. Theoretical substantiation, development and research of the method of speeding up the calculation of the exponent on Galois fields by organizing the parallel calculation of the exponent on finite Galois fields, which is distinguished by the fact that in each of the parallel processes a group of fragments of the exponent code is processed for which the value of the exponent templates, which are raised to the power of two using other recalculations, is pre-calculated, due to which the acceleration of the calculation on multi-core processor platforms of the exponent on Galois fields. 8. Creation of software tools for the experimental study of the effectiveness of the proposed methods and approaches to speeding up the implementation of the basic exponentiation operation for cryptographic protocols on finite Galois fields. The object of research is the calculation processes of the basic exponentiation operation on finite Galois fields for cryptographic applications, which is performed on numbers whose length is much larger than the processor's bit capacity. The subject of research is methods of organizing the computing process of exponentiation on finite Galois fields GF(2n). Research methods are based on the basic principles of the theory of finite Galois fields, the theory of recursive functions, the theory of probability, as well as the basic principles of statistical and simulation modeling. The scientific novelty of the obtained work results is as follows: 1.For the first time, a method of exponentiation on finite Galois fields GF(2 n) was developed and studied, which differs in that the bits of the exponent code are processed in the direction from high to low in groups of h digits, while all multiplication operations within the group are replaced by one such operation using recalculations, which is carried out before each exponentiation, and a group of h operations of raising to the square is replaced by one operation of raising to the power of 2h using precomputations , which are performed when changing the forming Galois polynomial field, which allows to reduce the number of multiplicative operations on the Galois field to implement exponentiation. 2. For the first time, a method of accelerated calculation of the exponent on Galois fields was developed and researched, which differs from the known ones in that it organizes the combination in time of the execution of two multiplicative operations on the Galois field - squaring and multiplying by a constant number, due to which the acceleration of this operation, which is important for cryptographic applications, is ensured. It is theoretically proven and experimentally confirmed that the proposed method allows to speed up the computer implementation of exponentiation on Galois fields by 4.5 times compared to known methods. 3. For the first time, the method of calculating the exponent on Galois fields GF(2n) was substantiated, developed and researched, which is distinguished by the fact that the processing of the exponent code is carried out from higher orders and is organized into groups consisting of a unit and zeros preceding it and is carried out for each of them in the form of one combined multiplication operation on Galois fields using recalculations, due to which a reduction in the number of multiplication operations is achieved. 4. For the first time, an approach to the parallel calculation of the exponent on finite Galois fields was theoretically substantiated, proposed and investigated, which is based on the tabular method of rapid raising to an arbitrary power of two, which allows to determine almost simultaneously the starting values for k independent computational processes. The proposed approach is specified in the form of three methods of parallel calculation of the exponent on finite Galois fields, the first of which is distinguished by the fact that within each of the k calculation processes, a number is raised to a power, the code of which contains n/k significant bits of the exponent, separated by k-1 zero bits; the second of which is distinguished by the fact that within the framework of each of the k calculation processes, the number is raised to the power of two to obtain the starting value for calculating the partial exponent, which contains n/k adjacent digits of the exponent code; the difference of the third method is that in each of the k parallel processes, a group of exponent code fragments is processed for which exponent template values are pre-calculated, which are raised to the power of two using special recalculations. The proposed approach makes it possible to speed up exponentiation by Galois fields by the action of two components: simultaneous execution of k independent computational processes and pre-calculations, which allows, in the end, to achieve an acceleration of more than k times depending on the method of organizing parallelization. | |
| dc.format.extent | 187 с. | |
| dc.identifier.citation | Нікольський, С. С. Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа : дис. … д-ра філософії : 123 Комп’ютерна інженерія / Нікольський Сергій Сергійович. - Київ, 2026. - 187 с. | |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/82152 | |
| dc.language.iso | uk | |
| dc.publisher | КПІ ім. Ігоря Сікорського | |
| dc.publisher.place | Київ | |
| dc.subject | поля Галуа | |
| dc.subject | експоненціювання | |
| dc.subject | безпека інформації | |
| dc.subject | кібербезпека | |
| dc.subject | криптографія | |
| dc.subject | цілісність інформації | |
| dc.subject | безпека | |
| dc.subject | передобчислення | |
| dc.subject | паралельні обчислення | |
| dc.subject | розподілені системи | |
| dc.subject | Galois fields | |
| dc.subject | exponentiation | |
| dc.subject | information security | |
| dc.subject | сybersecurity | |
| dc.subject | cryptography | |
| dc.subject | integrity of information | |
| dc.subject | security | |
| dc.subject | precomputations | |
| dc.subject | parallel computation | |
| dc.subject | distributed systems | |
| dc.subject.udc | 004.056.5 | |
| dc.title | Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа | |
| dc.title.alternative | Methods for acceleration of data protection cryptographic mechanisms based on the algebra of Galois fields computer implementation | |
| dc.type | Thesis Doctoral |
Файли
Контейнер файлів
1 - 1 з 1
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 8.98 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: