ШИФР DES

Алгоритм шифрування DES (від англ. «Data Encryption Standard») був опублікований в 1977 році і призначався для захисту важливої, але несекретной інформації в державних і комерційних організаціях США. Реалізовані в ньому ідеї були багато в чому запозичені в більш ранній розробці корпорації IBM - шифр «Люцифер» (а саме в IBM працював Хорст Фейсгель, автор розглянутої вище схеми). Але для свого часу «Люцифер» був занадто складним, і його реалізації відрізнялися низькою швидкодією.

Шифр DES є блоковим - перетворення в ньому проводяться блоками по 64 біта. Ключ також 64-бітний, але значущими є тільки 56 біт - кожен 8-й розряд використовувався для контролю парності (шифр розроблявся тоді, коли апаратура була не надто надійної і подібні перевірки були необхідні). Узагальнена схема алгоритму представлена на рис. 2.4.

Узагальнена схема шифру DES

Мал. 2.4. Узагальнена схема шифру DES

Кінцева перестановка - IP 1 -є зворотною по відношенню до начальной- IP. Задають їх таблиці жорстко визначені стандартом (таблиці можна дізнатися з офіційного опису стандарту, також вони наводяться, наприклад в [9]).

Раунди шифрування стоятся відповідно до розглянутої раніше схемою Фейстеля (рис. 2.2). Шифрування проводиться в 16 раундів. Схема раундової функції F представлена на рис. 2.5.

Спочатку 32-бітний правий полублок перетворюється тексту розширюється до 48 біт за допомогою функції розширення Е. Ця функція виробляє дублювання і перестановку деяких елементів блоку. У табл. 2.2 показано, як ця функція працює. Після розширення в перших позиціях отриманого 48-бітпого блоку будуть стояти 32-й, 1-й і т. Д. Біти вхідного блоку.

Схема раундової функції шифру DES

Мал. 2.5. Схема раундової функції шифру DES

Таблиця 2.2

Функція Е - розширення блоку

Після розширення отриманий 48-розрядний блок складається побитно по модулю 2 з раундовим ключем АТ "схема генерації якого буде розглянута нижче.

Далі проводиться підстановка за таблицями Si, 5 «, в результаті якої кожному 6-разрядному вхідному значенню ставиться у відповідність 4-розрядний вихідний. Таким чином, отримавши на вході 48 біт, на виході знову маємо 32. 5, являє собою таблицю з 16-ю стовпчиками і 4-ма рядками, що містить 4-бітові елементи. Таблиці підстановки, також як і перестановки, чітко визначені стандартом.

Обчислення раундовий ключів

Мал. 2.6. Обчислення раундовий ключів

Нехай на вхід підстановки подається 6-розрядний блок B = b? 2 ... b 6 . Тоді сукупність старшого і молодшого розрядів ЬЬ Ь буде вказувати номер рядка, а четирехбітних значення b 2 b 2 b 4 b 5 - номер стовпчика. З осередку на перетині знайдених рядки і стовпці буде братися вихідне значення підстановки. Отриманий з'єднанням вихідних значень підстановок 5],. S » 32-бітний блок піддається перестановці Р, порядок якої також строго визначений в стандарті.

Розглянемо тепер порядок формування раундовий ключів на основі секретного. У загальному вигляді алгоритм представлений на рис. 2.6.

Як було зазначено раніше, секретний ключ шифру DES має довжину 64 біта, але кожен 8-й призначається для контролю парності, тому ефективна довжина ключа - 56 біт. Функція PC 1 (скорочення «РС» від англ. «Permuted Choice» - вибір з перестановкою) здійснює перестановку елементів вихідного блоку, відкидаючи 8-й, 16-й і т. Д. Біти. Після перестановки отриманий блок ділиться на напівблоки З () і Д> довжиною 28 біт кожен.

Залежно від номера кроку напівблоки С, і Д незалежно один від одного перетворюються шляхом циклічного зсуву вліво на одну або дві позиції (зрушення на одну позицію проводиться на 1, 2, 9 і 16-м кроках, в інших випадках - зрушення на дві позиції ). Функція РС2 перетворює блок С, 1Д, переставляючи елементи і відбираючи 48 біт, які і формують раундовий ключ шифрування До , (/ = 1-16).

Для того щоб мати можливість використовувати шифр DES для вирішення різних криптографічних завдань, визначені 4 режими його роботи:

  • - електронна кодова книга (англ. «Electronic Code Book» - ЄСВ);
  • - зчеплення блоків шифру (англ. «Cipher Block Chaining» - СВС);
  • - зворотний зв'язок по шифртексту (англ. «Cipher FeedBack» - CFB);
  • - зворотний зв'язок по виходу (англ. «Output FeedBack» - OFB).

При використанні режиму ЄСВ захищається повідомлення розбивають на 64-бітові блоки М ,. Кожен такий блок шифрують незалежно від інших, з використанням одного і того ж ключа шифрування (рис. 2.7). При розшифрування криптограми С, також перетворять незалежно.

Шифрування (а) і розшифрування (б) в режимі ЄСВ

Мал. 2.7. Шифрування (а) і розшифрування (б) в режимі ЄСВ

