НОУ ІНТУЇТ | лекція | Традиційні шифри з симетричним ключем

  1. Об'єднання двох підходів Сучасні шифри перестановки, щоб досягти кращого скремблювання, об'єднують...
  2. Використання матриць
  3. Криптоаналіз шифрів перестановки
  4. статистична атака
  5. Атака грубої сили
  6. Атака за зразком
  7. Шифри c подвійний перестановкою

Об'єднання двох підходів

Сучасні шифри перестановки, щоб досягти кращого скремблювання, об'єднують два підходи. Шифрування і дешифрування робиться в три кроки. Перший: текст пишеться таблицею рядок за рядком. Другий: робиться перестановка, змінюючи порядок проходження стовпців. Третій: стовпець за стовпцем читається нова таблиця. Перші і треті кроки забезпечують безключового глобальна зміна порядку проходження; другий крок забезпечує блокову ключову перестановку. Ці типи шифрів згадуються часто як ключові шифри перестановки стовпців.

приклад 4.26

Припустимо, що Аліса знову зашифровує повідомлення в прикладі 4.25, на цей раз використовуючи об'єднаний підхід. Шифрування і дешифрування показано на Мал. 4.21 .


Мал.4.21.

приклад 4.27

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

ключі

У прикладі 4.27 єдиний ключ використовувався в двох напрямках для зміни порядку проходження стовпців - вниз для шифрування, вгору для дешифрування. Зазвичай прийнято створювати два ключа для цього графічного представлення: один для шифрування і один для дешифрування. Ключі накопичуються в таблицях, що мають одну адресу (вхід) для кожного стовпця. Вхід містить вихідний номер стовпця - номер стовпчика пункту призначення, який вказує його стан від номера входу. малюнок 4.22 показує, як ці дві таблиці можуть бути створені за допомогою графічного представлення ключа.


Мал.4.22.

Шифрування / дешифрування в шифрі перестановки

Ключ шифрування - (3 1 4 5 2). Перший вхід показує, що стовпець 3 (зміст) в джерелі стає стовпчиком 1 (положення або індекс входу) в пункті призначення. Ключ дешифрування - (2 5 1 3 4). Перший вхід показує, що стовпець 2 в джерелі стає стовпчиком 1 в пункті призначення.

Як знайти ключ дешифрування, якщо дано ключ шифрування або, навпаки, даний ключ дешифрування? Процес може бути виконаний вручну за кілька кроків, як це показано на Мал. 4.23 . Спочатку додамо індекси до таблиці ключів, потім зробимо зрушення у відповідності з отриманим ключем, і, нарешті, сортуємо пару відповідно до індексу.


Мал.4.23.

Інверсія ключа в шифрі перестановки

Використання матриць

Ми можемо використовувати матриці, щоб показати процес шифрування / дешифрування для шифру перестановки. Оригінальний текст і зашифрований текст - матриця Ми можемо використовувати матриці, щоб показати процес шифрування / дешифрування для шифру перестановки ., Що представляє числові значення символів; ключі - квадратні матриці розміру . У матриці перестановки кожен рядок або стовпець мають строго одну одиницю (1), і інша частина значень - нулі (0). Шифрування виконується множенням матриці вихідного тексту на ключову матрицю, щоб отримати матрицю зашифрованого тексту; дешифрування виконується множенням зашифрованого тексту на інверсію ключовий матриці, після чого отримуємо вихідний текст.

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

приклад 4.27

малюнок 4.24 показує процес шифрування. множення матриці малюнок 4 вихідного тексту на ключову матрицю шифрування дає матрицю зашифрованого тексту . Матрична маніпуляція вимагає зміни символів в прикладі 4.27 до їх числовим значенням (від 00 до 25). Зверніть увагу, що матричне множення забезпечує тільки перестановку стовпців; читання і запис в матрицю повинні бути забезпечені іншою частиною алгоритму.


Мал.4.24.

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

Криптоаналіз шифрів перестановки

Шифри перестановки уразливі до декількох видів атак тільки для зашифрованого тексту.

статистична атака

