Методи формування s-блокових конструкцій випадкового типу з покращеними показниками стійкості для блокових симетричних шифрів

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

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

РАДІОЕЛЕКТРОНІКИ

Спеціальність: 05.13.21 - системи захисту інформації

УДК 681.3.06:519.248.681

Автореферат

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

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

Методи формування S-блокових конструкцій випадкового типу з покращеними показниками стійкості для блокових симетричних шифрів

Широков Олексій Вікторович

Харків 2010

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

Робота виконана в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент Лисицька Ірина Вікторівна, Харківський національний університет радіоелектроніки, доцент кафедри безпеки інформаційних технологій

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

доктор технічних наук, професор Сорока Леонід Степанович, в.о. ректора Академії митної служби України, м. Дніпропетровськ

доктор технічних наук, професор Олексійчук Анатолій Миколайович, професор Інституту спеціального зв'язку та захисту інформації Національного технічного університету України «Київський політехнічний інститут», м. Київ

Захист відбудеться «7» грудня 2010 р. о 10 годині на засіданні спеціалізованої вченої ради К 64.052.05 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна,14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна,14.

Автореферат розісланий «6» листопада 2010 р.

Вчений секретар спеціалізованої вченої ради М.М. Рожицький

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

випадковість комбінаторний підстановка

Актуальність теми. Симетричні методи шифрування зберігають свою придатність й переваги для використання, як в ближній, так і в далекій перспективі, і питання їх подальшого удосконалення складає одне з важливіших й актуальніших напрямів розвитку сучасної криптографії.

Історично для України судьба склалася так, що вона не має симетричного блочного шифру власної розробки. І сьогодні діючим стандартом в Україні є ГОСТ 28147-89, розроблений у колишньому Радянському Союзі та сьогодні перезатверджений як ДСТУ ГОСТ 28147:2009. Цей стандарт, однак, в світі останніх досягнень сучасної криптографії вже не може рахуватися достатньо надійним. На заміну діючих стандартів шифрування новими сьогодні пішли все країни-лідери засвоєння сучасних інформаційних технологій.

Актуальність прогресивного подальшого розвитку технологій симетричного шифрування ярко підтверджується організацією й проведенням міжнародних конкурсів, минулі в останні десятиріччя: AES (по вибору нового стандарту шифрування США), а також NESSIE і CRYPTREC.

По цьому ж шляху пішла й Україна. 30 червня 2005 р. на сайті ДСТЗІ України з'явилася офіційна об'ява о проведенні конкурсу по висуванню кандидатів на національній стандарт шифрування. В процесі проведення конкурсу було розглянуто п'ять пропозицій, з котрих на остаточний розгляд було представлено чотири (шифри ADE, Калина, Мухомор и Лабіринт). В відборі й аналізі представлених рішень прийняли участь вчені та розробники колективу ЗАТ ІІТ, котрі представили на конкурс дві своїх пропозиції (Калина, Мухомор). Звичайно, робота над експертизою проектів потребувала засвоїти накопичений міжнародний досвід, й форсувати розробку власних підходів та методик, які дозволяють прискорити процес аналізу та прийняття рішень. За результатами конкурсу прийнято рішення зупинитися на загальноприйнятому мировому стандарті Fips-197. Національні пропозиції оказались або занадто близькими за конструкцією до мирового лідера, або недостатньо прозорими з точки зору очікуваних показників стійкості в порівнянні з світовим авторитетом. Це означає, що робота по пошуку більш перспективних рішень, по подальшому розвитку й удосконаленню технологій блочного симетричного шифрування для України зберігає свою актуальність та затребуваність.

Актуальність теми даної роботи визначається необхідністю розвитку національної криптографічної бази по розробці нових симетричних блочних алгоритмів шифрування. Інтереси роботи зосереджуються на вивченні та дослідженні перспективних принципів побудування блоків нелінійних замін для сучасних шифрів, котрі багато в чому визначають їх криптографічні властивості й показники.

Зв'язок роботи з науковими програмами, планами, темами. Автор роботи приймав участь в розробках ЗАТ ІІТ-а по блочним симетричним шифрам, що були представлені на український конкурс по відбору кандидата на національний стандарт шифрування в частині обґрунтування й оцінки поданих рішень, а також у виконанні НДР №09-06 Дослідження та розробка комбінованих інфраструктур з відкритими ключами на основі використання існуючих ІВК та системи на ідентифікаторах (ДР № 0109U002498), що виконувалась в ХНУРЕ, в частині реалізації протоколів з застосуванням блочних симетричних шифрів.

