ABCDEFGHIJKLMNOPQRSTUVWXYZ 9 страница

 

Рисунок 4.3 - Схема реалізації алгоритму Диффі-Хеллмана

Користувачі А і В обирають модуль N, який має бути простим числом, та примітивним елементом g Î Zn, (1 £ g £ N-1), що утворює усі ненулеві елементи множини Zn, чи

{g, g2, … , gN-1 = 1} = ZN - {0}

 

Цілі числа N и g держати в таємниці не обов’язково. Звичайно, вони є спільними для усіх користувачів – учасників інформаційного обміну мережі.

 

Потім користувачі А і В, незалежно один від одного, обирають власні секретні ключі kA и kB ( kA и kB - випадкові цілі великі числа, які зберігаються користувачами в таємниці.).

 

Далі користувач А обчислює відкритий ключ

 

yA = g kA (mod N),

а користувач В - відкритий ключ

yВ = g kB (mod N).

 

Потім А і В обмінюються обчисленними значеннями ключів yA и yВ по незахищенному каналу.

 

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

Сторона АK = (yВ ) kA = (g kB) kA (mod N)

 

Сторона ВK' = (yА ) kB = (g kA) kB(mod N)

 

При цьому К = К' ,

тому що

(g kB) kA=(g kA)) kB.

 

Ключ К може використовуватися в якісті спільного секретного ключа в симетричній криптосистемі.

Крім того, сторони можуть використовувати ключ К для несиметричного шифрування згідно з правилом

 

С = ЕК (М)= М К(mod N).

 

З цією метою слід визначити ключ, який призначений для розшифровування К*, з співвідношення

 

К*К*º1(mod N).

Це дозволить відтворювати повідомлення за правилом

 

 

М = DК (C)= С К*(mod N).

 

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

Великий вплив на безпеку системи робить вибір значень

 

Существенное влияние на безопасность системы оказывает выбор значений N та g. Модуль N маєбути великим простим числом.

Число (N - 1)/2 також має бути простим.

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

Метод Диффі-Хеллмана дає змогу забезпечити кожний сеанс зв’язку новими ключами та не зберігати їх де-небудь.

Крім того, генерація ключів методом Диффі-Хеллмана здійснюється в сотні разів быстріше в зрівнянні з алгоритмом RSA.

 

Приклад: Нехай

p = 13, a = 7, m = 3, k = 4.

 

Відкритий ключ, який передається стороной Адорівнює

 

yА º7 3(mod 13) º 343(mod 13) º 5

 

Відкритий ключ, який передається стороной Bдорівнює

 

yВ º74(mod 13) º 2401(mod 13) º 9

 

Секретне число, яке розраховується сторонами, дорівнює

К º5 4(mod 13) º 625(mod 13) º 1,

K' º9 3(mod 13) º 729(mod 13) º 1.

 

4.8.3.2 Переваги та недоліки алгоритму Диффі-Хеллмана

Диффі и Хеллман дали пропозицію для створення криптографічних систем з відкритим ключем функ­цію дис­крет­но­го піднесе­ння до сте­пеня.

Необоротність перетворення в цьому випадку забезпечується тим, щолегко обчислити показникову функцію в кінцевому полі Галуа, яке складається з p елементів(p- просте число чи просте в будь-якому степені).

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

Так, якщо для прямого перетворення 1000-бітових простих чисел треба 2000 операцій, то для зворотного перетворення (обчислення логарифму в полі Галуа) – треба біля 1030 операцій.

Даний алгоритм відрізняється від алгоритму RSA тим, що не дає змогу шифрувати саме інформацію.

Другим недоліком алгоритма Диффі-Хеллмана є відсутність гарантованної нижчої оцінки трудомісткості зламування ключа.

Крім того залишається проблема автентифікації, тому що є небезпека імітації користувача.

 

 

 

 

         
 
 

 

 

5 Приклади розв’язування завдань

 

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

 

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

 

5.1.1 Шифрування за допомогою класичних шифрів перестановки

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

 

1 2 … n

i1 i2 … in,

 

де і1 – номер місця шифртексту, на котре потрапляє перша літера вихідного повідомлення за обраного перетворення; і2 – номер місця для другої літери й т. д. У верхньому рядку таблиці виписано одне за одним числа від 1 до n, а в нижньому – ті ж самі числа, але в довільному порядку. Така таблиця називається підставлянням ступеня n.

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

 

Наприклад, якщо для перетворення використовується підставляння

1 2 3 4 5

5 2 3 1 4

 

і відповідно до нього зашифровується слово УЧЕНЬ, то виходить НЧЕЬУ.

 

5.1.2 Шифрування за допомогою табличних шифрів перестановки

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

Наприклад, повідомлення

 

МАЄШ ГОЛОВУ, МАЙ ЖЕ РОЗУМ

 

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

М О М Р
А Л А О
Е О Й З
Ш В Ж У
Г У Е М

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

МОМРА ЛАОЕО ЙЗШВЖ УГУЕМ

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

 

5.1.3 Шифрування за допомогою шифрів маршрутної перестановки

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

Зашифруємо, наприклад, зазначеним способом фразу: