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

Abstract

Пустовіт О.С. Застосування теорії екстремальних графів до сучасних проблем інформаційної безпеки. - Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – Інформаційні технології. – Інститут телекомунікацій і глобального інформаційного простору Національної академії наук України, Київ, 2021. Дисертаційна робота присвячена вирішенню актуальної науково-практичної проблеми розробки методів захисту інформації, пов’язаних з викликом Великих Даних та появою перших зразків квантового комп’ютера. У першому розділі розглядаються задачі класичної криптографії від багатьох змінних, що пов’язані зі створенням криптографічних ключів. Коротко оглянуто виники міжнародного тендеру NIST (інституту стандартизації інформаційних технологій Сполучених Штатів Америки) на створення постквантових публічних ключів для розв’язання задач безпечного обміну інформації та постквантових алгоритмів електронного підпису. Напрямок криптографії від багатьох змінних у цьому тендері конкурує з напрямками алгоритмів, що базуються на решітках, криптосистем, що використовують коди захисту від шумів, криптосистем, що використовують супереліптичні криві та алгоритмів побудованих з використанням хеш функцій. В липні 2020 року розпочався останній третій раунд цього проекту. Результати відбору в галузі алгоритмів захисту обміну інформації (шифрування) не сприятливі для класичної криптографії від багатьох змінних – жодний з алгоритмів цього класу не залишився у списку кандидатів на переможця. Зазначимо, що класична криптографія від багатьох змінних використовує відображення простору шифрограм степені 2. Це мотивує дослідження криптосистем від багатьох змінних, що базуються на відображеннях необмеженої степені або таких, що задають взаємно-однозначну відповідність. Саме цьому напрямку і присвячено перший розділ дисертації. У ньому визначені основні алгебраїчні об’єкти криптографії від багатьох змінних. Це перш за все афінний простір вимірності n над скінченним комутативним кільцем K (алфавітом для текстів). У другому розділі було імплементовано потоковий алгоритм та детально досліджено вибрану функцію шифрування G з алгоритму, що використовує властивості графів A(n,K). Було розглянуто інформацію про ці графи та їх проективну границю A(K), що використовується в алгоритмі. Граф 𝐴(𝐹 ) є нескінченним q – регулярним 𝑞 деревом. Задання графу 𝐴(𝐹 ) вирішує проблему презентації графу рівняннями у 𝑞 Гільбертовому просторі 𝐹. 𝑞 Важливою категорією інформаційного простору є довіра до документів. Легко побачити, що навіть користування надійними засобами шифрування не забезпечує повної довіри до документів, тому що треба рахуватися із шумами у каналах та проблемами безпечного збереження файлів у електронних сховищах, де документи можуть бути підроблені, пошкоджені комп’ютерними вірусами, технічними помилками в роботі обчислювальної техніки та інше. Останнім часом постійно зростає загроза потужних кібертерористичних атак на сховища, їх наслідки це не тільки виток інформації, але й ушкодження або фальсифікування документів. Зрозуміло, що після виявлення кібератаки потрібно робити аудит усіх файлів системи. Для задач виявлення кібератак, верифікації та автентифікації документів потрібні так звані залежні від ключiв хеш-функції (автентифікаційні коди повідомлень або MACи) які залежать. від гасла. Хеш-функція потрібна для генерації скомпенсованої форми оригінального документа довільно обраного розміру. Таку форму називають хешем або дайджестом документа, її використовують у різних криптографічних застосуваннях. Хеш-функція h працює з файлом довільного розміру n, її значення має фіксований розмір. Третій розділ присвячено задачам симетричної криптографії, а саме, потоковому шифруванню та створенню чутливих дайджестів електронних документів, що залежать від ключа. Симетрична криптографія не є частиною постквантової криптографії, але при дослідженні захищеності алгоритмів також потрібно розглядати можливість атак супротивника з використанням квантового комп’ютера. У випадку дайджестів вже визначено поняття постквантової стабільності алгоритму. Критичним параметром симетричних алгоритмів є швидкодія, тому що розміри інформації для обробки постійно зростають, потрібно рахуватися з викликом Великих Даних. Потокові алгоритми симетричного шифрування потрібно підтримувати безпечними протоколами обміну ключів. Популярний протокол Діффі-Хеллмана вже не витримує атак з використанням квантового комп’ютера. Четвертий розділ присвячено побудові криптосистем з публічним ключем криптографії від багатьох змінних, що спираються на відображення необмеженої степені на відміну від першого розділу розглядається випадок бієктивних відображень. Ейлерівські перетворення афінного простору або поліноміальні відображення генеровані за лінгвістичними графами розглядаються окремо, як самостійні методи шифрування. Використано більш загальні лінгвістичні графи типу (k, k, n-k) вершини яких мають визначений першими k координатами вектору з простору 𝐾𝑛, де K – довільне комутативне кільце. Визначено напівгрупи та групи SL(K) та GL(K), що відповідають парі лінгвістичних графів L(K) та 𝐿(𝐾[𝑥,𝑥,…,𝑥 ]). Вони утворені поліноміальними 1 2 𝑛 перетвореннями простору 𝐾𝑛, що використовується як простір відкритих текстів над алфавітом K. Наведено приклади публічних ключів, побудованих на комбінації Ейлерівського перетворення з відображенням лінійної степені, що є побудованим за лінгвістичним графом над комутативним кільцем K. У п’ятому розділі абстрактні схеми протоколів обміну ключів доводяться до рівня алгоритмів у випадках Подвоєних графів Шуберта, напівгрупи всіх Ейлерівських перетворень та групи визначеною за стабільними кубічними групами GA(n,K). Приведено Tahoma протокол, назва якого походить від tame homomorphism, тобто гомоморфізму який можна обчислити за поліноміальний час. Детально описується схема для Unbalanced Oil and Vinegar (UOV) систем цифрового підпису. Зазначимо, що UOV один з кандидатів у переможці тендеру NIST PQC. Наводиться модифікація цієї системи, що елімінує багато відомих атак супротивника та підвищує її криптостійкість. Постквантовий статус цього модифікованого цифрового підпису ґрунтується на безпеці Тахома протокола, який можна використовувати для контролю доступу до інформаційної системи (ІС). У роботі пропонуються швидкі, постквантово стійкі алгоритми створення дайджестів електронних документів. Описано нові алгоритми з публічним ключем, визначені перетвореннями від багатьох змінних необмеженої степені. Досліджені властивості нових асиметричних алгоритмів шифрування типу Ель Гамаля, визначених постквантовими протоколами. Запропоновано нові алгоритми цифрового підпису, безпека яких також визначено постквантовими протоколами некомутативної криптографії, визначиними у термінах криптографії від багатьох змінних.