8.6 Модульна арифметика
У криптографії та криптоаналізі часто буває необхідно скласти дві послідовності чисел або відняти одну з іншої. Таке додавання і віднімання проводиться, зазвичай, не з допомогою звичайних арифметичних дій, і з допомогою операцій, званих модульної арифметикою. У модульній арифметиці додавання, віднімання виконується щодо деякого фіксованого числа, яке називається модуль. Типовими значеннями модулів, що використовуються в криптографії, є 2, 10 і 26. Який би модуль ми не взяли, всі числа, що зустрічаються, замінюються на залишки від поділу цих чисел. Якщо в залишку виходить негативне число, то до нього додають значення модуля, щоб залишок став невід'ємним. Наприклад, якщо використовується модуль 26, то єдино можливі числа лежать у діапазоні від 0 до 25. Так, якщо додати 17 до 19, то результат дорівнює 10, оскільки 17+19 = 36, а 36 при розподілі на 26 дає залишок 10. вказати, що використовується модуль 26, прийнята форма запису:
Якщо відняти 19 з 17, то результат (-2) виходить негативним, тому до нього додається 26, і в результаті виходить 24.
При додаванні за модулем 26 двох числових послідовностей сформульовані правила додавання застосовуються в кожній парі чисел окремо, без «перенесення» на наступну пару. Аналогічно, при відніманні за модулем 26 однієї числової послідовності з іншої правила віднімання застосовуються до кожної пари чисел окремо, без «запозичення» з наступної пари.
Скласти по модулю 26 послідовності 15 11 23 06 11 та 17 04 14 19 23
та в результаті 06 15 11 25 08
Якщо модуль дорівнює 10, використовуються числа від 0 до 9; при модулі 2 – лише 0 та 1
Арифметика за модулем 2, або, як її зазвичай називають, двійкова (бінарна) арифметика,має особливе значення, оскільки в цьому випадку додавання та віднімання є ідентичними операціями, тобто завжди дають однаковий результат, а саме:
0 0 1 1 0 0 1 1
+ 0 1 0 1 - 0 1 0 1
0 1 1 2 0 -1 1 0
0 1 1 0 0 1 1 0 (mod 2) в обох випадках.
Модульне додавання та віднімання букв
Давайте розглянемо приклад модульної додавання і віднімання застосовно до букв.
Додати TODAY до NEVER за модулем 26
Відняти TODAY з NEVER за модулем 26
TODAY = 19 14 03 00 24
NEVER =13 04 21 04 17
Сума = 32 18 24 04 41 06 18 24 04 15 = GSYEP
TODAY = 19 14 03 00 24
NEVER =13 04 21 04 17
Різниця = 06 10 -18 -04 07 06 10 08 22 07 = GKIWH
У лекції розглянуті питання, пов'язані з шифруванням та дешифруванням текстів. Дано визначення коду, шифру, дешифрування, криптографії. Розглянуто застосування модульної арифметики до питань шифрування.
Дайте визначення монографа, диграфа, триграфа та поліграфа чим вони відрізняються один від одного.
Дайте визначення символу.
Дайте визначення рядка.
Як визначається довжина рядка?
Що таке система шифрування?
Дайте визначення термінам зашифрування та розшифрування.
Чим розшифрування відрізняється від дешифрування?
Дайте визначення криптографії і хто їй займається.
Назвіть етапи дешифрування та охарактеризуйте їх.
Дайте визначення коду та шифру.
Як оцінити стійкість шифру?
Дайте визначення кодам, що виявляють та виправляють помилки.
Назвіть методи приховування повідомлень.
Дайте визначення модульної арифметики та її призначення для шифрування текстів.