Мета та задачі досліджень. Метою досліджень є розробка (удосконалення) методів побудування (відбору) підстановочних конструкцій (S-блоків) блочних шифрів з покращеними крипрографічними показниками стійкості.

Для досягнення поставленої мети вирішені наступні основні задачі:

1. Оцінити сучасний стан і методи проектування і розробки S-блокових конструкцій БСШ, що будуються з використанням математичного апарату булевої алгебри. Виконати дослідження алгебраїчних показників блоків замін сучасних шифрів, у тому числі шифрів, представлених на український конкурс.

2. Розробити (розвинути) альтернативний підхід до побудови (відбору) S-блоків з використанням показників випадковості, зокрема, удосконалити методи відбору підстановок за комбінаторними показниками (інверсіям, зростанням і циклам) на основі посилювання існуючих критеріїв.

3. Дослідити (оцінити) очікувану ефективність (реалізуємість) двох нових запропонованих методів відбору випадкових підстановок, що будуються на основі оцінки близькості емпіричних законів розподілу XOR таблиць і емпіричних законів розподілу зсувів таблиць лінійних апроксимацій S-блоків теоретичним законам розподілів ймовірностей випадкових підстановок.

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

5. Виконати дослідження показників випадковості і кореляційних властивостей S-блокових конструкцій сучасних блокових симетричних ширах (БСШ), у тому числі і БСШ, представлених на український конкурс з вибору кандидата національного стандарту.

6. Виконати дослідження кореляційних властивостей і інших криптографічних показників S-блоків, відібраних по новій системі критеріїв з метою підтвердження їх ефективності.

7. Виробити пропозиції і рекомендації по побудові S-блоковіх конструкцій для перспективних шифрів.

Об'єктом досліджень є процеси криптографічних перетворень з використанням блокових симетричних шифрів.

Предметом досліджень є криптографічні показники S-блокових конструкцій сучасних шифрів.

Методи досліджень. При виконанні дисертаційної роботи використовувались наступні методи: теорії ймовірностей; математичної статистики; комбінаторіки і системнного аналізу; методи статистичних випробувань; методи булевої алгебри.

Наукова новизна отриманих результатів дисертаційної роботи полягає в наступному:

1. Удосконалені та розроблені нові методи відбору випадкових підстановок за комбінаторними, диференціальними і лінійними показниками, що дозволяють відібрати підстановки з покращеними криптографічними показниками.

2. Теоретично обґрунтовані значення параметрів відбору і відповідні цим значенням параметри проходження випадкових підстановок, що реалізуються.

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

4. Вперше показано, що досконалі підстановки (підстановки, відібрані за новими критеріями), не дивлячись на те, що вони не реалізують мінімально можливих значень максимумів XOR таблиць і зсувів таблиць лінійних апроксимацій, володіють вищими показниками по середньому числу векторів, що задовольняють критерію розповсюдження і кореляційної імунності.

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

Практична значимість отриманих результатів полягає у наступному:

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

2. Встановлена можливість відбору досконалих підстановок, що володіють теоретичними значеннями показників випадковості підстановки, вибраної з повного ансамблю підстановок симетричеської групи довільним (випадковим) чином.

3. Теоретично і експериментально встановлено, що для підстановок порядку 2⁸, що використовуються в сучасних шифрах (байтових підстановок), із загального числа підстановок симетричної групи 8,57810⁵⁰⁶ досконалими і близькими до них є близько 6,86210⁵⁰² підстановок.

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

5. Запропоновані конкретні підстановочні конструкції для вживання в перспективних шифрах.

Основні результати роботи використані в ЗАТ Інститут Інформаційних Технологій, а також в учбовому процесі в Харківському національному університеті радіоелектроніки.

