Перетворення Мережею Фейстеля



МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ

 

ХАРКIВСЬКИЙ НАЦІОНАЛЬНИЙ

УНIВЕРСИТЕТ РАДIОЕЛЕКТРОНIКИ

 

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторних робіт з дисципліни

 «Безпека програм та даних»

 

 

для студентiв усіх форми навчання

напряму підготовки 6.050103 «Програмна інженерія»

 

Електронне видання

 

 

Затверджено

кафедрою ПІ

Протокол № 8

від 05.02.2014 р.

 

Авторська редакція

 

ХАРКIВ 2014


Методичні вказівки до лабораторних робіт з дисципліни «Безпека програм та даних» для студентів усіх форм навчання напряму 6.050103 «Програмна інженерія»  [Електронне видання] / Упоряд. О.П. Турута. – Харків: ХНУРЕ, 2014. – 27с.

 

 

Упорядник      О.П. Турута

 

 

Ó Турута О.П., 2014 рік


ЗМІСТ

ВСТУП.. 3

Лабораторна работа № 1. СТВОРЕННЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ АЛГОРИТМУ ШИФРУВАННЯ des. 4

1.1 Мета роботи. 4

1.2 Теоретичні відомості 4

1.2.1 Блоковий шифр. 4

1.2.2 Перетворення Мережею Фейстеля. 4

1.2.3 Алгоритм DES. 5

1.3 Завдання до виконання роботи. 9

1.4 Зміст звіту. 10

1.5 Контрольні запитання. 10

Лабораторна работа № 2. ПРОГРАМНА РЕАЛІЗАЦІЯ ШИФРУВАННЯ ДАНИХ ЗА ДОПОМОГОЮ НЕСИМЕТРИЧНОГО КРИПТОАЛГОРИТМУ RSA.. 11

1.1 Мета роботи. 11

1.2 Теоретичні відомості 11

1.3 Алгоритм створення відкритого і секретного ключів. 11

1.3.1. Шифрування і розшифрування. 12

1.4 Завдання до виконання роботи. 12

1.5 Створити програмну реалізацію алгоритму* шифрування RSA. 12

1.6 Створити приємний та зрозумілий інтерфейс для перевірки зробленої роботи. 12

1.7 Реалізувати функції кодування для web-интерфейсу, які (1) сформують ключі для відправлення даних на сервер, (2) відправлять дані та отримають відповідь. 12

1.8 Сформувати звіт в електронному вигляді. 12

1.9 Зміст звіту. 12

1.10  Контрольні запитання. 13

Лабораторна работа № 3. ПРОГРАМНА РЕАЛІЗАЦІЯ ХЕШ-Функцій. 14

1.11  Мета роботи. 14

1.12  Порядок роботи. 14

1.13  Теоретичні відомості 14

1.14  Задание для лабораторной работы.. 16

1.15  Практическая часть. 16

1.16  Контрольные вопросы.. 17

Лабораторна работа № 4. Алгоритм обмІнУ ключаМИ ДІффІ-Хеллмана. 18

1.1 Мета роботи. 18

1.2 Теоретичні відомості 18

1.3 Завдання до виконання роботи. 19

3.4 Зміст звіту. 19

3.5 Контрольні запитання. 20

Лабораторна работа № 5. Реалізація платіжної форми веб-сайту. 21

1.1 Мета роботи. 21

1.2 Порядок роботи. 21

1.3 Теоретичні відомості 21

1.4 Задание для лабораторной работы.. 23

1.5 Контрольные вопросы.. 23

ПЕРЕЛІК ПОСИЛАНЬ. 24

 

ВСТУП

 

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

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

Усі лабораторні роботи виконуються з застосуванням ЕОМ. При цьому необхідно:

- виконувати правила техніки безпеки при роботі з ЕОМ;

- виконувати правила поведінки в лабораторії ЕОМ;

- приходити на заняття строго по розкладу;

- не допускається зміна прав доступу до системних  ресурсів.

До роботи допускаються тільки підготовлені студенти, які ознайомлені з теоретичним матеріалом.

Якщо ЕОМ не хватає для кожного студента лабораторну роботу виконує бригада. Звіт оформлюється один на бригаду, але кожний студент здає лабораторну роботу індивідуально.

Звіт повинен включати в себе:

- назву лабораторної роботи;

