Коротка математика: групи
Алгоритм або протокол Діффі-Хеллмана (далі DH) працює за допомогою простих чисел. Нехай а – це достатньо велике число, що належить безлічі простих чисел. Алгоритм передбачає використання числа розміром 250-500 байт. Нехай Zа – мультиплікативна група кільця відрахувань по модулю а, яка буде використана алгоритмом шифрування Діффі-Хеллмана. Вона складається з безлічі чисел 1, …, a-1.
Візьмемо якийсь елемент b з групи Zа і розглянемо нескінченну послідовність 1, b, b2, b3, b4, … З того факту, що група Za за визначенням є кінцевим безліччю, рано чи пізно розглянута послідовність {b} почне повторюватися. Покладемо bi = bj (i < j).
Тепер розділимо кожну частину рівності, bi (за модулем a) і отримаємо bj-i = 1. Це означає, що існує таке число k = j-i, для якого вірно bk = 1 (mod a). Найменше число k, для якого виконується дана рівність, називається порядком числа b. Щоб уникнути непорозуміння з іншою спеціальною літературою для пояснення системи Діффі-Хеллмана використовуються стандартні математичні позначення.
Таким чином, зводячи число b, називається твірним елементом, ступінь, ми отримуємо послідовність чисел (множина) 1, …, bk-1 . Кількість елементів цієї множини в точності дорівнює k.
Властивість множення за модулем a свідчить, що існує хоча б одне число b, яке породжує всі елементи групи Z*a . Інакше кажучи, існує число, для якого вірно k = a – 1. Дана властивість дозволяє представити числа групи Z*a у вигляді 1, b, b2, … ba-2 . Таке число b називається примітивним числом групи.
Надалі за ознаками групи легко доводиться, що безліч, породжене числом b, також є групою і успадковує всі властивості груп. Іншими словами, операції в межах породженої групи або підгрупи можна проводити точно таким же чином, як в групі з модуля a.
Розглянемо твердження. Для будь-якого елемента b його порядок є дільником числа a-1. Це легко показати. Нехай a=7. Число b = 3 – примітивне, т. к. 1, …, b5 = 1, 3, 2, 6, 4, 5. Тоді число h = 2 буде породжувати підгрупу 1, …, h2 = 1, 2, 4, так як h3 = 23 mod 7 = 1. h = 6 породжує підгрупу 1, 6. Розміри груп дорівнюють 3 і 2, відповідно. Очевидно, що вони є дільниками числа a-1 = 6.
