Лекция 5. Введення в основи сучасних шифрів із симетричним ключем

Цілі:

- познайомити студентів з основними сучасними шифрами з симетричним ключем;
- сформувати в студентів представлення про сучасні методи шифрування інформації.

План.

  1. Сучасні блокові шифри
  2. Компоненти сучасного блокового шифру
  3. Складені шифри

Традиційні шифри із симетричним ключем, які ми вивчали дотепер, орієнтуються на символи. З появою комп'ютера стали необхідні шифри, орієнтовані на біт. Тому що інформація, яку треба зашифрувати, - не завжди тільки текст; вона може також складатися із чисел, графіки, аудіо- і відеоданих. Зручно перетворити ці типи даних у потік бітів, щоб зашифрувати цей потік, і потім передати зашифрований потік. Крім того, коли текст оброблений на розрядному рівні, кожний символ замінений на 8 (або 16) біт, а це означає, що число символів стає в 8 (або 16) раз більше. Змішування більшого числа символів збільшує безпеку.

1. Сучасні блокові шифри

Сучасний блоковий шифр із симетричними ключами шифрує n-бітовий блок вихідного тексту або розшифровує n-бітовий блок зашифрованого тексту. Алгоритм шифрування або дешифрування використовують k-бітовий ключ. Алгоритм дешифрування повинен бути інверсією алгоритму шифрування, і обоє в роботі використовують той самий ключ.


Рис. 1. Сучасний блоковий шифр

Якщо повідомлення має розмір менше, чим n біт, потрібно додати заповнення, щоб створити цей n-розрядний блок; якщо повідомлення має більше, чим n біт, воно повинне бути розділене на n-розрядні блоки, і якщо буде потреба потрібно додати до останнього блоку відповідне заповнення. Загальні значення для n звичайно 64, 128, 256 або 512 бітів.

Приклад 1. Скільки додаткових біт потрібно додати до повідомлення 100 символів, якщо для кодування використовується ASCII по 8 бітів і блоковий шифр ухвалює блоки 64 біта?

Розв'язок. Закодувати 100 символів, використовуючи ASCII по 8 бітів. Це повідомлення містить 800 біт. Вихідний текст повинен ділитися без остачі на 64. Якщо | M | і | Pad | - довжина повідомлення й довжина заповнення, то | M | + | Pad | == 0 mod 64 | Pad | = -800 mod 64 32 mod 64

Це означає, що потрібно до повідомлення потрібно додати 32 біта заповнення (наприклад, нулів). Текст тоді буде складатися з 832 бітів або тринадцяти 64-розрядних блоків. Помітимо, що тільки останній блок містить заповнення. Шифратор використовує алгоритм шифрування тринадцять раз, щоб створити тринадцять блоків зашифрованого тексту.

Підстановка, або транспозиція

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

Якщо шифр спроектований як шифр підстановки, значення біта 1 або 0 у вихідному тексті можуть бути замінені або на 0, або на 1. Це означає, що вихідний текст і зашифрований текст можуть мати різне число одиниць. Блок вихідного тексту на 64 біта, який містить 12 нулів і 52 одиниці, може бути представлено в зашифрованому тексті 34 нулями й 30 одиницями. Якщо шифр спроектований як шифр перестановки (транспозиції), біти тільки міняють порядок проходження (переміщаються), зберігаючи то ж саме число символів у вихідному й зашифрованому текстах. У кожному разі, число можливих n-бітових вихідних текстів або зашифрованих текстів рівно 2n, тому що кожний з n бітів, використаних у блоці, може мати одне із двох значень - 0 або 1.

Сучасні блокові шифри спроектовані як шифри підстановки, тому що властивості транспозиції (збереження числа одиниць або нулів) роблять шифр уразливим до атак вичерпного пошуку, як це показують нижченаведені приклади.

Приклад 2. Припустимо, що ми маємо блоковий шифр, де n = 64. Якщо є 10 одиниць у зашифрованому тексті, скільки випробувань типу "проб і помилок" повинна зробити Єва, щоб одержати вихідний текст перехопленого зашифрованого тексту в кожному з наступних випадків?

a. Шифр спроектований як шифр підстановки.
b. Шифр спроектований як шифр транспозиції.

Розв'язок.