Особистий внесок здобувача. Дисертація є результатом самостійної роботи автора. У роботах, написаних в співавторстві, претендентові належить: у [1] постановка статистичного експерименту і статистична обробка результатів експериментальних досліджень за оцінкою впливу значень критеріїв відбору на відсоток проходження (відбору) випадкових підстановок; [2] дослідження диференціальних властивостей зменшеної моделі шифру Лабіринт; [3] виведення розрахункових співвідношень за оцінкою відсотка проходження підстановок при виборі параметрів відбору, що забезпечують збіг значень емпіричних законів розподілу зсувів таблиць лінійних апроксимацій випробовуваних підстановок з теоретично обчисленими значенням, і експериментальна перевірка відповідності розрахункових даних результатам статистичного експерименту по відбору досконалих (що пройшли нові критерії відбору) підстановок.

Апробація результатів. Основні положення дисертаційної роботи та результати досліджень доповідалися і обговорювалися на конференціях: Перша Міжнародна науково-технічна конференція Комп'ютерні науки и технології (Білгород, 2009р.); ХII Міжнародна науково-практична конференція Безпека інформації в інформаційно-телекомунікаційних системах (Київ, 2009р.) - два доклади; ХIII Міжнародна науково-практична конференція Безпека інформації в інформаційно-телекомунікаційних системах (Київ, 2010р.) - чотири доклади.

Публікації. Результати дисертаційної роботи опубліковані в трьох статтях у наукових журналах та збірниках наукових праць, що входять до переліку наукових фахових видань України, та 7 матеріалах і тезах наукових конференцій.

Структура та об'єм дисертації. Робота складається зі вступу, чотирьох розділів, чотирьох додатків. Загальний обсяг дисертації складає 227 сторінок, з яких основний зміст викладено на 173 сторінках друкованого тексту, 3 рисунки, 52 таблиці. Список використаних джерел складається з 159 найменувань на 16 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі до дисертації обґрунтовано актуальність проблеми, сформульована мета роботи, дано стислу анотацію отриманих результатів, відзначено їх наукову новизну та практичне значення.

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

Актуальність прогресивного подальшого розвитку технологій симетричного шифрування ярко підтверджується організацією й проведенням міжнародних конкурсів, що пройшли в останні десятиріччя (AES по вибору нового стандарту шифрування США, а також NESSIE та CRYPTREC).

В цій роботі під технологіями блочного симетричного шифрування розуміється як проектування та розробка безпосередньо шифрів, так і забезпечуючи методи проектування й розробки шифрів відповідні теоретичні та практичні методи оцінки показників стійкості (надійності) шифрів (методи криптоаналізу).

По цьому ж шляху рухається й Україна. 30 червня 2006 року на сайті ДСТЗІ України з'явилась офіційна об'ява о проведенні конкурсу по висуванню кандидатів на національний стандарт шифрування. В процесі проведення конкурсу було розглянуто п'ять пропозицій, з котрих на остаточний розгляд було представлено чотири (шифри ADE, Калина, Мухомор та Лабіринт). У відборі й аналізі представлених рішень прийняли участь й вчені і розробники колективу ЗАТ ІІТ, котрі самі представили на конкурс дві своїх пропозиції (Калина, Мухомор). Звичайно, робота над експертизою проектів потребувала засвоїти міжнародний досвід, і форсувати розробку власних підходів і методик, що дозволяють прискорити процес аналізу та прийняття рішень. По результатам конкурсу прийнято рішення зупинитися на загально признаному світовому стандарті Fips-197. Національні пропозиції виявилися або надто близькими за конструкцією до світового лідера, або недостатньо прозорі з точки зору сподіваних показників стійкості в порівнянні з світовим авторитетом. Це означає, що робота по пошуку більш перспективних рішень, подальшому розвитку й удосконаленню технологій блочного симетричного шифрування для України зберігає свою актуальність та затребуваність й сьогодні.

Зосереджується увага на новому підході в теорії та методах криптоаналізу, що розвивається на кафедрі БІТ ХНУРЕ. Він орієнтований, з одного боку, на використання при визначенні очікуваних показників стійкості БСШ результатів аналізу їх зменшених версій, а з другої, уточненій за останній час на основі вивчення властивостей та показників випадкових підстановок та зменшених моделей шифрів, що розглядаються як підстановочні перетворення, концепції (нової ідеології) визначення показників стійкості БСШ к атакам диференційного та лінійного крипто аналізу. У цьому випадку вдається подолати труднощі аналізу повномасштабних моделей (алгоритмів) за рахунок розробки й дослідження зменшених моделей прототипів, для котрих обчислювальних ресурсів, що маються, виявляється вже достатнім. Виникає можливість вирішити багато які задачі аналізу й порівняння показників стійкості відповідних великих версій.