Шифр перестановки не змінює частоту букв в зашифрованому тексті; він тільки переставляє літери. Так що перша атака, яка може бути застосована, - аналіз частоти окремої літери. Цей метод може бути корисний, якщо довжина зашифрованого тексту досить велика. Ми таку атаку розглядали раніше. Однак шифри перестановки незберігають частоту пар і триграм. Це означає, що Єва не може використовувати такі інструментальні засоби. Фактично, якщо шифр не зберігається частоту пар і триграм, але зберігає частоту окремих букв, то найімовірніше, що це шифр перестановки.

Атака грубої сили

Єва, щоб розшифрувати повідомлення, може спробувати всі можливі ключі. Однак число ключів може бути величезна 1! + 2! + 3! + ... + L!, Де L - довжина зашифрованого тексту. Кращий підхід полягає в тому, щоб спробувати відгадати число стовпців. Єва знає, що число стовпців ділиться на L. Наприклад, якщо довжина шифру - 20 символів, то Єва, щоб розшифрувати повідомлення, може спробувати всі можливі ключі . Це означає, що номером стовпців може бути комбінація цих коефіцієнтів (1, 2, 4, 5, 10, 20). Однак тільки один стовпець і тільки один рядок - малоймовірні варіанти.

приклад 4.28

Припустимо, що Єва перехопила повідомлення зашифрованого тексту "EEMYNTAACTTKONSHITZG". Довжина повідомлення L = 20, число стовпців може бути 1, 2, 4, 5, 10 або 20. Єва ігнорує перше значення, тому що це означає тільки один стовпець і воно малоймовірно.

a. Якщо число стовпців - 2, єдині дві перестановки - (1,2) і (2, 1). Перше означає, що перестановки не було. Єва пробує другу комбінацію. Вона ділить зашифрований текст на модулі по два символи "EE MY NT AA CT TK ON SH IT ZG". Потім вона пробує переставляти кожен модуль з них, отримуючи текст "ee ym nt aa tc kt no hs ti gz", який не має сенсу.

b. Якщо номер стовпців - 4, тоді є 4! = 24 перестановки. Перша перестановка (1 2 3 4) означає, що не було ніякої перестановки. Єва повинна спробувати інші. Після випробування всіх 23 можливостей Єва знаходить, що ніякої вихідний текст при таких перестановках не має сенсу.

c. Якщо число стовпців - 5, тоді є 5! = 120 перестановок. Перша (1 2 3 4 5) означає відсутність перестановки. Єва повинна спробувати інші. Перестановка (2 5 13 4) приносить плоди - вихідний текст "enemyattackstonightz", який має сенс після видалення фіктивної букви z і додавання пробілів.

Атака за зразком

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

1 -й символ в зашифрованому тексті виходить з 3-го символу вихідного тексту. 2 -й символ в зашифрованому тексті виходить з 8-го символу вихідного тексту. 20 -й символ в зашифрованому тексті виходить з 17-го символу вихідного тексту, і так далі. У нас є зразки в вищезгаданому списку. Ми маємо п'ять груп: (3, 8, 13, 18), (1, 6, 11, 16), (4, 9, 14, 19), (5, 10, 15, 20) і (2, 7, 12, 17). У всіх групах різниця між двома суміжними номерами - 5. Ця регулярність може використовуватися криптоаналітиків, щоб зламати шифр. Якщо Єва знає або може припустити число стовпців (в цьому випадку воно дорівнює 5), вона може перетворити зашифрований текст в групи по чотири символи. Перестановка груп може забезпечити ключ до знаходження вихідного тексту.

Шифри c подвійний перестановкою

Шифри з подвійною перестановкою можуть утруднити роботу криптоаналитика. Прикладом такого шифру було б повторення двічі алгоритму, який використовується для шифрування і дешифрування в прикладі 4.26. На кожному кроці може застосовуватися різний ключ, але зазвичай ключ використовується один і той же.

приклад 4.29

Повторимо приклад 4.26, де використана подвійна перестановка. малюнок 4.25 показує процес.


Мал.4.25.

Подвійний шифр перестановки

Хоча криптоаналитик може ще використовувати частоту появи окремого символу для статистичної атаки на зашифрований текст, атака за зразком тепер утруднена.

13 16 05 07 03 06 10 20 18 04 10 12 01 09 15 17 08 11 19 02

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

Як знайти ключ дешифрування, якщо дано ключ шифрування або, навпаки, даний ключ дешифрування?