a. У першому випадку (підстановка) Єва поняття не має, скільки одиниць перебуває у вихідному тексті. Єва повинна спробувати всі можливі 264 блоку по 64 біта, щоб знайти один, який має сенс. Якби Єва могла пробувати 1 мільярд блоків у секунду, і тоді їй треба було б сотні років, перш ніж ця робота могла б принести успіх.

b. У другому випадку (перестановка) Єва знає, що у вихідному тексті є точно 10 одиниць, тому що транспозиція не змінює числа одиниць (або нулів) у зашифрованому тексті. Єва може почати атаку вичерпного пошуку, використовуючи тільки ті 64-бітові блоки, які мають точно 10 одиниць. Є тільки (64!) / [(10!) (54!)] = 151 473 214 816 з 264 слів по 64 біта, які мають точно 10 одиниць. Єва може перевірити всіх їх менше ніж за 3 хвилини, якщо вона може провести 1 мільярд випробувань у секунду.

Стійкий до атаки вичерпного пошуку, сучасний блоковий шифр повинен бути спроектований як шифр підстановки.

Блокові шифри як групові математичні перестановки

Припустимо, що ключ досить довгий, щоб створити відображення будь-якої можливої вхідної інформації у вихідну. Він називається повнорозмірним ключовим шифром. Практично, ключ менше; довгий ключ можна застосовувати тільки для деяких відображень вхідної інформації у вихідну. Хоча блоковий шифр повинен мати ключ, який є секретним при обміні між передавачем і приймачем, у шифрі використовуються також компоненти, які не залежать від ключа.

Повнорозмірні ключові шифри

Повнорозмірні ключові блокові шифри транспозиції. Такий ключовий шифр переміщає біти, не змінюючи їх значення, так що може бути змодельований як перестановка n-мірного об'єкта із множиною n! таблиць перестановки, у яких ключ визначає, яка таблиця використовується Алісою й Бобом. Ми повинні мати n! можливих ключів, і такий ключ повинен мати довжину біт.

Повнорозмірні ключові блокові шифри підстановки. Такі шифри не переміщають біти - вони заміняють біти. Декодування тут означає перетворення n-розрядного цілого числа в рядок 2 n-біт з єдиною одиницею 1 і 2n–1 нулями. Позиція єдиної одиниці вказує значення цілого числа в упорядкованій послідовності позицій рядка від 0 до 2n – 1. Оскільки нова вхідна інформація має завжди єдину одиницю, шифр може бути змодельований як перестановка 2n! об'єктів.

Повнорозмірний ключ - це n-розрядний шифр транспозиції або блоковий шифр підстановки. Вони можуть бути змодельовані як шифри перестановки, але розміри їх ключа різні: для шифру транспозиції ключ довжиною - [log2n!] для шифру підстановки ключ довжиною -[log2(2n)!].

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

Шифри ключа часткового розміру

Фактичні шифри не можуть використовувати повнорозмірні ключі, тому що розмір ключа стає нісенітно більшим, особливо для блокового шифру підстановки. Наприклад, загальний шифр підстановки – DES - застосовує 64 - розрядний блоковий шифр. Якби проектувальники DES використовували повнорозмірний ключ, він був би бітів. На практиці ключ для DES тільки 56 бітів, що є дуже маленьким фрагментом повнорозмірного ключа. Це означає, що DES використовує тільки відображень із приблизно можливих відображень.

Група перестановки. Задамо собі питання: чи можна встановити, що багатоступінчаста транспозиція із частковим ключем або підстановка - це група перестановки з композицією операцій? Відповідь на це питання надзвичайно важливий, тому що він говорить нам про те, чи є багатоступінчаста версія із частковим шифром таким же засобом шифрування, як і сам шифр. Цей факт дозволяє досягти більшого ступеня безпеки.

Частковий ключовий шифр – це група, якщо це - підгрупа відповідного розміру ключа шифру. Інакше кажучи, якщо повнорозмірний ключовий шифр - це група G = <M, o>, де М. - множина відображень і (o) - композиція операцій, то шифр із ключем часткового розміру повинен представляти підгрупу H = <N, o>, де N - підмножина М с тими ж самими операціями.

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

Шифри без ключа

Хоча використання окремо шифру без ключа фактично даремно, можливо їх застосування як компоненти ключових шифрів,

