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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

НАЦIОНАЛЬНИЙ ТЕХНIЧНИЙ УНIВЕРСИТЕТ УКРАЇНИ

“ КИЇВСЬКИЙ ПОЛIТЕХНIЧНИЙ IНСТИТУТ “

Cпецiальнiсть 05.13.13 - Обчислювальнi машини, системи та мережi

Автореферат дисертацiї на здобуття наукового ступеня

кандидата технiчних наук

Розробка пiдходу i застосування апарату булевих

функцiй для аналiзу i синтезу ефективних

криптографiчних алгоритмiв захисту iнформацiї

Бардiс Нiколас

Київ - 1998

Дисертація є рукопис.

Робота виконана у Національному Технічному Університеті України (НТУУ) “Київський Політехнічний Інститут”

на кафедрі обчислювальної техніки.

Науковий керівник - Член-кореспондент НАН України,

доктор технічних наук, професор

Самофалов Костянтин Григорович,

професор кафедри обчислювальної техніки НТУУ

Офіційні опоненти:

- Доктор технічних наук, професор Брюхович Євгеній Iванович завідуючий відділом інституту кібернетики ім.В.М.Глушкова НАН України.

- Кандидат технічних наук Селігей Олександр Мінович, начальник конструкторського бюро НВО “Електронмаш”.

Провідна установа :

Iнститут проблем реєстрації інформації НАН України.

Відділ проблемно-орієнтованих інформаційно-обчислювальних систем.

Захист відбудеться 25.01.1999 р. в 14:30 на засіданні спеціалізованної ради Д26.002.02 в Національному Технічному Університеті України “Київський Політехнічний Інститут” (м.Київ, пр.Перемоги, 37, корп.18, ауд.306)

Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 252056, м.Київ, пр.Перемоги, 37, Вченому секретарю НТУУ “КПI”.

З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України “КПI”.

Автореферат розісланий 25 грудня 1998 р.

Вчений секретар

спеціалізованої вченої ради М.М. Орлова

АНОТАЦIЯ

Метa дисертацiйної роботи полягає в розробцi засобу оцiнки рiвня захищеностi криптографiчних алгоритмiв захисту iнформацiї на основi їx анал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й з заданими криптографiчними властивостями, зокрема функцiй, що задовольняють критерiю максимуму повної та умовної ентропiї (Strict Avalanche Criterion - або скорочено - SAC-критерiю ).

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

Дослiдження криптостiйкостi icнуючих алгоритм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внянь. До тaкої системи рiвнянь завжди може бути зведено будь-який алгоритм криптографiчного захисту iнформацiї, що має блочну структуру.

Базовi теореми, тверження i наслiдки, що встановлюють умови вiдповiдностi булевих функцiй критерию максимуму повної та умовної ентропiї ( Strict Avalanche Criterion ), по алгебраїчнiй нормальнiй формi функцiї.

Метод синтезу балансних SAC-функцiй, який забезпечує, в порiвняннi з вiдомими пiдходами, мiнiмiзацiю часу для одержання функцiй такого класу з високами показниками нелiнiйностi.

Метод синтезу алгебраїчних нормальних форм булевих SAC-функц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 cучасних систем захисту iнформацiї є криптографiчне перетворення iнформацiї. Швидке зростання продуктивностi cучасних засобiв обчислювальної технiки та можливостi органiзацiї паралельного вирiшення задач криптоаналiзу на об'єднаних у мережi комп'ютерах рiзко знижує рiвень захищеностi багатьох традицiйних криптографiчних алгоритмiв. До цього слiд додати значнi успiхи, зробленi в останнi роки в галузi теоретичного криптоаналiзу, що також вимагає суттєвого перегляду icнуючих та розробки нових криптограф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ї, до теперiшнього часу залишаються не розв'язаними ряд важливих проблем, таких, зокрема як проблема оцiнки з єдиних методичних позицiй рiвня захищеностi криптографiчних алгоритмiв, насамперед вiд аналiтичних та комбiнованих методiв порушення захисту. Потребують дальшого вирiшенння i важливi для практики задачi автоматизованого cинтезу криптостiйких алгоритмiв. Зокрема широко застосовуємий метод одержання SAC-функц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 в дисертац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дки, які встановлюють за алгебраїчною нормальною формою булевих функцiй наявнiсть у них специфiчних криптографiчних властивостей, що зумовлюють високу криптостiйкiсть алгоритмiв захисту iнформацiї побудованих на таких булевих функцiях.

Розроблено метод синтезу алгебраїчних нормальних форм булевих SAC-функцiй нульового та вищого порядкiв, який не потребує об'ємiв пам'ятi експонцiйно залежних вiд числа змiнних i дозволяє одержувати SAC-функцiї вiд великої кiлькостi змiнних ( бiльше сотнi).

