Основні способи знаходження обернених величин а

1 Перевірити по черзі значення 1, 2,…, n – 1, доки не буде знайдено

а ^{- 1}≡ 1 mod n, таке, що а·а ^{- 1} (mod n) ≡ 1 mod n.

2 Якщо відома функція Ейлера φ(n), томожна обчислити

а ^{- 1} (mod n) ≡ а ^φ(ⁿ⁾ ^{- 1} (mod n),

при цьому можна використовувати алгоритм швидкогопіднесення до степеня.

3 Якщо функція Ейлера φ(n) не відома, то можна використовувати розширений алгоритм Евкліда.

Розглянемо основні способи знаходження обернених величин на числових прикладах.

1 Перевірка по черзі значення 1, 2,…, n – 1, доки не буде знайдено таке

х = а ^{- 1} (mod n), що ах (mod n) ≡ 1 mod n.

Нехай n = 7, a = 5.

Треба знайти х = а ^{- 1} (mod n).

ах (mod n) ≡ 1 mod n чи 5· х≡ 1 mod 7

n – 1 = 7 – 1 = 6

Результати перевірки усіх значень по черзі подано у таблиці 6.1

Таблиця 6.1 - Результати перевірки

х	5х	5х mod 7

З дістаної таблиці можна зробити висновок, що х = 5 ^{- 1} (mod 7) = 3.

2 Обчислення а ^{- 1} (mod n), якщо відома функція Ейлера φ(n).

Нехай n = 7, a = 5.

Треба знайти х = а ^{- 1} (mod n) =5 ^{- 1} (mod 7).

Функція Ейлера φ(n) характеризує число елементів в приведеному набору лишків(табл.6.1).

Таблиця6.1 - Означення функції Ейлера φ(n)

Модуль n	Функція Ейлера φ(n)
n – просте n² … n ^к	n – 1 n (n - 1) … n ^{к – 1}(n - 1)
p · q (p, q - прості)	(p - 1) (q - 1)

Модуль n = 7 – просте число.

Тому функція Ейлера φ(n) = φ(7) = n – 1 = 7– 1 = 6.

Обернена величина від 5 за модулем 7

а ^{- 1} (mod n) ≡ а ^φ(ⁿ⁾ ^{- 1} (mod n) = 5^{6 - 1} mod 7 = 5⁵ mod 7 =

=(5² mod 7)·(5 ³ mod 7) mod 7 = (25 mod 7)·(125 mod 7) = 24 mod 7= 3.

Так, маємо х = 5 ^{- 1} (mod 7) = 3.

3 Обчислення а ^{- 1} (mod n), якщо функція Ейлера φ(n) не відомаза допомогоюрозширеного алгоритму Евкліда.

За допомогою цього способу можна також одночасно обчислити такі цілі числа u₁ та u₂, що

а u₁ + b u₂ = НСД (а, b).

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

1. У чому сутність арифметики за модулем?

2. Що називають лишком числа а за модулем n?

3. Які числа називають простими?

4. Які числа називають взаємно простими?

5. Як знайти найбільший спільний дільник (НСД) за допомогою алгоритма Евкліда?

6. Які числа називають оберненими?

Завдання

Завдання 6.1.1 Обчислити: а) (15 · 19) mod 18;

б) (12 · 30) mod 9;

в) (3 · 5 · 36) mod 7;

г) 3 ¹⁵mod 10;

д) 4 ¹⁰mod 14.

Завдання 6.1.2 Знайти найбільший спільний дільник за допомогою алгоритма Евкліда:

а) (56, 15);

б) (275, 198).

Завдання 6.1.3 Знайти найменше спільне кратне (НСК) чисел 24 та 45.

6.2 Практична робота № 2

Шифри перестановки

Метою роботи є вивчення шифрів перестановки. Для цього студент повинен:

· ознайомитися з теоретичними відомостями наведеними в розділі 1.1 даного посібника;

· розглянути приклади розв’язування завдань наведеними в розділі 5.1 даного посібника;

· вміти дати відповіді на контрольні питання;

