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

ТЕМА 1. БАЗОВІ МАТЕМАТИЧНІ ОСНОВИ КРИПТОГРАФІЧНИХ ЗАСОБІВ ЗАХИСТУ ІНФОРМАЦІЇ
Мета роботи: зрозуміти і практично дослідити базові поняття, функції та методи криптографічних засобів захисту інформації.
Рекомендовані інструментальні засоби до виконання роботи:

• 
  мова програмування – Python 3.x.x;
  
• 
  середовище Python–програмування (IDE) – Thonny 3.3.6;
  
• 
  табличний процесор – MS Excel.
  

1. Функції модульної арифметики (арифметики в класах залишків). Будуть потрібні в подальшому для дослідження одноключових (симетричних) криптоалгоритмів і криптосистем, двохключових (несиметричних) криптоалгоритмів і криптосистем, а також криптографічних хеш - функцій.
Надалі, якщо не буде зазначено іншого, будуть розглядатися виключно позитивні цілі числа.
1.1. Операція обчислення залишку (остачі) r числа Х за модулем М записується як
r = Х mod M, або Х mod M = r, або як X  r (mod M).
Ця операція пов’язана з тим, що будь-яке ціле число Х може бути представлено у загальному вигляді як
k*M + r, де k, r – цілі числа.
Приклади:
M = 9; X = 23. r = 23 mod 9 = 5. Пояснення: 23 - 5 = 18; 18/9 = 2; 23 = 2*9 + 5.
M = 9; X = 23. r = 72 mod 9 = 0. Пояснення: 72 - 0 = 72; 72/9 = 8; 72 = 8*9 + 0.
Якщо M = 9, то 0  r  8 також і для інших цілих Х.
M = 231; X = 5678. r = 5678 mod 231 = 134. Пояснення: 5678 - 134 = 5544; 5544/231 = 24; 5678 = 24*231 + 134.
Якщо M = 231, то 0  r  230 також і для інших цілих Х.
M = 2; X = 1903; r = 1903 mod 2 = 1. Пояснення: 1903 - 1 = 1902; 1902/2 = 951; 1903 = 951*2 + 1.
M = 2; X = 128; r = 128 mod 2 = 0. Пояснення: 128 - 0 = 128; 128/2 = 64; 128 = 64*2 + 0.
Якщо M = 2, то r = 0 або 1 також і для інших цілих Х.
Якщо Х  М, то r = Х, наприклад, 3 mod 9 = 3, 14 mod 15 = 14.
Якщо ж Х = k*М, де k – ціле, то r = 0. Наприклад, 15 mod 15 = 0, 45 mod 15 = 0.
Примітка. В Python операція обчислення залишку mod реалізується виключно просто, оператором "%":
Х % М # Х, М – константи, змінні або вирази – див. документацію по Python.
Завдання 1. З'ясуйте, як операція mod реалізується в MS Excel. Обчисліть залишки r за модулем М = 7 для чисел Х в діапазоні 0 до 28 на робочому аркуші MS Excel. Яку закономірність Ви помітили?
1.2. Деякі властивості модульної арифметики
Два цілих числа А і В називаються рівними (порівняними, конгруентними) за модулем М, що записують як А  В (mod М), якщо їх залишки рівні:
r_А = r_B,
де: r_А = A mod M r_B = B mod M.
Справедливі такі правила арифметики у класах залишків (наводяться без доказів):
[(A mod M) + (B mod M)]mod M = (A + B) mod M
[(A mod M) – (B mod M)]mod M = (A – B) mod M
[(A mod M) * (B mod M)]mod M = (A * B) mod M
Завдання 2. Перевірте наведені вище правила арифметики у класах залишків, в середовищі Python.
1.3. Особливий випадок операції mod – операція XOR.
Особливе значення у криптографії має випадок застосування операції mod, а саме, коли М = 2. При цьому вважається, що Х  [0,1]. У цьому випадку замість позначення mod уживають позначення XOR, або символ . У цьому випадку 0 mod 2 = 0, 1 mod 2 = 1.
У застосуванні для 2-х операндів А  [0,1] та В  [0,1] маємо (у різних формах запису) :
(0 + 0) mod 2 = 0  0  0 = 0  0 XOR 0 = 0
(0 + 1) mod 2 = 1  0  1 = 1  0 XOR 1 = 1
(1 + 0) mod 2 = 1  1  0 = 1  1 XOR 0 = 1
(1 + 1) mod 2 = 0  1  1 = 0  1 XOR 1 = 0
Можна також для компактності використовувати запис виду XOR(А,В) якщо А,В являють собою бітові або байтові рядки.
Операцію  використовують для обчислення кодової відстані між двома кодовими векторами (рядками) однакової довжини
[А] = [a₁, a₂, a₃, a₄, a₅, a₆, …],
[В] = [b₁, b₂, b₃, b₄, b₅, b₆, …].
Кодовою відстанню d між [А] і [В] називають кількість розрядів з однаковими індексами, які не співпадають.
Приклад.
[А] = [0 1 1 0 1 0 1 1 0 0 1];
[В] = [1 1 1 0 0 0 1 1 0 1 1].
Застосовуємо побітово операцію  і отримуємо вектор [S]:
0 1 1 0 1 0 1 1 0 0 1

1 1 1 0 0 0 1 1 0 1 0
________________
[S] = 1 0 0 0 1 0 0 0 0 1 1
Кількість ненульових розрядів у результуючому векторі [S] = [А]  [В] дорівнює 4. Тобто кодова відстань d = 4.
Завдання 3. Розробіть на Python функцію codedist (a,b), де a,b – байтові рядки довільної, але однакової довжини, яка повертає кодову відстань d між ними. Збережіть цю функцію у Вашому репозиторії для подальшого використання.