Алгоритм DES: опис і приклад

Data Encryption Standard (DES) - це стандарт шифрування даних, винайдений в США в 80-х роках ХХ століття. Серед шифрів він по праву вважається "пенсіонером", при цьому залишаючись робочою конячкою криптографії. DES перестав бути придатним в умовах надшвидкої техніки і великих об'ємів даних через обмеження у 56 біт на ключ і 64 біт на дані. Однак він все ще використовується.

Що таке блокові шифри?

DES - алгоритм блочного шифрування. За останні 20-30 років було створено безліч блокових шифрів, але створити хороший шифр, який був би безпечним, завдання досить складне. Важливо, щоб шифр мав характеристики, які дозволять йому функціонувати в багатьох сферах і галузях. Блокові шифри складаються з декількох ітерацій почергового використання деякого шифру. Кожна ітерація називається раундом. Як показує практика, навіть деякі з примітивних алгоритмів при послідовному використанні здатні створювати надійні шифри. Алгоритм DES - приклад, який залишався надійним і незламним 20 років.


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

Використання DES

Хоча DES визнаний застарілим і не відповідає сучасним вимогам, він може бути використаний, наприклад, у вигляді 3DES, коли шифр застосовується три рази поспіль. Такий підхід знімає обмеження в розмірі ключа, але блок шифруемых даних залишається незмінним. У свій час DES був достатньо швидким і криптоустойчивым шифром. Зараз це не так, а 3DES і зовсім працює втричі повільніше. Незважаючи на це DES, як і раніше використовується в ряді систем, але його застосування в нових проектах заборонено.


Офіційно алгоритм шифру DES був стандартом у США до 1998 року. У 1997 році почалося створення нового стандарту, який був названий AES (Advanced Encryption System), і хоча криптоаналіз показує, що спроба зламати DES призводить до безлічі систем нелінійних рівнянь, аналітичні методи не здатні допомогти вирішити завдання - його слабким місцем є мале безліч можливих ключів. Їх кількість дорівнює 2 56 і всі варіанти можна перебрати за допомогою сучасних технологій за відносно короткий термін.

Один раунд в алгоритмі

Для ясності викладу і опису алгоритму DES використовуємо малюнок (лінійну діаграму обчислень) 4.1 показує структуру одного раунду. Кожен прямокутник у лінійній діаграмі представляє собою якісь обчислення, а виходить з нього стрілка вказує, куди будуть передані результати роботи блоку. Знаком плюс, обведеним в гурток, позначається операція "що виключає або", звана в програмування XOR. Операція ще носить ім'я "побітове додавання" або "додавання без переносу". У мережі можна знайти алгоритм DES на C і вивчити його для кращого розуміння. DES приймає текстовий блок, розміром 64 біта. Він проходить через початкову перестановку за певним принципом. При аналізі алгоритму з'ясувалося, що сенсу в цій перестановці мало, оскільки вона не дає якогось криптографічного ефекту. Текстовий блок розбивається на 2 рівні частини: права (R) і ліва (L). Потім шифровані частини міняються місцями і об'єднуються, а в кінці раунду виходить 64-бітовий блок даних, зашифрований.

Загальний алгоритм

Алгоритм DES включає в себе 16 раундів, які здійснюються за схемою, описаною вище. Всі раунди пронумеровані через i, де i = (1; 16). Кожен i-ий раунд з пари (Li-1 Ri-1) отримує нову пару (Li, Ri), використовуючи ключ Ki. Основні перетворення відбуваються всередині функції F.

Алгоритм роботи функції F

Як видно з рисунку 4.1 R проходить через операцію "Розширення". Даний блок дублює ряд бітів з R і доповнює його ними, отримуючи 48-бітове значення. Отриманий результат проходить через побітове додавання з 48-бітовим ключем Кі. І результат цієї операції передається в блок S. Блок S містить 8 маленьких матриць-підстановки, які підібрані особливим чином. Кожна матриця отримує на вході 6 бітів інформації і видає 4-бітове значення. У підсумку на вході блок S отримує дані розміром 48 біт, а на виході являє результат у вигляді 32-бітового значення. Дане 32-бітне значення проходить через ще одну операцію перестановки, після чого підсумовується операцією xor з L. Нарешті права і ліва частина міняються місцями й раунд завершується. Як вже говорилося раніше, таких раундів алгоритм вчиняє 16 штук. Тут ми не будемо перевантажувати статтю прикладами, які займають багато місця. Роботу алгоритму шифрування DES і приклади можна подивитися в мережі.

Шифр Фейстеля

Алгоритм DES заснований на шифрі Фейстеля. Його ідея дуже витончена. На кожному раунді частина L складається зі значенням F(R, Ki) і L змінюється позицією з R. Ключовою особливістю алгоритму Фейстеля є те, що дешифрування і шифрування складаються з однакових кроків: частини L і R міняються місцями, а потім виконується операція додавання L і F (R, Ki). Це дозволяє зробити процедури шифрування і розшифровки простими і зрозумілими.
У шифрах Фейстеля найчастіше вводиться одне цікаве зміна - скасування перестановки L і R в останній ітерації. Це робить алгоритми шифрування і дешифрування повністю симетричними. Різниця полягає лише в порядку використання ключів Ki. Цей принцип виявився дуже зручним для використання на програмному рівні, так як шифрування і розшифрування відбувається засобами однієї функції. Наприклад, лаконічна реалізація алгоритму шифрування DES на C.

Ключі шифрування