Шифр транспозиції без ключа. Шифри без ключа (або з фіксованим ключем) можна розглядати як шифр транспозиції, реалізований в апаратних засобах. Фіксований ключ (єдине правило перестановки) може бути представлений як таблиця у випадку реалізації шифру в програмнім забезпеченні. Наступна частина цієї лекції обговорює шифри транспозиції без ключа, названі P-Блоками, які використовуються як стандартні блоки сучасних блокових шифрів.

Шифри підстановки без ключа. Такий шифр без ключа (або з фіксованим ключем) можна уявити собі як заздалегідь певне відображення вхідної інформації до вихідної. Відображення може бути презентовано як таблиця, як математична функція, а також іншими способами. У наступній частині цієї лекції розглядаються шифри підстановки без ключів, названі S-Блоками, які застосовуються як стандартні блоки сучасних блокових шифрів.

2. Компоненти сучасного блокового шифру

Сучасні блокові шифри звичайно є ключовими шифрами підстановки, у яких ключ дозволяє тільки часткові відображення можливих входів інформації в можливі виходи. Однак ці шифри звичайно не проектують як єдиний модуль. Щоб забезпечувати необхідні властивості сучасного блокового шифру, такі як розсіювання й перемішування інформації (обговорюється коротко), цей шифр формується як комбінація модулів транспозиції (називаних P-Блоками), модулів підстановки (називаних S-Блоками) і деякими іншими модулями (обговорюється коротко).

P-Блок (блок перестановки) подібний традиційного шифру транспозиції символів. Він переміщає біти. У сучасних блокових шифрах ми можемо знайти три типи P-Блоків: прямі P-Блоки, P-Блоки розширення й P-Блоки стиску, що й показане на рис. 2.


Рис. 2. Три типи P-Блоків


Рис. 3. Можливі відображення P-Блоку 3x3

Оборотність. Прямій P-Блок є оборотним. Це означає, що ми можемо використовувати прямій P-Бітовий шифр і дешифрувати його.

Прямій P-Блок є оборотним, а P-Блоки стиску й розширення - немає.

S-Блок (блок підстановки) можна уявити собі як мініатюрний шифр підстановки. Цей блок може мати різне число входів і виходів. Інакше кажучи, вхід до S-Блоку може бути n-бітовим словом, а вихід може бути розрядним словом, де і - не обов'язково однакові числа. Хоча S-Блок може бути ключовим або без ключа, сучасні блокові шифри звичайно використовують S-Блоки без ключів, де відображення від інформаційних входів до інформаційних виходів заздалегідь визначене.

Лінійний і нелінійний S-Блоки. В S-Блоці з n входами й m виходами ми позначимо входи і виходи . Співвідношення між входами й виходами можуть бути представлені як система рівнянь



...

У лінійному S-Блоці вищезгадані співвідношення можуть бути виражені як



...

У нелінійному S-Блоці ми не можемо завжди задати для кожного виходу зазначені вище співвідношення.

Оборотність. S-Блоки - шифри підстановки, у яких відносини між входом і виходом визначені таблицею або математичним співвідношенням. S-Блок може бути або може не бути оборотним. В оборотному S-Блоці число вхідних бітів повинне бути рівним числу біт виходу.

Циклічне зрушення

Інший компонент, застосовуваний у деяких сучасних блокових шифрах, – операція циклічного зрушення. Зсув може бути вліво або вправо. Кругова операція лівого зрушення зрушує кожний біт в n-бітовім слові на k позиції вліво; крайні ліві k-біти віддаляються ліворуч і стають самими правими бітами. Кругова операція правого зрушення зрушує кожний біт в n-бітовім слові на k позицій вправо; самі праві k-біти праворуч віддаляються й стають крайніми лівими бітами.

Циклічна операція зрушення змішує біти в слові й допомагає сховати зразки в первіснім слові. Хоча число позицій, на які біти будуть зрушені, може використовуватися як ключ, циклічна операція зрушення звичайно – без ключа; значення k установлюється й задається заздалегідь.

Оборотність. Циклічна операція лівого зрушення – інверсія операції правого зрушення. Якщо одна з них використовується для шифрування, інша може застосовуватися для дешифрування.

Заміна

