 (9)
де  и  - довiльнi булевi функцiї, визначенi на множинах  и  вiдповiдно.
Викладений метод iлюструється наступним прикладом синтезу SAC-функцiї 1-го порядку от 6 змiнних.
Згiдно з викладеним вище, кожне з пiдмножин  i  на якi подiляється множина змiнних має включати не менше  елементи. Нехай  та  Множину пар змiнних, що належать вказаним пiдмножинам довiльно але з урахуванням наведених вище умов визначимо таким чином :
Функцiю  можна вибрати довiльно, в тому числi вважати що вона вiдсутня. Функцiю  можнa довiльно вибрати у виглядi:  . Тодi вiдшукувана SAC-функцiя 1-го порядку може бути представлена таким чином:
Одержана булева функцiя вiдповiдає SAC-критерiю нульового та першого порядкiв i має нелiнiйнiсть, що дорiвнює 20 .
Запропонованi методи синтезу значно простiшi за вiдомi. що базуються на використаннi перетворень Уолша та вiдмiну вiд них не накладають технологiчних обмежень на кiлькicть змiнних, оскiльки в процесi наведеного синтезу немає потреби в зберiганнi в пам’ятi таблицi iстиностi aбо спектру Уолша.
В заключному розділі роботи з використанням запропонованого способу досліджено криптостійкість найбільш поширених на практиці алгоритмів криптографічного перетворення- DES ( зворотний, симетричний алгоритм), та SHA (незворотний алгоритм).
Одержані булеві функції еквівалентної DES системи рівняні, аналіз яких показав, що нелінійність булевих функцій не є максимальною, а значить, DES-алгоритм є потенційно вразливим до методів порушення захисту в основі яких лежить лінійна апроксимація.
ОСНОВНI РЕЗУЛЬТАТИ РОБОТИ
- Запропонований та теоретично обгрунтований пiдхiд i засiб оцiнки рiвня захищеностi криптографiчних алгоритмiв на основi одержання та аналiзу еквiвалентної системи булевих функцiй, до якої завжди може бути зведено будь-який алгоритм криптографiчного захисту iнформацiї, що має блочну структуру.
- Проведено аналiз та дослiдження властивостей булевих функцiй, що визначають можливiсть аналiзу та визначення рiвня захищеностi алгоритму вiд спроб злому аналiтичними методами.
- Запропоновано та теоретично обгрунтувано метод формального синтезу булевих функцiй, якi задовольняють критерiю максимуму повної та умовної ентропiї (Strict Avalanche Criterion - або скорочено - SAC-критерiю ).
- Розроблено метод одержання алгебраїчних нормальних форм булевих SAC-функцiй нульового та вищого порядкiв, який не потребує об’ємiв пам’ятi, експоненцiйно залежних вiд кiлькостi змiнних, що дозволяє одержувати SAC-функцiї вiд великої кiлькостi змiнних (бiльше сотнi).
- Розроблена iтерацiйна органiзацiя обчислювального процесу для одержання значень систем булевих функцiй криптографiчних алгоритмiв.
- Виробленi рекомендацiї щодо прискорення обчислення криптографiчних алгоритмiв за рахунок паралельної органiзацiї обчислювальних процесiв.
- Проведена оцiнка рiвня надiйностi захисту найбiльш поширених криптографiчних алгоримiв захисту iнформацiї.
Основнi результати дисертацiї опублiкованi в таких роботах.
- Самофалов К.Г., Марковский А.П., Бардис Николас, Гаваагийн Улзисайхан. Метод получения булевых баллансных SAC-функций для систем защиты информации. Вicн. Нацiонального Технiчного Унiверситету. Iнформатика, управлiння та обчислювальна технiка. Вип.31. 1998 - С. 3-13.
Дисертантом запропоновано метод одержання балансних SAC-функцiй шляхом композицiї часткових SAC-функцiй вiд меншої кiлькостi змiнних.
- Марковский А.П., Бардис Николас, Гаваагийн Улзисайхан. Об одном подходе к повышению эффективности и уровня защищенности систем хранения информации на основе хеш-памяти. Вicн. Нацiонального Технiчного Унiверситету. Iнформатика, управлiння та обчислювальна технiка. Вип.31. 1998 - С.14-23.
Дисертантом розроблено спосiб одержання хеш-сигнатур з використанням лiнiйних булевих функцiй, показана можливiсть використання хеш-адресацiї iнформацiйних повiдомлень для реалiзацiї криптографiчних перестановок.
- Марковский А.П., Бардис Николас, Абу-Усбах А.Н., Кищенко А.В. Анализ защищенности криптографических алгоритмов с использованием булевых функций. - Вicн. Нацiонального Технiчного Унiверситету. Iнформатика, управлiння Автоматизацiя, керування та обчислювальна технiка. Вип.31. 1998 - С.24-34.
Бардисом Нiколасом запропоновано пiдхiд i засiб оцiнки рiвня захищеностi криптографiчних алгоритмiв на основi одержання та аналiзу булевих функцiй еквiвалентних до дослiджуваний алгоритмiв захисту iнформацiї.
- Бардис Е., Бардис Н. Влияние степени заполнения памяти на єффективность и надежность хеш-адресации. Деп. в УкрНДIНТI N 1965 Ук-94 Деп.-К., 1994.-7 с.
Дисертантом дослiджена залежнiсть швидкодiї систем хеш-адресацiї та можливостi захисту iнформацiї вiд ступеню заповнення адресового простору. Одержанi аналiтичнi оцiнки вказаних залежностей.
- Бардис Е., Бардис Н., Марковский А.П. Об одном подходе к уменьшению информационной избыточности хранения данных в хеш-памяти. Деп. в Укр НДIНТI N2163 Ук-94 Деп.-К., 1994.-12 с.
Дисертантом запропоновано спосiб пiдвищення захисту iнформацiї в хеш-пам’ятi за рахунок зберiгання в пам’ятi не повних кодiв, а їх хеш-сигнатур, cпосiб обчислення яких функцiонально пов’язаний з хеш-алгоритмом.
Бардiс Нiколас. Розробка пiдходу i застосування апарату булевих функцiй для аналiзу i cинтезу ефективних криптографiчних алгоритмiв систем захисту iнформацiї. -рукопис.
Дисертацiя на здобуття наукового ступеня кандидата технiчних наук за спецiальностю 05.13.13- обчислювальнi машини, системи та мережi. Нацiональний Технiчний Унiверситет України “Київський Полiтехнiчний Інститут”, Київ, 1998.
Дисертацiя присвячена розробцi пiдходу до аналiзу рiвня захищеностi та синтезу алгоритмiв криптографiчного захисту iнформацiї на основi використання апарату булевих функцiй. Показана тотожнiсть проблем розкриття криптографiчних алгоритмiв та розв’язання системи булевих рiвнянь, якi визначаються булевими функцiями бiтових перетворень, що реалiзуються алгоритмом. Встановлено критерiї оцiнки складностi розв’язання систем булевих рiвнянь, та засоби їх практичного визначення. Запропонованi методи синтезу булевих функцiй, якi забезпечують високий рiвень криптостiйкостi алгоритмiв, побудованих на їх основi. З використанням запропонованого пiдходу проведено дослiдження криптостiйкостi найпоширенiших алгоритмiв захисту iнформацiї.
Ключовi cлова: криптографiя, булевi функцiї, SAC- функції.
Бардис Николас. Разработка подхода и использования аппарата булевых функций для анализа и синтеза эффективных криптографичных алгоритмов систем защиты информации. - рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 - вычислительные машины, системы и сети. Национальный Технический Университет Украины “Киевский Политехнический Институт”, Киев, 1998.
Диссертация посвящена исследованию общего подхода к анализу уровня защищенности алгоритмов криптографической защиты информации на основе использования аппарата булевых функций и разработке формализованных методов получения булевых функций специальных классов, пригодных для использования в криптографических алгоритмах. Показано, что любой криптографический алгоритм, независимо от математического принципа, положенного в его основу, может быть представлен эквивалентной системой булевых функций. Доказана эквивалентность проблемы вскрытия криптографического алгоритма решению системы нелинейных булевых уравнений, которые определяются булевыми функциями битовых преобразований, реализуемых алгоритмом. Предложено оценивать устойчивость криптографических алгоритмов к вскрытиям аналитического типа через оценку сложности решения эквивалентной системы нелинейных булевых уравнений.
Установлены критерии оценки сложности решения эквивалентных систем булевых уравнений посредством оценки специфических криптографических свойств булевых функций : соответствие критерию максимуму полной и условной энтропии, нелинейности и попарной некоррелированости, предложены способы их практического определения. Теоретически исследованы криптографические свойства булевых функций, в частности установлены критерии определения соответствия SAC-критерию по алгебраической нормальной форме функций, на основе которых предложены формализованные методы синтеза булевых функций этого класса, которые могут использоваться в качестве функциональной основы устойчивых к вскрытиям аналитическими методами алгоритмов криптографической защиты информации. В частности, предложены методы получения баллансных SAC-функций и SAC-функций нулевого и высших порядков, манипулирующих с алгебраическими нормальными формами и, в отличие от известных методов, не требующих для своей реализации обьемов памяти, экспоненциально зависящего от числа переменных. Использование предложенных методов позволяет практически снять технологические ограничения на синтез SAC-функций от большого числа переменных. Предложены итерационная организация для эффективного вычисления значений систем булевых функций, обладающих специфическими криптографическими свойствами, на универсальном микропроцессоре, С использованием предложенного подхода выполнено исследование криптостойкости наиболее распространенных алгоритмов защиты информации.
Основные результаты работы состоят в следующем:
- Предложен и теоретически обоснован подход и способ оценки уровня защищенности криптографических алгоритмов на основе получения и анализа эквивалентной системы булевых функций, к которой всегда может быть сведен любой алгоритм криптографической защиты информации, обладающий блочной структурой.
- Проведен анализ и исследование свойств булевых функций, которые определяют возможность анализа и определения уровня защищенности алгоритма от попыток вскрытия аналитическими методами.
- Предложен и теоретически обоснован метод формального синтеза булевых функций, которые удовлетворяют критерию максимума полной и условной энтропии (Strict Avalanche Criterion-SAC-критерию).
- Разработан метод получения алгебраических нормальных форм булевых SAC-функций нулевого и высших порядков, который не требует обьемов памяти, экспоненциально зависящих от числа переменных, что позволяет получать SAC-функции от большого числа переменных (больше сотни).
- Разработана итерационная организация вычислительного процесса для получения значений систем булевых функций криптографических алгоритмов.
- Выработаны рекомендации по ускорению вычислительного процесса вычисления значений систем булевых функций.
- Проведена оценка уровня надежности защиты наиболее распространенных криптографических алгоритмов защиты информации.
Ключевые слова: криптография, булевы функций, SAC функции.
Bardis Nikolas. Development of an approach and applications of Boolean Functions tools to analysis and synthesis of effective Cryptographic algorithms of Information Security Systems.- manuscript.
Thesis for a Ph.D. degree by speciality 05.13.13.- Computers, Systems and Networks, National Technical University of Ukraine, “Kiev Polytechnic Institute”, Kiev 1998.
The aim of the thesis is to develop an approach for analysis the level and to synthesis of cryptographic information security algorithms on the basis of Boolean function tools application. The identity of the problem of cryptographic algorithm break, with solution of a system of Boolean equations, which are determined by Boolean functions of bit transformations being implemented by the algorithm has, been shown. Criteria for evaluation of equivalent Boolean equation system solution difficulty are worked out as well as means of their practical identification are presented. Methods of Boolean function synthesis, which ensure a high level of cryptoresistance for the algorithms constructed on this basis, are suggested. Verification of cryptoresistance of the most widespread algorithms for information security have been carried out with application of the above approach.
Key words: Cryptography, Boolean functions, SAC functions.
| 