Ілюструється важлива роль та місце блочних симетричних шифрів у сучасних технологіях захисту інформації, на прикладі широко розповсюдженого SKIP протоколу, реалізовано в багатьох сучасних стандартах у вигляді гібридних шифрів, у котрих асиметричні шифри використовуються для зашифрування секретного ключа, який у свою чергу використовуються для зашифрування фактичного повідомлення з застосуванням симетричних криптографічних методів.

На прикладі шифру Rijndael кратко обговорюються сучасні методи проектування й розробки БСШ, де відмічається важлива роль, яка приділяється вибору S-блоків (блоків нелінійної заміни) при конструюванні цього шифру.

Викладається характеристика сучасних підходів до оцінки показників стійкості БСШ к атакам диференційного та лінійного криптоанализу, які пов'язуються в більшості робіт з диференційними та лінійними властивостями S-блоків, що використовуються практично у всіх шифрах.

Формулюються мета й задачі роботи, які визначаються актуальністю рішення ряду теоретичних та практичних задач удосконалення технологій блочного симетричного шифрування, спрямованих, в першу чергу, на пошук нових рішень по побудуванню підстановочних перетворень з покращеними криптографічними показниками по відношенню до найбільш потужних атак лінійного та диференційного криптоаналізу.

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

Відмічається також запропонований у свій час на кафедрі БІТ ХНУРЕ підхід до відбору підстановок, що будується на основі оцінки показників їх випадковості (значень числа циклів, зростань та інверсій), доповнений обмеженнями на максимально припустимі значення таблиць XOR різниць та таблиць лінійних апроксимацій. Вже давно виникло бажання знайти зв'язок між відміченими підходами й, зокрема, оцінити місто й корисність критеріїв випадковості в спільному комплексі питань, пов'язаних з рішенням задач побудування криптографічно стійких підстановочних конструкцій. Цьому напрямку й буде в подальшому присвячена дана робота.

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

К показникам стійкості нелінійних перетворень в термінах булевих функцій відносять: збалансованість вихідної послідовності; нелінійність функції; кореляційний імунітет; критерій розповсюдження; алгебраїчну степінь перемінних; значення функції автокореляції та інші. В розділі розглянута розроблена в цьому напрямку термінологія, введені терміни й означення.

Окремо розглядаються критерії оцінки криптографічних властивостей S-блоків, побудовані з використанням алгебраїчних методів серед яких: нормалізоване значення квадратів помилок, нормалізована коваріація і варіація, кореляційний коефіцієнт,лавинний вектор або лавинна змінна, критерій бітовій незалежності, критерій нелінійності, суворий лавинний критерій, максимальний порядок Суворого Лавинного Критерію, лінійна апроксимаційна таблиця LAT, XOR таблиця.

Подальший матеріал присвячений викладенню суті відомих підходів до побудуванню (генерації) криптографічно стійких S-блоків.Висвітлюються не всі відомі підходи та методи конструювання S-блокових конструкцій. Увага зосереджується лише на тих роботах, котрі відрізняються найбільшою теоретичною завершеністю, а також практичною спрямованістю та результативністю.

В числі регулярних методів конструювання S-блоків що відрізняються теоретичною завершеністю розглядаються два підходи, що відібрані на основі виконаного аналізу великої кількості публікацій у даному напрямку. Це перш за все підходи й результати, викладені в роботах К. Нюберг, а також розробки групи австралійських вчених під керівництвом Дж. Себеррі.

У відношенні до підходу, що розвинутий групою Дж. Себеррі робиться висновок, що запропонований підхід, не глядячи на красивий математичний апарат, котрий дозволив виконати строге обґрунтування властивостей S-блоків, що конструюються, він все ж таки представляється достатньо складним для практичного застосування. Наші спроби скористатися цим методом для породження S-блоків розміру (n = 8) закінчилися невдачею, ми не змогли отримати набір підходящих булевих функцій необхідного розміру. Підкреслимо також, що нам не вдалося знайти й свідоцтв застосування цього підходу для конструювання S-блоків іншими дослідниками.

