Системи лінійних заборон над скінченним полем

Скорочена інформація про документ
dc.contributor.advisorЯковлєв, Сергій Володимирович
dc.contributor.authorКурінний, Олег Вікторович
dc.date.accessioned2020-06-20T15:26:53Z
dc.date.available2020-06-20T15:26:53Z
dc.date.issued2020-05-20
dc.description.abstractenDiploma work includes: 86 pages, 1 drawing, 2 tables, 35 references. The goal of work is improving and clarifying models and methods of algebraic cryptanalysis. The research object are information processes in systems of cryptographic security. The research subject is system of linear restrictions and its properties. In this work we overviewed existing methods of algebraic cryptanalysis and formulated problem of recovering unknown vector by partial information in the form of linear dependencies. We proposed formalization of this problem by introducing a notation of the system of linear restrictions over finite field. We constructed criterion of solution existence for the system of linear restrictions. We proved several claims about number of solutions for the system of linear restrictions generated by an unknown fixed vector. We get non-trivial upper bound on a saturation point for the system with non-zero right-hand side. We formulated decision and search problems for the system of linear restrictions and proved that these problems are Turing equivalent. We formulated several related problems and identified their complexity classes. We constructed polynomial probabilistic algorithms for decision and search problems in some partial cases. Also we constructed probabilistic heuristic algorithm for finding several solutions in some partial cases.uk
dc.description.abstractukКваліфікаційна робота містить: 86 стор., 1 рисунок, 2 таблиці, 35 джерел. Метою роботи є розвиток та уточнення алгебраїчних моделей та методів криптоаналізу. Об’єктом дослідження є інформаційні процеси в системах криптографічного захисту. Предметом дослідження є система лінійних заборон та її властивості. У даній роботі проведено огляд наявних методів алгебраїчного криптоаналізу та сформульовано задачу відновлення невідомого вектора за частковою інформацією, представленою у формі певних лінійних залежностей. Запропоновано формалізацію цієї задачі шляхом введення нотації системи лінійних заборон над скінченним полем. Побудовано критерій існування розв’язку систем лінійних заборон. Доведено ряд тверджень про кількість розв’язків системи лінійних заборон у випадку коли система лінійних заборон породжена фіксованим невідомим вектором. Отримано нетривіальну оцінку на точку насичення у випадку ненульових правих частин системи. Визначено задачі перевірки існування та пошуку розв’язку системи лінійних заборон, та доведено їх еквівалентність за Тюрінгом. Сформульовано ряд суміжних задач та доведено приналежність цих задач відповідним класам складності. Побудовано поліноміальні імовірнісні алгоритми перевірки існування та пошуку розв’язку для деяких часткових випадків. Також побудовано імовірнісний евристичний алгоритм пошуку декількох розв’язків системи лінійних заборон для деяких часткових випадків.uk
dc.format.page86 с.uk
dc.identifier.citationКурінний, О. В. Системи лінійних заборон над скінченним полем : магістерська дис. : 113 Прикладна математика / Курінний Олег Вікторович. – Київ, 2020. – 86 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/34326
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectалгебраїчний криптоаналізuk
dc.subjectсистеми лінійних заборонuk
dc.subjectalgebraic cryptanalysisuk
dc.subjectsystem of linear restrictionsuk
dc.subject.udc512.624.3uk
dc.titleСистеми лінійних заборон над скінченним полемuk
dc.typeMaster Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Kurinnyi_magistr.pdf
Розмір:
758.54 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.06 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (ММЗІ)
Магістерські роботи