ABCDEFGHIJKLMNOPQRSTUVWXYZ 5 страница

Всі арифметичні операції виконуються за модулем 26 (кількість літер в абетці). Це означає, що 26 ототожнюється з 0, 27 – з 1, 28 – з 2 і т. д.

Оберемо ціле число d ³ 2. Воно зазначає розмірність використовуваних матриць. У процедурі зашифровування набори з d літер вихідного повідомлення зашифровуються разом. Візьмемо d = 2.

Нехай тепер А – квадратна d´d матриця. Елементами А є цілі числа від 0 до 25. Вимагатимемо далі, аби матриця А була невиродженою, тобто існувала обернена матриця А^–1. Наприклад,

А = та А^–1 = .

Нагадаємо, що арифметичні операції провадяться за модулем 26. Це дає, приміром,

2 · 17 + 5 · 9 = 79 = 1 + 3 · 26 = 1,

тобто, як і мало бути, одиницю на головній діагоналі одиничної матриці.

Зашифровування здійснюється за допомогою рівняння

АР = С,

де Р та С – d-розмірні вектори-стовпці. Більш докладно: кожен набір з d літер вихідного повідомлення визначає вектор Р, компонентами якого є номери літер. Врешті, С знову інтерпретується як набір d літер криптотексту.

Наприклад, HELP визначає два вектори:

P₁ = = та P₂ = = .

З рівнянь

АP₁ = = C₁ та АP₂ = = C₂

дістаємо криптотекст HІTE.

Розглянемо тепер сферу діяльності криптоаналітика. Припустімо, що аналітик здогадався, що d = 2. Йому потрібно віднайти матрицю А чи, ще краще, обернену матрицю А^–1. З цією метою він обирає вихідне повідомлення HELP і довідується, що відповідний криптотекст є HІTE. Криптоаналітикові відомо, що

А = та А = .

Це може бути записано у вигляді

А = = = .

Обернена матриця А^–1 одразу ж обчислюється з матриці А. Після цього який завгодно криптотекст може бути розшифровано за допомогою М^–1.

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

Припустімо тепер, що криптоаналітик працює з іншою початковою постановкою – "відоме є певне вихідне повідомлення". Більш докладно: нехай криптоаналітикові відомо, що CKVOZІ – криптотекст, який відповідає вихідному повідомленню SAHARA. Хоча ми маємо тут приклад довшого повідомлення, аніж раніше, однак добуваної з нього інформації є набагато менше.

Насправді, тепер рівняння для повідомлення криптотексту мають вигляд

А = , А = та А = .

Не існує оберненої квадратної матриці, котру може бути утворено з трьох векторів-стовпців, які з'являються як коефіцієнти М.

Криптоаналітик виявляє, що кожна обернена квадратна матриця

А =

може бути базисом криптосистеми, оскільки вона шифрує SAHARA як CKVOZІ. Отже, криптоаналітик може зупинитися на матриці

А = ,

для якої оберненою є матриця

(А)^–1 = .

Криптоаналітик є готовий до перехоплення криптотексту. Він дістає текст NAFG й одразу обчислює

= та = .

Два вектори-стовпці породжують вихідне повідомлення NAZІ. Однак легальний користувач знає оригінальну матрицю А та її обернену матрицю й обчислює

= та = ,

що дає вихідне повідомлення NAVY.

Криптоаналітик припустився прикрої помилки, котра могла спричинитися до хибних кроків.

Алгоритм зашифровування в криптосистемі Хілла.

Дано квадратну матрицю виду

А = .

1Обчислюється визначник D матриці А:

D = а₁₁а₂₂ – а₁₂а₂₁ = 3 · 5 – 2 · 3 = 15 – 6 = 9.

2 Визначається долучена матриця алгебричних доповнень А*, складена з алгебричних доповнень до елементів матриці А, причому алгебричне доповнення до елемента а_ij перебуває на перетинанні j-того рядка й і-того стовпця.

А* = .

Під алгебричним доповненням А_ij елемента а_ijрозуміють мінор М_ij, домножений на (–1)ⁱ^+j:

А_ij = (–1)^i+j М_ij,

тобто