- мету лабораторної роботи;

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

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

Всі лабораторні роботи здаються на ЕОМ.

Лабораторна работа № 1. СТВОРЕННЯ ПРОГРАМНОЇ РЕАЛІЗАЦІЇ АЛГОРИТМУ ШИФРУВАННЯ des

Мета роботи

Ознайомитись з методами і засобами симетричної криптографії, навчитись створювати програмні засоби з використанням криптографічних інтерфейсів.

Теоретичні відомості

Блоковий шифр

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

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

 

Перетворення Мережею Фейстеля

Це перетворення над блоками які представляють собою ліву і праву половини регістру зсуву. В алгоритмі DES використовуються пряме перетворення мережею Фейстеля в шифруванні (Рис.1.1) та зворотне перетворення мережею Фейстеля в розшифруванні (Рис.1.2).

 

Рисунок 1.1 – Пряме перетворення мережею Фейстеля

L та R – послідовності бітів (ліва (left) и права (right));

XOR — операція побітового додавання по модулю 2;

f – функція шифрування;

kі – ключ на кожному раунді.

 

 

Рисунок 1.2 – Зворотне перетворення мережею Фейстеля

Функція шифрування та генерування ключів детальніше будуть розглянуті нижче.

 

Алгоритм DES

Загальна схема шифрування представлена на рис 1.3. Алгоритм DES - це симетричний алгоритм шифрування, який є типовим представником сімейства блокових шифрів. Призначений для шифрування даних 64-бітовими блоками. Довжина ключа дорівнює 56 бітам. Алгоритм представляє собою комбінацію двох основних методів шифрування підстановки і перестановки. Основним комбінаційним блоком DES є застосування до тексту одиничної комбінації цих двох методів. Такий блок називається раундом. DES включає в себе 16 раундів.

 

 


Рисунок 1.3 – Загальна схема шифрування в алгоритмі DES

Начальна перестановка IP (Initial Permutation). Згідно з рис. 1.3 блок вхідного тексту перетворюється за допомогою матриці начальної перестановки IP, тобто біти вхідного блоку переставляються згідно з табл. 1.1.

 

Таблиця 1.1 – Начальна перестановка IP

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

 

Після начальної перестановки 64-бітовий блок IP(Т) приймає участь у 16 циклах перетворення Фейстеля.

Необхідно розбити IP(Т) на дві частини L0 та R0, де L0 та R0 - відповідно 32 старших бітів і 32 молодших бітів блока. ПрипустимоТi-1=Li-1Ri-1 результат (i-1) ітерації, тоді результат i-ой ітерації Ti = LiRi знаходиться:

Li = Ri-1

Ri= Li-1 ⊕ f(Ri-1,ki)

Ліва частина Li дорівнює правій частині попереднього вектору Li-1Ri-1. В свою чергу права частина Ri — це бітове додавання Li-1 та f(Ri-1,ki) по модулю 2.

В 16 циклах перетворення Фейстеля функція f грає роль шифрування. Аргументами функції f є 32-бітовий вектор Ri-1 та 48-бітовий ключ ki, які є результатом перетворення 56-бітового начального ключа шифру.

Для обчислення функції f використовуються: функція розширення Е, перетворення S (з 8 перетворень S-блоків), і перестановка P.

Функція Е розширює 32-бітовий вектор Ri-1 до 48-бітового вектора E(Ri-1) шляхом дублювання деяких бітів із Ri-1. Порядок бітів вектора E(Ri-1) приведено в табл. 1.2.

 

Таблиця 1.2 – Функція розширення E

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

 

Після перестановки згідно з табл. 1.2 блок E(Ri-1) додається по модулю 2 з ключами ki. Далі представляється у вигляді восьми послідовних блоків B1, B2, ... B8. E (Ri-1) = B1B2 ... B8. Кожен Bj є 6-бітовим блоком. Далі кожен з блоків Bj трансформується в 4-бітови4й блок B'j за допомогою перетворень Sj. Перетворення Sj визначаються таблицею 1.3.

Таблиця 1.3 – Перетворення Sj, j=1…8

  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  
0 14 4 13 1 2 5 11 8 3 10 6 12 5 9 0 7

S1

1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

 

0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10

S2

1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

 

0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8

S3

1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

 

0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15

S4

1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

 

0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9

S5

1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

 

0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11

S6

