Ноу Інти, лекція, алгоритми шифрування des і aes
Анотація: Однією з найбільш відомих криптографічних систем з закритим ключем є DES - Data Encryption Standard. Ця система першою отримала статус державного стандарту в області шифрування даних. І хоча старий американський стандарт DES в даний час втратив свій офіційний статус, цей алгоритм все ж заслуговує на увагу при вивченні криптографії. Крім того в цій лекції пояснюється, що таке "дворазовий DES", атака "зустріч посередині" і способи її усунення. У цій же лекції коротко розглядається новий стандарт США на блоковий шифр - алгоритм Rijndael.
Мета лекції. познайомити студента з основними відомостями про алгоритм шифрування DES.
Основні відомості
Однією з найбільш відомих криптографічних систем з закритим ключем є DES - Data Encryption Standard. Ця система першою отримала статус державного стандарту в області шифрування даних. Вона розроблена фахівцями фірми IBM і вступила в дію в США 1977 році. Алгоритм DES широко використовувався при зберіганні і передачі даних між різними обчислювальними системами; в поштових системах, в електронних системах креслень і при електронному обміні комерційною інформацією. Стандарт DES реалізовувався як програмно, так і апаратно. Підприємствами різних країн було налагоджено масовий випуск цифрових пристроїв, що використовують DES для шифрування даних. Всі пристрої проходили обов'язкову сертифікацію на відповідність стандарту.
Незважаючи на те, що вже деякий час ця система не має статусу державного стандарту, вона як і раніше широко застосовується і заслуговує на увагу при вивченні блокових шифрів з закритим ключем.
Довжина ключа в алгоритмі DES становить 56 біт. Саме з цим фактом пов'язана основна полеміка щодо спроможності DES протистояти різним атакам. Як відомо, будь-який блоковий шифр із закритим ключем можна зламати, перебравши всі можливі комбінації ключів. При довжині ключа 56 біт можливі 2 56 різних ключів. Якщо комп'ютер перебирає за одну секунду 1 000 000 ключів (що приблизно дорівнює 2 20), то на перебір всіх 2 56 ключів потрібно 2 36 секунд або трохи більше двох тисяч років, що, звичайно, є неприйнятним для зловмисників.
Однак можливі більш дорогі і швидкі обчислювальні системи, ніж персональний комп'ютер. Наприклад, якщо мати можливість об'єднати для проведення паралельних обчислень мільйон процесорів, то максимальний час підбору ключа скорочується приблизно до 18 годин. Це час не надто велике, і криптоаналитик, оснащений подібної дорогою технікою, цілком може виконати розтин даних, зашифрованих DES за прийнятне для себе час.
Основні параметри DES. розмір блоку 64 біта, довжина ключа 56 біт. кількість раундів - 16. DES є класичною мережею Фейштеля з двома гілками. Алгоритм перетворює за кілька раундів 64-бітний вхідний блок даних в 64-бітний вихідний блок. Стандарт DES побудований на комбінованому використанні перестановки, заміни та гамування. Шіфруемие дані повинні бути представлені в двійковому вигляді.
шифрування
Загальна структура DES представлена на рис. 4.1. Процес шифрування кожного 64-бітового блоку вихідних даних можна розділити на три етапи:
- початкова підготовка блоку даних;
- 16 раундів "основного циклу";
- кінцева обробка блоку даних.
На першому етапі виконується початкова перестановка 64-бітного вихідного блоку тексту, під час якої біти певним чином змінювати порядок.
На наступному (основному) етапі блок ділиться на дві частини (гілки) по 32 біта кожна. Права гілка перетворюється з використанням деякої функції F і відповідного часткового ключа. одержуваного з основного ключа шифрування за спеціальним алгоритмом перетворення ключів. Потім проводиться обмін даними між лівою і правою гілками блоку. Це повторюється в циклі 16 разів.
Нарешті, на третьому етапі виконується перестановка результату, отриманого після шістнадцяти кроків основного циклу. Ця перестановка обратна початковій перестановці.
Мал. 4.1. Загальна схема DES
Розглянемо більш докладно всі етапи криптографічного перетворення за стандартом DES.
На першому етапі 64-розрядний блок вихідних даних піддається початковій перестановці. У літературі ця операція іноді називається "забеліваніе" - whitening. При початковій перестановці біти блоку даних певним чином змінювати порядок. Ця операція надає деяку "хаотичність" вихідного повідомлення, знижуючи можливість використання криптоанализа статистичними методами.
Одночасно з початковою перестановкою блоку даних виконується початкова перестановка 56 біт ключа. З рис. 4.1. видно, що в кожному з раундів використовується відповідний 48-бітний частковий ключ Ki. Ключі Ki виходять за певним алгоритмом, використовуючи кожен з бітів початкового ключа по кілька разів. У кожному раунді 56-бітний ключ ділиться на дві 28-бітові половинки. Потім половинки зрушуються вліво на один або два біта в залежності від номера раунду. Після зсуву певним чином вибирається 48 з 56 бітів. Так як при цьому не тільки вибирається підмножина бітів, а й змінюється їх порядок, то ця операція називається "перестановка із стисненням". Її результатом є набір з 48 бітів. В середньому кожен біт вихідного 56-бітного ключа використовується в 14 з 16 подключей, хоча не всі біти використовуються однакову кількість разів.
Далі виконується основний цикл перетворення, організований по мережі Фейштеля і складається з 16 однакових раундів. При цьому в кожному раунді (рис. 4.2) виходить проміжне 64-бітове значення. яке потім обробляється в наступному раунді.
Мал. 4.2. Структура одного раунду DES
Ліва і права гілки кожного проміжного значення обробляються як окремі 32-бітові значення, позначені L і R.
Спочатку права частина блоку Ri розширюється до 48 бітів, використовуючи таблицю, яка визначає перестановку плюс розширення на 16 бітів. Ця операція призводить розмір правої половини в відповідність до розміру ключа для виконання операції XOR. Крім того, за рахунок виконання цієї операції швидше зростає залежність всіх бітів результату від бітів вихідних даних і ключа (це називається "лавинним ефектом"). Чим сильніше виявляється лавинний ефект при використанні того чи іншого алгоритму шифрування, тим краще.
Після виконання перестановки з розширенням для отриманого 48-бітного значення виконується операція XOR з 48-бітовим підключити Ki. Потім отримане 48-бітове значення подається на вхід блоку підстановки S (від англ. Substitution - підстановка), результатом якої є 32-бітове значення. Підстановка виконується в восьми блоках підстановки або восьми S-блоках (S-boxes). При виконанні цієї операції 48 бітів даних діляться на вісім 6-бітових подблоков, кожен з яких по своїй таблиці замін замінюється чотирма бітами. Підстановка за допомогою S-блоків є одним з найважливіших етапом DES. Таблиці замін для цієї операції спеціально спроектовані фахівцями так, щоб забезпечувати максимальну безпеку. В результаті виконання цього етапу виходять вісім 4-бітових блоків, які знову об'єднуються в єдине 32-бітове значення.
Далі отримане 32-бітове значення обробляється за допомогою перестановки Р (від англ. Permutation - перестановка), яка не залежить від використовуваного ключа. Метою перестановки є максимальне переупорядочивание бітів таке, щоб в наступному раунді шифрування кожен біт з великою ймовірністю оброблявся іншим S-блоком.
І, нарешті, результат перестановки об'єднується за допомогою операції XOR з лівою половиною початкового 64-бітового блоку даних. Потім ліва і права половини міняються місцями, і починається наступний раунд.
Після шістнадцяти раундів шифрування виконується кінцева перестановка результату. Ця перестановка інверсний (обернена) початкової перестановці.
Після виконання всіх цих дій блок даних вважається повністю зашифрованим і можна переходити до шифрування наступного блоку вихідного повідомлення.