А₁₁ = (–1)¹⁺¹· М₁₁ = (–1)² · а₂₂ = 1· 5 = 5;

А₁₂ = (–1)²⁺¹· М₁₂ = (–1)³ · а₁₂ = –1· 2 = –2;

А₂₁ = (–1)¹⁺²· М₂₁ = (–1)³ · а₂₁ = –1· 3 = –3;

А₂₂ = (–1)²⁺²· М₂₂ = (–1)⁴ · а₁₁ = 1· 3 = 3.

Отже, можна записати здобуту матрицю алгебричних доповнень:

А* = .

3 Визначається обернена матриця А^–1.

За обернену матрицю для А слугуватиме матриця, котра виходить із долученої матриці А* діленням усіх її елементів на D.

А^–1 = = .

Перевіримо, чи виконується умова А·А^–1 = Е, де Е – квадратна одинична матриця.

За правилом перемножування матриць, елемент, який розміщено в і-тому рядку й j-тому стовпці матриці добутку, дорівнює сумі добутків відповідних елементів і-того рядка матриці А та j-того стовпця матриці А^–1.

А· А^–1 = · = = =

= = Е.

Отже, можна дійти висновку, що обернену матрицю знайдено правильно.

4 Зведення оберненої матриці за модулем 26.

А^–1mod 26 = mod 26 = mod 26 = .

Нотатка: число 135 – це результат пушуку числа, яке дає залишок 5 за модулем 26. При цьому виконується додаткова умова – знайдене число повинно ділитися на 9 без залишку. Аналогічно здобуваються числа 153, 180, 81.

5 Зашифровування відкритого повідомлення.

Зашифровування здійснюється за допомогою рівняння А · Р = С, де А – матриця перетворення; Р – вектор, компонентами якого є номери літер відкритого повідомлення відповідно до табл. 3.1; С – вектор, компонентами якого є номери літер закритого повідомлення відповідно до табл. 3.1.

Зашифруємо слово HELP.

Спочатку розіб'ємо n-граму відкритого тексту на біграми. Потім у кожній біграмі відкритого тексту замінимо кожну літеру на її числовий еквівалент відповідно до табл. 3.1.

Вихідне повідомлення HELP визначає два вектори:

Р₁= = та Р₂= = ;

С₁= А · Р₁= · = mod 26 = mod 26 = ;

С₂= А · Р₂= · = mod 26 = mod 26 = .

Отже, здобули послідовність чисел 7, 8, 0, 19.

З табл. 3.1 дістаємо криптотекст HІAT.

Процес розшифровування йде за зворотним алгоритмом.

Р₁ = А^–1· С₁= · = mod 26 = mod 26 = ;

Р₂ = А^–1· С₂= · = mod 26 = mod 26 = .

Здобута цифрова послідовність 7, 4, 11, 15 відповідно до табл. 3.1 надає можливість відновити вихідний текст: HELP.

3.3 Сучасні симетричні криптосистеми

К.Шеннон в своїх роботах по теорії звязку зробив висновки, що в практичних шифрах необхідно використовувати два принципу: розсіювання та перемішування.

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

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

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

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

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

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

3.4 Стандарт шифрування DЕS

Стандарт шифрування даних DES (Data Encryption Standard) був опублікований у 1977 р. Національним бюро стандартів США. Типичний блоковий шифр, стандарт DES призначений для захисту від несанкціонованого доступу до важливої, але несекретної інформації в державних і комерційних організаціях США. Алгоритм, покладений в основу стандарту, у 1980 був схвалений Національним інститутом стандартів і технологій США (НІСТ). Алгоритм DES найбільш часто застосовується в системах захисту комерційної інформації.

В даний час розроблено програмне забезпечення і спеціалізовані ЕОМ, що реалізують шифрування і розшифровування інформації в мережах передачі даних.

Суть алгоритму зводиться до наступного.

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

Система DES використовує операції заміни та перестановок символів та додавання за модулем 2.

Зручністю застосовуваного алгоритму є те, що операції шифрування і розшифрування в DES є зворотними. Узагальнена схема процесу шифрування в алгоритмі DES має такий вигляд (Рис.3.1)

Ключ