Більш прогресивними бачаться пропозиції й розробки К. Нюберг. Саме вони знайшли подальший розвиток та практичне застосування при побудові таких сучасних шифрів, як Camellia, Rijndael, ADE, Калина, Лабіринт та інші.

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

Найбільш результативна частина розділу присвячена дослідженню криптографічних властивостей S-блоків сучасних шифрів з допомогою викладеного апарату булевих функцій, доповнених перевіркою виконання критеріїв випадковості. Для здійснення цих досліджень були розроблені програмні комплекси, які дозволили одразу отримати (розрахувати) дві групи криптографічних показників. В одну групу увійшли:число зростань, число циклів, число інверсій, -рівномірність S-блоку, максимальне значення лінійної апроксимаційної таблиці.

В другу групу показників, які, орієнтовані на алгебраїчний опис S-блоків з допомогою математичного апарату булевих функцій, ввійшли: збалансованість булевих функцій S-блоку, середня й мінімальна за множиною функцій S-блоку кількість термів АНФ, середня й мінімальна за змінними множин функцій кількість термів, кореляційний імунітет S-блоку , критерій розповсюдження (суворий лавинний критерій) функції , алгебраїчна степінь булевих поліномів S-блоку , сума квадратів автокореляцій, тобто,

й пов'язане с цим показником нормалізоване значення квадратів помилок.

.

Численні розрахункові й статистичні результати не вдається подати в авторефераті. Ми тут лише відмітимо, що були розглянуті й перевірені по визначеним вище групам показників S-блоки шифрів AES, ADE, Лабіринт, Мухомор, Калина, FOX, ICEBERG, Camellia, GrandCru та Anudis.

Аналіз показав, що усі розглянуті S-блоки сучасних шифрів виходять за рамки випадкових підстановок по інверсіям, зростанням і циклам, і, що більш цікаво, не задовольняють таким важливим показникам булевих функцій як критерій розповсюдження та не володіють кореляційною імунністю.

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

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

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

Випадковою при цьому підході вважається підстановка, котра по інверсіям, зростанням і циклам попадає в інтервали, що задаються середньоквадратичним відхиленням кожного із цих параметрів від математичного очікування відповідного асимптотичного (нормального) закону розподілу, що відповідає значенню критерію відбору по комбінаторним показникам a = 1 (a нормуючий коефіцієнт перед середньоквадратичним відхиленням, котре також визначається з теоретичного розподілу).

Виконуючи оцінку цих результатів з позицій теперішнього часу, робиться висновок, що запропоновані в відомих роботах параметри відбору є вельми м'якими. Досвід показує, що границі, які використовуються в відомому підході, проходять підстановки з далеко не кращими криптографічними властивостями. Тому в роботі вивчаються можливості підвищення жорсткості критеріїв відбору по інверсіям, зростанням і циклам. Реалізуючи цю задачу було виконано теоретичне обґрунтування цієї можливості з подальшою наступною експериментальною перевіркою. Результати розрахунків підтвердили можливість здійснення значень інверсій, зростань і циклів навіть співпадаючих з теоретичними значеннями, які випливають з асимптотичних законів розподілу відповідних параметрів (можна реалізувати критерії відбору практично для параметру a = 1). Розрахунки свідчать, що показниками, співпадаючими з теоретичними (одночасно по інверсіям, зростанням і циклам), володіють 4% підстановок 16-го порядку (експеримент 1%). Для байтових підстановок відповідні цифри складають 0,002% (експеримент 0,001%). Отже, підвищення жорстокості критеріїв відбору привело до суттєвого зменшення множини допустимих підстановок (старі критерії проходило близько 50% всіх підстановок).

Подальші дослідження концентруються на двох нових методах (нових критеріях) відбору випадкових підстановок. Ці два критерії були сформульовані як додатні к трьом розглянутим вище.

Основна ідея побудування нових критеріїв містилась в тому, щоб перенести властивості криптографічних перетворень, властиві блочним симетричним шифрам, що розглядаються як підстановки, на підстановочні конструкції в цілому, тобто була поставлена задача розширити критерії відбору випадкових підстановок за рахунок додатних критеріїв випадковості, характерних саме для шифрів.

