Системи лінійних заборон над скінченним полем
Вантажиться...
Дата
2020-05-20
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Кваліфікаційна робота містить: 86 стор., 1 рисунок, 2 таблиці, 35 джерел.
Метою роботи є розвиток та уточнення алгебраїчних моделей та методів криптоаналізу. Об’єктом дослідження є інформаційні процеси в системах криптографічного захисту. Предметом дослідження є система лінійних заборон та її властивості.
У даній роботі проведено огляд наявних методів алгебраїчного криптоаналізу та сформульовано задачу відновлення невідомого вектора за частковою інформацією, представленою у формі певних лінійних залежностей. Запропоновано формалізацію цієї задачі шляхом введення нотації системи лінійних заборон над скінченним полем. Побудовано критерій існування розв’язку систем лінійних заборон. Доведено ряд тверджень про кількість розв’язків системи лінійних заборон у випадку коли система лінійних заборон породжена фіксованим невідомим вектором. Отримано нетривіальну оцінку на точку насичення у випадку ненульових правих частин системи. Визначено задачі перевірки існування та пошуку розв’язку системи лінійних заборон, та доведено їх еквівалентність за Тюрінгом. Сформульовано ряд суміжних задач та доведено приналежність цих задач відповідним класам складності. Побудовано поліноміальні імовірнісні алгоритми перевірки існування та пошуку розв’язку для деяких часткових випадків. Також побудовано імовірнісний евристичний алгоритм пошуку декількох розв’язків системи лінійних заборон для деяких часткових випадків.
Опис
Ключові слова
алгебраїчний криптоаналіз, системи лінійних заборон, algebraic cryptanalysis, system of linear restrictions
Бібліографічний опис
Курінний, О. В. Системи лінійних заборон над скінченним полем : магістерська дис. : 113 Прикладна математика / Курінний Олег Вікторович. – Київ, 2020. – 86 с.