Рисунок 3.1- Узагальнена схема шифрування в алгоритмі DES

З файлу вихідного тексту зчитується черговий 64-бітовий блок Т. Процес його шифрування полягає в початковій перестановці, шістнадцятьох циклах шифрування і, нарешті, у кінцевій перестановці бітів.

Вхідна послідовність М = m₁, m₂, …, m₆₄ перетворюється блоком початкових перестановок в послідовність M= m₅₈, m₅₀, …,m₇, де m_і може приймати значення 0 чи 1. Перетворення виконується по фіксованої таблиці 3.2.

Таблиця 3.2 – Початкові перестановки

58 50 42 34 26 18 10 2

60 52 44 36 28 20 12 4

62 54 46 38 30 22 14 6

64 56 48 40 32 24 16 8

57 49 41 33 25 17 9 1

59 51 43 35 27 19 11 3

61 53 45 37 29 21 13 5

63 55 47 39 31 23 15 7

За допомогою матриці початкової перестановки IP, що містить 8 стовпців і 8 рядків здійснюється перестановка символів вхідного блоку.

Символи блоку вписують у таблицю по стовпцях, починаючи з лівого нижнього осередку. Потім рядки міняються місцями в порядку 2,4,6,8,1,3,5,7. Далі символи, розташовані в осередках таблиці, зчитуються по рядках.

Завершальне перетворення алгоритму - зворотна перестановка здійснюється за допомогою матриці зворотної перестановки IP ^-1.

Символи блоку вписують у таблицю по стовпцях, починаючи з лівого нижнього осередку. Потім стовпці міняються місцями в порядку 5,1,6,2,7,3,8,4. Далі символи, розташовані в осередках таблиці 3.3, зчитуються по рядках.

Таблиця 3.3 – Кінцеві перестановки

40 8 48 16 56 24 64 32

39 7 47 15 55 23 63 31

38 6 46 14 54 22 62 30

37 5 45 13 53 21 61 29

36 4 44 12 52 20 60 28

35 3 43 11 51 19 59 27

34 2 42 10 50 18 58 26

33 1 41 9 49 17 57 25

Алгоритмпобудований на основі мережі Фейстеля (Рис.2.10).

Процес шифрування здійснюється таким чином.

Отримана після першої перестановки 64-бітна послідовність M розбивається навпіл на два 32-розрядних блоки L₀ і R₀.

Потім виконується ітеративний процес шифрування, що складає з 16-ти кроків.

Нехай M_i- результат i -ї ітерації:

M_i= L_i R_i

де L _i = m ₁, m ₂, …, m ₃₂; R _i = m ₃₃, m ₃₄,…, m ₆₄... У цьому випадку результат ітерації описується наступними формулами:

L_i = R_i-1, i =1,2,…,16;

R_i = L_i-1 Å f (R_i-1, K_i), i =1,2,…,16;

Функція f називається функцією шифрування. Її аргументами є послідовність R_i-1, одержана на попередньому кроці шифрування і 48-бітовий ключ шифрування K, що формується за визначеним правилом з 64-бітового ключа шифрування K.

Усі перетворення, виконувані в рамках алгоритму DES, ілюструє схема представлена на рисунку 3.2

K₁

K₂

K₁₆

Вихідна послідовність (шифртекст), 64 біт

Рисунок 3.2 Схема алгоритму DES

Значення L₀і R₀ виходять звичайною розбивкою блоку M, який підвергся первісній перестановці, навпіл. Далі, блок L₁виходить, за правилом L₁ = R_0.Для одержання значення R₁, необхідно обчислити значення функції f (R₁, K₁). Ця операція здійснюється у відповідності з наступним алгоритмом (Рис. 3.3).

R _i_-132 біта

К_i, 48 біт

f (R_i_-1, K_i ), 32 біта

Рисунок 3.3 - Схема обчислення функції шифрування f (R_i-1, K_i).

На початку 32-х бітний блок розширюється до 48-ми символів. При цьому, додаткових 16 символів беруться, за визначеним правилом, з розширюваного блоку згідно таблиці 3.4.

Таблиця 3.4 Функція розширювання Е

32 1 2 3 4 5

