Загальні поняття та визначення — IT1406 Інформаційна безпека

Нехай m - деяке натуральне число. Не всі натуральні числа поділяються на m. Можливими залишками від розподілу є 1, 2, . m - 1, 0 (останній при розподілі націло). За модулем m кожне натуральне число сприймається як залишок від розподілу цього числа на m : $$25\,mod\,3 = 1, \\ 9\,mod\,7=2, \\ 100\,mod\,26=22 , \ 100 \, mod \, 32 = 4 $ $ і т.п.

Два числа a і b називаються порівнянними по модулю m , якщо за розподілі на m вони дають однакові залишки, тобто. якщо %% a \, mod \, m = b \, mod \, m% %.

У цьому випадку пишуть %%a≡b (mod,m)%% («a порівняно з %%b%% за модулем %%m%%»). Так, наприклад, $$ 5 equiv11 (mod 3), 25 equiv0 (mod 5), 48 equiv6 (mod 7).

На множині чисел %%1, 2, . m – 1%%, %%0%% вводиться додавання по модулю %%m%%: як результат береться залишок від розподілу звичайної суми доданків на модуль %%m%%, тобто. %%a+_m b=(a+b)mod\, m%%. Наприклад, при додаванні за модулем 2 отримуємо %%0+_2 0=1+_2 1=0%% та %%0+_21=1+_20=1%%. Складемо таблицю додавання за модулем 3:

%%+_3%%	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Як бачимо, %% 2+_32 = (2 +2) mod, 3 = 4, mod, 3 = 1%.

При відніманні по модулю m для відповідних чисел здійснюють звичайне віднімання і, якщо в результаті вийде негативне число, до нього додають m . Наприклад, за модулем 5 маємо: %%1 –_5\,4 = -3\,mod\,5 = 2%%.

Якщо деякий алфавіт має потужність m (тобто в ньому m букв), то додавання та віднімання по модулю m можна тлумачити як додавання та віднімання букв з відповідними номерами. Так, за m=32 (український алфавіт) маємо: $$Й - Ц = 10 -_ 23 = -13\,mod\,32= 19 = Т, $ $ $ $ Т + Т = 19 +_ 19 = 38 \, mod \, 32 = 6 = Е $ $ і т.п.

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

кожен з яких буквально складається з ключем:

$$(шифрування) + (завдання) = (25,9,21,17,3,9) +_ (8,1,5,1,24,1) =\\ (33,10,26,18, 27,10) mod \, 32 = (1,10,26,18,27,10) = АЙЩСЬЙ,$$

$$(женера) + (завдання) = (7,6,14,6,17,1) +_ (8,1,5,1,24,1) =\\ (15,7,19,7, 9,2)=ОЖЖЖИБ$$

Підсумкова криптограма: АЙЩСЬЙОЖТЖИБ .

При дешифруванні з блоку криптограми буквально віднімається ключ. Так, знаючи, що криптограма LAGZJEUUXRTJE отримана на ключі Віженера p r o b l em («завдання»), легко відновлюємо відкритий текст. Спочатку з першого блоку криптограми буквально віднімаємо ключ:

$$LAVGZJE - PROBLEM = (12,1,22,7,26,10,5) -_ (16,18,15,2,12,5,13) = \\ (-4, -17,7, 5,14,5,-8)mod\, 26 = (22,9,7,5,14,5,18) = vigener$$

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

$$UUXRTJE - PROBLEM = (21,21,24,18,20,10,5) -_(16,18,15,2,12,5,13) =\\ (5,3,9,16, 8,5,-8)mod \,26 = (5,3,9,16,8,5,18) = ecipher.$$

Відкритий текст: Vigenere cipher (шифр Віженера).

Надалі знадобиться і множення по модулю m: воно виконується аналогічно до додавання – як результат береться залишок від розподілу на m звичайного твору співмножників. Наприклад, для множення за модулем 4 отримуємо таку таблицю:

%%×_4%%	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

Відзначимо незвичайну рівність %%2 ×_4 2=0%%, обидва співмножники відмінні від нуля, а їх добуток дорівнює нулю.

---