Ідея підходу міститься на доведених вченими кафедри БІТ в останній час двох теоремах, які визначають теоретичні закони розподілу переходів таблиць XOR різниць та зміщень таблиць лінійних апроксимацій.

Нагадаємо спочатку сутність запропонованих критеріїв відбору. У цитує мій роботі вони були сформульовані у вигляді четвертого і п'ятого критеріїв (1-ий, 2-ий та 3-ій це комбінаторні критерії) наступним чином:

- підстановка задовольняє критерію випадковості 4, якщо закон розподілу переходів

,

,

її таблиці XOR різниць для входів, що приписуються до ненульових характеристик, відповідає за критерієм згоди Колмогорова теоретичному закону розподілу переходів для випадкових підстановок, тобто найбільше значення модуля різниці теоретичного і емпіричного інтегральних законів розподілу вірогідності задовольняє умові

F_Т(x_k) - F(x_k)? b;

- підстановка задовільняє критерію випадковості 5, якщо закон розподілу однотипних переходів

,

для масок входу і виходу, , її таблиці лінійних апроксимацій відповідає за критерієм згоди Колмогорова теоретичному закону розподілу лінійних апроксимацій випадкових підстановок, тобто найбільше значення модуля різниці теоретичного і емпіричного інтегральних законів розподілу вірогідності задовольняє умові.

F_Т(x_k) - F(x_k)? c.

Тут k* половинні значення максимумів переходів XOR таблиці і зміщень LAT (лінійної апроксимаційної таблиці) випадкової підстановки відповідно. Значення граничних параметрів b і c були визначені як такі що підлягають уточненню за результатами експериментів. Отже в роботі і розглядається задача обґрунтування граничних значень параметрів b і c в критеріях відбору для запропонованих правил.

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

Досліджувалися підстановки порядку 2⁴ та 2⁸, що є найбільш популярними при конструюванні сучасних шифрів.

Спочатку були використані граничні значення параметрів b і c, які були розраховані відповідно до критерію Колмогорова (для = 0,5 з таблиці розподілу Колмогорова-Смірнова маємо ). Отже для підстановок порядку 2⁴ (в критерії Колмогорова використовується параметр n = 225) маємо . Відповідно для підстановок порядку 2⁸ (параметр критерію Колмогорова n = 255²) приходимо до результату.

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

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

Далі була виконана теоретична оцінка очікуваного числа випадкових підстановок с заданими розподілами переходів парних різниць XOR таблиць зміщень таблиць лінійних апроксимацій, тобто з'ясовувалися питання практичної реалізуємості підстановок с граничними показниками, що відповідають еталонним.

В основі отриманих результатів лежить використання рівняння, котре виконується для ймовірності події, яка міститься в тому, що випадкова взята підстановка буде мати перехід вхідної різниці в вихідну рівний (максимально можливому значенню таблиці XOR різниць)

.

Подібний вираз можна отримати і для таблиць лінійних апроксимацій.

В результаті для практично цікавих ситуацій використання в шифрах S-блоків з розмірами бітових входів рівними n=4 і n=8 для вірогідності отримання (генерації) S-блоків випадкового типу з параметрами таблиць XOR різниць і лінійних апроксимацій, що повторюють теоретичні розподіли таблиць, приходимо до таких значень:

(при отриманні цього виразу враховано, що максимальне значення може досягатися в одному з ненулевих рядків XOR таблиці).

Подібні результати отримані і для таблиць лінійних апроксимацій.

Результати експериментів підтвердили можливість генерації підстановок з показниками, що відповідають еталонним значенням законів розподілу ймовірностей. Підстановки, що проходять систему самих жорстких критеріїв відбору по всім п'яти критеріям запропоновано називати досконалими.

Результатом цього напрямку досліджень стало побудування (відбір) досконалих підстановок порядків та .

Окремо також були виконані дослідження на відповідність новим критеріям відбору підстановочних конструкцій сучасних БСШ. Всі вони крім шифру DES опинилися далекими від досконалих.

В четвертому розділі роботи виконується оцінка ефективності підстановок, відібраних за новою системою критериїв.

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

Подальші дослідження концентруються на визначенні кореляційних властивостей підстановочних конструкцій. В основі використаної методики розрахунок матриці залежностей та матриці відстаней. Вони визначаються як

,