Запропоновано метод формалiзованого синтезу булевих функцiй, що вiдповiдають критерiю максимуму повної та умовної ентропiї (балансних SAC-функцiй), що генерують бiльш якiснi у криптографiчному вiдношеннi функцiї, а також забезпечують значно бiльшу продуктивнicть в порiвняннi з вiдомими методами одержання SAC -функцiй.

Практична цiннicть результатiв дисертацiйної роботи полягає у тому, що застосування запропонованого засобу оцiнки рiвня захищеностi криптографiчних алгоритмiв дозволяє суттєво пiдвищити надiйнiсть перевiрки криптостiйкостi алгоритмiв захисту iнформацiї . Розробленi методи формалiзованого синтезу SAC-функцiй доведенi до практичної реалiзацiї у виглядi програм і їх застосування дозволяє значно прискорити процес розробки нових криптографiчних алгоритмiв захисту iнформацiї, забезпечуючи при цьому бiльшу криптостiйкicть алгоритму.

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

Апробацiя роботи Основнi результати дисертацiйної роботи обговорювалися на мiжнароднiй конференцiї “Cучаснi проблеми робототехнiки та обчислювальної технiки” (Грецiя, Афiни, 10-14 вересня 1997 р.)

Публiкацiї Основнi результати дисертацiйної роботи опублiковано в 5 статтях.

Структура на обсяг дисертацiї. Дисертацiйна робота складається з вступу, чотирьох роздiлiв, заключної частини та додаткiв, що викладенi на 132 сторiнках друкованого тексту, мiстить 5 малюнкiв, 4 таблиць, список лiтератури з 150 найменувань.

У вступ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ї з використанням унiверсальних i спецiaлiзованих обчислювальних засобiв.

В другому роздiлi викладена концептуальна основа загального методу об'єктивної оцiнки криптостiйкостi алгоритмiв захисту iнформацiї через визначення складностi розв'язання еквiвалентної cистеми булевих р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зу та синтезу cистем булевих функцiй, що забезпечують криптостiйкicть алгоритму.

В третьому роздiлi виконано теоретичне дослiдження булевих функцiй, що відповідають критерiю максимуму умовної ентропiї (Strict Avalanche Criterion - або скорочено - SAC) - функцiй, які лежать в основi cинтезу криптостiйких алгоритмiв захисту iнформацiї. На основi одержаних теоретичних положень запропонованi та дослiдженi формальнi методи побудови функцiй цього класу. Зокрема розроблено методи синтезу балансових SAC-функцiй, а також метод одержання SAC-функцiй високих порядкiв, що не наклає технологiчних обмежень на синтез функцiй вiд великої кiлькостi змiнних.

В четвертому роздiлi з використанням запропонованого способу оцiнки рiвня захищеностi криптографiчних алгоритмiв виконано детальний аналiз найбiльш поширених на практицi зворотних та незворотних алгоритмiв: DES та SHA. Досліджено практичні аспекти реалізаціє криптографічних алгоритмів на універсальних та спеціалізованих обчислювальних засобах.

У висновках наведен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 алгоритми криптограф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х алгоритм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дбору, або ж анал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в лiнiйної апроксимацiї. Найпошириним засобом протидiї методам пiдбору є збiльшення розрядностi криптографiчного перетворення. Але цей простий засiб, окрiм зниження продуктивностi практично не впливає на криптостiйкicть алгоритму проти анал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й:

( 1 )

Для вирiшення задач криптоаналiзу стосовно зворотнiх алгоритмів, тобто за умови, що заданi вектори та , cистема (1) булевих функцій породжує систему булевих рiвнянь яка має бути розв'язана вiдносно компонент вектора . Стосовно незворотнiх алгоритмiв, вiдомi вектори та i цiллю криптоаналiзу є вiднаходження колiзiруючого -розрядного вектора такого, що . Вирішення цієї задачі також можна розглядати, як процесс розв'язання відносно системи булевих рівнять, в яку перетворюється система булевих функцій (1). Тобто, незалежно від класу криптографічного алгоритму задача порушення його захисту в математичному плані зводиться до розв'язання системи булевих рівнянь, на яку перетворюється система (1) булевих функцій, що еквівалентна досліджуємому алгоритмові. Таким чином, складнiсть задачi аналiтичного криптоаналiзу можна оцiнювати за складнiстю розв'язання відповідноі системи булевих рівнянь, що може бути одержана з системи (1) булевих функцій, еквiвалентної алгоритму.

