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

Структура та обсяг дисертації. Дисертація складається з вступу, чотирьох розділів, висновків, переліку використаних джерел і чотирьох додатків.

Повний обсяг дисертації складає 225 сторінок, з них 11 сторінок рисунків, 8 сторінок таблиць, 10 сторінок використаних джерел із 102 найменувань, 37 сторінок додатків.

криптографічний шифрування булевий

• ОСНОВНИЙ ЗМІСТ РОБОТИ
• У вступі обґрунтовується вибір теми та її актуальність, визначаються об'єкт та предмет дослідження, мета та завдання роботи, методи дослідження. Наголошено на науковій новизні результатів дисертаційного дослідження, вказано практичне значення здобутих результатів.
• У першому розділі досліджуються перспективні напрямки розвитку симетричних засобів криптографічного захисту інформації (ЗІ), обґрунтовуються критерії та показники ефективності нелінійних вузлів замін для симетричних криптографічних засобів захисту інформації (КЗЗІ). Проводяться порівняльні дослідження відомих методів формування криптографічних булевих функцій, які описують нелінійні вузли замін симетричних КЗЗІ, обґрунтовується вибір напрямку досліджень і формулюється математична постановка наукового завдання дисертаційного дослідження.
• Забезпечення безпеки інформаційних технологій покладається на симетричні засоби захисту інформації. Ключовим елементом симетричної криптографічної системи є блок нелінійного ускладнення, або нелінійний вузол замін - S-блок.
• Стійкість нелінійних вузлів замін, що здійснюють необоротні нелінійні перетворення, визначає ефективність симетричних КЗЗІ. Тому першочергового значення для підвищення ефективності симетричних засобів ЗІ набуває розробка математичних моделей і обчислювальних методів побудови нелінійних вузлів замін з поліпшеними властивостями.
• Найбільш обґрунтованим підходом визначення ефективності нелінійних вузлів замін є оцінка, яка основана на ефективності протистояння вузла заміни криптоаналітичним атакам у термінах булевих функцій. Це дозволяє використовувати загальний математичний апарат як для потокових, так і для блокових засобів ЗІ.
• Основними показниками ефективності криптографічних булевих функцій (власне і самого нелінійного вузла замін) є:
• Збалансованість (Сб) - рівність числа нулів і одиниць у вихідній послідовності:
• | {x | f(x) = 0} | = | {x | f(x) = 1}| = 2 ^n-1. (1)
• Нелінійність N_S перетворення - мінімальна відстань Хемінга між вихідною послідовністю S і всіма послідовностями афінних функцій :
• N_S = min {d(S,)}. (2)
• Строгий лавинний критерій - КР : 1 W() k.
• Найважливішими показниками, що визначають криптографічну стійкість, є показники нелінійності - мінімальна відстань Хемінга між вихідною послідовністю S і всіма вихідними послідовностями афінних функцій та значення функції автокореляції, що забезпечує витік інформаційного потоку із входу на вихід функції.
• Внутрішні переходи між поданим на входи відкритим текстом і одержаним на виході закритим текстом в нелінійних вузлах замін описуються сукупністю компонентних булевих функцій.
• Проведений аналіз нелінійних вузлів заміни, використовуваних у блокових методах криптографічного перетворення інформації (AES, SOBER, Camellia) і трьох нелінійних вузлів заміни, побудованих відповідно до відомих методів Себері, Маітри, Чжаня над кінцевим полем GF(2⁸), показує, що в цілому розглянуті нелінійні вузли є ефективними, однак такі показники, як нелінійність і значення функції автокореляції, можуть бути поліпшені.
• Переважна більшість нелінійних вузлів замін має нелінійність 112, у той час як досяжною є нелінійність 116. Значення функції автокореляції є неприпустимо високими (32 - 80) при мінімально досяжному значенні 16.
• Таким чином, розглянуті нелінійні вузли замін не дозволяють забезпечити найвищі показники стійкості симетричних КЗЗІ.
• Необхідний запас стійкості розглянутих криптоалгоритмів досягається збільшенням кількості раундів перетворення, що значно підвищує складність криптографічного перетворення та знижує їх ефективність. Перспективним напрямком досліджень є розробка математичних моделей і обчислювальних методів формування нелінійних вузлів замін з поліпшеними властивостями для підвищення ефективності симетричних КЗЗІ.
• У другому розділі розробляється математична модель нелінійних вузлів замін симетричних засобів ЗІ, яка дозволяє в термінах булевої алгебри описувати внутрішню структуру і оцінювати основні показники. Проведено аналіз і порівняльні дослідження відомих методів, заснованих на імовірнісному пошуку булевих функцій з необхідними криптографічними показниками.
• Введено показники обчислювальної ефективності евристичних методів, обґрунтовано актуальність подальшого вдосконалювання методів імовірнісного пошуку з метою підвищення їх обчислювальної ефективності.
• Для формального аналітичного опису внутрішньої структури і оцінки властивостей нелінійного вузла замін запропонована математична модель, як абстрактна сукупність таких елементів (математичної символіки):
• 1) множина вхідних векторів
• 2) множина вихідних векторів
• 3) множина відображень вхідних векторів з множини в множину вихідних векторів , тобто, кожне відображення з множини параметризується сукупністю компонентних криптографічних булевих функцій
• Вузли замін, відповідно до запропонованої моделі, задаються значеннями функцій, тобто значення на виході S-блока задаються сукупністю рівностей.
• При цьому будь-яка функція, отримана лінійною комбінацією функцій, задо-вольняє системі обмежень математичної моделі.
• Таким чином, запропонована математична модель нелінійних вузлів замін блокових симетричних КЗЗІ, на основі аналітичного опису основних структурних компонентів, системи обмежень за нелінійністю, збалансованістю, кореляційному імунітету, критерію поширення та автокореляції, дозволяє в термінах булевої алгебри описувати внутрішню структуру нелінійних вузлів замін і оцінювати основні показники їх ефективності.
• Аналіз відкритої літератури показав, що відомі методи побудови нелінійних функцій можна умовно розділити на три класи: евристичні методи, методи випадкової генерації і алгебраїчні методи. Найбільшого поширення набули алгебраїчні методи побудови криптографічних булевих функцій. Однак дані методи не дозволяють будувати функції з необхідними показниками над будь-яким векторним простором.
• У зв'язку з цим в останні роки істотно розширились дослідження евристичних методів (генетичні методи, методи імітації відпалу та методи градієнтного підйому) як більш гнучких та універсальних. Цей клас методів використовує ітераційно-оптимізаційну модель, суттю якої є відбір функцій з необхідними показниками на кожному кроці ітерації.
• Генетичні методи і методи імітації відпалу дозволяють будувати функції з найвищими показниками стійкості, однак на останньому етапі вони використовують метод градієнтного підйому, що дозволяє їм будувати функції з високою нелінійністю.
• Істотним недоліком цих методів є велика обчислювальна складність у порівнянні з методом градієнтного підйому. Таким чином, евристичні методи дозволяють конструювати функції з високою нелінійністю й найвищими показниками стійкості. Актуальним напрямком у їх розвитку є розробка нових підходів, які дозволили б із прийнятною обчислювальною складністю формувати нелінійні вузли перспективних засобів захисту інформації.
• У третьому розділі теоретично обґрунтовується евристичний метод імовірнісного формування криптографічних булевих функцій з поліпшеними властивостями. Розробляються обчислювальні алгоритми формування криптографічних булевих функцій, досліджується конструктивність запропонованого методу, проводяться порівняльні дослідження з методом випадкової генерації і найближчим аналогом - евристичним методом градієнтного пошуку.
• При розробці запропонованого методу за основу взятий евристичний метод градієнтного підйому В. Міллана, Е. Кларка, Е. Доусона. Цей метод заснований на перетворенні вихідних послідовностей та полягає в підвищенні нелінійності довільної булевої функції шляхом комплементації деякої позиції в таблиці істинності. Кожна позиція таблиці істинності відповідає унікальним вхідним даним функції. Таким чином, метод дозволяє створити повний список таких вхідних даних функції, що комплементація будь-якої відповідної даному входу вихідної позиції в таблиці істинності буде збільшувати нелінійність функції. У рамках дисертаційної роботи список таких позицій у таблиці істинності позначається як Improvement Set (поліпшена множина) функції, або IS_f.
• Визначення 1. Нехай g(x) = f(x) 1 для х = х_а та g(x) = f(x) для всіх інших х. Якщо N_g > N_f, то х_а IS_f.
• Для знаходження поліпшеної множини IS_f заданої булевої функції необхідно спочатку визначити значення коефіцієнтів перетворення Уолша - Адамара, які відповідали б величинам, близьким до абсолютного значення максимального коефіцієнта, WH_max (див. визначення 2).
• Визначення 2. Нехай f(x) є булевою функцією з перетворенням Уолша - Адамара F(w), де WH_max позначає максимальне абсолютне значення F(w). Тоді будуть існувати одна або більше лінійних функцій L_w(x), що мають мінімальну відстань до функції f(x), і для даних w буде справедливою рівність |F(w)| = WH_max.
• Визначається така множина:
• = { w: F(w) = WH_max } і = { w: F(w) = = -WH_max }.
• Також визначаються множини w, для яких значення WHТ (перетворення Уолша - Адамара) наближені до максимуму:
• = { w: F(w) = WH_max - 2},
• = { w: F(w) = - (WH_max - 2)},
• = { w: F(w) = WH_max - 4}
• і = { w: F(w) = - (WH_max - 4)}.
• Теорема 1. Нехай задана деяка булева функція f(x) з WHТ F(w) і визначені множини W⁺ = і W-W^- = . Тоді для деякого входу х існує елемент із IS_f і виконуються такі дві умови: (x) = L_w(x) для всіх w W⁺ і f(x) ? L_w(x) для всіх w W-W^-. Якщо функція f(x) не збалансована, зниження незбалансованості може бути досягнуто використанням додаткового обмеження.
• Теорема 1 дає конструктивний механізм підвищення нелінійності вихідної булевої функції за допомогою ітеративної покрокової комплементації позицій у таблиці істинності. Крім того, зауваження (12) дає механізм зниження незбалансованості розглянутої послідовності.
• Аналіз евристичних методів показує, що основні обчислювальні витрати відбуваються за рахунок повторюваних ітеративних процедур, покликаних підвищити певні показники стійкості.
• Саме за рахунок багатокрокової процедури підвищення нелінійності евристичні методи стають настільки трудомісткими, що не гарантують при цьому успішної модифікації кожної вхідної послідовності. Відповідно, знизити дані обчислювальні витрати можна за рахунок зменшення кількості відповідних процедур. Ефективним шляхом вирішення даного завдання є використання в якості вхідних даних не послідовностей, згенерованих випадково, а бент-послідовностей (бент-функцій), що дозволить знизити обчислювальну складність даних методів і домогтися високих показників стійкості.
• Концепція побудови запропонованого методу базується на використанні в якості вхідних даних бент-послідовностей, що мають свідомо привабливі криптографічні властивості. Метою методу є мінімально-можливе зниження не-лінійності для приведення її до збалансованого вигляду, що дозволяє одержати криптографічну функцію з високими показниками стійкості. Отримане і доведене твердження 1 дає конструктивний механізм визначення криптографічних булевих функцій шляхом зниження ступеня нелінійності бент-послідовності для приведення її до збалансованого вигляду.
• Твердження 1. Нехай задана бент-послідовність довжини 2ⁿ, що містить 2 ⁿ - ¹ + 2 ^{n/2 - 1} одиниць і 2 ^{n - 1} - 2 ^{n/2 - 1} нулів, або навпаки. Тоді комплементарне доповнення 2^{n/2 - 1} позицій у бент-послідовності приводить до збалансованої функції над V_n, що має нелінійність N_f 2 ^{n - 1} - 2 ^n/2 .
• Твердження 2 теоретично обґрунтовує можливість формування збалансованих булевих функцій з високими показниками нелінійності і алгебраїчного степеня, що задовольняють строгому лавинному критерію та кореляційному імунітету степеня 1.
• Твердження 2. Функції, побудовані на основі використання методу градієнтного спуску з наступним застосуванням процедур відновлення алгебраїчної нормальної форми булевої функції та афінних перетворень, є збалансованими, мають нелінійність N_f 2 ^{n - 1} - 2 ^n/2, задовольняють строгому лавинному критерію і кореляційному імунітету степеня 1 та мають високий алгебраїчний степінь, який дорівнює deg(f) n - 2, де n - розмірність векторного простору.
• Суть методу: припустимо, що маємо деякий простір, де точками відзначені послідовності всіх лінійних і афінних функцій даного векторного простору. Стартом роботи методу є формування бент-послідовності і відповідної їй бент-функції (точка 1).
• Бент-функція має максимально можливу нелінійність і мінімально можливу автокореляцію, однак вона незбалансована. Тому замінюючи біти у бент-послідовності для приведення її до збалансованого вигляду, вимірюємо відстань за Хемінгом до всіх лінійних функцій і вибираємо максимальне значення, при якому значення коефіцієнта перетворення Уолша - Адамара буде мінімальним.
• Тобто, комплементуючи відповідну позицію в таблиці істинності, “відштовхуємося” від точки і переходимо в деяку точку 2, де ітеративна процедура повторюється, знову замірюється за Хемінгом відстань до всіх лінійних функцій і вибирається максимальне значення, при якому значення коефіцієнта перетворення Уолша - Адамара буде мінімальним. Шляхом виконання ітераційних процедур одержуємо точку, у якій збалансована нелінійна булева функція має некритичне падіння нелінійності. Таким чином, запропонований метод дозволяє заздалегідь визначити, яку кількість комплементацій необхідно виконати, щоб при незначному зниженні нелінійності привести бент-функцію до збалансованого вигляду.
• Функціонування евристичних методів описується випадковим процесом, а формування булевої функції з тими або іншими показниками стійкості є випадковою подією, тобто значення нелінійності й автокореляції випадково сформованої булевої функції є випадковою величиною.
• Як видно з наведених даних, евристичний метод градієнтного спуску дозволяє формувати криптографічні функції з заданими показниками нелінійності більше 112 з імовірністю 1, з нелінійністю більше 114 з імовірністю 0.48ч0.49, з нелінійністю 116 з імовірністю 0.5ч0.52.
• З наведених даних видно, що евристичний метод градієнтного спуску дозволяє формувати криптографічні функції з показником автокореляції 24 з імовірністю 0,25, метод градієнтного пошуку дозволяє формувати функції з подібними характеристиками з імовірністю 0,1, а метод випадкової генерації малоефективний і не дозволяє робити функції з показником автокореляції 24.

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