· вирішити завдання 6.2.1 – 6.2.5

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

1 У чому сутність шифрів перестановки?

2 Охарактеризуйте різновиди шифрів перестановки.

3 В чому полягає зміст шифру маршрутної перестановки?

4 Що є ключем шифру Сцитала? Кому приписують винахід дешифрувального пристрою цього шифру?

5Як виконується процедура зашифровування за допомогою „магічного квадрату”?

6 Який метод шифрування називається подвійною перестановкою?

7 Що в шифрувальних таблицях використовується в якості ключа?

Завдання

Завдання 6.2.1 Розшифруйте повідомленняЯ ′ В О З К З, здобуте внаслідок перетворення за допомогою підставляння

1 2 3 4 5 6 7

4 3 2 6 1 7 5

Завдання 6.2.2 Зашифруйте за допомогою „магічного квадрата” 4´4 фразу: «БЕРЕЖІТЬ ДРУЗІВ!».

Завдання 6.2.3 Розшифруйте повідомлення

ОИРМ ЕОСЮ ВТАЬ ЛГОП,

здобуте за допомогою „магічного квадрата” 4´4.

Завдання 6.2.4 Зашифруйте методом подвійної перестановки повідомлення

ПОЧИНАТИ ПЕРЕДАЧУ

Ключем до шифру слугує послідовність номерів стовпців 4132 й номерів рядків 3142 вихідної таблиці.

Відкритий текст вписувати та шифртекст зчитувати порядково блоками по чотири літери.

Завдання 6.2.5 Шифртекст

ЛЖОЕ НФЯН ЖРЕД ВЕЛИ

здобуто методом подвійної перестановки з ключами, наведеними у завданні 6.2.4. Віднайти вихідне повідомлення.

Шифртекст вписувати порядково блоками по чотири літери.

6.3 Практична робота № 3

Шифри простої заміни

Метою роботи є вивчення шифрів простої заміни. Для цього студент повинен:

· ознайомитися з теоретичними відомостями наведеними в розділі 1.2 даного посібника;

· розглянути приклади розв’язування завдань наведеними в розділі 5.2 даного посібника;

· вміти дати відповіді на контрольні питання;

· вирішити завдання 6.3.1 – 6.3.6

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

1 У чому сутність шифрів простої заміни?

2 Охарактеризуйте різновиди шифрів простої заміни.

3 Що є ключем до шифру Цезаря?

4 Чим відрізняються монограмні шифри від біграмних?

5 У чому суть подвійного шифрування?

6 Який головний недолік шифрування методом простої заміни?

Завдання

