Главная | Обратная связь | Поможем написать вашу работу!

Загальні відомості про блокові шифри

Характерною рисою блокових криптоалгоритмів є той факт, що в ході своєї роботи вони здійснюють перетворення блоку вхідної інформації фіксованої довжини й одержують результуючий блок того ж об'єму, але недоступний для прочитання сторонніми особам, що не володіють ключем. Таким чином, схему роботи блокового шифру можна описати функціями Z=EnCrypt(X,Key) і X=DeCrypt(Z,Key).

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

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

Криптоалгоритм називається ідеально стійким, якщо прочитати зашифрований блок даних можна тільки перебравши всі можливі ключі, доти, поки повідомлення не виявиться осмисленим. За теорією ймовірності шуканий ключ буде знайдений з імовірністю 1/2 після перебору половини всіх ключів, то на злом ідеально стійкого криптоалгоритму із ключем довжини N буде потрібно в середньому 2^N-1 перевірок. Таким чином, у загальному випадку стійкість блокового шифру залежить тільки від довжини ключа й зростає експоненціально з її ростом. Навіть припустивши, що перебір ключів проводиться на спеціально створеній багатопроцесорній системі, в якій завдяки діагональному паралелізму на перевірку 1 ключа йде тільки 1 такт, то на злом 128 бітного ключа сучасній техніці буде потрібно не менш 10²¹ років. Природно, що все сказане відноситься тільки до ідеально стійких шифрів, якими, наприклад, з великою долею впевненості є наведені в табл. 3.1 алгоритми (ці розробки всесвітньо визнані стійкими алгоритмами й публікацій про універсальні методи їхнього злому в засобах масової інформації на момент створення матеріалу не траплялися).

Таблиця 3.1 - Блокові алгоритми

Назва алгоритму	Автор	Розмір блоку	Довжина ключа
IDEA	Xuejia Lia and James Massey	64 біта	128 біт
CAST128		64 біта	128 біт
BlowFish	Bruce Schneier	64 біта	128–448 біт
ДЕРЖСТАНДАРТ	НДІ ***	64 біта	256 біт
TwoFish	Bruce Schneier	128 біт	128–256 біт
MARS	Корпорація IBM	128 біт	128–1048 біт

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

Таким чином, на функцію стійкого блокового шифру Z=EnCrypt(X,Key) накладаються такі умови:

1 Функція EnCrypt повинна бути зворотною.

2 Не повинно існувати інших методів прочитання повідомлення X за відомим блоком Z, крім повного перебору ключів Key.

3 Не повинно існувати інших методів визначення яким ключем Key було зроблене перетворення відомого повідомлення X у повідомлення Z, крім повного перебору ключів.

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

Всі дії, що здійснюються над даними блоковим криптоалгоритмами, засновані на тому факті, що перетворюваний блок може бути представлений у вигляді цілого невід’ємного числа з діапазону, що відповідає його розрядності. Так, наприклад, 32-бітний блок даних можна інтерпретувати як число з діапазону 0..4294967295. Крім того, блок, розрядність якого звичайно є "степенем двійки", можна трактувати як кілька незалежних невід’ємних чисел з меншого діапазону (розглянутий вище 32-бітний блок можна також представити у вигляді 2 незалежних чисел з діапазону 0..65535 або у вигляді 4 незалежних чисел з діапазону 0..255).

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

Як параметр V для кожного із цих перетворень може використовуватися:

