4.5. Перестановні алгоритми
У перестановочних алгоритмах символи відкритого тексту змінюють порядок проходження відповідно до правила, яке визначається ключем .
Найпростіший приклад перестановки: символи відкритого тексту не ліворуч, а зверху вниз, при цьому довжина стовпця обмежена. Результатом буде текст, виписаний рядками.
Мал. 6. Найпростіший перестановний шифр.
Такий шифр буде дуже вразливий до перебору ключів (як ключ буде виступати довжина стовпця), оскільки ключ у будь-якому випадку не може бути довшим, ніж довжина самого повідомлення.
Розглянемо найцікавіший приклад: грати Флейберга. Ключем до цього шифру є квадратні грати, сторони яких містять парне число осередків. Чверть осередків решітки вирізаються за таким принципом: якщо деякий осередок вирізаний, то
7 Додавання відбувається за модулем потужності алфавіту. Якщо зашифровується текст, поданий у двійковому вигляді, то операція шифрування є виключним або (XOR), застосованим до ключа і відкритого тексту.
не можна вирізати ті осередки, в які вона переходить при повороті ґрат на 90, 180 і 270 градусів.
Щоб зашифрувати текст, решітка з прорізами накладається на розкреслений квадрат, після чого літери тексту послідовно записуються в прорізи. Коли всі прорізи заповнені, грати повертаються на 90 градусів, причому, згідно з принципом побудови решітки, прорізи при цьому виявляться на місці незаповнених осередків. У прорізі записується продовження тексту, після чого залишок знову повертається і таким чином процедура повторюється ще двічі. Якщо текст не помістився в один квадрат, так само заповнюється наступний. Порожніми комірки останнього квадрата, що залишилися, заповнюють випадковими символами.
Мал. 7. Прикладшифрування за допомогою грат Флейберга
Шифр Флейберга, очевидно, вразливий до криптоаналізу з відомим відкритим текстом, причому для двійкового алфавіту ця вразливість значно менша, ніж для естеалфавітів.
4.6. Сучасні алгоритми симетричного шифрування
Сучасні алгоритми симетричного шифрування використовують як підстановку, і перестановку. Стандартом є кілька раундів шифрування з різними ключами, які генеруються з урахуванням одного загального ключа. Більшість сучасних алгоритмів мають структуру, аналогічну до структури шифру Файстеля, розробленого в 1973 році.
Шифр Файстеля створювався як приклад практичної реалізації ідеї Клода Шен-
нона: надійний алгоритм шифрування повинен задовольняти двом властивостям: дифузії та кофузії.
Дифузія — кожен біт відкритого тексту має впливати кожен біт зашифрованого тексту. Суть дифузії полягає у розсіюванні статистичних характеристик відкритого тексту всередині шифрованого тексту.
Конфузія – відсутність статистичного взаємозв'язку між ключем та зашифрованим текстом. Навіть якщо противник визначить статистичні особливості зашифрованого тексту, їх має виявитися недостатньо, щоб отримати будь-яку інформацію про ключ.
Розглянемо структуру шифру Файстеля.
Том (тобто і відкритий і зашифрований текст представлені послідовністю бітів) і призначений для реалізації на ЕОМ.
На вхід алгоритму шифрування подається блок відкритого тексту, що має парну довжину 2l ключ K . Блок поділяється на дві рівні частини - праву R0 та ліву L0. Далі ці частини проходять m раундів обробки, після чого знову поєднуються в зашифрований текст.
Кожен раунд полягає в генерації підключення K i (на основі загального ключа K) тазастосуванні до блоку R i деякого залежить від ключа перетворення F . Результат складається з блоком L i за допомогою операції XOR (що виключає або) і виходить блок R i +1 . Блок R i без змін береться як блок L i +1 .
Процес дешифрування принципово нічим не відрізняється, але вхід подається зашифрований текст, а ключі K i обчислюються у порядку.
Мал. 8. Схема раунду шифрування шифру Файстеля
Різні алгоритми, що використовують структуру шифру Файстеля, можуть відрізнятися такими параметрами:
1. Довжина ключа. Чим довший ключ, передбачений алгоритмом, тим складніше здійснити перебір. Зараз надійною вважається довжина ключа щонайменше 1024 біта.
2. Розмір блоку. Що розмір блоку, то більше вписувалося надійність шифру, але швидкість операцій шифрування/дешифрування у своїй знижується.
3. Число раундів обробки. З кожним новим раундом обробки надійність шифру підвищується.
4. Функція раунду F - чим вона складніша, тим важче криптоаналіз шифру.
5. Алгоритм обчислення проміжних ключів K i.
Довгий час найпопулярнішим алгоритмом симетричного шифрування був DES (Data Encrypting Standart), прийнятий 1977 року. Цей алгоритм базується на структурі шифру Файстеля розміром блоку 64 біта іключом.
Функція раунду F використовує набір з восьми так званих Кожна матриця складається з 4 рядків, причому кожен рядок є перестановкою чисел від 0 до 15 (відповідно, 16 стовпців). Матриці жорстко задані 8 . Кожна матриця по-
8 вважалися найсумнівнішою частиною алгоритму DES, оскільки творці алгоритму не розкрили принципи їх заповнення — чому вибрано саме ці матриці і чи алгоритм не містить
проходить на вхід шість біт і видає чотирибітовийрезультат. Перший і останній біт вхідного значення задають рядок матриці, а чотири інших - стовпець. Двійкове уявлення числа, що знаходиться на їхньому перетині, і буде результатом перетворення. Власне перетворення F полягає в наступному:
1. блок R i розширюється до 48 бітів за допомогою спеціальної таблиці шляхом дублювання деяких 16 бітів.
2. Отриманий результат складається із підключенням K i операцією XOR.
3. Результат складання розбивається на 8 шестибітових блоків і кожен із них перетворюється за допомогою відповідної
4. Отриманий у результаті блок піддається жорстко заданої алгоритмі перестановці.
Довгий час DES був федеральним стандартом шифрування США. Цей алгоритм показує хороший лавинний ефект (зміна одного біта відкритого тексту або ключа призводить до зміни багатьох бітів зашифрованого тексту) і успішно протистояв багаторічним спробам злому. Однак довжина ключа в 56 бітів при збільшеній продуктивності ЕОМ зробила шифр потенційно вразливим до перебору ключів, тому в 1997 був оголошений конкурс на новий алгоритм, який повинен був стати криптостандартом на найближчі роки.
Переможця конкурсу було визначено 2000 року — ним став бельгійський шифр.
RIJNDAEL, який був перейменований на AES (Advanced Encryption Standard). Він виявляє-
ся нетрадиційним блоковим шифром, оскільки не використовує мережу Фейштеля. Кожен блок вхідних даних представляється у вигляді двовимірного масиву байт (4х4, 4х6 або 4х8 залежно від розміру блоку, що може змінюватись). Залежно від розміру блоку та довжини ключа алгоритм містить від 10 до 14 раундів, у кожному з яких проводиться низка перетворень - або над незалежними стовпцями, або над незалежними рядками, абовзагалі над окремими байтами у таблиці.
Серед інших сучасних алгоритмів симетричного шифрування слід назвати шифри IDEA, Blowfish, RC5,
4.7. Режими функціонування блокових шифрів
"таємних ходів". Проте за роки спроб злому цього алгоритму слабкості так і не було виявлено.