Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа
Дата
2026
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Нікольський С.С. Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії за спеціальністю 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 раз в залежності від методу організації розпаралелювання.
Опис
Ключові слова
поля Галуа, експоненціювання, безпека інформації, кібербезпека, криптографія, цілісність інформації, безпека, передобчислення, паралельні обчислення, розподілені системи, Galois fields, exponentiation, information security, сybersecurity, cryptography, integrity of information, security, precomputations, parallel computation, distributed systems
Бібліографічний опис
Нікольський, С. С. Методи прискорення комп’ютерної реалізації криптографічних механізмів захисту даних на основі алгебри полів Галуа : дис. … д-ра філософії : 123 Комп’ютерна інженерія / Нікольський Сергій Сергійович. - Київ, 2026. - 187 с.