1) фіксоване число (наприклад, X'=X+125);

2) число, одержане із ключа (наприклад, X'=X+F(Key));

3) число, одержане з незалежної частини блоку (наприклад, X₂'=X₂+F(X₁)).

Останній варіант використається в схемі, названій за іменем її творця мережею Фейштеля (нім. Feistel).

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

Таблиця 3.2 - Бієктивні математичні функції

	Додавання	X'=X+V
	Виключне АБО	X'=X XOR V
	Множення по модулю 2^N+1	X'=(XV) mod (2^N+1)*
	Множення по модулю 2^N	X'=(XV) mod (2^N)*
Бітові зміщення
	Арифметичний зсув вліво	X'=X SHL V
	Арифметичний зсув вправо	X'=X SHR V
	Циклічний зсув вліво	X'=X ROL V
	Циклічний зсув вправо	X'=X ROR V
Табличні підстановки
	S-box (англ. substitute)	X'=Table[X,V]

Характерною ознакою блокових алгоритмів є багаторазове й непряме використання матеріалу ключа. Це диктується в першу чергу вимогою неможливості зворотного декодування відносно ключа при відомих вихідному й зашифрованому текстах. Для рішення цієї задачі в наведених вище перетвореннях найчастіше використовується не саме значення ключа або його частини, а деяка, іноді необоротна (небієктивна) функція від матеріалу ключа. Більше того, у подібних перетвореннях той самий блок або елемент ключа використовується багаторазово. Це дозволяє при виконанні умови оборотності функції щодо величини X зробити функцію необоротною щодо ключа Key.

Оскільки операція зашифровки або розшифровки окремого блоку в процесі кодування пакета інформації виконується багаторазово (іноді до сотень тисяч разів), а значення ключа й, отже, функцій V_i(Key) залишається незмінним, то іноді стає доцільно заздалегідь однократно обчислити дані значення й зберігати їх в оперативній пам'яті разом із ключем. Оскільки ці значення залежать тільки від ключа, то вони у криптографії називаються матеріалом ключа. Необхідно відзначити, що дана операція ніяким чином не змінює ні довжину ключа, ні криптостійкість алгоритму в цілому. Тут відбувається лише оптимізація швидкості обчислень шляхом кешування (англ. caching) проміжних результатів. Описані дії зустрічаються практично в усіх блокових криптоалгоритмах і називаються розширенням ключа (англ. key scheduling).

Мережа Фейштеля

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

Незалежні потоки інформації, породжені з вихідного блоку, називаються гілками мережі. У класичній схемі їх дві. Величини V_i називаються параметрами мережі, звичайно це функції від матеріалу ключа. Функція F називається утворюючою. Дія, що складається з однократного обчислення утворюючої функції й наступного накладення її результату на іншу вітку із обміном їх місцями, називається циклом або раундом (англ. round) мережі Фейштеля. Оптимальне число раундів K - від 8 до 32. Важливо те, що збільшення кількості раундів значно збільшує криптостійкість будь-якого блокового шифру до криптоаналізу. Можливо, ця особливість і вплинула на настільки активне поширення мережі Фейштеля - адже при виявленні, скажімо, якого-небудь слабкого місця в алгоритмі, майже завжди досить збільшити кількість раундів на 4-8, не переписуючи сам алгоритм. Часто кількість раундів не фіксується розроблювачами алгоритму, а лише вказуються розумні межі (обов'язково нижній, і не завжди - верхній) цього параметра.

Відразу ж виникає питання, – чи є дана схема зворотною? Очевидно, так. Мережа Фейштеля володіє такою властивістю, що навіть якщо в якості утворюючої функції F буде використане необоротне перетворення, то й у цьому випадку весь ланцюжок буде відновлюваний. Це відбувається внаслідок того, що для зворотного перетворення мережі Фейштеля не потрібно обчислювати функцію F^-1.

Класична мережа Фейштеля має структуру, зображену на рис. 3.2.

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

Рисунок 3.2 - Мережа Фейштеля

З незначними доробками мережу Фейштеля можна зробити й абсолютно симетричною, тобто виконуючою функції шифрування й дешифрування тим самим набором операцій. Математичною мовою це записується як "Функція EnCrypt тотожно дорівнює функції DeCrypt ".

Рисунок 3.3 - Модифікація мережі Фейштеля

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

А от модифікацію мережі Фейштеля для більшого числа гілок застосовують набагато частіше. Це в першу чергу пов'язане з тим, що при більших розмірах кодованих блоків (128 і більше біт) стає незручно працювати з математичними функціями по модулю 64 і вище. Як відомо, основні одиниці інформації оброблювані процесорами на сьогоднішній день - це байт і подвійне машинне слово 32 біта. Тому все частіше й частіше в блокових криптоалгоритмах зустрічається мережа Фейштеля з 4-ма гілками. Найпростіший принцип її модифікації зображений на рис. 3.4 а. Для більш швидкого перемішування інформації між гілками (а це основна проблема мережі Фейштеля з великою кількістю гілок) застосовуються дві модифіковані схеми, названі "type-2" й "type-3". Вони зображені на рис. 3.4 б й 3.4 в відповідно.

Мережа Фейштеля надійно зарекомендувала себе як криптостійка схема виконання перетворень, і її можна знайти практично в будь-якому сучасному блоковому шифрі. Незначні модифікації стосуються звичайно додаткових початкових й кінцевих перетворень (англомовний термін – whitening) над шифрованим блоком. Таким чином, криптостійкість блокового шифру, що використовує мережу Фейштеля, визначається на 95 % функцією F і правилом обчислення V_i із ключа. Ці функції і є об'єктом все нових і нових досліджень фахівців в області криптографії.

Рисунок 3.4 - Мережа Фейштеля з великою кількістю гілок

Блоковий шифр TEA

Розглянемо один з найпростіших у реалізації, але визнано стійких криптоалгоритмів - TEA (Tiny Encryption Algorithm).

Параметри алгоритму: Розмір блоку – 64 біта. Довжина ключа – 128 біт. В алгоритмі використана мережа Фейштеля із двома гілками в 32 біта кожна. Утворююча функція F оборотна. Мережа Фейштеля несиметрична через використання функції арифметичного додавання.

Схема роботи алгоритму наведена на рис. 3.5.

Відмітною рисою криптоалгоритму TEA є його розмір. Простота операцій, відсутність табличних підстановок й оптимізація під 32-розрядну архітектуру процесорів дозволяє реалізувати його мовою ASSEMBLER у гранично малому об'ємі коду. Недоліком алгоритму є деяка повільність, викликана необхідністю повторювати цикл Фейштеля 32 рази (це необхідно для ретельного "перемішування даних" через відсутність табличних підстановок).

Мінімальна кількість циклів, які можуть змінити одиничний біт даних - шість, але для надійного шифрування краще зробити 32 цикли (дія, що складається з однократного обчислення утворюючої функції F і наступного накладення її результату на іншу гілку з обміном їх місцями, називається циклом чи раундом (англ. round)). Схема роботи алгоритму приведена на рисунку 3.5. В даному алгоритмі ключ складається з 128 біт, що робить спробу розшифрувати дані за допомогою техніки неможливою. Дані для кодування розбиваються на дві частини Y та Z. В деяких алгоритмах ключі KEY0 та KEY1 змінювалися за допомогою додавання. Але в цьому випадку використовується змінна сума sum (її початкове значення рівне 0х00000000 в шістнадцятковій системі числення), яка утворюється арифметичним додаванням деякої константи delta в кожному циклі, що спрощує версію та робить її більш ефективною. Значення цієї константи delta= (в шістнадцятковій системі числення значення delta=0x9е3779b9). Різні частини delta використовуються в кожному циклі таким чином, що жоден біт даної частини не змінюється багаторазово.

Рисунок 3.5 - Шифр TEA

Розглянемо утворюючу функцію F, яка формується наступним чином: спочатку утворюються два доданки для операції XOR k (рис 3.5). Перший доданок формується так: значення даних X зсувається на 4 біти вліво і арифметично додається до KEY0. Другий доданок: значення даних X зсувається на 5 бітів вправо і арифметично додається до KEY1. Результат операції XOR k є першим доданком для операції XOR m (рис 3.5). А другий доданок для операції XOR m утворюється так: значення даних X арифметично додається до значення sum. Утворення функції F на цьому закінчується.

Далі значення функції F арифметично додається до значення даних Z і отримані результати X i Z попарно міняються місцями. Далі починається наступний раунд, в якому кодується значення другої половини даних (X).

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