4 5 6 7 8 9

8 9 10 11 12 13

12 13 14 15 16 17

16 17 18 19 20 21

20 21 22 23 24 25

24 25 26 27 28 29

28 29 30 31 32 1

Потім, до отриманого 48-ми розрядному блоку додають за модулем 2 символи першого 48-ми розрядного ключа K₁.

На наступному етапі отримана 48-ми розрядна послідовність розбивається на 8 груп по 6 символів і кожна 6-ти символьна група, відповідно до шифрувальної таблиці 3.5 перетвориться в 4-символьну групу. Після цього отримані таким чином, вісім 4-х символьних груп складають 32-х бітовий блок, що піддають черговій табличній перестановці (Таблиця 3.6).

Таблиця 3.5 Функціональні перетворення S_j

_Рядки _{Стовпці}

₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉ ₁₀ ₁₁ ₁₂ ₁₃ ₁₄ ₁₅

S₁

₀ ₁ ₂ ₃ ₁₄ ₄ ₁₃ ₁ ₂ ₁₅ ₁₁ ₈ ₃ ₁₀ ₆ ₁₂ ₅ ₉ ₀ ₇

₀ ₁₅ ₇ ₄ ₁₄ ₂ ₁₃ ₁ ₁₀ ₆ ₁₂ ₁₁ ₉ ₅ ₃ ₈

₄ ₁ ₁₄ ₈ ₁₃ ₆ ₂ ₁₁ ₁₅ ₁₂ ₉ ₇ ₃ ₁₀ ₅ ₀

₁₅ ₁₂ ₈ ₂ ₄ ₉ ₁ ₇ ₅ ₁₁ ₃ ₁₄ ₁₀ ₀ ₆ ₁₃

S₂

₀ ₁ ₂ ₃ ₁₅ ₁ ₈ ₁₄ ₆ ₁₁ ₃ ₄ ₉ ₇ ₂ ₁₃ ₁₂ ₀ ₅ ₁₀

₃ ₁₃ ₄ ₇ ₁₅ ₂ ₈ ₁₄ ₁₂ ₀ ₁ ₁₀ ₆ ₉ ₄ ₅

₀ ₁₄ ₇ ₁₁ ₁₀ ₄ ₁₃ ₁ ₅ ₈ ₁₂ ₆ ₉ ₃ ₂ ₁₅

₁₃ ₈ ₁₀ ₁ ₃ ₁₅ ₄ ₂ ₁₁ ₆ ₇ ₁₂ ₀ ₅ ₁₄ ₉

S₃

₀ ₁ ₂ ₃ ₁₀ ₀ ₉ ₁₄ ₆ ₃ ₁₅ ₅ ₁ ₁₃ ₁₂ ₇ ₁₁ ₄ ₂ ₈

₁₃ ₇ ₀ ₉ ₃ ₄ ₆ ₁₀ ₂ ₈ ₅ ₁₄ ₁₂ ₁₁ ₁₅ ₁

₁₃ ₆ ₄ ₉ ₈ ₁₅ ₃ ₀ ₁₁ ₁ ₂ ₁₂ ₁₅ ₁₀ ₁₄ ₇

₁ ₁₀ ₁₃ ₀ ₆ ₉ ₈ ₇ ₄ ₁₅ ₁₄ ₃ ₁₁ ₅ ₂ ₁₂

S₄

₀ ₁ ₂ ₃ ₇ ₁₃ ₁₄ ₃ ₀ ₆ ₉ ₁₀ ₁ ₂ ₈ ₅ ₁₁ ₁₂ ₄ ₁₅

₁₃ ₈ ₁₁ ₅ ₆ ₁₅ ₀ ₃ ₄ ₇ ₂ ₁₂ ₁ ₁₀ ₁₄ ₉

₁₀ ₆ ₉ ₀ ₁₂ ₁₁ ₇ ₁₃ ₁₅ ₁ ₃ ₁₄ ₅ ₂ ₈ ₄

₃ ₁₅ ₀ ₆ ₁₀ ₁ ₁₃ ₈ ₉ ₄ ₅ ₁₁ ₁₂ ₇ ₂ ₁₄