Операція заміни - спеціальний випадок операції циклічного зрушення, де k = n/2 означає, що ця операція можлива, тільки якщо n - парний номер. Оскільки зрушення вліво n/2 - те ж саме, що зрушення n/2 вправо, ця операція є оборотною. Операція заміни для шифрування може бути повністю розкрита операцією заміни для дешифровці.

Розбивка й об'єднання

Дві інших операції, застосовувані в деяких блокових шифрах, - розбивка й об'єднання. Розбивка звичайна розділяє n-бітове слово в середині, створюючи два слова рівної довжини. Об'єднання зв'язує два слова рівної довжини, щоб створити n-бітове слово. Ці дві операції інверсні один одному й можуть використовуватися як пари, щоб зрівноважити один одного. Якщо одна використовується для шифрування, то інша - для дешифрування.

3. Складені шифри

Шеннон увів поняття складені шифри. Складений шифр – комплекс, який поєднує підстановку, перестановку й інші компоненти, розглянуті в попередніх розділах.

Розсіювання й перемішування

Ідея Шеннона у виставі складеного шифру повинна була дати можливість блоковим шифрам мати дві важливі властивості: розсіювання й перемішування. Розсіювання повинне сховати відносини між зашифрованим текстом і вихідним текстом. Це спантеличить супротивника, який використовує статистику зашифрованого тексту, щоб знайти вихідний текст. Розсіювання має на увазі, що кожний символ (символ або біт) у зашифрованому тексті залежить від одного або всіх символів у вихідному тексті. Інакше кажучи, якщо єдиний символ у вихідному тексті змінений, трохи або всі символи в зашифрованому тексті будуть також змінені.

Розсіювання приховує відносини між зашифрованим текстом і вихідним текстом.

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

Перемішування приховує відносини між зашифрованим текстом і ключем.

Раунди

Розпилення й перемішування можуть бути досягнуті використанням повторення складених шифрів, де кожна ітерація - комбінація S-Блоків, P-Блоків і інших компонентів. Кожна ітерація називається раундом. Блоковий шифр використовує ключовий список, або генератор ключів, який створює різні ключі для кожного раунду від ключа шифру. В N-Раундном шифрі, щоб створити зашифрований текст, вихідний текст шифрують N раз; відповідно, зашифрований текст розшифровується N раз. Текст, створений на проміжних рівнях ( між двома раундами), називається середнім текстом.

Практичні шифри. Щоб поліпшити розсіювання й перемішування, практичні шифри використовують великі блоки даних, більше S-Блоків і більше раундів. Очевидно, що деяке збільшення числа раундів при використанні великого числа S-Блоків може створити кращий шифр, у якім зашифрований текст виглядає усе більш як випадкове n-бітове слово. Таким чином, відносини між зашифрованим текстом і вихідним текстом будуть повністю сховані (розсіяні). Збільшення числа раундів збільшує число ключів раундів, що краще приховує відносини між зашифрованим текстом і ключем.

Два класи складених шифрів

Сучасні блокові шифри - усі складові, але вони розділені на два класи. Шифри в першому класі використовують і оборотні, і необоротні компоненти. Ці шифри згадуються звичайно як шифри Фейстеля. Блоковий шифр DES (DATA ENCRYPTION STANDARD) - гарний приклад шифру Файстеля. Шифри в другому класі застосовують тільки оборотні компоненти. Обертаємо ваша увага на шифри в цьому класі як шифри не-файстеля ( через відсутність іншої назви). Блоковий шифр AES (ADVANCED ENCRYPTION STANDARD) - гарний приклад шифру не-Файстеля.

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

Файстель проектував дуже інтелектуальний і цікавий шифр, який використовувався протягом багатьох десятиліть. Шифр Файстеля може мати три типи компонентів: самооборотний, оборотний і необоротний.

Шифр Файстеля містить у блоках усі необоротні елементи й використовує той самий модуль в алгоритмах дешифрування й шифрування.

Шифри не-файстеля

Шифр не-файстеля використовує тільки оборотні компоненти. Компонент у вихідному тексті має відповідний компонент у шифрі. Наприклад, S-Блоки повинні мати рівне число входів і виходів, щоб бути сумісними. Не дозволяється ніякий стиск або розширення P-Блоків, тому що вони стануть необоротними.