Опис афінної системи підстановок Цезаря
Цезар не був програмістом і тим більше не володів наукової криптографією. І тим не менше про цю ось аффинную систему підстановок і досі читають. А ще їй мучать студентів на лабораторних. Порятунок від цього - відкрити код сторінки і стягнути звідти скрипт і HTML-код демонстрації. Можна навіть без відома автора сайту і тим більше пана Цезаря)))
1. Алгоритм системи підстановок Цезаря + приклади
Нехай є якийсь алфавіт з N символів, нумерація символів ведеться з нуля (це дратує, але так вже придумано). Так, для англійського алфавіту N = 26, номер символу 'a' - 0, 'c' - 2, 'z' - 25.
Є якісь параметри A, K - цілі числа, що лежать в проміжку [0, N-1]. Ці параметри утворюють ключ аффинной системи підстановок Цезаря. При цьому A і N - взаємно прості числа. Для особливо нетямущих: взаємно прості - це числа, які одночасно діляться тільки на 1, не можна знайти іншого числа, на яке вони б обидва ділилися остачі.
Припустимо, деякий символ з рядка відкритого тексту має номер X в заданому алфавіті. Тоді він відображається в символ номер (AX + K) mod N.
Наведемо приклад роботи аффинной системи підстановок Цезаря. Нехай A = 3, K = 2, алфавіт англійський. Тоді слово bug відображається в fku. Наприклад, 'u' йде під номером 20, (20 * 3 + 2) mod 26 = 10, тобто в зашифрованому тексті це буде 'k'.
Навіщо A і N повинні бути взаємно простими? Якщо ця умова порушена, буде ситуація, коли різні символи відкритого тексту відображаються в один і той же символ шифрованого. Ясно, що розшифрування отриманого тексту може бути неоднозначним. Припустимо, A = 2, K = 3. Тоді результат застосування перетворення (2X + 3) mod 26 буде однаковий для символів, які відстоять в алфавіті один від одного на 13 позицій.
На число K правила аффинной системи підстановок Цезаря накладають особливих обмежень. Хіба що можна брати K = 0, якщо A = 1. В інших випадках і при K = 0 аффинная система підстановок Цезаря працює нормально, якщо тільки A вибрати правильно.
До речі кажучи, так званий шифр Цезаря, де кожен символ відкритого тексту зсувається на фіксоване число позицій, є окремий випадок аффинной системи підстановок Цезаря. Підставляємо A = 1 і переконуємося в цьому. Очевидно, що шифр Цезаря малонадёжен: якщо в алфавіті N символів, по суті є N-1 варіантів ключів. Формула шифру Цезаря: замість символу номер X беремо символ (X + K) mod N, де N - кількість символів алфавіту, K - ключ шифру Цезаря.
2. Злом системи підстановок Цезаря
Визначимо, скільки може бути придумано ключів (A, K), якщо в алфавіті N символів. Аффинная система підстановок Цезаря передбачає, що A і N - не мають спільних дільників, ну хіба що одиницю (тобто взаємно прості), на K ніяких обмежень немає. Ось так ось - одним все можна, іншим заборони, втім ... хіба Цезар був демократом?
Нехай f (N) - кількість таких чисел серед 1,2, ..., N-1, які не мають з N загальних дільників, крім одиниці. Тоді виходить, що чісленціо A можна вибрати f (N) способами, а K - не інакше, як N способами. При цьому якщо A = 1 і K = 0, то (AX + K) mod N = X, тобто ми нічого не шифруємо по суті. Підсумок: можна вигадати N * f (N) - 1 ключів.
Отже, тепер у нас є формула. Давайте подумаємо, N * f (N) - 1 - багато чи мало? Припустимо, закинули в алфавіт маленькі букви, великі, цифри, розділові знаки, ще якусь нісенітницю і отримали 100 символів. Якщо число закінчується на 1, 3, 7, 9, то воно має з сотнею тільки один спільний дільник - одиницю. Так що f (100) = 4 * 10 = 40. Можемо посперечатися на пиво, що пораховано вірно. Вважаємо далі 100 * f (100) = 100 * 40 = 4000. Чи багато це? Якщо, припустимо, на перевірку кожного варіанту ми витрачаємо 5 хвилин, то на все - 20000 хвилин, тобто по суті 2 тижні. Але оскільки ми ще повинні поїсти, поспати, попити пивка і т.д., то насправді як мінімум місяць. Або навіть більше. Тобто колись зломщику довелося б сильно помучитися. Це, правда, про найгірший випадок йшлося. В середньому час буде вдвічі менше, але і це не особливо радує.
Але зараз-то тільки ПОВНИЙ LOSER буде перебирати вручну. А для компа 4000 варіантів - та так, дрібниці. Так що зараз аффинная система підстановок Цезаря суть спогади про минуле і 1-2 години студентських страждань. А шифр Цезаря - так і того менше.
Щоб уникнути останніх, можна відкрити вихідний код цієї сторінки і стягнути звідти те, що служить для демонстрації нижче.
Система підстановок Цезаря і шифр Цезаря онлайн
Увага! Прогалини потрібно вказувати явно в алфавіті, в зашифрованому тексті вони для зручності замінюються підкресленням. У алфавіті має бути не менше 5 символів. Якщо в поле для множника введете одиницю, буде шифр Цезаря.
Множник Доданок
Відкритий текст
Шифрованний текст
Немає коментарів:
Дописати коментар