1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

 

0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1

S7

1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

 

0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7

S8

1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

 

Припустимо, що B3 = 101111, і ми хочемо знайти B'3. Перший і останній розряди B3 є двійковим записом числа а, 0<=a<=3, середні 4 розряди представляють число b, 0<=b<=15. Рядки таблиці 1.3 нумеруються від 0 до 3, стовпці – нумеруються від 0 до 15. Пара чисел (а, b) визначає число, що знаходиться на перетині рядка а і стовпця b. Двійкове подання цього числа дає B'3. У нашому випадку a = 112 = 3, b = 01112 = 7, та число, яке визначається парою (3,7), дорівнює 7. Його двійкове подання B'3 = 0111.

Значення функції f (Ri-1, ki) (32 біт) знаходиться перестановкою Р, яку застосовують до 32-бітового блоку B'1B'2 ... B'8. Перестановка Р задана таблицею 1.4.

 

Таблиця 1.4 – Перестановка Р

16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25

 

f(Ri-1, ki)=P(B’1B’2…B’8)

Згідно таблиці 1.4, перші чотири біта результуючого вектора після дії функції f - це біти 16, 7, 20, 21 вектора B'1B'2 ... B'8.

 

Генерування ключів ki

Ключі ki виходять з початкового ключа k (64 біт = 8 байтів або 8 символів у ASCII). Вісім бітів, що знаходять в позиціях 8, 16, 24, 32, 40, 48, 56, 64 додаються в ключ k таким чином щоб кожен байт містив непарне число одиниць. Це використовується для виявлення помилок при обміні і зберіганні ключів. Потім роблять перестановку для розширеного ключа (крім бітів що додаються 8, 16, 24, 32, 40, 48, 56, 64). Така перестановка визначена у таблиці 1.5.

Таблиця 1.5 – Перестановка бітів для знаходження розширеного ключа

57 49 41 33 25 17 9 1 58 50 42 34 26 18

C0

10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 46 38 30 22

D0

14 6 61 53 45 37 29 21 13 5 28 20 12 4

Ця перестановка визначається двома блоками C0 і D0 по 28 біт кожен. Перші 3 біти C0 є біти 57, 49, 41 розширеного ключа. А перші три біта D0 є біти 63, 55, 47 розширеного ключа. Ci, Di i = 1,2,3 ... виходять з Ci-1, Di-1 одним або двома лівими циклічними зсувами згідно з таблицею 1.6.

Таблиця 1.6 – Циклічні зсуви

і 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Число зсуву 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

Ключ ki, i = 1 ... 16 складається з 48 біт, вибраних з бітів вектора CiDi (56 біт) згідно з таблицею 1.7. Перший і другий біти ki є біти 14, 17 вектора CiDi.

Таблиця 1.7 – 48 біт ключа

14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4
26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40
51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

Кінцева перестановка.

Кінцева перестановка IP-1 діє на T16 і використовується для відновлення позиції. Вона є зворотною до перестановки IP. Кінцева перестановка визначається таблицею 1.8.

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

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

 

Схема розшифрування

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

Ri-1 = Li

Li-1 = Ri ⊕ f(Li, ki)

Завдання до виконання роботи

1. Створити програмну реалізацію алгоритму* шифрування DES (без використання готових функцій).

* завдання узгодити з викладачем лабораторних робіт.

2. Зробити перевірку на виключення слабких ключів.

3. Створити приємний та зрозумілий інтерфейс для перевірки зробленої роботи.

4. Сформувати звіт в електронному вигляді.

Зміст звіту

1. Тексти розроблених програм.

2. Копії екранних форм з результатами.

3. Висновки.

 

Контрольні запитання

1. Які криптографічні шифри називають симетричними?

2. Зобразить схематично роботу алгоритму DES.

3. Що мається на увазі під поняттям блоковий шифр?

4. Що представляє собою мережа Фейстеля?

5. Назвіть головні параметри шифру DES (довжина блоків, довжина ключа, кількість раундів роботи мережі Фейстеля).

6. Як генеруються ключі в раундах?

7. Які перестановки існують в даному алгоритмі?

8. Що представляють собою S-блоки?

9. Які ви знаєте слабкі ключі?

10. Як проходить розшифрування по алгоритму DES?

 

 


Дата добавления: 2018-02-18; просмотров: 938; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!