Завдання 6.3.1 Використовуючи шифр Цезаря, зашифрувати свої іменні дані (прізвище, ім'я, по батькові).

Завдання 6.3.2 Зашифрувати свої іменні дані, якщо ключем є таблиця 5.2, наведена в прикладі розд. 5.2.1.

Завдання 6.3.3 Зашифрувати слово ЖУК простою заміною за допомогою ключа, наведеного у таблиці 5.3 прикладу розд. 5.2.3.

Якщо процес шифрування продовжувати необмежено, то в якому циклі вперше з'явиться вихідне слово?

Завдання 6.3.4 За допомогою афінної системи підставляння Цезаря для української абетки перетворити відкрите повідомлення КЛЮЧ на шифртекст.

Е _{а, b} (t) = at + b (mod m), де m = 31, a = 3, b = 5.

Завдання 6.3.5 Зашифрувати за допомогою таблиці Трисемуса свої іменні дані.

За ключ взяти слово ДОКУМЕНТ.

Завдання 6.3.6 Зашифрувати за допомогою шифра Плейфейра свої іменні дані.

За ключ взяти слово ДОКУМЕНТ.

6.4 Практична робота № 4

Шифри складної заміни

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

· ознайомитися з теоретичними відомостями наведеними в розділі 1.3 даного посібника;

· розглянути приклади розв’язування завдань наведеними в розділі 5.3 даного посібника;

· вміти дати відповіді на контрольні питання;

· вирішити завдання 6.4.1 – 6.4.3

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

1. Чим відрізняються шифри складної заміни від шифрів простої заміни?

2. У чому відмінність між шифром Гронсфельда й шифром Віженера?

3. Чому шифри складної заміни мають більшу крипостійкість ніж шифри простої заміни?

4. Що є ключем до шифру Уітстона „подвійний квадрат”?

5. Які змінні ключа можуть використовуватись у роторних машинах?

Завдання

Завдання 6.4.1 Зашифрувати за допомогою таблиці Віженера свої іменні дані (П.І.Б.). Ключове слово – ДОКУМЕНТАЦІЯ.

Завдання 6.4.2 Зашифрувати методом "подвійного квадрата" свої іменні дані.

Ж	Щ	Н	Ю	Р	И	Ч	Г	Я	Т
И	Т	Ь	Ц	Б	Ф	Ж	Ь	М	О
Я	М	Е	Л	С	З	Ю	Р	В	Щ
В	І	П	Ч	А	Ц	У	П	Е	Л
Х	Д	У	О	К	Є	А	Н	Б	Х
З	Є	Ф	Г	Ш	І	К	С	Ш	Д

Завдання 6.4.3 Зашифрувати шифром Гронсфельда свої іменні дані. Як ключ застосувати дату свого народження (наприклад, 25 березня 1987 року буде подано такою послідовністю чисел: 25031987).

6.5 Практична робота № 5

Криптосистема Хілла

Метою роботи є вивчення основних принципів шифрування за допомогою криптосистеми Хілла. Для цього студент повинен:

· ознайомитися з теоретичними відомостями наведеними в розділі 3.2 даного посібника;

· вміти дати відповіді на контрольні питання;

· вирішити завдання

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

1 До якого класу шифрів належить криптосистема Хілла?

2 До якого класу криптосистем належить криптосистема Хілла?

3 Від чого залежить модуль числа за яким виконуються всі арифметичні операції в криптосистемі Хілла?

4 Що є ключем в криптосистемі Хілла?

Завдання

Зашифрувати за допомогою криптосистеми Хілла своє прізвище, якщо коефіцієнти квадратної матриці є такі:

а ₁₁ = 9; а ₁₂= 2; а₂ ₁ = 4; а ₂₂ = 7.

Абетка – українська + 5 розділових знаків (mod 38).

6.6 Практична робота № 6

Вивчення алгоритму криптосистеми DES.

Метою роботи є вивчення основних принципів шифрування за допомогою криптосистеми DES. Для цього студент повинен:

· ознайомитися з теоретичними відомостями наведеними в розділі 3.4 даного посібника;

· вміти дати відповіді на контрольні питання;

· розв’язати завдання

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

1 До якого класу криптосистем належить криптосистема DES?

2 Чому дорівнює довжина блока вихідного повідомлення в криптосистемі DES?

3 Скільки етапів шифрування в криптосистемі DES?

4 Чому дорівнює довжина ключа в криптосистемі DES?

5 Які перетворення здійснюються в криптосистемі DES при шифруванні блока вихідного повідомлення?

6 На базі якої мережі будується алгоритм шифрування в криптосистемі DES?

7 Скільки режимів роботи є в криптосистемі DES?

8 Яка довжина ключа використовується для обчислення функції шифрування при функціональних перетвореннях в криптосистемі DES?

9 Які недоліки є в криптосистемі DES?

10 Призначення режимів роботи алгоритму DES.

Завдання

Зобразити схему обчислення функції шифрування f (R_i-1, K_i) в криптосистемі DES для послідовності бітів b₁-b₆(надається викладачем) в блоці заміни S_i, де i = N (mod 8)+1; N – порядковий номер студента у журналі групи (див.рис.3.3).

6.7 Практична робота № 7

Режими роботи криптосистеми DES.

Метою роботи є вивчення основних режимів роботи криптосистеми DES. Для цього студент повинен:

· ознайомитися з теоретичними відомостями наведеними в розділах 3.4.1 – 3.4.4 даного посібника;

· вміти дати відповіді на контрольні питання;

6.8 Практична робота № 8

Шифрування методом гаммування.

Метою роботи є вивчення способу шифрування методом гаммування.

Для цього студент повинен:

· ознайомитися з теоретичними відомостями наведеними в розділі 2.7 даного посібника;

· вміти дати відповіді на контрольні питання;

Питання

1. Що визначає поняття “документ” в інформаційних системах?

2. Що визначає поняття “секретна інформація” в інформаційних системах?

3. Що визначає поняття “відкрита інформація” в інформаційних системах?

4. Привести схему секретної системи зв¢язку.

5. Що визначає поняття “закрита інформація” в інформаційних системах?

6. В чому суть понять “перемішування” та “розсіювання” за К. Шенноном?

7. Які існують канали несанкціонованого витоку інформації

в системах телекомунікації?

8. Які питання вивчає криптоаналіз?

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

10. Що називають атаками на інформаційні об¢єкти?

11. Пояснити поняття “пасивної атаки”.

12. Пояснити поняття “активної атаки”.

13. Принцип рівноміцного захисту в інформаційних системах.

14. Що називають загрозами інформаційним об¢єктам?

15. У яких трьох аспектах має вирішуватись проблема захисту

інформації в телекомунікаціях?

16. Які алгоритми називають блоковими?

17. Які існують види інформаційних злочинів в телекомунікаційних мережах?

18. Принципи будуванняшифрів на базі мережі Фей стеля.

19. Що визначає поняття “ключ” в інформаційних системах?

20. Поясніть суть методів шифрування: підставляння, переставляння та гаммування.

21. Поясніть вміст понять: інформаційні ресурси, інформаційні процеси, інформаційні системи.

22 За якими принципами загрози інформаційним об¢єктам розподіляють на

можливі та навмисні?

23 Поясніть вміст використання засобів забезпечення безпеки: физичних, апаратних, програмних, організаційних, законодавчих.

24 Що визначає поняття “відкрита інформація” в інформаційних системах?

25 Які алгоритми називають несиметричними?

26 Які алгоритми називають симетричними?

27 Що визначає поняття “ інформаційна взаємодія” в інформаційних системах?

28 Принципи шифрування за допомогою операції переставляння. Основні шифри перестановки.

29 З яких складових складається криптологія. У чому їх сутність?

30 Чим відрізняються процеси розшифровування та дешифрування інформації?

31 Які питання варто задати перш, ніж вдаватися до захисту інформації?

32 Які питання вивчає криптографія?

33 Що визначає поняття „криптостійкість”?

34 Який шифр є стійким за Шенноном?

35 Властивості інформації.

ДОДАТОК А

Таблиця Віженера для української абетки

Ключ

Список рекомендованої літератури

1 Введение в криптографию / Под общ. ред. В.В. Ященко. – СПб.: Питер, 2001. – 288 с.: ил.

2 Барабаш А.В., Шанкин Г.П. Криптография: Науч.-попул. изд. Серия «Аспекты защиты». – М.: Солон-Р, 2002. – 511 с.

3 Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях / Под ред. В.Ф. Шаньгина. – М.: Радио и связь. – 328 с.

4 Анин Б.Ю. Защита компьютерной информации. – СПб.: БХВ – Санкт-Петербург, 2000. – 384 с.: ил.

5 Саломаа А. Классическая криптография: Пер. с англ. – М.: Мир, 1996. – 304 с.

6 Петров А.А. Компьютерная безопасность. Криптографические методы защиты. – М.: ДМК, 2000. – 448 с.: ил.

7 Жельников В. Криптография от папируса до компьютера. – М.: АВF, 1997. – 336 с.

8 Фомичев В.М. Дискретная математика и криптология. – М.: Диалог-МИФИ, 2003.- 400с.

9 Шнайер Б. Прикладная криптография. – М.: Издательство ТРИУМФ,2003 – 816 с.

10 Фергюсон Н., Шнайер Б. Практическая криптография.: Пер. с англ.. – М.: Издательский дом „Вильямс”, 2005. – 424 с.

Основні способи знаходження обернених величин а - 1≡ 1 mod n.