Міністерство освіти і науки України Національний університет “Львівська політехніка” Звіт про виконання лабораторної роботи №3 На тему: „ Алгоритм шифрування DES” З курсу: “Методи і засоби криптологічних перетворень” Львів 2008 Мета: дослідити симетричні шифри на прикладі алгоритму DES. Теоретичні відомості Стандарт шифрування даних (англійською Data Encryption Standard — DES) був розроблений у 70-х роках фахівцями з IBM і у 1976 році був прийнятий через NBS та ANSI у якості федерального стандарту Сполучених Штатів для захисту комерційної та урядової інформації, не пов’язаної з національною безпекою. Цим актом увінчався цілий етап у розвитку криптографії — майже одночасно з’явилися принципово нові криптосистеми з відкритим ключем, яким присвячено більшість подальших розділів цієї книжки. Спробуємо простежити уявний шлях від шифру одноразового блокноту до криптосистеми DES. Для цього нагадаємо дві основні харак3К3стики першого. З одного боку, шифр одноразового блокноту є абсолютно надійним, а з іншого, він далеко не завжди є практичним через велику довжину ключа. Тому перший крок є таким — довжина ключа має бути фіксованою, а шифрування має відбуватися блоками. Як і шифр одноразового блокноту, DES оперує з інформацією поданою у двійковій формі, а довжина блоку і довжина ключа вибрані рівними 64. Іншими словами, двійкове повідомлення М розбивають на блоки по 64 біти і шифрують кожен блок окремо, використовуючи один і той же двійковий ключ К довжини 64. Таким чином, повідомлення М = М1М2М3 … перетворюється у криптотекст С = С1С2С3…, де d — ЕK(Мi). У стандарті DES кожен блок криптотексту Сi також є двійковою послідовністю довжини 64. Звернемося до питання вибору алгоритму Е. Апріорно він повинен задовольняти три умови: можливість дешифрування: для будь-якого ключа K різним блокам повідомлення М’ і М» відповідають різні блоки криптотексту ЕK(М’) і ЕK(М»), інакше кажучи, алгоритм ЕK з будь-яким ключем здійснює перестановку двійкових послідовностей довжини 64; ефективність: і шифрування, і дешифрування відбуваються швидко; надійність: якщо ключ невідомий, то немає способу розкриття шифру. Останній пункт потребує принципового уточнення. Зрозуміло, що як би вдало алгоритм Е не був спроектований, надійність, що давалася шифром одноразового блокноту, вже буде недосяжною. Недосяжною з тої причини, що будь-який блоковий шифр можна зламати за допомогою брутальної атаки, яка у нашому випадку полягає в переборі всіх двійкових ключів К довжини 64. Про яку ж надійність йдеться? Зауважимо, що всього двійкових ключів довжини 64 є 264. Елементарні обчислення показують, що комп’ютер із тактовою частотою 100 MHz перебиратиме всі можливі ключі 264/108 секунд, тобто довше ніж 5800 років. Звичайно, повний перебір необхідний лише у найгіршому випадку. У середньому, потрібний ключ буде знайдено вдвічі швидше — приблизно за 2900 років — час, за який таємниця втратить актуальність. Якщо для шифру невідомо методу його ламання упродовж більш реалістичного терміну, то такий шифр вважають надійним в обчислювальному сенсі. Якщо ми хочемо отримати криптосистему надійну у такому новому розумінні, зразу відмовимось від наївної спроби вдосконалити шифр одноразового блокноту і покласти ЕK(Мi) = Мi,K. Таке шифрування є дуже швидке, але вкрай ненадійне. Для розкриття досить просумувати за модулем 2 криптотекст із самим собою, але зсунутим на 64 позиції. Із рівності КК=0 випливає, що результат буде тим же, що й при сумуванні повідомлення із самим собою зсунутим на ту ж кількість позицій. Із цієї інформації, яка вже ніяк не залежить від ключа, неважко отримати саме повідомлення, запорукою чого є феномен надлишковості будь-якої природної мови. Розробники стандарту DES пропонують наступну конструкцію (подальший опис алгоритму спрощено задля акцентування найважливіших фаз його роботи). Алгоритм E приймає на вхід двійковий блок М довжини 64 та використовує ключ К, з якого виділяються 16 частин K1,…,K16 по 48 бітів кожна. Це так звані циклові ключі. Блок М розбивається на дві рівні частини по 32 біти: ліву L0 та праву R0. Відбувається 16 циклів перетворення повідомлення М=L0R0. У і-му циклі (Lі-1, Rі-1) за допомогою Кі перетворюється у (Lі, Rі) наступним чином: Lі = Rі-1, R і = Lі-1f(Rі-1, Kі), де f — деяка функція, що перетворює двійкові послідовності довжини 80 у двійкові послідовності довжини 32. Насамкінець ліва та права частини міняються місцями, що і є результатом роботи алгоритму: ЕК(М) = R16Ll6. Описана процедура різні блоки М’ і М» перетворює у різні блоки 3К(М’) і Ек(М»), незалежно від вибору функції f. Більше того, якщо Ек1,…,к16(М) = С, то М = Ек1,…, к16{С), тобто дешифруючий алгоритм ідентичний із шифруючим, варто лише взяти послідовність ключів у зворотньому порядку. Функцію f стандарт DES пропонує такої форми: f(R,Ki) = s(e(R) Кi). Функція e розширює R із 32 бітів до 48, вставляючи копії деяких 16 позицій. Функція s перетворює двійкові послідовності довжини 48 у двійкові послідовності довжини 32. Вона реалізується так. Двійковий вхід А довжини 48 розбивається на 8 блоків А1 … A8 по 6 бітів і кожен блок Аi замінюється на деякий блок із 4 бітів шляхом застосування деякої функції s,. Кожна із цих 8-ми функцій реалізована незалежно від інших. Реалізації цих функцій називаються S-блоками. Після цього отримані 32 біти перемішуються згідно із деякою перестановкою р. Таким чином, s(A) = p(s1(A1) … S8(A8)), що й завершує опис алгоритму DES. Згідно із стандартом, описана нами процедура починається із переставлення бітів блоку М відповідно до фіксованої перестановки IP і завершується застосуванням до отриманого результату оберненої перестановки IP-1. Із 64 бітів ключа К алгоритм DES насправді використовує лише 56. Решта бітів можуть служити для перевірки неушкодженості даних при пересиланні ключа — з цією метою кожен восьмий біт покладають рівним сумі за модулем 2 попередніх семи. Результат виконання шифрування Ключ ABCDEF0123456789  Відкритий текст ABCDEFABCDEF1234   Initial KEY=ABCDEF0123456789 1010101111001101111011110000000100100011010001010110011110001001 SETTING ROUND KEYS Initially C=1000011101100110010101010000 D=0101010101100110100001110000 Key for round 1 C=0000111011001100101010100001 D=1010101011001101000011100000 K0=110001010111110000010010101100001010110000011010 Key for round 2 C=0001110110011001010101000010 D=0101010110011010000111000001 K1=000001000100001101101110100100110001010110001101 Key for round 3 C=0111011001100101010100001000 D=0101011001101000011100000101 K2=101000100101000100110101100010100001001110100001 Key for round 4 C=1101100110010101010000100001 D=0101100110100001110000010101 K3=100011010000101101100001010100100110101100100101 Key for round 5 C=0110011001010101000010000111 D=0110011010000111000001010101 K4=100000110111001010111001011100100000100110011000 Key for round 6 C=1001100101010100001000011101 D=1001101000011100000101010101 K5=100111010001011111000000110000010011000100011011 Key for round 7 C=0110010101010000100001110110 D=0110100001110000010101010110 K6=010100100101101011001001011001110011001000101000 Key for round 8 C=1001010101000010000111011001 D=1010000111000001010101011001 K7=000110011111000101000100011100000001100101101110 Key for round 9 C=0010101010000100001110110011 D=0100001110000010101010110011 K8=100101110010110000011100010111101100010100000100 Key for round 10 C=1010101000010000111011001100 D=0000111000001010101011001101 K9=010011100010011010010000100010000110010111001000 Key for round 11 C=1010100001000011101100110010 D=0011100000101010101100110100 K10=010111101001110000101100111010001111001000000001 Key for round 12 C=1010000100001110110011001010 D=1110000010101010110011010000 K11=110010101010000001001010111100100100011000101010 Key for round 13 C=1000010000111011001100101010 D=1000001010101011001101000011 K12=001010001100111000101110100111000001101100001010 Key for round 14 C=0001000011101100110010101010 D=0000101010101100110100001110 K13=111000000011100100001010100101000111001001110000 Key for round 15 C=0100001110110011001010101000 D=0010101010110011010000111000 K14=001000001010111001110001011100011010101001100000 Key for round 16 C=1000011101100110010101010000 D=0101010101100110100001110000 K15=101110001101000001010100010000101100001010011101 E N C R Y P T I O N input block=ABCDEFABCDEF1234 1010101111001101111011111010101111001101111011110001001000110100 Rounds 1 L=36C0B63F R=3FAD3F6D K1=110001010111110000010010101100001010110000011010 2 L=3FAD3F6D R=5E4C3E96 K2=000001000100001101101110100100110001010110001101 3 L=5E4C3E96 R=3A47E827 K3=101000100101000100110101100010100001001110100001 4 L=3A47E827 R=42211720 K4=100011010000101101100001010100100110101100100101 5 L=42211720 R=C090DC40 K5=100000110111001010111001011100100000100110011000 6 L=C090DC40 R=9755107F K6=100111010001011111000000110000010011000100011011 7 L=9755107F R=727D1D2D K7=010100100101101011001001011001110011001000101000 8 L=727D1D2D R=F7F666D6 K8=000110011111000101000100011100000001100101101110 9 L=F7F666D6 R=7F4EC556 K9=100101110010110000011100010111101100010100000100 10 L=7F4EC556 R=1FF7999E K10=010011100010011010010000100010000110010111001000 11 L=1FF7999E R=1501B315 K11=010111101001110000101100111010001111001000000001 12 L=1501B315 R=20FDFF4C K12=110010101010000001001010111100100100011000101010 13 L=20FDFF4C R=F62B50EE K13=001010001100111000101110100111000001101100001010 14 L=F62B50EE R=9BFB4549 K14=111000000011100100001010100101000111001001110000 15 L=9BFB4549 R=C1277BBA K15=001000001010111001110001011100011010101001100000 16 L=C1277BBA R=EC9C76B7 K16=101110001101000001010100010000101100001010011101 output block=020BFEA57BCE9CA7 0000001000001011111111101010010101111011110011101001110010100111 D E C R Y P T I O N input block=020BFEA57BCE9CA7 0000001000001011111111101010010101111011110011101001110010100111 Rounds 1 L=3454EC9A R=EC9C76B7 K16=101110001101000001010100010000101100001010011101 2 L=EC9C76B7 R=C1277BBA K15=001000001010111001110001011100011010101001100000 3 L=C1277BBA R=9BFB4549 K14=111000000011100100001010100101000111001001110000 4 L=9BFB4549 R=F62B50EE K13=001010001100111000101110100111000001101100001010 5 L=F62B50EE R=20FDFF4C K12=110010101010000001001010111100100100011000101010 6 L=20FDFF4C R=1501B315 K11=010111101001110000101100111010001111001000000001 7 L=1501B315 R=1FF7999E K10=010011100010011010010000100010000110010111001000 8 L=1FF7999E R=7F4EC556 K9=100101110010110000011100010111101100010100000100 9 L=7F4EC556 R=F7F666D6 K8=000110011111000101000100011100000001100101101110 10 L=F7F666D6 R=727D1D2D K7=010100100101101011001001011001110011001000101000 11 L=727D1D2D R=9755107F K6=100111010001011111000000110000010011000100011011 12 L=9755107F R=C090DC40 K5=100000110111001010111001011100100000100110011000 13 L=C090DC40 R=42211720 K4=100011010000101101100001010100100110101100100101 14 L=42211720 R=3A47E827 K3=101000100101000100110101100010100001001110100001 15 L=3A47E827 R=5E4C3E96 K2=000001000100001101101110100100110001010110001101 16 L=5E4C3E96 R=3FAD3F6D K1=110001010111110000010010101100001010110000011010 output block=ABCDEFABCDEF1234 1010101111001101111011111010101111001101111011110001001000110100 Висновок: під час виконання даної лабораторної роботи ми ознайомилися з алгоритмом шифрвання DES та за допомогою програмної реалізації даного коду зашифрували 16-розрядне повідомлення ABCDEFABCDEF1234 за допомогою ключа ABCDEF0123456789 та отримали як результат зашифрований текст 020BFEA57BCE9CA7.