Вказівки
Створіть реалізацію афінного шифру, стародавньої системи шифрування, що виникла на Близькому Сході.
Афінний шифр належить до моноалфавітних шифрів заміни.
Кожен символ зіставляється зі своїм числовим еквівалентом, шифрується за допомогою математичної функції, а потім перетворюється на літеру, що відповідає його новому числовому значенню.
Хоча всі моноалфавітні шифри слабкі, афінний шифр значно сильніший за шифр Атбаш, бо має набагато більше ключів.
Шифрування
Функція шифрування така:
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
