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

Блокові шифри

Характерною рисою блокових криптоалгоритмів є той факт, що в ході своєї роботи вони здійснюють перетворення блоку вхідної інформації фіксованої довжини й одержують результуючий блок того ж об'єму, але недоступний для прочитання сторонніми особам, що не володіють ключем. Таким чином, схему роботи блокового шифру можна описати функціями 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'=(X*V) mod (2^N+1)
	Множення по модулю 2^N	X'=(X*V) 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).

Дата добавления: 2014-01-07