Вiдомо, що розв'язання систем нелiнiйних булевих рiвнянь (1) в загальному випадку являє собою досить складну математичну задачу, проте при недостатньо криптостiйкому алгоритмi застосуванням спецiальних прийомiв система (1) може бути суттєво спрощена i в кiнцевому рахунку розв'язана комбiнованим використанням аналiтичних методiв та направленого пiдбору. Зокрема, якщо рiвняння системи (1) мають малу нелiнiйность, то можуть бути застосованi методи лiнiйної апроксимацiї, що на практицi дозволить на багато порядкiв зменшити число варiантiв пiдбору. Виконаний в роботi аналiз показав, що основними критерiями складностi розв'язання системи булевих рiвнянь, до якої зводиться при криптоаналізі еквівалентна система (1) являються:

кiлькiсть рiвнянь - ;

ентропiя кожної з булевих функцiй, які складають систему (1): cкладнiсть її роз'язання тим бiльша, чим бiльша ентропiя кожної з функцiй, причому умовою максимальної ентропiї є баланснiсть булевої функцiї.

нелiнiйнiсть - тобто хемiнгова вiдстань до найближчої лiнiйної булевої функцiї: чим бiльша нелiнiйнiсть функцiй, що складають систему (1), тим складнiшим є її розв'язання;

попарна незалежність кожної пари булевих функцiй, які складають систему (1). Для забезпечення складностi розв'язання cистеми рiвнянь (1) необхiдною умовою є досягнення некорельованості значень компонент вихідного вектору , що забезпечеється максимальним значенням умовної ентропiї булевих функцій, побудованих композицією пар булевих функцiй, які складають систему (1) ;

максимальне значення умовної ентропiї кожної з булевих функцiй вiдносно будь-якої iз змiнних, на яких визначена функцiя. Виконання цієї умови робить неефективним розв'язання систем булевих рівнянь за методом виключення змінних. Формально, булева функцiя визначена на множинi набoрiв змiнних , задовольняє критерiю максимуму умовної ентропiї або SAC- критерiю , якщо виконується:

(2)

З точки зору синтезу нових, стiйких до аналiтичних методiв розкриття, алгоритмiв, то найбiльш суттєвою проблемою є одержання SAC-функцiй. В роботi виконано теоретичне дослiдження цього важливого для систем захисту iнформацiї класу булевих функцiй, що дозволило розробити ряд методiв одержання таких функцiй.

Будь-яка булева функцiя завжди може бути представлена в виглядi:

(3)

Теоретичною основою розроблених методiв побудови алгебраїчних нормальних форм булевих SAC - функцiй являється наступна, доведена в роботi теорема.

Теорема Для того, щоб булева функцiя задовольняла SAC необхiдно i достатньо, щоб кожна з функцiй була балансною.

Використовуючи цю теорему в роботi доведено важливе для практики положення:

Булева функцiя задовольняє SAC-критерiю, якщо цьому критерiю задовольняє функцiя , а функцiя є лiнiйною функцiєю, або, що те ж саме: додавання до SAC-функцiї лiнiйної функцiї не порушує її вiдповiднiсть SAC- критерiю.

Виходячи з наведеної теореми задача одержання SAC-функцiї трансформується в задачу вiднаходження системи балансних булевих функцiй от змiнних:

(4)

где - множина всiх можливих значень булевих змiнних . Булева функция, що задовольняє SAC-критерiю формується у виглядi:

(5)

На основi наведених теоретичних засад розроблена методика формального одержання алгебраїчної нормальної форми SAC -функцiї, яка полягає в послiдовному виконаннi cлiдуючих дiй:

Множина змiнних раздiляється на двi непересічних між собою пiдмножини: та .

Довiльним чином задається вiдношення , що спiввiдносить кожний елемент множини одному з елементiв множини . Практично це вiдношення визначає множину пар елементiв множин та .

Будуються k булевих функцiй , , причoму , у виглядi:

(6)

причому функцiї i вибираються довiльно.

Будуються булевих функцiй , , причoму , у виглядi:

(7)

де - функцiя, що вибирається довiльним чином i не залежить вiд .

Вiдшукувана булева SAC-функцiя може буди одержана як диз'юнкція всiх кон'юнкцiй змiнних xi и ранiш одержаниx часткових балансних булевих функцiй

(8)

Доведено, що запропонований метод забезпечує одержання SAC-функцiї, максимальнa степiнь термiв якої cтановить при гарантованiй нелiнiйностi . Доведенi теоретичнi засади можуть слугувати за основу розробки методiв побудови SAC-функцiй високих порядкiв.

Нижче наведено запропонований в роботi метод генерацiї SAC-функцiй m- порядка:

Множина змiнних подiляється на двi пiдмножини:та , причому кiлькiсть змiнних в кожнiй з пiдмножин має бути не меншим за .

Визначається множина пар змiнних, що не належать одночасно множинам та , причому кiлькiсть пар, в якi входить кожна iз змiнних має бути не меншим за , а самi пари, що входять до множини не повиннi повторюватися.

SAC-функцiя - го порядку формується в такому виглядi:

(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зу 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.

Размещено на Allbest.ru

...