Як працює афінний шифр

Ідея одним реченням

Афінний шифр — це Підстановка, керована прямою лінією: кожну літеру спершу розтягує множник, потім зсуває зсув, і все це в Модульна арифметика — арифметиці, що обертається колом на 26.

Рецепт

1. Оберіть ключ: множник a і зсув b.

2. Множник має бути взаємно простим із довжиною алфавіту: для 26-літерного алфавіту це лишає дванадцять значень (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25). Будь-який спільний дільник із 26 сплющив би кілька літер в одну — і інструмент відмовляється будувати такий алфавіт.

3. Пронумеруйте літери від 0 (A = 0). Шифруйте літеру номер x у літеру номер (a·x + b) mod 26.

4. Прочитайте нову літеру з алфавіту.

Розібраний приклад

З множником 3 і зсувом 7 S (літера 18) потрапляє на (3·18 + 7) mod 26 = 9 — J. E (літера 4) — на 19, тобто T. Середній стовпець — чесне серце шифру: одне множення й одне додавання з обертанням на 26.

Формула

шифрування:   y = (a·x + b) mod 26
розшифрування: x = a⁻¹·(y − b) mod 26

Розшифруванню потрібен обернений множник — число, яке в добутку з a дає 1 mod 26. Для a = 3 обернене — це 9, бо 3·9 = 27 ≡ 1 (mod 26). Лише множники, взаємно прості з 26, мають обернене — тому простір ключів дорівнює 12 × 26 = 312 ключів.

Чому два числа кращі за одне

Чистий зсув (Цезар, a = 1) ковзає алфавітом, але зберігає відстані між літерами: шаблон A-B-C видно за будь-якого зсуву. Множник перекроює проміжки — B вже не «крок після A». Кожна відстань змінюється з множенням, і Частотний аналіз, що валить Цезаря, тут вимагає більшої праці.

Покрокові інструкції

Зашифруйте перше повідомлення

1. Наберіть повідомлення у поле повідомлення.

2. Виставте множник у поле множника — спробуйте 3, класичний вибір, взаємно простий із 26.

3. Виставте зсув у поле зсуву — цезарів доданок, будь-яке значення від 0 до 25.

4. Прочитайте результат у поле результату. Та сама літера відкритого тексту завжди дає ту саму літеру шифротексту, але відповідність вже не просте ковзання.

Розшифруйте отримане повідомлення

1. Вставте криптограму у поле повідомлення і натисніть кнопку обміну кнопку обміну.

2. Уведіть той самий множник поле множника і той самий зсув поле зсуву, що й у відправника. Інструмент сам обчислює обернене множення — жодної модульної арифметики з вашого боку.

3. Прочитайте початкове повідомлення у поле результату.

Зламайте повідомлення без ключа

Афінний шифр усе ще одна нерухома Підстановка, тож падає під класичною атакою — і під швидким шляхом теж:

1. Якщо знаєте дві пари «літера відкритого → літера шифротексту», розв'яжіть пряму безпосередньо: відніміть два рівняння, щоб прибрати b, потім поділіть — тобто помножте на модульний обернений елемент — і отримаєте a.

2. Маючи a, відновіть b з будь-якої пари.

3. Уведіть обидва числа у поле множника і поле зсуву, перемкніться в режим розшифрування і прочитайте повідомлення.

4. Немає відомих літер? Поверніться до Частотний аналіз: найчастіша літера шифротексту відповідає E (або T, чи A), і кожна здогадка про пару кандидатів визначає ключ-кандидата для перевірки на наступних літерах.

Злам афінного шифру

Афінний шифр — одноалфавітна Підстановка з математичним кістяком, і саме кістяк його видає. Дві відомі літери розвалюють весь ключ. Ця сторінка показує обидва шляхи.

Вада: пряма лінія лишає слід

Два параметри, одна лінійна правило: y = (a·x + b) mod 26. Кожна пара ключа лежить на тій самій прямій. Дві точки визначають пряму — отже, дві відомі пари літер визначають ключ.

Атака 1 — двох відомих літер досить

1. Вгадайте або здобудьте дві пари «відкрита → шифрована», скажімо x₁ → y₁ і x₂ → y₂.

2. Відніміть: y₁ − y₂ ≡ a·(x₁ − x₂) (mod 26). Поділіть на x₁ − x₂ — у Модульна арифметика ділення означає множення на модульний обернений елемент — і відновите a.

3. Підставте назад і відновите b.

4. Уведіть ключ і розшифруйте. Ключове слово — відомі слова на початку повідомлення — дають пари задарма.

Атака 2 — частотний аналіз, як завжди

Без відомих літер шифр усе ще нерухома Підстановка: найчастіша літера шифротексту відповідає E, друга — T чи A, і кожна здогадна відповідність — це гіпотеза про (a, b), яку перевіряють на наступних літерах. Периоду шукати не треба, структури окрім самої відповідності немає — Частотний аналіз працює точнісінько як проти Цезаря, лише алфавіти-кандидати менш впорядковані.

Чому правило взаємної простоти важливе

Множник має бути взаємно простим із 26 — інакше дві літери відкритого тексту зіллються в одну шифровану, і повідомлення неможливо однозначно розшифрувати. Ця вимога вдвічі звужує простір ключів до 312 комбінацій, і саме тут початківець уперше зустрічає ідею, що несе сучасну криптографію: оборотність всередині модульної арифметики.

Від Цезаря до афінного до RSA

Цезарів зсув — афінний шифр з a = 1. Афінний додає одне множення, а з ним — поняття модульного оберненого елемента. Підніміть ставки — піднесення до степеня замість множення — і ви прибудете до математики відкритих ключів RSA. Шифр-іграшка й банківська система поділяють одну й ту саму граматику.