Слайд 1Сіденко Володимир Павлович,
Старший викладач кафедри “Безпека інформаційних та комунікаційних систем”
1
ЗМІСТОВНИЙ
МОДУЛЬ № 1
КЛАСИЧНІ КРИПТОГРАФІЧНІ СИСТЕМИ
Слайд 2Тема № 2
КЛАСИЧНІ КРИПТОГРАФІЧНІ СИСТЕМИ З ШИФРАМИ ПЕРЕСТАНОВКИ
2
Слайд 33
Лекція № 5
ШИФРИ З АНАЛІТИЧНИМИ ПЕРЕТВОРЮВАННЯМИ. АБСОЛЮТНО СТІЙКИ ШИФРИ
Слайд 4Питання лекції № 5
1. Шифри з аналітичними пе- ретворюваннями
2. Абсолютно
стійки шифри
Література: Л2, с. 17 – 20, 113 -
125;
Л3, с. 54 – 65.
4
Слайд 5
1. ШИФРИ З АНАЛІТИЧНИМИ ПЕ- РЕТВОРЮВАННЯМИ
5
Слайд 66
1.1. ШИФР ХІЛЛА
До методу матричного шифрування відноситься шифр Хілла,
винайдений Лес- тером С. Хіллом.
У шифрі Хілла ключ - квадратна
матри- ця розміру m × m, в якому m є розміром блоку. Якщо викликається ключова матри- ця K, то кожен елемент ki,j визначається матрицею, як показано на рис. 5.1.
Слайд 77
Рис. 5.1. Ключ в шифрі Хілла
Використання матриць дозволяє відп- равникові
зашифрувати весь вхідний текст. У цьому випадку вхідний текст -
l × m – мат- риця, в якій l є номером блоків. Шиф- рування текстових повідомлень за допомо- гою шифру Хілла здійснюється за прави- лом
Слайд 88
а розшифрування
Покажемо, як виходить один блок за- шифрованого тексту. Якщо
позначимо блоком m символів вхідного тексту p1, p2, ..., pm,
відповідні символи в блоке зашиф- рованого тексту будуть c1, c2, ..., cm. Тоді бу- демо мати
Слайд 99
c1 = (p1·k11 + p2·k21 + … + pm·km1) mod
n;
c2 = (p1·k12 + p2·k22 + … + pm·km2)
mod n;
…………………………………
cm = (p1·k1m + p2·k2m + … + pm·kmm) mod n.
Рівняння показують, що кожен символ зашифрованого тексту, такий, як c1, зале- жить від символів всього вхідного тексту в блоці (p1, p2, ..., pm). Однак необхідно знати, що не всі квадратні матриці мають мульти- плікативні інверсії в Zn, так що відправник і одержувач повинні бути обережні у виборі ключа.
Слайд 1010
Одержувач не зможе розшифрувати зашифрований текст, переданий відправ- ником, якщо
матриця не має мультипліка- тивної інверсії.
Приклад 5.1. Нехай вхідний текст
"COD IS READY" ("код готовий") необхідно за- шифрувати, а потім розшифрувати зашиф- рований текст за допомогою шифру Хілла (n = 26), використовуючи ключову матрицю K (GYBNQKURP в буквеному вигляді; 06, 24, 01, 13, 16, 10, 20, 17, 15 у числовому вигля- ді):
Слайд 1111
Розв’язок. Вхідної текст може бути представлений як матриця розміром 4 × 3
при додаванні додаткового фіктивного символу "z" до останнього блоку і
вида- ленні пропусків між словами. Вхідної текст для шифрування в такому випадку буде: "CODEISREADYZ". Числовий еквівалент да- ного повідомлення представляється у виг- ляді: 02, 14, 03, 04, 08, 18, 17, 04, 00, 03, 24, 25.
Слайд 1212
Шифрування даних за допомогою шифру Хілла показано на рис. 5.2.
Рис.
5.2. Шифрування повідомлень за допомогою шифру Хілла
Як бачимо, в
результаті шифрування отримане зашифроване повідомлення: 20, 11, 05, 20, 10, 16, 24, 04, 05, 24, 23, 20.
Слайд 1313
Це зашифроване повідомлення відпо- відає "ULFUKQYEFYXU" з використанням англійського алфавіту.
Одержувач
може розшифрувати пові- домлення, використовуючи інверсну мат- рицю-ключ K-1, таку,
що (K × K-1) mod n = I, де I - одинична матриця.
Для нашого прикладу множення мат- риці-ключа K на інверсну матрицю-ключ K-1 буде дорівнювати
Слайд 14 Розшифрування повідомлень за допо- могою шифру Хілла показано на рис.
5.3.
14
Рис. 5.3. Розшифрування повідомлень за допомогою шифру Хілла
Слайд 15 З рис. 5.3 бачимо, що в результаті роз- шифрування отримане
повідомлення 02, 14, 03, 04, 08, 18, 17, 04, 00,
03, 24, 25, яке відповідає "CODEISREADYZ" з використан- ням англійського алфавіту. Відкидаючи останній символ, в результаті отримуємо - "CODEISREADY", що відповідає вхідному тексту.
15
Слайд 16
На відміну від попередніх шифрів, шифр Хілла дозволяє шифрувати повідом-
лення блоками символів. Причому кожен отриманий символ зашифрованого пові- домлення
залежить від декількох символів відкритого тексту і ключа. Це призводить до суттєвого підвищення криптостійкості. Криптостійкість залежить і від розміру ключовий матриці.
16
Слайд 1717
1.2. ШИФР НА ОСНОВІ МЕТОДА УКЛАДАННЯ РЮКЗАКА
Слайд 18 Першим алгоритмом для узагальнено- го шифрування з відкритим ключем став
алгоритм рюкзака, розроблений Ральфом Меркель і Мартіном Хеллманом. Безпека алгоритму
рюкзака спирається на пробле- му рюкзака. Проблема рюкзака нескладна. Дано набір предметів різної маси. Чи можна покласти деякі з цих предметів в рюкзак так, щоб маса рюкзака стала дорівнювати певному значенню? Або більш формально, дано набір значень p1, p2, ..., pm і сума C. Обчислити значення bi, такі що:
18
Слайд 19C = b1·p1 + b2·p2 + … + bn·pn ,
де
bi може бути нулем або одиницею. Оди- ниця показує, що
предмет кладуть в рюк- зак, а нуль - що не кладуть. В загальному випадку час, необхідний для вирішення цієї проблеми, з ростом кількості предметів в наборі зростає експоненціальне.
В основі алгоритму рюкзака Меркле-Хеллмана лежить ідея шифрувати повідом- лення, як рішення набору проблем рюкза- ка. Предмети з набору вибираються за до- помогою блоку відкритого тексту, по дов- жині рівного кількості предметів в наборі
19
Слайд 20(біти відкритого тексту відповідають зна- ченням b), а шифротекст є
отриманою су- мою.
Завдання про укладання рюкзака фор- мулюються в такий
спосіб.
Задано вектор
20
який надалі буде відігравати роль ключа. Як правило, елементами цього вектора є прості числа. Для однозначного шифруван- ня та розшифрування елементи вектора E обираються згідно правилу
Слайд 21 Кожний символ відкритого повідом- лення pi, якій передається, представляєть- ся
послідовністю з k біт
21
В результаті відкрите повідомлення являє собою матрицю
Слайд 22де m - довжина відкритого повідомлення.
Символи зашифрованих даних C вихо-
дять як добуток матриці E та вектора-стовпця P
22
Приклад 5.2. Зашифрувати
відкрите по- відомлення: НАКАЗ (13, 00, 10, 00, 07) з ви- користанням ключа у вигляді
Слайд 23 Розв’язок. Запишемо символи відкри- того повідомлення п’ятирозрядним двійко- вим кодом
23
Створимо
матрицю повідомлення
Слайд 24 Зробимо відповідні до (5.3) операції
24
Слайд 25 Значить зашифроване повідомлення буде мати вигляд: 22, 00, 16, 00,
12 (ЦАРАМ).
Приклад 5.3. Розшифруємо це зашиф- роване повідомлення. П’ятирозрядні двій-
кові числа відкритого повідомлення вихо- дять зі матричного рівняння (5.3).
Розв’язок. Відкрите повідомлення можна одержати, вирішуючи шість рівнянь
25
Слайд 27 Перший елемент повідомлення (п’яти- розрядне двійкове число) одержимо вирішуючи перше
скалярне рівняння
Перше скалярне рівняння
29·p1,5 + 13·p1,4 + 7·p1,3 + 3·p1,2
+ 2·p1,1 = 22.
Це скалярне рівняння буде справед- ливим тільки в тому випадку, якщо p1,5 = 0, p1,4 = 1, p1,3 = 1, p1,2 = 0 і p1,1 = 1.
Це двійковий код числа – 1310 = 011012 .
Друге скалярне рівняння
29·p2,5 + 13·p2,4 + 7·p2,3 + 3·p2,2 + 2·p2,1 = 00.
27
Слайд 28 Це скалярне рівняння буде справедли- вим тільки в тому випадку,
якщо p2,5 = 0, p2,4 = 0, p2,3 = 0,
p2,2 = 0 і p2,1 = 0.
Це двійковий код числа – 0010 = 000002 .
Трете скалярне рівняння
29·p3,5 + 13·p3,4 + 7·p3,3 + 3·p3,2 + 2·p3,1 = 16.
Це скалярне рівняння буде справедли- вим тільки в тому випадку, якщо p3,5 = 0, p3,4 = 1, p3,3 = 0, p3,2 = 1 і p3,1 = 0.
Це двійковий код числа – 1010 = 010102 .
Четверте скалярне рівняння
28
Слайд 2929·p4,5 + 13·p4,4 + 7·p4,3 + 3·p4,2 + 2·p4,1 =
00.
Це скалярне рівняння буде справедли- вим тільки в тому випадку,
якщо p4,5 = 0, p4,4 = 0, p4,3 = 0, p4,2 = 0 і p4,1 = 0.
Це двійковий код числа – 0010 = 000002 .
П’яте скалярне рівняння
29·p5,5 + 13·p5,4 + 7·p5,3 + 3·p5,2 + 2·p5,1 = 12.
Це скалярне рівняння буде справедли- вим тільки в тому випадку, якщо p5,5 = 0, p5,4 = 0, p5,3 = 1, p5,2 = 1 і p5,1 = 1.
Це двійковий код числа – 0710 = 001112.
29
Слайд 30 Таким чином отримуємо відкрите пові- домлення
30
Було запропоновано велику кількість варіантів
реалізації цього алгоритму, але практично всі були зламані. Але й
ті, що за- лишилися, вимагають для зламу набагато менших зусиль, ніж деякі інші алгоритми асиметричною криптографії.
Слайд 3133
1.3. ШИФРИ НА ОСНОВІ ЕКСПОНЕНТНИХ ПЕРЕТВОРЕНЬ
Слайд 32 Метод шифрування з використанням експонентного перетворення базується на дискретних логарифмах.
При цьому процес зашифрування й розшифрування здійс- нюється за допомогою
наступних перетво-рювань
де n – довжина алфавіту; e - ціле число (відкритий ключ шифру); d – ціле число (секретний ключ шифру).
32
Слайд 33 Приклад 5.4. Відкритий текст: ПРИКАЗ (15, 16, 08, 10, 00, 07).
Нехай
n = 77, d = 43 і e = 7.
Зашифруємо повідомлення за допомогою (5.4):
33
Слайд 3434
Зашифроване повідомлення буде мати вигляд: 71, 58, 57, 10, 00,
28.
Розшифруємо дане зашифроване пові-домлення за допомогою (5.5)
Слайд 35 Розшифроване повідомлення буде ма- ти вигляд:
15, 16, 08, 10, 00,
07,
тобто відповідати слову ПРИКАЗ.
Найбільшою стійкістю володіють шиф- ри, засновані на
аналітичних перетворю- ваннях, особливо ті, які використовують шифр Хілла та експонентне перетворюван- ня.
35
Слайд 36
2. АБСОЛЮТНО СТІЙКИ ШИФРИ
2.1. ШИФР ВЕРНАМА
36
Слайд 37 Одна з цілей криптографії - ідеальна секретність. Майже всі застосовувані
на практиці шифри характеризуються як умов- но надійні, оскільки вони
можуть бути в принципі розкриті при наявності необмеже- них обчислювальних можливостей. Абсо- лютно надійні шифри не можна зруйнувати навіть при використанні необмежених об- числювальних можливостей. Існує єдиний такий шифр, використовуваний на практи- ці, - одноразовий блокнот. Характерною особливістю такої системи шифрування є одноразове використання ключовою послі- довності.
37
Слайд 38 Шифр був винайдений в 1917 році співробітниками AT&T (одна з
найбільших американських телекомунікаційних компа- ній США) Мейджором Джозефом Моборном і
Гільбертом Вернамом. У літературі він часто називається шифром Вернама. Шифр Вернама з'явився на світ після без- успішних спроб Вернама удосконалити шифр Віженера (шифр, який вважався та- ким, що не зламується, але був дешиф- рований Фрідріхом Касіскі в 1854 році) до не зламуємого.
38
Слайд 39 Суть шифру Вернама полягає в тому, що зашифрований тест є
об'єднання відк- ритого тексту і ключа за допомогою опера- ції
XOR, тобто
EncryptedText = OpenText XOR Key.
Ключ (Key) - випадкова послідовність біт. Вернам побудував телеграфний апа- рат, який виконував цю операцію після по- дачі стрічки з ключем. Вернам помітив, що для забезпечення стійкості шифру кожна стрічка повинна бути одноразовою.
39
Слайд 40 Це непросто застосувати на практиці, тому можливо закільцьовувати кілька стрі-
чок, причому їх довжини різні і є взаємно-простими. наприклад,
40
Як бачимо,
в зеленій і жовтій стрічках немає закономірностей у розміщенні біт, при цьому довжини 7 і 5 - взаємно прості. Коли ця єдина велика стрічка закінчується, знову починаємо з лівого біта зеленої стрічки. При практичному застосуванні шифру Вернама, зрозуміло, краще більше стрічок і довжини побільше.
Слайд 41 У 1949 році була опублікована робота К. Шеннона, де він
довів абсолютну стій- кість шифру Вернама. У цій роботі Шеннон
показав, що не існує інших шифрів з подіб- ними властивостями і його висновком ста- ло таке твердження: шифр Вернама – най- безпечніша криптографічна система з усіх наявних.
Дослідження К. Шеннона показали, що ідеальна секретність може бути досягнута, при виконанні наступних правил:
- ключ для шифрування вибирається випадковим чином;
41
Слайд 42 - довжина ключа повинна бути дорів- нювати довжині шифруємого тексту;
-
ключ повинен використовуватися тільки один раз.
Наприклад, адитивний шифр (шифр Цезаря)
може бути легко зламаний, тому що використовується один і той же ключ. Але навіть і цей шифр може бути ідеаль- ним, якщо ключ, який застосовується для шифрування кожного символу, обраний ви- падково з множини ключів (00, 01, 02, ..., n-1): якщо перший символ зашифрований за допомогою ключа 04, другий символ - з до-
42
Слайд 43помогою ключа 02, третій - за допомогою ключа 21, і
так далі. Атака "тільки для за- шифрованого тексту" стає неможлива.
Якщо відправник змінює ключ, використо- вуючи кожен раз іншу випадкову послі- довність цілих чисел, інші типи атак також будуть неможливі.
Для реалізації цієї системи підстановки іноді використовують одноразовий блок- нот. Цей блокнот складений з відривних сторінок, на кожній з яких надрукована таблиця з випадковими числами (ключами) ki.
43
Слайд 44 Блокнот виконується в двох примір- никах: один використовується відправни- ком,
а інший - одержувачем. Для кожного символу pi повідомлення використовуєть-
ся свій ключ ki з таблиці тільки один раз. Після того як таблиця використана, вона повинна бути вилучена з блокнота і знище- на. Шифрування нового повідомлення по- чинається з нової сторінки.
Цей шифр абсолютно надійний, якщо набір ключів K дійсно випадковий і непе- редбачуваний.
44
Слайд 45 Якщо криптоаналітик спробує викорис- товувати для заданих зашифрованих даних всі
можливі набори ключів і відновити всі можливі варіанти вхідних даних,
то вони все виявляться рівноймовірними. Не існує способу вибрати вхідні дані, які були насп- равді відіслані.
Здавалося би, що завдяки даній пере- вазі одноразові системи слід застосовува- ти у всіх випадках, що вимагають абсолют- ної інформаційної безпеки. Проте можли- вості застосування одноразової системи обмежені чисто практичними аспектами.
45
Слайд 46 Суттєвим моментом є вимога однора- зового використання випадкової ключової послідовності.
Ключова послідовність з довжиною, не меншою довжини повідом- лення, повинна
передаватися одержуваче- ві повідомлення заздалегідь або окремо по деякому секретному каналу. Ця вимога не буде занадто обтяжлива для передачі дійс- но важливих одноразових повідомлень. Однак така вимога практично нездійсненна для сучасних систем обробки інформації, де потрібно шифрувати багато мільйонів символів.
46
Слайд 47 В деяких варіантах одноразового блок- нота вдаються до більш простого
управ- ління ключовою послідовністю, але це призводить до деякого зниження
надійнос- ті шифру. Наприклад, ключ визначається зазначенням місця в книзі, відомої відправ- никові і одержувачеві повідомлення. Клю- чова послідовність починається з вказано- го місця цієї книги і використовується та- ким же чином, як в системі Виженера. Іноді такий шифр називають шифром з біжучим ключем.
47
Слайд 48 Управління ключовою послідовністю в такому варіанті шифру набагато простіше, так
як довга ключова послідовність може бути представлена в компактній формі.
Але з іншого боку, ці ключі не будуть випадко- вими. Тому у криптографічного аналітика з'являється можливість використовувати інформацію про частоти букв вихідної при- родної мови.
Система шифрування Вернама є по су- ті окремим випадком системи шифрування Виженера при значенні модуля n = 2.
48
Слайд 49 Конкретна версія цього шифру, запро- понована в 1926 р. Г.
Вернамом співробіт- ником фірми AT&T (США) і використовує двійкове подання
символів вхідних даних.
Кожен символ вхідного відкритого тексту з англійського алфавіту {А, В, С, D, … , Z}, розширеного шістьма допоміжними символами (пробіл, повернення каретки і т.п.), спочатку кодувався в п’ятибітовий блок (b0, b1, b2, b3, b4) телеграфного коду Бодо.
Випадкова послідовність двійкових п’ятибітових ключів {k0, k1, k2, …} зазда- легідь записувалася на паперовій стрічці.
49
Слайд 50 Схема передачі повідомлення з вико- ристанням шифрування методом Вернама показана
на рис. 5.4.
50
Рис. 5.4. Схема шифрування і розшифрування повідомлень методом
Вернама
Слайд 51 Шифрування вхідних даних, попе- редньо перетворених в послідовність двій- кових
символів m, здійснюється шляхом додавання по модулю 2 символів m
з пос- лідовністю ключів k.
Символи зашифрованих даних перет- ворюються наступним чином
51
Розшифрування полягає у додаванні за модулем 2 символів зашифрованих да- них ci з тією ж послідовністю ключів ki
Слайд 52 При цьому послідовності ключів, вико- ристані при шифруванні і розшифруванні,
компенсують один одного (при додаванні за модулем 2), і в
результаті відновлюють- ся символи вхідних даних mi.
Приклад 5.5. Зашифруємо за допомо- гою системи Вернама відкритий текст "БЛАНК" за допомогою ключа "ОХТУР".
Розв’язання. Перетворимо відкритий текст "БЛАНК" в ASCII коди: Б = 193, Л = 203, A = 192, Н = 205, К = 202. В двійковому вигляді послідовність 193, 203, 192, 205, 202 представиться у вигляді
52
Слайд 5311000001 11001011 11000000 11001101 11001010.
Перетворимо ключ "ОХТУР" в ASCII коди:
О = 206, Х = 213, Т = 210, У
= 211, Р = 208. В двійковому вигляді послідовність 206, 213, 210, 211, 208 буде мати вигляд
11001110 11010101 11010010 11010011 11010000.
Підпишемо двійковий код ключа під двійковим кодом відкритого тексту і вико- наємо додавання по модулю 2 відповідних бітів.
53
Слайд 5454
Для розшифрування зашифрованого тексту підпишемо двійковий код ключа під двійковим
кодом зашифрованого тексту і виконаємо додавання по модулю 2 відпо-
відних бітів.
Слайд 5555
Як бачимо, отриманий розшифрований текст: 11000001 11001011 11000000 11001101 11001010,
що відповідає символам ASCII кодів - БЛАНК.
Слайд 5656
Будь якій ключ дозволяється викорис- товувати для шифрування тільки один
раз, звідси й назва: одноразовий блокнот (шифроблокнот). Щоб переконатися в
не- минучості неприємностей при шифруванні кількох текстів одним ключем, розглянемо атаку з вибором відкритого тексту. Припус- тимо, що Аліса завжди користується одним ключем для шифрування даних. Єва нама- гається визначити цей ключ і вживає нас- тупну атаку:
- генерує повідомлення m і підсовує його Алісі для шифрування;
Слайд 5757
- отримує c = p k;
- обчислює k =
p c.
Ви можете заперечити, що Аліса не на- стільки
дурна, щоб шифрувати повідом- лення Єви. Але при розробці криптосисте- ми ми зобов'язані врахувати будь-які си- туації, у тому числі й дурного користувача, тобто створити "захист від дурнів".
Інша проблема, що виникає при под- війному використанні ключа, полягає в на- ступному. Припустимо, Єва перехопила два повідомлення, зашифровані одним ключем
Слайд 5858
c1 = p1 k , c2 = p2
k .
Тоді вона може отримати часткову інформацію про
повідомлення, склавши шифрограми:
c1 c2 = p1 k p2 k = p1 p2 .
Незважаючи на проблеми, пов'язані з розподілом ключів, одноразовий шифр-блокнот застосовувався як у минулих вій- нах, так і в дипломатичній пошті.
При розробці своєї системи Вернам перевіряв її за допомогою закільцьованих стрічок, встановлених на передавальної і
Слайд 5959
приймальні сторонах для того, щоб вико- ристовувалася одна і та
ж послідовність ключів (рис. 5.5).
Рис. 5.5. Система Вернама, яка використовує
закільцьовані стрічки
Слайд 6060
У реальних системах спочатку готують дві однакові стрічки з випадковими
цифра- ми ключа. Одна залишається у відправника, а інша передається
"неперехоплюючим" чи- ном наприклад, кур'єром з охороною, закон- ному одержувачу. Коли відправник хоче пе- редати повідомлення, він спочатку перет- ворює його в двійкову форму і поміщає в пристрій, який до кожної цифрі повідом- лення додає по модулю два цифри, зчитані з ключової стрічки.
Слайд 6161
На приймаючій стороні шифроване по- відомлення записується і пропускається че-
рез машину, схожу на пристрій, якій вико- ристовується для шифрування.
Цій прист- рій до кожної двійкової цифрі повідомлення додає (віднімає, так як додавання і відніман- ня по модулю два еквівалентні) по модулю два цифри, зчитані з ключовою стрічки, отримуючи таким чином відкритий текст. При цьому, природно, ключова стрічка по- винна просуватися абсолютно синхронно зі своїм дублікатом, використовуваним для зашифрування.
Слайд 6262
Головним недоліком цієї системи є те, що для кожного біта
переданої інформації повинен бути заздалегідь підготовлений біт ключової інформації, причому
ці біти по- винні бути випадковими. При шифруванні великого обсягу даних це є серйозним обме- женням. Тому дана система використовуєть- ся тільки для передачі повідомлень найви- щої секретності.
Щоб обійти проблему попередньої пе- редачі секретного ключа великого об'єму, інженери і винахідники придумали багато схем генерації дуже довгих потоків псевдо-
Слайд 6363
випадкових цифр з декількох коротких по- токів відповідно до деякого
алгоритму. Одержувача шифрованого повідомлення при цьому необхідно забезпечити точно та-
ким же генератором, як і у відправника. Але такі алгоритми додають регулярності в шифротекст, виявлення яких може допо- могти аналітику дешифрувати повідомлен- ня. Один з основних методів побудови по- дібних генераторів полягає у використанні двох або більше бітових стрічок, зчитані з яких дані побітно складаються для отри- мання "змішаного" потоку (рис. 5.6).
Слайд 6464
Рис. 5.6. Система Вернама, яка використовує "змішаний" потік
Слід зазначити що
метод Вернама не залежить від довжини послідовності клю- чів і,
крім того, він дозволяє використо- вувати випадкову послідовність ключів.
Слайд 6565
Однак при реалізації методу Вернама виникають серйозні проблеми, пов'язані з
необхідністю доставки одержувачу таку же послідовність ключів як у відправника,
або з необхідністю безпечного зберігання іден- тичних послідовностей ключів у відправни- ка і одержувача. Ці недоліки системи шиф- рування Вернама подолані при шифруван- ні методом гамування.
Слайд 6666
2.2. ШИФРУВАННЯ МЕТОДОМ ГАМУВАННЯ
Слайд 6755
Суть цього методу полягає в тому, що символи даних, які
шифруються послідов- но складаються з символами деякої спе- ціальної послідовності,
яка називається гамою. Іноді такий метод представляють як накладення гами на вхідні дані, тому він отримав назву "гамування".
Нехай є якийсь алфавіт, його символи закодовані числами. Кожне число предс- тавляється у вигляді групи з m біт, а m ви- бирається так, щоб можна було закодувати всі символи алфавіту. Припустимо, в алфа- віті 32 символи.
Слайд 6868
Якщо m = 4, можемо закодувати тільки 16 з них,
а ось m = 5 - піде.
Що далі? Отриманий ланцюжок
бітів відкритого повідомлення розбивається на блоки по q біт, нехай всього вийшло N бло- ків. Нехай є ще група G з p цілих різних псевдовипадкових чисел, не менших 0 і не більших за 2q - 1. Нумерація блоків і псев- довипадкових чисел ведеться з нуля, i-й блок складаємо з q-бітовим представлен- ням (i mod p)-го числа групи G, отримуємо якусь групу біт B(i).
Слайд 6969
Всі отримані таким способом групи біт (тобто B(i), i =
0,1, ..., N-1) об'єднуємо і далі по отриманому набору біт
виписуємо сим- воли зашифрованого тексту. Важливо, щоб параметр q був досить великим числом - це підвищує стійкість до атак.
Псевдовипадкові числа виходять за допомогою спеціальних генераторів псев- довипадкових чисел (ГПВЧ). За рахунок їх застосування псевдовипадкову послідов- ність безпосередньо зберігати не потрібно - замість цього потрібно зберігати декілька параметрів алгоритму генерації.
Слайд 7070
Такі послідовності є періодичними, і параметр p, зазначений вище, як
раз і є пе- ріод.
Приклад 5.6. Візьмемо російський ал- фавіт
(n = 32). Відкритий текст - БАГ.
Розв’язання. Відкрите повідомлення можна кодувати по 5 біт (m = 5): A = 00000, Б = 00001, У = 00010 ... . Тоді БАГ = 00001 00000 00011.
Нехай q = 3, p = 2, G = {4, 5}10 = {100, 101}2. В такому випадку представимо БАГ = 000 010 000 000 011.
Слайд 7171
Подивіться уважно на середній рядок - бітові набори, які накладаються,
циклічно повторюються: їх менше, ніж блоків.
Набори з нижнього рядка об'єднуємо.
Оскільки символи алфавіту кодувалися 5 бітами, групуємо по 5 біт: ШИФР (БАГ) = 10011 11001 011112 = {19, 25, 15}10, що відпо- відає УЩП. Тобто БАГ змінився до невпіз- нання.
Слайд 7272
Описаний метод шифрування назива- ється гамуванням. Послідовність біт, яка "перетворює"
відкритий текст, назива- ється гамою або гамма-послідовністю.
Основні відмінності шифру Вернама
та гамування:
1. При гамуванні не використовується ніяких шифроблокнотів, які вимагають пов- ністю зберігати ключ. Потрібно лише знан- ня параметрів ГПВЧ, на основі яких послі- довність псевдовипадкових чисел віднов- люється по мірі необхідності - при шифру- ванні та розшифрування.
Слайд 7373
2. Гамування є блоковим шифром. Це було легко помітити на
прикладі, де відкри- тий текст поділявся на блоки біт (в
таблич- ці до нього один з рядків так і називається - "блок"). Шифр Вернама блоковим не є, що легко зрозуміти за описом. Він відноситься до так званих потокових шифрів.