Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”

Міністерство освіти і науки України

Національний університет кораблебудування

ім. адмірала Макарова

Блінцов В.С. Гальчевський Ю.Л.

Учбово-методичний посібник

для виконання лабораторних робіт з дисципліни
„Основи теорії криптографії і криптоаналізу”

Миколаїв 2004

Зміст.................................................................................................. 2

Передмова.......................................................................................... 5

Вступ................................................................................................. 7

Частина I. Математичні основи криптології.............................. 21

1.1  Теорія інформації...................................................................... 21

1.1.1  Основні властивості інформації як предмета захисту............ 21

1.1.2.  Ентропія і невизначеність....................................................... 35

1.1.3.  Норма мови............................................................................. 37

1.1.4.  Безпека криптосистеми........................................................... 37

1.1.5.  Відстань унікальності............................................................. 39

1.1.6.  Плутанина і дифузія............................................................... 41

1.2  Теорія складності...................................................................... 43

1.2.1.  Складність алгоритмів............................................................ 43

1.2.2.  Складність проблем................................................................ 46

1.2.3.  NP-повні проблеми................................................................. 49

1.3  Теорія чисел............................................................................... 50

1.3.1.  Арифметика відрахувань....................................................... 50

1.3.2.  Прості числа............................................................................ 53

1.3.3.  Найбільший загальний дільник.............................................. 55

1.3.4.  Теорія порівнянь..................................................................... 59

1.3.5.  Повна система відрахувань.................................................... 61

1.3.6.  Приведена система відрахувань. Функція Ейлера. Теорема Ейлера.         62

1.3.7.  Квадратичні відрахування..................................................... 64

1.3.8.  Символ Лежандра................................................................... 66

1.3.9.  Символ Якобі.......................................................................... 68

1.3.10.  Генератори............................................................................ 70

1.3.11.  Розкладання на множники.................................................... 72

1.3.12.  Квадратні корені по модулю n............................................. 74

1.3.13.  Генерація простих чисел...................................................... 75

1.3.14.  Сильні прості числа.............................................................. 81

1.3.15.  Дискретні логарифми в кінцевому полі............................... 81

1.3.16.  Обчислення дискретних логарифмів у кінцевій групі........ 82

1.4  Кінцеві поля............................................................................... 84

1.4.1.  Основні поняття. Поле і розширення поля............................ 84

1.4.2.  Кільце поліномів, поля розкладання поліномів, алгебраїчні замикання    86

1.5  Генератори псевдовипадкових послідовностей....................... 89

1.5.1.  Лінійні конгруентні генератори............................................. 89

1.5.2.  Об'єднання лінійних конгруентних генераторів................... 92

1.5.3.  Регістри зрушення з лінійним зворотним зв'язком............... 93

1.5.4.  Програмна реалізація РЗЛЗЗ............................................... 101

1.5.5.  Проектування й аналіз потокових шифрів.......................... 103

1.5.6.  Лінійна складність................................................................. 103

1.5.7.  Кореляційна незалежність.................................................... 104

1.5.8.  Інші розкриття...................................................................... 104

1.5.9.  Адитивні генератори............................................................ 105

Частина II. Криптографія.............................................................. 106

2.1.  Лабораторна робота № 1. Одиночна перестановка по ключу, подвійна перестановка по ключу, шифр решіток, магічні квадрати.................................... 106

2.2.  Лабораторна робота №2. Шифр Playfair і шифр подвійного квадрата.        115

2.3.  Лабораторна робота № 3. Шифрування за допомогою таблиці Віженера.   119

2.4.  Лабораторна робота №4. Шифрування методом Гронсфельда. 123

2.5.  Лабораторна робота № 5. Державний стандарт шифрування DES.    127

2.6.  Лабораторна робота №6. Стандарт криптографічного перетворення даних ГОСТ 28147-89............................................................................................ 138

2.7.  Лабораторна робота № 7. Алгоритм шифрування даних IDEA.         144

2.8.  Лабораторна робота № 8. Шифрування методом гамування.     149

2.9.  Лабораторна робота №9. Системи з відкритим ключем. Криптосистема RSA.     155

2.10.  Лабораторна робота № 10. Криптосистема Ель-Гамаля..... 162

2.11.  Лабораторна робота № 11. Розподіл ключів. Протокол Діффі-Хелмана.   165

2.12.  Лабораторна робота №12. Геш-функції та їхнє застосування.  168

Частина III. Криптоаналіз............................................................. 173

3.1.  Лабораторна робота № 13. Первинний аналіз шифровки. Іспити збігу.       173

3.2.  Лабораторна робота № 14. Криптоаналіз шифрів одноалфавітної заміни.  182

3.3.  Лабораторна робота №15. Статистичний аналіз багатоалфавітних шифрів на прикладі шифру Гронсфельда......................................................... 190

3.4.  Лабораторна робота №16. Криптоаналіз шифру подвійної перестановки.  200

3.5.  Лабораторна робота №17. Аналіз шифрів гамування шляхом виділення тренду псевдовипадкової послідовності...................................................... 204

Додатки............................................................................................ 215

Додаток 1.  Вхідні дані до лабораторних робіт 1-17..................... 215

Додаток 2. Таблиці перестановок та підстановок використані при описі алгоритму DES........................................................................................................... 324

Додаток 3. Детермінована таблиця замін використана при описі алгоритму ГОСТ.     327

Додаток 4. Таблиці розподілу кількостей (імовірностей) біграм для простого українського тексту.......................................................................... 328

Бібліографічні джерела.................................................................. 335

Передмова