Вказівки
Створіть реалізацію афінного шифру, стародавньої системи шифрування, створеної на Близькому Сході.
Афінний шифр належить до моноалфавітних шифрів підстановки.
Кожен символ зіставляється з його числовим еквівалентом, шифрується математичною функцією, а потім перетворюється на літеру, що відповідає його новому числовому значенню.
Хоча всі моноалфавітні шифри слабкі, афінний шифр значно стійкіший за шифр Атбаш, бо має набагато більше ключів.
Шифрування
Функція шифрування має такий вигляд:
E(x) = (ai + b) mod m
Де:
-
i - це індекс літери від 0 до довжини алфавіту мінус 1.
-
m - це довжина алфавіту.
Для латинського алфавіту m дорівнює 26.
-
a і b - це цілі числа, з яких складається ключ шифрування.
Значення a і m мають бути взаємно простими (або взаємнопростими), щоб автоматичне розшифрування було успішним: тобто їхнім єдиним спільним дільником є число 1 (докладніше в статті Вікіпедії про взаємно прості числа).
Якщо a не є взаємно простим із m, програма має вказати, що це помилка.
В іншому разі вона має зашифрувати або розшифрувати текст із наданим ключем.
У цій вправі цифри є припустимими вхідними даними, але їх не шифрують.
Пробіли та розділові знаки виключаються.
Шифротекст записують групами фіксованої довжини, розділеними пробілом; традиційно група складається з 5 літер.
Це потрібно, щоб було важче вгадати зашифрований текст, орієнтуючись на межі слів.
Розшифрування
Функція розшифрування має такий вигляд:
D(y) = (a^-1)(y - b) mod m
Де:
-
y - це числове значення зашифрованої літери, тобто y = E(x)
- важливо зазначити, що
a^-1 - це обернене за модулем число (MMI) для a mod m
- обернене за модулем число існує лише тоді, коли
a і m взаємно прості.
MMI для a - це таке x, що остача від ділення ax на m дорівнює 1:
ax mod m = 1
Докладніше про те, як знайти обернене за модулем число і що воно означає, можна прочитати в статті Вікіпедії.
Загальні приклади
- Шифрування
"test" дає "ybty" з ключем a = 5, b = 7
- Розшифрування
"ybty" дає "test" з ключем a = 5, b = 7
- Розшифрування
"ybty" дає "lqul" з неправильним ключем a = 11, b = 7
- Розшифрування
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" дає "thequickbrownfoxjumpsoverthelazydog" з ключем a = 19, b = 13
- Шифрування
"test" з ключем a = 18, b = 13 є помилкою, бо 18 і 26 не взаємно прості
Приклад знаходження оберненого за модулем числа (MMI)
Знаходимо MMI для a = 15:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1, тобто 105 mod 26 = 1
-
7 - це MMI для 15 mod 26