Для шифрування даних DES використовується шістнадцять 48-бітових ключів. По одному ключу на раунд. Кожен ключ створюється вибіркою 48 біт з 56-бітового основного ключа. Створення ключів або іншого раунду визначається механізмом, докладно описаними в документації DES. Коротко алгоритм вибірки i ключа виглядає наступним чином. В основний ключ на позиції 81624 324048 5664 додаються біти. Робиться це таким чином, щоб кожен байт містив непарну кількість одиниць. Дотримання правил допомагає виявляти помилки при обміні ключів. Після цього, використовуючи спеціальні таблиці, доповнений ключ піддається перестановці і зрушень, за винятком бітів, які були додані. Таким чином виходить необхідний ключ.

Компоненти DES

Кожен компонент алгоритму DES вирішує певну задачу: Алгоритм Фейстеля спрощує шифрування і розшифровку, гарантуючи при цьому змішування обох половин тексту. Побітове додавання частин тексту з ключами перемішує відкриті дані з ключем і шифрує їх. S-блок і таблиці відповідностей роблять алгоритм нелінійним, підвищуючи його стійкість до різних атак. Розширення, S-блок і перестановки забезпечують дифузію алгоритму - лавинний ефект. Іншими словами, якщо у вхідних даних функції F зміниться хоч 1 біт, то це викличе зміну відразу безлічі бітів. Якщо лавинний ефект у шифрі не спостерігається, то зміни відкритих даних будуть призводити до рівноцінним змін у шифрованому вигляді, які можна відстежити і використовувати для злому. У криптографії існує критерій лавинного ефекту. Алгоритм задовольняє йому, якщо при зміні 1 біта відкритих даних змінюється не менше половини шифрованих даних. Алгоритм DES задовольняє йому, починаючи з 4 раунди. Підсумок - при зміні 1 біта відкритих даних у шифрі DES зміняться 29 бітів.

Проблеми безпеки в DES

Очевидною проблемою DES є вибірка ключів шифрування із загального ключа. Що буде, якщо в якості ключа вибрати нульове значення (всі біти ключа дорівнюють 0)? Це призведе до того, що вибірка всіх ключів для шифрування на кожному раунді буде однаковою, а всі ключі будуть дорівнюють нулю. Мало того, що 16 шифрований пройдуть з одним ключем, так із-за того, що алгоритми шифрування і дешифрування DES відрізняються тільки порядком застосування ключів, вони будуть абсолютно однаковими. Втратиться весь сенс шифрування.
DES має 4 ключами, які називаються слабкими, що призводять до описаного ефекту. У DES є 12 полуслабых і 48 псевдослабых ключів, які призводять до обмеження варіацій генеруються ключів в раундах. Іншими словами, є імовірність, що в ході шифрування в 16 раундах буде використано не 16 різних ключів, а 8 4 або навіть 2. Менш очевидним недоліком DES є властивість комплементарності. Воно означає, що якщо при шифруванні використовувати додаток відкритого тексту і доповнення ключа, то в підсумку вийде значення, яке є доповненням шифрованого тексту. Це безглузде властивість може призводити до успішних атак на проекти, що використовують DES для забезпечення безпеки.

Проблема ключа шифрування

Є основоположною для DES і вважається головною причиною, чому варто відмовитися від цього алгоритму. Так як розмір ключа DES становить 56 біт, то для перебору всіх ключів знадобиться переглянути 2 56 варіантів. Чи Так це багато? Якщо здійснювати за 10 мільйонів перевірок ключів в секунду, то на перевірку піде близько 2000 років. Здається, що алгоритм досить стійкий. Він був таким у минулому столітті, коли створення комп'ютера подібної потужності було майже неможливим завданням як з технічної, так і з фінансової точки зору. Якщо створити комп'ютер з мільйоном чіпів, то перебір всього безлічі ключів DES займе 20 годин. Перший подібний комп'ютер для розшифровки за алгоритмом DES з'явився ще в 1998 році, який впорався з поставленим завданням за 56 годин. Сучасні технології мереж і паралельних процесів дозволяють скоротити цей час ще більше.

Криптоаналіз і DES

Можна без перебільшення заявити, що DES став причиною появи прикладної науки під назвою "Криптографічний аналіз". З самого початку появи DES робилися спроби його зламати, проводилися наукові роботи по його вивченню. Все це призвело до зародження таких областей математики, як: лінійний криптоаналіз - вивчення і виявлення залежності між відкритим текстом і шифрованим; диференціальний криптоаналіз - вивчення та аналіз залежностей між кількома відкритими текстами та їх шифрованими версіями; криптоаналіз на пов'язаних ключах - вивчення залежностей між шифрованими текстами, отриманими на первинному ключі, і ключах, пов'язаних з первинним яким-небудь чином. DES витримав 20 років всесвітнього криптоаналізу і атак, але залишився стійким шифром. Але хто шукає - той завжди знайде Бихам і Шамір, вчені з Ізраїлю, в 1991 році показали за допомогою диференціального криптоаналізу, що на DES можна зробити атаку, при якій ключ обчислювався за умови, що у атакуючого є 2 47 спеціально підібраних пар відкритого і шифрованого текстів. Японський учений Митсуру Мацуї в 1993 році показав, що обчислити ключ можна за допомогою лінійного криптоаналізу. Для цього всього лише потрібно знати 2 47 пар відкритого тексту і відповідної шифрованого варіанти. Надалі ці методи злому були трохи дороблені, поліпшені і спрощені, також з'явився ряд нових способів злому. Але вони залишаються надто складними, на їх фоні повний перебір всіх варіантів ключів виглядає найбільш адекватною атакою на DES.