Метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем

Ескіз

Файли

Matiyko_dys.pdf (4.17 MB)

Дата

2023

Автори

Науковий керівник

Олексійчук, Антон Миколайович

Назва журналу

Номер ISSN

Назва тому

Видавець

КПІ ім. Ігоря Сікорського

Анотація

Матійко А.А. Метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття наукового ступеня доктора філософії з галузі знань 12 Інформаційні технології за спеціальністю 125 Кібербезпека. – Національний технічний університет України “Київський політехнічний інститут імені Ігоря Сікорського”, Київ, 2023. Дисертаційна робота присвячена вирішенню актуальної наукової задачі, яка полягає у розробці методу побудови симетричних NTRU-подібних шифросистем, що є обґрунтовано стійкими відносно атак на основі підібраних відкритих текстів. Протягом останніх років проведено численні дослідження у галузі квантових комп’ютерів, які використовують квантово-механічні явища для розв’язання обчислювальних задач, що є практично нерозв’язними за допомогою звичайних комп’ютерів. Оскільки створення квантових комп’ютерів є лише питанням часу, це серйозно загрожує конфіденційності та цілісності інформації у спеціальних інформаційно-комунікаційних системах. Виходячи з цього, у 2016 р. Національний інститут стандартів і технологій США оголосив відкритий конкурс зі стандартизації асиметричних постквантових криптопримітивів. Майже третина усіх криптосистем і протоколів, представлених на цьому конкурсі, належить до NTRU-подібних. (Зауважимо, що асиметрична шифросистема NTRU є на сьогодні однією з найшвидших та представляє широкий клас постквантових криптосистем з однойменною назвою, стійкість яких базується на складності знаходження коротких векторів у деяких решітках в евклідовому просторі). До того ж, новітній постквантовий алгоритм відкритого шифрування, стандартизований в Україні (ДСТУ 8961:2019 «Скеля») також є NTRU-подібним. Однією з актуальних задач сучасної криптології є створення постквантових симетричних шифросистем, стійкість яких, аналогічно асиметричним, базується на складності розв’язанні лише однієї обчислювальної задачі. Зауважимо, що сучасні блокові чи потокові шифри не володіють такою властивістю. При цьому тривіальний метод побудови симетричних шифросистем, виходячи з асиметричних (шляхом “засекречування відкритого ключа”), виявляється цілком неприйнятним, оскільки не гарантує стійкості отриманих шифросистем відносно певних атак на основі підібраних відкритих текстів. Єдиною відомою на сьогодні симетричною NTRU-подібною шифросистемою є алгоритм NTRUCipher, запропонований в 2017 р. Розробником шифросистеми проведено попередній аналіз її стійкості та наведено рекомендації стосовно вибору параметрів, які гарантують її стійкість відносно розглянутих ним атак. Поряд з тим, як показують подальші дослідження, шифросистема NTRUCipher є вразливою відносно деяких інших атак, причому природний спосіб модифікувати цю шифросистему задля підвищення її стійкості не приводить до успіху. Як наслідок, постає потреба у створенні методів побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем, які відрізняються за сутністю від відомої. Таким чином, існує певне протиріччя між потребами практики в обґрунтовано стійких постквантових (зокрема, NTRU-подібних) симетричних шифросистемах та відсутністю методів побудови таких шифросистем. Зазначене протиріччя приводить до наукової задачі, яка полягає у розробці методу побудови симетричних NTRU-подібних шифросистем, що є обґрунтовано стійкими відносно атак на основі підібраних відкритих текстів. Для розв’язання поставленої наукової задачі використано методи теорії скінченних полів, теорії дискретного перетворення Фур’є на скінченних абелевих групах, лінійної алгебри, теорії ймовірностей та кореляційного криптоаналізу. Метою дисертаційної роботи є створення обґрунтовано стійких симетричних NTRU-подібних шифросистем для систем захисту інформації в інформаційно-комунікаційних системах. Об’єктом дослідження у дисертаційній роботі є процес перетворення інформації з використанням сучасних NTRU-подібних шифросистем, а предметом дослідження – методи побудови та обґрунтування стійкості зазначених шифросистем відносно атак на основі підібраних відкритих текстів. В роботі вперше отримано аналітичні співвідношення для оцінювання ймовірності оборотності випадкових поліномів, які використовуються в NTRU-подібних шифросистемах. На відміну від відомого співвідношення для ймовірності оборотності випадкового рівноймовірного елементу кільця зрізаних поліномів, отримані співвідношення є справедливими для більш загальної схеми формування випадкових поліномів. Вони базуються на застосуванні апарату перетворення Фур’є розподілів ймовірностей на скінченному полі та надають змогу оцінювати (а в окремих практично важливих випадках – обчислювати) значення ймовірності оборотності випадкових поліномів, що використовуються в ролі компонентів секретних ключів NTRU-подібних шифросистем. Удосконалено аналітичні співвідношення для оцінювання ймовірності помилкового розшифрування повідомлень в NTRU-подібних шифросистемах. На відміну від раніше відомих, отримані співвідношення є справедливими для усіх видів сучасних NTRU-подібних шифросистем (як асиметричних, так і симетричних). Окрім того, вони дозволяють оцінювати ймовірність помилкового розшифрування повідомлень в NTRU-подібних шифросистемах при фіксованому ключі, надаючи, таким чином, більш адекватну інформацію про частоту виникнення помилок при розшифруванні. Дістав подальший розвиток метод оцінювання стійкості симетричних шифросистем NTRUCipher та NTRUCipher+ за рахунок дослідження трьох додаткових атак на ці шифросистеми. Для зазначених атак отримано аналітичні оцінки складності та показано, що, принаймні, одна з них може бути реалізована в режимі реального часу (хоча й не дозволяє відновлювати ключі шифросистем, а тільки відрізняти послідовності їхніх шифрованих повідомлень від суто випадкової послідовності). Вперше запропоновано метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем. Показано, що на відміну від відомих симетричних NTRU-подібних шифросистем, запропоновані шифросистеми мають обґрунтовану стійкість відносно атак на основі підібраних відкритих повідомлень, яка базується на складності еталонної обчислювально складної задачі Decision-Ring-LWE. Практичне значення одержаних результатів полягає в тому, що дисертанткою розроблено програмні реалізації, які дозволяють в режимі реального часу обчислювати значення параметрів для побудови запропонованих обґрунтовано стійких NTRU-подібних шифросистем, обчислювати ймовірність оборотності випадкових поліномів та ймовірність помилкового розшифрування повідомлень у довільних NTRU-подібних шифросистемах. Крім того, отримані в роботі результати дозволяють: - зменшити ймовірність необоротності випадкового полінома в кільці Rn.q (з 0,5 до 2 15 10- , - ) за рахунок належного вибору параметрів q і n NTRU-подібної шифросистеми; -вибирати параметри NTRU-подібних шифросистем, що забезпечують належне (мале) значення ймовірності помилкового розшифрування повідомлень при фіксованому секретному ключі; -встановити, що трудомісткість BKW-атаки на шифросистему NTRUCipher+ є в 15 2 - 69 2 разів вище в порівнянні з трудомісткістю аналогічної атаки на шифросистему NTRUCipher; -довести, що шифросистема NTRUCipher+ є цілком вразливою відносно розрізнювальної атаки, яка може бути реалізована в режимі реального часу (при цьому найбільше значення обсягу матеріалу, потрібного для реалізації атаки становить 19 t -2 ); – обирати параметри NTRU-подібних шифросистем, які гарантують їхню стійкості на заздалегідь визначеному рівні - (зокрема n -631, q -2693 , d -56 при 128 --2 , n -883, q -8089, d -168 при 256 --2 ). Наукові та практичні результати дисертаційної роботи реалізовані в Службі зовнішньої розвідки України в результаті виконання НДР “Дорадо” та НДР “Сарган”, а також в науково-технічних розробках АТ “Інститут інформаційних технологій”.

Опис

Ключові слова

кібербезпека, криптоаналіз, постквантова криптографія, криптосистеми на основі решіток, статистичні атаки, NTRU-подібні шифросистеми, обґрунтування стійкості, ймовірність помилкового розшифрування, cybersecurity, cryptanalysis, post-quantum cryptography, latticebased cryptosystems, statistical attacks, NTRU-like encryption schemes, provable security, decryption failure probability

Бібліографічний опис

Матійко, А. А. Метод побудови обґрунтовано стійких симетричних NTRU-подібних шифросистем : дис. … д-ра філософії : 125 Кібербезпека / Матійко Александра Андріївна. – Київ, 2023. – 183 с.

URI

https://ela.kpi.ua/handle/123456789/63144

DOI

Зібрання

Дисертації (СК №1)
Дисертації (вільний доступ)