Тема базові математичні основи криптографічних засобів захисту інформації

с = gcd (a, b).
Позначення gcd для найбільшого загального дільника походить від англійських слів greatest common divisor і є загальноприйнятним.
Приклад. gcd (10,15) = 5; gcd (8,28) = 4.
Для знаходження найбільшого спільного дільника використовують так званий алгоритм Евкліда.
Алгоритм Евкліда на псевдокоді виглядає так:
ВХІД: Позитивні цілі числа а, b , а > b.
ВИХІД: Найбільший спільний дільник gcd (a, b).
WHILE b  0 DO
r  a mod b
a  b
b  r
RETURN a
Тоді, для визначення взаємної простоти пари чисел можна скористатися тим, що числа a, b є взаємно простими, якщо gcd (a, b) = 1.
Завдання 5. Створіть програму gcd (a, b), яка знаходить і повертає НСД чисел а і b за алгоритмом Евкліда. Програму оформіть як функцію Python. Перевірка а > b на вході обовʼязкова, але сама функція повинна бути нечутливою до порядку аргументів при її виклику.
2.3. Зворотні числа по заданому модулю. Розширений (узагальнений) алгоритм Евкліда. Функція Ейлера.
Якщо цілі числа А та N взаємно прості, то тоді і тільки тоді (!) існує число А', таке, що (А*А') mod N = 1. Число А' називають зворотним до А по модулю N і використовують позначення А^-1 (mod N). Обчислити А^-1 можна, наприклад, скориставшись так званим розширеним (узагальненим) алгоритмом Евкліда.
Але в окремому випадку, тобто для реалізації алгоритмів компʼютерної криптографії, в яких необхідно знаходити зворотні числа по заданому модулю, значно простіше спиратися на властивості функції Ейлера.
Функція Ейлера  (N) визначена на множині натуральних чисел. Нехай дано ціле число N  1. Значення функції Ейлера  (N) дорівнює кількості чисел в ряду 1,2,3,...,N - 1, взаємно простих з N.
Мають місце такі властивості функції Ейлера:
1) якщо N – просте число, то
 (N) = N – 1;

2) якщо N і М – прості числа, такі, що N  М, N < М, то

 (N*М) = (N – 1)*( М – 1).
Через функцію Ейлера  (N) зворотне число А^-1 по заданому модулю N обчислюється дуже просто:
А^-1 = А^{ (N) – 1} mod N.
Завдання 6. Напишіть функцію Python euler (N), яка повертає значення кількості чисел в ряду 1,2,3,...,N - 1, взаємно простих з N, для довільних натуральних (не тільки простих) чисел N.
Завдання 7. Напишіть функцію Python inverse (А, N), яка повертає значення зворотного числа А^-1 , використовуючи формулу А^-1 = А^{ (N) – 1} mod N. Перед обчисленням функція inverse (А, N), повинна перевірити взаємну простоту А та N. Для цього можна скористатися функцією gcd ( ) із Завдання 2.2.
2.4. Дискретний логарифм. Первісні корені.
Формально дискретний логарифм можна визначити наступним чином.
Спочатку визначимо первісний корінь простого числа N (інакше – породжуючий елемент або генератор скінченної циклічної групи порядка N) як таке число , ступені якого породжують усі цілі числа від 1 до N – 1.
Це означає, що якщо  є первісним коренем простого числа N, то усі числа
 ¹ mod N,  ² mod N, ... ,  ^(N-1) mod N
будуть різними і представлятимуть усі цілі числа від 1 до N – 1 в деякій перестановці.
Для будь-якого цілого числа b і будь-якого первісного кореня  простого числа N однозначно визначається показник ступеня i, при якому
b =  ⁱ mod N , де 0 < i < (N – 1).
Цей показник ступеня i називається дискретним логарифмом, або індексом b за основою  по модулю N, що може записуватися також у формі ind _,N (b).
Приклади.
Якщо N = 7, то при цьому первісними корінями будуть такі:
3, 5.
А якщо N = 23, то при цьому первісними корінями будуть такі:
5, 7, 10, 11, 14, 15
Переконаймося, що число 3 є первісним коренем за модулем N = 7. Для цього достатньо кожне число від 1 до 6 представити як певну ступінь 3 за модулем N = 7:
3⁰ = 1 (mod 7)
3¹ = 3 (mod 7)
3² = 2 (mod 7)
3³ = 6 (mod 7)
3⁴ = 4 (mоd 7)
З⁵ = 5 (mod 7)
Отримані числа 1, 3, 2, 6, 4, 5 являють собою перестановку чисел натурального ряду 1, 2, 3, 4, 5, 6.
Для довідки наведемо таблицю перших первісних коренів  простих чисел N < 1000, узяту за адресою www.intuit.ru/studies/courses/553/409/lecture/17867: