МПС РФ
Московський Державний Університет
Шляхів Сполучення (МІІТ)
Кафедра «Електроніка та захист інформації»
Курсова робота з дисципліни: «Криптографічні методи захисту інформації»
На тему: «Композиції шифрів»
Виконав: Ефалов П.А.
Студент гр. АКБ-311
ІСУТЕ
Перевірив: Титов Е.В.
Москва-2003
ЗМІСТ:
Вступ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... .4
1. Комбіновані методи шифрування
Комбінування простих способів шифрування .. ... ... ... ... ... ... ... ... ... 5
2. Теорія проектування блокових шифрів ... ... ... ... ... ... ... ... ... ... ... ... ... 8
2.1. Мережі Файстеля ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 8
2.2. Прості співвідношення ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .9
2.3. Групова структура ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 9
2.4. Слабкі ключі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
2.5. Стійкість алгоритму до диференціальних і лінійному криптоаналіз ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10
2.6. Проектування S-блоків ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 11
2.7. Проектування блочного шифру ... ... ... ... ... ... ... ... ... ... ... ... ... 13
3. Блокові шифри ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 14
3.1. Алгоритм Lucifer ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 14
3.2. Алгоритм Madryga ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .15
3.2.1. Опис алгоритму Madryga ... ... ... ... ... ... ... ... ... ... ... ... 16
3.2.1. Криптоаналіз алгоритму Madryga ... ... ... ... ... ... ... ... ... ... .17
3.3. Алгоритм REDOC ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 18
3.3.1. Алгоритм REDOC III ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 18
3.4. Алгоритм LOKI ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 19
3.4.1. Алгоритм LOKI91 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 19
3.4.2. Опис алгоритму LOKI91 ... ... ... ... ... ... ... ... ... ... ... ... 21
3.4.3. Криптоаналіз алгоритму LOKI91 ... ... ... ... ... ... ... ... ... ... .21
3.5. Алгоритм Knufu і Knafre ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 22
3.5.1. Алгоритм Knufu ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... 23
3.5.2. Алгоритм Knafre ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... 23
3.6. Алгоритм ММВ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .24
3.6.1. Стійкість алгоритму ММВ ... ... ... ... ... ... ... ... ... ... ... ... ... 25
3.7. Алгоритм Blowfish ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 26
3.7.1. Опис алгоритму Blowfish ... ... ... ... ... ... ... ... ... ... ... ... 26
3.7.2. Стійкість алгоритму Blowfish ... ... ... ... ... ... ... ... ... ... ... .. 29
3.8. Алгоритм RC5 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 29
4. Об'єднання блокових шифрів ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 32
4.1. Подвійне шифрування ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 32
4.2. Потрійне шифрування ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... 33
4.2.1. Потрійне шифрування з двома ключами ... ... ... ... ... ... ... .. 33
4.2.2. Потрійне шифрування із трьома ключами ... ... ... ... ... ... ... ... 35
4.2.3. Потрійне шифрування з мінімальним ключем ... ... ... ... .. 35
4.2.4. Режими потрійного шифрування ... ... ... ... ... ... ... ... ... ... ... 35
4.2.5. Варіанти потрійного шифрування ... ... ... ... ... ... ... ... ... ... .37
4.3. Подвоєння довжини блоку ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 38
4.4. Інші схеми багаторазового шифрування ... ... ... ... ... ... ... ... ... 39
4.4.1. Подвійний режим OFB/лічильника ... ... ... ... ... ... ... ... ... ... ... .39
4.4.2. Режим ECB + OFB ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 39
4.4.3. Схема xDESi ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 40
4.4.4. П'ятикратне шифрування ... ... ... ... ... ... ... ... ... ... ... ... ... .41
4.5. Зменшення довжини ключа в CDMF ... ... ... ... ... ... ... ... ... ... ... ... 42
4.6. Відбілювання ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 42
4.7. Каскадне застосування блокових алгоритмів ... ... ... ... ... ... ... ... 43
4.8. Об'єднання декількох блокових алгоритмів ... ... ... ... ... ... ... 44
Висновок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .45
Список літератури ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 46
ВСТУП
Шіфрсістеми класифікуються за різними ознаками: за видамизахищається інформації (текст, мова, відеоінформація), з криптографічногостійкості, за принципами забезпечення захисту інформації (симетричні,асиметричні, гібридні), за конструктивним принципам (блокові і потокові)та ін При побудові відображень шифру використовуються з математичної точкизору два види відображень: перестановки елементів відкритого тексту ізаміни елементів відкритого тексту на елементи деякої множини. У зв'язкуз цим безліч шифрів ділиться на 3 види: шифри перестановки, шифри заміниі композиційні шифри, що використовують поєднання перестановок і замін.
Розглянемо останній клас шифрів, тобто шифри композиції.
На практиці зазвичай використовують два загальних принципу шифрування:розсіювання та перемішування. Розсіювання полягає у поширеннівпливу один символ відкритого тексту на багато символів шифртексту: цедозволяє приховати статистичні властивості відкритого тексту. Розвитком цьогопринципу є поширення впливу одного символу ключа на багатосимволів шифрограми, що дозволяє виключити відновлення ключа почастинах. Перемішування полягає у використанні таких шифруючихперетворень, які виключають відновлення взаємозв'язку статистичнихвластивостей відкритого і шифрованого тексту. Поширений спосібдосягнення хорошого розсіювання полягає у використанні складного шифру,який може бути реалізований у вигляді деякої послідовності простихшифрів, кожен з яких вносить невеликий внесок у значний сумарнийрозсіювання та перемішування. В якості простих шифрів найчастішевикористовують прості підстановки і перестановки. Відомі також методианалітичного перетворення, гамування, а також метод комбінованогошифрування.
Приблизно до кінця 19 століття всі використовувані шифри практичнопредставляли собою різні комбінації шифрів заміни та перестановки,причому часто досить витончених. Наприклад, використовувалися шифри зкількома таблицями простої заміни, вибір яких здійснювався взалежно від шифрування попереднього знака, в шифри заміни перестановкибудувалися з використанням спеціальних правил і т.д. Особливо надійнимишифрами відрізнявся російський «Чорний кабінет" - організація займаласярозробкою власних шифрів і дешифрування шифрів закордонних. Привідсутність сучасних методів, а головне обчислювальної техніки, данішифри могли вважатися цілком надійними. Деякі з них проіснувалиаж до другої світової війни, наприклад, широко відомий шифр «Дваквадрата »застосовувався німцями аж до 1945 року (метод дешифруванняданого шифру був розроблений радянськими криптографами і активновикористовувався під час війни).
1. Комбіновані методи шифрування
Найважливішою вимогою до системи шифрування є стійкість даноїсистеми. На жаль, підвищення стійкості за допомогою будь-якого методуприводить, як правило, до труднощів і для шифрування відкритого тексту і прийого розшифрування. Одним з найбільш ефективних методів підвищення стійкостішифртексту є метод комбінованого шифрування. Цей методполягає у використанні і комбінуванні кількох простих способівшифрування. Шифрування комбінованими методами грунтується нарезультати, отримані К. Шенноном. Найбільш часто застосовуються такікомбінації, як підстановка і гама, перестановка і гама, підстановка іперестановка, гама і гамма. Так, наприклад, можна використовувати методшифрування простою перестановкою в поєднанні з методом аналітичнихперетворень або текст, зашифрований методом гамування, додатковозахистити за допомогою підстановки.
Розглянемо кілька прикладів:
Приклад 1. Візьмемо в якості відкритого тексту повідомлення: «Я пишукурсову ».
Захистимо цей текст методом простої перестановки, використовуючи якключа слово "зачет" і позначаючи пробіл буквою "ь". Виписуємо буквивідкритого тексту під буквами ключа. Потім букви ключа розставляємо валфавітному порядку. Виписуємо букви по стовпцях і отримуємо шифртексту:ььоіууяусшрюпкв.
Отримане повідомлення зашіфруем за допомогою методу підстановки:
Нехай кожного символу російського алфавіту відповідає число від 0 до 32. Теє букви А буде відповідати 0, букві Б - 1 і т.д. Візьмемо такожякесь число, наприклад, 2, яке буде ключем шифру. Додаючи до числа,відповідному певного символу 2, ми отримаємо новий символ,наприклад, якщо А відповідає 0, то при збільшенні 2 отримуємо В і такдалі. Користуючись цим, отримуємо новий шифртексту: ююркххбхуьтасмд.
Отже, маючи відкритий текст: «Я пишу курсову», після перетвореньотримуємо шифртексту: ююркххбхуьтасмд, використовуючи методи перестановки ізаміни. Розкрити текст розшифровувача зможе, знаючи, що ключами єчисло 2 і слово "зачет" і відповідно послідовність їх застосування.
Приклад 2. В якості прикладу також розглянемо шифр, запропонований Д.
Френдбергом, який комбінує многоалфавітную підстановку з генераторомпсевдовипадкових чисел. Особливість даного алгоритму полягає в тому, що привеликому обсязі шифртексту частотні характеристики символів шифртекстублизькі до рівномірного розподілу незалежно від змісту відкритоготексту.
1. Встановлення початкового стану генератора псевдовипадкових чисел.
2. Встановлення початкового списку підстановки.
3. Усі символи відкритого тексту зашифровані?
4. Якщо так - кінець роботи, якщо ні - продовжити.
5. Здійснення заміни.
6. Генерація випадкового числа.
7. Перестановка місцями знаків у списку заміни.
8. Перехід на крок 4.
Приклад 3. Відкритий текст: "Абракадабра".
Використовуємо одноалфавітную заміну відповідно до таблиці 1.
Таблиця 1:
| А | Б | Д | К | Р |
| X | V | N | R | S |
Послідовність чисел, що виробляється датчиком: 31412543125.
1. у1 = Х.
Після перестановки символів вихідного алфавіту отримуємо таблицю 2 (h1 = 3).
Таблиця 2:
| Д | Б | А | К | Р |
| X | V | N | R | S |
2. у2 = V. Таблиця 2 після перестановки (h2 = 1) приймає вигляд, представленийу таблиці 3.
Таблиця 3:
| Б | Д | А | К | Р |
| X | V | N | R | S |
Здійснюючи подальші перетворення відповідно до алгоритму
Френдберга, отримуємо шифртексту: "XVSNSXXSSSN".
Одним з різновидів методу гамування є найбільш частозастосовується метод багаторазового накладення гам. Необхідно відзначити, щоякщо уi = Гk (Г1 (xi)), то Гk (Г1 (xi)) = Г1 (Гk (xi)). (1 *)
Тотожність (1 *) називають основною властивістю гами.
Приклад 4. Відкритий текст: "Шифр" (25 09 21 17 28 ");
Г1 = "ГАММА" ( "04 01 13 13 01");
Г2 = "ТЕКСТ" ( "19 06 11 18 19"), згідно з таблицею 1.
Яка використовується операція: додавання за mod 2.
1. Y1i = xi (h1i
11001 01001 10101 10001 11100
(
00100 00001 01101 01101 00001
=
11101 01000 11000 11100 11101.
2. У2i = y1i (h2i
11101 01000 11000 11100 11101
(
10011 00110 01011 10010 10011
=
01110 01110 10011 01110 01110.
Проведемо операцію шифрування, помінявши порядок застосування гам.
1. У1i = xi (h2i
11001 01001 10101 10001 11100
(
10011 00110 01011 10010 10011
=
01010 01111 11110 00011 01111.
2. У2i '= y1i' (h1i
01010 01111 11110 00011 01111
(
00100 00001 01101 01101 00001
=
01110 01110 10011 01110 01110.
Таким чином, y2i = y2i ', що є підтвердженням основного властивостігами.
При складанні комбінованих шифрів необхідно проявлятиобережність, тому що неправильний вибір складали шифрів може призвестидо вихідного відкритого тексту. Найпростішим прикладом служить накладення однієїгами двічі.
Приклад 5. Відкритий текст: "Шифр" ( "25 09 21 17 28");
Г1 = Г2 = "ГАММА" ( "04 01 13 13 01"), згідно з таблицею 1.
Яка використовується операція: додавання по mod 2:
11001 01001 10101 10001 11100
(
00100 00001 01101 01101 00001
(
00100 00001 01101 01101 00001
=
11001 01001 10101 10001 11100.
Таким чином, результат шифрування являє собою відкритий текст.
2. Теорія проектування блокових шифрів
К. Шеннон висунув поняття розсіювання та перемішування. Черезп'ятдесят років після формулювання цих принципів, вони залишаютьсянаріжним каменем проектування хороших блокових шифрів.
перемішування маскує взаємозв'язку між відкритим текстом,шифртексту і ключем. Навіть незначна залежність між цими трьомаскладовими може бути використана в диференціальній і лінійномукриптоаналіз. Гарне перемішування настільки ускладнює статистикувзаємозв'язків, що пасують навіть потужні криптоаналітичних кошти.
Розсіювання поширює вплив окремих бітів відкритого тексту наможливо більший обсяг шифртексту. Це теж маскує статистичнівзаємозв'язку і ускладнює криптоаналіз.
Для забезпечення надійності досить тільки перемішування. Алгоритм,що складається з єдиної, залежною від ключа таблиці підстановок 64 бітвідкритого тексту в 64 біт шифртексту був би досить надійним. Недолікв тому, що для зберігання такої таблиці знадобилося б надто багатопам'яті: 1020 байт. Сенс створення блокового шифру і полягає в створенні чогосьто подібного такої таблиці, але пред'являє до пам'яті більш помірнівимоги.
Тонкість, полягає в тому, що в одному шифрі слід періодичнозмішувати в різних комбінаціях перемішування (з набагато меншимитаблицями) і розсіювання. Такий шифр називають складовим шифром (productcipher). Іноді блочний шифр, який використовує послідовніперестановки і підстановки, називають мережею перестановок-підстановок, або SP -мережею.
Розглянемо функцію f алгоритму DES. Перестановка з розширенням і Р -блок реалізують розсіювання, а S-блоки - перемішування. Перестановка зрозширенням і Р-блок лінійних, S-блоки - нелінійна. Кожна операція сама пособі дуже проста, але разом вони працюють чудово.
Крім того, на прикладі DES можна продемонструвати ще кількапринципів проектування блокових шифрів. Перший принцип реалізує ідеюітеративного блочного шифру. При цьому передбачається, що проста функціяраунду послідовно використовується кілька разів. Двораундовому алгоритм
DES занадто ненадійний, щоб всі біти результату залежали від всіх бітівключа і всіх бітів вихідних даних. Для цього необхідно 5 раундів. Вельминадійний 16-раундовий алгоритм DES, а 32-раундовий DES ще більш стійкий.
2.1. Мережі Файстеля
Більшість блочних алгоритмів належать до так званих мереж
Файстеля. Ідея цих мереж датується початком сімдесятих років. Візьмемоблок завдовжки п і розділимо його на дві половини довжиною n/2: L і R. Зрозуміло,число п повинно бути парним. Можна визначити ітеративний блочний шифр, вякому результат j-го раунду визначається результатом попереднього раунду:
Li = Ri-1
Ri = Li-1 (f (Ri-1, Ki)
Ki - з'єднання j-го раунду, а f - довільна функція раунду.
Застосування цієї концепції можна зустріти в алгоритмах DES, Lucifer,
FEAL, Khufu, Khafre, LOKI, ГОСТ, CAST, Blowfish та інших. Цимгарантується оборотність функції. Так як для об'єднання лівої половини зрезультатом функції раунду використовується операція XOR, завжди істиннонаступне вираз:
Li-1 (f (Ri-1, Ki) (Li-1 (f (Ri-1, Ki) = Li-1
Шифр, що використовує таку конструкцію, гарантовано звернемо, якщо можнавідновити вихідні дані f на кожному раунді. Сама функція f не важлива,вона не обов'язково оборотна. Ми можемо спроектувати як завгодно складнуфункцію f, але нам не знадобиться реалізовувати два різних алгоритму - одиндля зашифрування, а інший для розшифрування. Про це автоматичноподбає структура мережі Файстеля.
2.2. Прості співвідношення
Алгоритм DES характеризується наступну властивість: якщо ЄК (Р) = С, то
ЕK '(Р') = З ', де Р', С 'і K' - побітового додатки Р, С і K. Цевластивість вдвічі зменшує складність лобового розтину. Властивостікомплементарності в 256 разів спрощують лобове розтин алгоритму LOKI.
Просте співвідношення можна визначити так:
Якщо ЕK (Р) = С, то Ef (K) (g (P, K)) = h (C, K)де f, g та h - прості функції. Під «простими функціями» мають на увазіфункції, обчислення яких нескладно, набагато простіше ітерації блочногошифру. В алгоритмі DES функція f є побітове доповнення
K, g - побітове додаток Р, ah - побітове доповнення C. Це --наслідок складання ключа і тексту операцією XOR. Для гарного блочногошифру простих співвідношень немає.
2.3. Групова структура
При вивченні алгоритму виникає питання, чи не утворює він групу.
Елементами групи служать блоки шифртексту для кожного можливого ключа, агруповий операцією служить композиція. Вивчення групової структуриалгоритму являє собою спробу зрозуміти, наскільки зростаєдодаткове приховування тексту при багаторазовому шифрування.
Важливий, однак, питання не про те, чи дійсно алгоритм - група, апро те, наскільки він близький до такого. Якщо не вистачає тільки одногоелементу, алгоритм не утворює групу, але подвійне шифрування було б, зточки зору статистики, просто втратою часу. Робота над DES показала,що цей алгоритм вельми далекий від групи. Існує також ряд цікавихпитань про напівгруп, одержуваної для шифрування DES. Чи містить вонатотожність, тобто, не утворює вона групу? Іншими словами, не генеруєЧи, зрештою, певна комбінація операцій зашифрування (нерозшифрування) тотожну функцію? Якщо так, яка довжина найкоротшоїз таких комбінацій?
Мета дослідження полягає в оцінці простору ключів длятеоретичного лобового розтину, а результат являє собою найбільшунижню межу ентропії простору ключів.
2.4. Слабкі ключі
У хорошому блоковому шифрі всі ключі однаково сильні. Як правило, немаєпроблем і з алгоритмами, що включають невелику кількість слабкі?? ключів,наприклад, DES. Імовірність випадкового вибору одного з них дуже мала, ітакий ключ легко перевірити та, при необхідності, відкинути. Однак якщоблочний шифр використовується як однонаправлений хеш-функція, ці слабкіключі іноді можуть бути задіяні.
2.5. Стійкість алгоритму до диференціальних і лінійному криптоаналіз
Дослідження диференціального та лінійного криптоаналізу значнопрояснили теорію проектування надійних блокових шифрів. Автори алгоритму
IDEA ввели поняття диференціалів, узагальнення основної ідеї характеристик.
Вони стверджували, що можна створювати блокові шифри, стійкі до атактакого типу. У результаті подібного проектування з'явився алгоритм IDEA.
Пізніше це поняття було формалізовано в роботах Кайса Ніберг (Kaisa
Nyberg) і Ларі Кнудсен, які описали метод створення блокових шифрів,доказовою стійких до Диференціальний криптоаналіз. Ця теорія буларозширена на диференціали вищих порядків і приватні диференціали. Яквидається, диференціали вищих порядків застосовні тільки до шифрів змалим числом раундів, але приватні диференціали прекрасно поєднуються здиференціалами.
Лінійний криптоаналіз з'явився порівняно недавно, і продовжуєудосконалюватися. Були визначені поняття ранжирування ключів табагаторазових апроксимацій. Кимось була зроблена спроба об'єднання водній атаці диференціального та лінійного методів криптоаналізу. Покинеясно, яка методика проектування зможе протистояти подібним атакам.
Кнудсен відомого домігся успіху, розглядаючи деякі необхідні
(але, можливо, недостатні) критерії того, що він назвав практичностійкими мережами Файстеля - шифрів, стійких як до диференціальних, такі до лінійного криптоаналіз. Ніберг запровадив для лінійного криптоаналізу аналогпоняття диференціалів в Диференціальний криптоаналіз.
Досить цікава, як видається, подвійністьдиференціального та лінійного методів криптоаналізу. Ця подвійністьстає очевидною як при розробці методики створення хорошихдиференціальних характеристик і лінійних наближень, так і при розробцікритерію проектування, що забезпечує стійкість алгоритмів до обохтипами розтину. Поки точно невідомо, куди заведе цей напрямокдосліджень. Для початку Деймен розробила стратегію проектуванняалгоритму, засновану на диференціальному і лінійному криптоаналіз.
2.6. Проектування S-блоків
Міць більшості мереж Файстеля, а особливо їх стійкість додиференціальне та лінійному криптоаналіз, безпосередньо пов'язана з їхньою S -блоками. Тому питання про те, що ж утворює гарний S-блок, ставоб'єктом численних досліджень.
S-блок - це просто підстановка: відображення m-бітових входів на n -бітові виходи. Застосовується велика таблиця підстановок 64-бітових входівна 64-бітові виходи. Така таблиця являє собою S-блок розміром
64 * 64 біт. S-блок з m-двійкового входом і n-двійкового виходом називається m * n -двійкового S-блоком. Як правило, обробка в S-блоках - єдинанелінійна операція в алгоритмі. Саме S-блоки забезпечують стійкістьблочного шифру. У загальному випадку, чим більше S-блоки, тим краще.
В алгоритмі DES використовуються вісім різних 6 * 4-бітових S-блоків. Уалгоритмах Khufu і Khafre передбачений єдиний 8 * 32-бітовий S-блок, в
LOKI - 12 * 8-бітовий S-блок, а в Blowfish і CAST - 8 * 32-бітові S-блоки. У
IDEA S-блоком, по суті, служить множення по модулю, це 16 +16- бітовий S -блок. Чим більше S-блок, тим складніше знайти статистичні дані,потрібні для розкриття методами диференціального або лінійного криптоаналізу.
Крім того, хоча випадкові S-блоки зазвичай не оптимальні з точки зорустійкості до диференціальних і лінійному криптоаналіз, стійкі S-блокилегше знайти серед S-блоків більшого розміру. Більшість випадкових S-блоківнелінійно, невирождени і характеризуються високою стійкістю до лінійногокриптоаналіз, причому зі зменшенням числа вхідних бітів стійкістьзнижується досить повільно.
Розмір т важливіше розміру п. Збільшення розміру п знижує ефективністьдиференціального криптоаналізу, але значно підвищує ефективністьлінійного криптоаналізу. Дійсно, якщо п? 2m - т, напевноіснує лінійна залежність між вхідними і вихідними битами S-блоку.
А якщо п? 2m, лінійна залежність існує навіть тільки між вихіднимибитами. Помітна частка робіт з проектування S-блоків полягає ввивченні бульових функцій. Для забезпечення безпеки, булеві функції S -блоків повинні відповідати певним вимогам. Вони не повинні бути нілінійними, ні афінному, ні навіть близькими до лінійних або афінному функцій.
Кількість нулів та одиниць має бути збалансованим, і між різнимикомбінаціями бітів не повинно бути ніяких кореляцій. При змінізначення будь-якого вхідного біта на протилежне вихідні біти повинні вестисебе незалежно. Ці критерії проектування так само пов'язані з вивченнямбент-функцій (bent functions): функцій, які, як можна показати,оптимально нелінійних. Хоча вони визначені просто і природно, їх вивченнядуже важко.
Мабуть, дуже важлива властивість S-блоків - лавинний ефект: скількивихідних бітів S-блоку змінюється при зміні деякого підмножинивхідних бітів. Неважко задати для булевих функцій умови, виконанняяких забезпечує певний лавинний ефект, але проектування такихфункцій завдання складне. Строгий лавинний критерій (Strict Avalanche
Criteria - SAC) гарантує зміна рівно половини вихідних бітів призміні єдиного вхідного бита. В одній з робіт ці критеріїрозглядаються з точки зору витоку інформації.
Кілька років тому кріпгографи запропонували вибирати S-блоки так, щобтаблиця розподілу відмінностей для кожного S-блоку була однорідною. Цезабезпечило б стійкість до Диференціальний криптоаналіз за рахунокзгладжування диференціалів на будь-якому окремому раунді. Як прикладтакого проектування можна назвати алгоритм LOKI. Проте такий підхідіноді полегшує диференціальний криптоаналіз. Насправді, вдалішепідхід, що гарантує найменше значення максимального диференціала.
Кванджу Кім (Kwangjo Kim) висунув п'ять критеріїв проектування S-блоків,нагадують критерії проектування S-блоків DES.
Вибір хороших S-блоків - нелегке завдання. Відомо безлічконкуруючих підходів її вирішення; серед hіх можна виділити чотириосновних.
V Випадковий вибір. Ясно, що невеликі випадкові S-блоки ненадійні, але великі випадкові S-блоки можуть виявитися досить хорошими.
Випадкові S-блоки з вісьмома та більше входами достатньо стійкі, ще краще 12-бітові S-блоки. Стійкість S-блоків зростає, якщо вони одночасно і випадкові, і залежать від ключа.
V Вибір із наступним тестуванням. У деяких шифри спочатку генеруються випадкові S-блоки, а затії їх властивості тестуються на відповідність вимогам.
V Розробка вручну. При цьому математичний апарат використовується вкрай незначно: S-блоки створюються з використанням інтуїтивних прийомів. Барт Пренел (Bart Preneel) заявив, що «... теоретично цікаві критерії недостатні (для вибору бульових функцій S-блоків )...», і «... необхідні спеціальні критерії проектування ».
V Математична розробка. S-блоки створюються відповідно до законів математики, тому мають гарантованої стійкістю до диференціальних і лінійному криптоаналіз і хорошими розсіюючими властивостями.
Лунали заклики об'єднати «математичний» і «ручний» підходи, алереально, мабуть, конкурують випадково вибрані S-блоки і S-блоки зпевними властивостями. До переваг останнього підходу можна віднестиоптимізацію проти відомих методів розкриття - диференціального ілінійного криптоаналізу. Однак у цьому випадку неясна ступінь захисту відневідомих методів розкриття. Розробники DES знали про диференціальномукриптоаналіз, тому S-блоки DES оптимізовані належним чином. Але,імовірніше за все, про лінійне криптоаналіз вони не знали, і S-блоки DES дужеслабкі по відношенню до такої атаки. Випадково обрані S-блоки в DES були бслабкіше до Диференціальний криптоаналіз, але стійкіші до лінійногокриптоаналіз.
З іншого боку, випадкові S-блоки можуть бути і неоптимальні до данихатак, але вони можуть бути досить великими і, отже, достатньостійкими. Крім того, вони, швидше за все, виявляться досить стійкими доневідомим методам розтину. Спори все ще киплять, але особисто мені здається,що S-блоки повинні бути такими великими, наскільки це можливо, випадковимиі залежними від ключа.
2.7. Проектування блочного шифру
Спроектувати блочний шифр неважко. Якщо розглядати 64-бітовийблочний шифр як перестановку 64-бітових чисел, ясно, що майже всі ціперестановки безпечні. Важко спроектувати такий блочний шифр, якийне тільки стійкий, але також може бути легко описано та реалізовано.
Неважко спроектувати блочний шифр, якщо обсяг пам'яті достатній длярозміщення 48 * 32-бітових S-блоків. Важко спроектувати нестійкий варіанталгоритму DES, якщо потрібно використовувати в ньому 128 раундів. При довжині ключа
512 бітів немає потреби турбуватися про яку-небудь залежить від ключакомплементарності.
Цей фокус - і причина, чому насправді дуже важкоспроектувати блочний шифр - це розробити алгоритм з можливонайменшим ключем, вимогам до пам'яті і максимальною швидкістю роботи.
3. Блокові шифри
3.1. Алгоритм Lucifer
Наприкінці шістдесятих років корпорація IBM запустила дослідницькупрограму з комп'ютерної криптографії, названу Lucifer (Люцифер) ікеровану спочатку Хорстом Файстелем (Horst Feistel), а потім Уолтом
Тачменом (Walt Tuchman). Таке ж ім'я - Lucifer - отримав блочний алгоритм,що з'явився в результаті цієї програми на початку сімдесятих років. УНасправді існує, щонайменше, два різних алгоритму зтаким ім'ям. Один з них містить ряд прогалин в специфікації алгоритму.
Все це призвело до помітної плутанини.
Алгоритм Lucifer є мережею перестановок та підстановок,його основні блоки нагадують блоки алгоритму DES. У DES результат функціїf складається операцією XOR з входом попереднього раунду, утворюючи вхіднаступного раунду. У S-блоків алгоритму Lucifer 4-бітові входи і виходи,вхід S-блоків являє собою перетасувати вихід S-блоків попередньогораунду, входом S-блоків першого раунду служить відкритий текст. Для виборувикористовуваного S-блоку з двох можливих використовується біт ключа. (Luciferреалізує все це в єдиному Т-блоці з 9 бітами на вході і 8 бітами навиході). На відміну від алгоритму DES, половини блоку між раунду непереставляються, та й саме поняття половини блоку в алгоритмі Lucifer НЕвикористовується. У цього алгоритму 16 раундів, 128-бітові блоки і більшепроста, ніж у DES, схема розгортки ключа.
Застосувавши диференціальний криптоаналіз до першого реалізації алгоритму
Lucifer, Біхам і Шамір показали, що Lucifer з 32-бітовими блоками і 8раундами можна зламати за допомогою 40 підібраних відкритих текстів за 229операцій. Цей же метод дозволяє розкрити Lucifer з 128-бітовими блоками і
8 раундами за допомогою 60 підібраних відкритих текстів за 253 кроків. Іншадиференціальна атака розкриває 18-раундовий, 128-бітовий Lucifer здопомогою 24 підібраних відкритих текстів за 221 операцій. У всіх цихрозтинах використовувалися стійкі S-блоки алгоритму DES. Застосувавшидиференціальний криптоаналіз до другої реалізації Lucifer, Біхам і Шамірвиявили, що його S-блоки набагато слабкіше, ніж в алгоритмі DES. Подальшийаналіз показав нестійкість більше половини можливих ключів. Криптоаналіз наоснові пов'язаних ключів дозволяє зламати 128-бітовий Lucifer з будь-якимчислом раундів за допомогою 233 підібраних відкритих текстів для підібранихключів або 265 відомих відкритих текстів для підібраних ключів. Другареалізація Lucifer ще слабше.
Деякі вважають, що Lucifer надійніше DES з-за більшої довжини ключанечисленність опублікованих відомостей. Але очевидно, що це не так. Наалгоритм Lucifer видані декількох патентів США. Терміни дії всіх цихпатентів вже минули.
3.2. Алгоритм Madryga
В. Е. Мадріга (WE Madryga) запропонував цей блоковий алгоритм у 1984році. Його можна ефективно реалізувати програмним шляхом: в алгоритмі немаєдратівливих перестановок, і всі операції виконуються над байтами.
Варто перерахувати завдання, які вирішував автор при проектуванніалгоритму:
V Без допомоги ключа відкритий текст неможливо отримати з шифртексту.
(Це означає тільки те, що алгоритм стійок).
V Число операцій, необхідних для відновлення ключа за зразком шифртексту і відкритого тексту, має бути статистично одно твором числа операцій для шифрування на число можливих ключів.
(Це означає, що ніяке розтин з відкритим текстом не може бути більш ефективним лобового розтину).
V Опублікування алгоритму не впливає на стійкість шифру. (Безпека повністю визначається ключем).
V Зміна одного біта ключа повинно радикально змінювати шифртексту одного і того ж відкритого тексту, а зміна одного біта відкритого тексту має радикально змінювати шифртексту для того ж ключа
(лавинний ефект).
V Алгоритм повинен містити некоммутатівную комбінацію підстановок і перестановок.
V Підстановки і перестановки, які використовуються в алгоритмі, повинні визначатися як вхідними даними, так і ключем.
V Надлишкові групи бітів відкритого тексту повинні бути повністю замасковані в шифртексту.
V Довжина шифртексту повинна збігатися з довжиною відкритого тексту.
V Між будь-якими можливими ключами та особливостями шифртексту неприпустимі прості взаємозв'язку.
V Всі можливі ключі повинні забезпечувати стійкість шифру. (Не повинно бути слабких ключів).
V Довжина ключа і текст повинні мати можливість варіювання для реалізації різних вимог до безпеки.
V Алгоритм повинен допускати ефективну програмну реалізацію на мейнфреймах, міні - і мікрокомпиотерах і за допомогою дискретної логіки.
(Власне кажучи, кількість функцій, що використовуються в алгоритмі, обмежена операціями XOR і двійкового зрушенням).
Алгоритм DES задовольняв перший дев'яти вимогам, але останні триз'явилися вперше. Якщо припустити, що найкращий спосіб злому алгоритму --лобове розтин, змінна довжина ключа, звичайно ж, змусить замовчатитих, хто вважає, що 56 бітів - занадто мала величина. Такі люди можутьреалізувати цей алгоритм з будь-якою довжиною ключа. А кожен, хто коли-небудьнамагався реалізувати DES програмними засобами, зрадіє алгоритму,який враховує особливості програмних реалізацій.
3.3.1. Опис алгоритму Madryga
Алгоритм Madryga складається з двох вкладених циклів. Зовнішній циклповторюється вісім разів (для гарантії надійності число циклів можназбільшити) і полягає в застосуванні внутрішнього циклу до відкритого тексту.
Внутрішній цикл перетворює відкритий текст в шифртексту і виконуєтьсяодноразово над кожним 8-бітовим блоком (байтом) відкритого тексту. Такимчином, весь відкритий текст послідовно вісім разів обробляєтьсяалгоритмом.
Ітерація внутрішнього циклу оперує з 3-байтовий вікном даних,званим робочим кадром (Мал. 1.). Це вікно зсувається на 1 байт заітерацію. (При роботі з останніми 2 байтами дані покладаються циклічнозамкнутими). Перші два байти робочого кадру циклічно зсуваються назмінне число позицій, а для останнього байта виконується операція XOR здекількома бітами ключа. У міру переміщення робочого кадру всі байтипослідовно циклічно зсуваються і піддаються операції XOR з частинамиключа. Послідовні циклічні зрушення перемішують результатипопередніх операцій XOR і циклічного зсуву, причому на циклічний зсуввпливають результати XOR. Завдяки цьому процес в цілому звернемо.
| рухомий | WF (1) | WF (2) | | WF (3) | | | |
| робочий кадр | | | | | | | |
| | 8 бітів | 8 бітів | | 8 бітів | | | |
| | ROT | | | | | |
| Переміщення | Об'єкт зсуву | | | Лічильник зсуву | | |
| | 16 біт | | 3 біта | | |
| | | | | XOR | | | |
| Хеш ключа | 1 | 2 | 3 | ... | KL | | |
| | | | | | | | |
Рис. 1. Одна ітерація алгоритму Madryga
Оскільки кожен байт даних впливає на два байти ліворуч і на один байтправоруч від себе, після восьми проходів кожен байт шифртексту залежить від
16 байтів зліва і 8 байтів справа.
При зашифрованими кожна ітерація внутрішнього циклу встановлюєробочий кадр на передостанній байт відкритого тексту і циклічно переміщуєйого до третього з кінця байту відкритого тексту. Спочатку весь ключпіддається операції XOR з випадковою константою і потім циклічносд?? ігается вправо на 3 біта (ключ і дані рухаються в різних напрямках,щоб мінімізувати надмірні операції з бітами ключа). Молодші три бітамолодшого байта робочого кадру зберігаються, вони визначають циклічний зсувінших двох байтів. Далі конкатенація двох старших байтом циклічнозсувається вліво на змінне число бітів (від 0 до 7). Потім над молодшимбайтом робочого кадру виконується операція XOR з молодшим байтом ключа.
Нарешті робочий кадр зміщується вправо на один байт і весь процесповторюється.
Випадкова константа призначена для перетворення ключа впсевдовипадкову послідовність. Довжина константи має дорівнюватидовжині ключа. При обміні даними абоненти повинні користуватися однією і тією жконстантою. Для 64-бітового ключа Мадріга рекомендує константу
0x0fle2d3c4b5a6978.
При розшифрування процес повторюється у зворотному порядку. У кожнійітерації внутрішнього циклу робочий кадр встановлюється на байт, третійліворуч від останнього байта шифртексту, і циклічно зсувається в зворотномунапрямку до байта, розташованого на 2 байтів лівіше останнього байташифртексту. 2 байти шифртексту в процесі циклічно зсуваються вправо, аключ - ліворуч. Після циклічних зрушень виконується операція XOR.
3.2.2. Криптоаналіз алгоритму Madryga
Вчені Квінслендського технічного університету (Queensland Universityof Technology) досліджували алгоритм Madryga і деякі інші блоковішифри. Вони виявили, що лавинний ефект при перетворенні відкритоготексту в шифртексту в цьому алгоритмі не виявляється. Крім того, у багатьохшифртексту частка одиниць перевищувала частки нулів.
Формальний аналіз цього алгоритму не справляє враження особливонадійного. При поверхневому знайомстві з ним Елі Біхам прийшов до наступнихвисновків:
Алгоритм складається тільки з лінійних операцій (циклічний зсув і XOR), трохи змінюваних залежно від даних.
Це анітрохи не нагадує міць S-блоків DES.
Парність всіх бітів шифртексту і відкритого тексту незмінна і залежить тільки від ключа. Тому, маючи відкритим текстом і відповідним шифртексту, можна передбачити парність шифртексту для будь-якого відкритого тексту.
Саме по собі жодна з цих зауважень не можна назвати убивчим,однак цей алгоритм не викликає у багатьох криптоаналітиків позитивнихемоцій. Деякі взагалі не рекомендують використовувати алгоритм Madryga.
3.3. Алгоритм REDOC
REDOC II являє собою ще один блочний алгоритм, розроблений
Майклом Вудом (Michael Wood) для корпорації Cryptech. У ньому використовуються 20 --байтовий (160-бітовий) ключ і 80-бітовий блок.
Алгоритм REDOC II виконує всі маніпуляції - перестановки,підстановки та операції XOR з ключем - з байтами. Цей алгоритм зручний дляпрограмної реалізації. У REDOC II використані змінні таблиці функцій.
На відміну від алгоритму DES, що має фіксований (хоча і оптимізованийз точки зору стійкості) набір таблиць підстановок і перестановок, в REDOC
II використовуються залежні від ключа і відкритого тексту набори таблиць (посуті, S-блоки). У REDOC II 10 раундів, кожен р.