Перевагою даного режиму є простота його реалізації. Головний недолік режиму ЄСВ полягає в тому, що якщо в вихідному повідомленні є повторювані блоки, то і значення відповідних блоків криптограми буде збігатися. А его дасть криптоаналітику противника додаткову інформацію про зміст повідомлення. Тому режим ЄСВ рекомендують використовувати для захисту невеликих обсягів даних (наприклад, криптографічних ключів), де ймовірність появи співпадаючих блоків повідомлення невелика.

Зазначеного вище недоліку позбавлений режим СВС. Оригінал тексту, як і в попередньому випадку, розбивається на блоки М, по 64 біта. Перший блок складається побитно по модулю 2 з 64-бітовим блоком, званим ініціалізувалися вектором IV, який відомий обом сторонам взаємодії, періодично ними змінюється і тримається в секреті від інших. Блок початкового повідомлення М 2 модифікується з використанням блоку криптограми С і т. Д. Аналогічні дії проводяться при розшифрування. Схема перетворення представлена на рис. 2.8.

Шифрування (а) і розшифрування (б) в режимі СВС

Мал. 2.8. Шифрування (а) і розшифрування (б) в режимі СВС

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

Режим CFB використовується в тих випадках, коли довжина перетворюється блоку відрізняється від 64 біт. Нехай необхідно зашифрувати повідомлення, прочитуване послідовно блоками по г біт, де 1 < г <64. Для побудови перетворення використовується зсувний регістр /, куди на 1-му кроці перетворення поміщається не започатковано вектор IV. Схема перетворення представлена на рис. 2.9.

Конвертувати повідомлення М розбите на блоки по г біт, позначені на рис. 2.9 як М ,. Блок криптограми С, буде дорівнює Му, складеному побитно по модулю 2 з г старшими бітами зашифрованого на j -му кроці блоку. Шіфруемого значення /, виходить шляхом зсуву попереднього блоку / у.] Вліво на г позицій і записи блоку криптограми Су. | в молодші позиції.

При розшифрування зсувний регістр також инициализируется значенням IV. Для того щоб отримати ту ж послідовність допоміжних значень Oj, що і при шифруванні, тут також використовується DES шифрування (а нс розшифрування, як наприклад, при зворотному перетворенні в режимі СВС).

Шифрування (а) і розшифрування (б) в режимі CFB

Мал. 2.9. Шифрування (а) і розшифрування (б) в режимі CFB

Шифрування (а) і розшифрування (б) в режимі OFB

Мал. 2.10. Шифрування (а) і розшифрування (б) в режимі OFB

Режим OFB також дозволяє шифрувати блоки, менші за довжиною, ніж 64 біта. Його схема представлена на рис. 2.10. Аналогічно режиму CFB, зсувний регістр спочатку містить значення не започатковано вектора. Є два варіанти модифікації його значення. На малюнку представлений варіант з повною заміною на j-м кроці вмісту зсувного регістру допоміжним значенням Oj. |. Другий варіант побудови схеми передбачає, як і в разі CFB, зрушення вліво на г розрядів і запис в молодші розряди зсувного регістру старших / - розрядів Oj ..

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

Деякий час шифр DES вважався досить безпечним. Але в міру розвитку обчислювальної техніки короткий 56-бітний ключ привів до того, що атака шляхом повного перебору ключового безлічі стала відносно легко реалізовується. Щоб збільшити стійкість алгоритму і в той же час зберегти існуючі напрацювання (у вигляді програмних і апаратних реалізацій алгоритму), було використано багаторазове шифрування.

Спочатку було запропоновано використовувати повторне шифрування на різних ключах. Позначимо шифрування на ключі до як Е до , а розшифрування як D k . Тоді пропонована схема прямого перетворення описувалася як С = Е к2к1 (М)), обратного- MD kl (D k2 (C)). Однак згодом було доведено, що через те, що два рази використовується один і той же перетворення, проти подібної схеми може бути успішно застосована атака «зустріч посередині». Її суть полягає в тому, що якщо зберігати в пам'яті великий обсяг предви- чіслсній (розрахунок криптограми для всіх можливих значень ключа), то можна зламати наведену вище схему дворазового шифрування за 2 п + | спроб (замість 2 2 "як було б при подвоєнні довжини ключа).

Більш надійною виявилася схема, що включає шифрування, розшифрування і повторне шифрування на різних ключах. Даний шифр отримав назву Triple DES. Варіанти схеми його побудови приведені на рис. 2.11.

I. Шифр Triple DES

Мал. 2.1 I. Шифр Triple DES

Використання в шифрі Triple DES різних ключів і перетворень (шифрування і розшифрування) дозволяє протистояти атаці «зустріч посередині». У першому випадку, вибір ключів проводиться так, як показано у верхній частині рис. 2.11: спочатку проводиться шифрування на ключі К і далі - розшифрування на ключі К 2 , після - шифрування на ключі К. Сумарна довжина ключа - 112 біт. Більш надійною вважається схема з використанням в третьому перетворенні ще одного ключа - До 3 (зображена в нижній частині рис. 2.11). Тоді сумарний ключ буде довжиною 168 біт.

За рахунок більш високої надійності в даний час шифр Triple DES використовується частіше, ніж шифр DES.

 
Переглянути оригінал
< Попер   ЗМІСТ   ОРИГІНАЛ   Наст >