Аффинный шифр

Как пользоваться аффинным шифром

1. 1. Выберите режим и введите текст. «Зашифровать» превращает открытый текст в шифртекст; «Расшифровать» делает обратное.
2. 2. Задайте ключ. Введите a — множитель — и b — сдвиг. a должно быть одним из 12 значений, перечисленных под полями, — нажмите на любое, чтобы использовать его. b может быть любым целым числом; оно приводится по модулю 26.
3. 3. Прочитайте ход вычислений. Панель под результатом показывает обе формулы для вашего ключа, обратное к a число и арифметику каждой буквы.
4. 4. Нет ключа? Попробуйте все. В режиме «Расшифровать» отметьте Не знаете ключ? Попробуйте все 312 ключей. Результаты ранжируются по тому, насколько частоты букв близки к английским, а Использовать этот ключ загружает любой из них.

Формула аффинного шифра

Пронумеруйте буквы с нуля: A = 0, B = 1 … Z = 25. Чтобы зашифровать букву x, умножьте её на a, прибавьте b и возьмите остаток от деления на 26: E(x) = (a·x + b) mod 26. Чтобы расшифровать букву y, выполните те же шаги в обратном порядке — вычтите b, затем умножьте на a⁻¹, обратное по модулю число к a: D(y) = a⁻¹·(y − b) mod 26. Обратное — это число, которое при умножении на a даёт остаток 1. Для a = 5 это 21, потому что 5 × 21 = 105 = 4 × 26 + 1.

Почему подходят только 12 значений a

Умножение на a никогда не должно отправлять две буквы в одно и то же место, иначе у расшифровки было бы два ответа. Это происходит всякий раз, когда a имеет общий множитель с 26 = 2 × 13. При a = 2, например, A (0) и N (13) обе попадают в b, потому что 2 × 13 = 26, а это 0 по модулю 26. Поэтому a должно быть нечётным и не равным 13, и остаются двенадцать чисел ниже — именно те, у которых есть обратное по модулю 26. При 26 вариантах b получается 12 × 26 = 312 ключей, один из которых (a = 1, b = 0) ничего не меняет.

Пример: a = 5, b = 8

При a = 5 и b = 8 AFFINE CIPHER шифруется в IHHWVC SWFRCP — это пример инструмента. Буквы слова AFFINE, шаг за шагом:

Чтобы расшифровать, инструмент умножает на a⁻¹ = 21. Буква I (8) превращается в 21 × (8 − 8) = 0, то есть A; буква H (7) превращается в 21 × (7 − 8) = −21, что равно 5 по модулю 26, то есть F. Отрицательные значения на этом шаге — норма: «по модулю 26» значит лишь, что к числу прибавляют или вычитают 26, пока оно не окажется между 0 и 25.

Два знакомых шифра — это аффинные шифры в другом обличье. При a = 1 формула принимает вид x + b — это сдвиг Цезаря на b; при a = 25 и b = 25 это шифр Атбаш, алфавит, прочитанный задом наперёд.

Как взломать аффинный шифр

Ключей, которые что-либо меняют, всего 311, поэтому самая прямая атака — перебрать их все, что режим полного перебора делает за доли секунды. Трудность в том, чтобы узнать правильный ответ, поэтому инструмент ранжирует каждый результат с помощью сравнения хи-квадрат частот его букв с типичным английским. На предложении или больше правильный ключ оказывается первым; на короткой фразе — может и не оказаться: для одного IHHWVC SWFRCP настоящий ключ (5, 8) занимает четвёртое место, — поэтому просматривайте список, а не доверяйте первой строке.

Криптоаналитики могут справиться лучше с помощью алгебры. Аффинный шифр — это моноалфавитная подстановка: каждая буква всегда превращается в одну и ту же букву, — поэтому частотный анализ подсказывает, какие буквы шифртекста соответствуют E и T, а две такие догадки дают два уравнения. При приведённом выше ключе E (4) становится C (2), а T (19) становится Z (25), так что 4a + b ≡ 2 и 19a + b ≡ 25 (mod 26). Вычитая первое из второго, получаем 15a ≡ 23; умножив на 7 — обратное к 15, — получаем a ≡ 161 ≡ 5, а затем b ≡ 2 − 20 ≡ 8. Две буквы известного открытого текста восстанавливают весь ключ.

Часто задаваемые вопросы

Что такое аффинный шифр?

Шифр подстановки, который превращает номер x каждой буквы в (a·x + b) mod 26, то есть каждая буква умножается на a, а затем сдвигается на b. Ключ — это пара (a, b). Поскольку данная буква всегда превращается в одну и ту же букву шифртекста, шифр моноалфавитный — более внушительно выглядящий родственник шифра Цезаря, и не более трудный для взлома.

Почему a должно быть взаимно простым с 26?

Расшифровка умножает на обратное к a число по модулю 26, а оно существует только тогда, когда у a и 26 нет общих множителей. Если они есть, две разные буквы шифруются в одну и ту же, и сообщение нельзя прочитать обратно однозначно. Это исключает все чётные числа и 13, оставляя 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25.

Как найти обратное по модулю число к a?

Найдите число от 1 до 25, которое при умножении на a даёт остаток 1 при делении на 26. Для a = 7 это 15, потому что 7 × 15 = 105 = 4 × 26 + 1. Случаев всего двенадцать, поэтому быстрее всего прочитать их в таблице выше; для больших модулей обратное напрямую находит расширенный алгоритм Евклида.

Сколько ключей у аффинного шифра?

312 — двенадцать вариантов a на 26 вариантов b. Один из них, a = 1 при b = 0, оставляет текст без изменений, так что реально шифруют 311. Этого достаточно мало, чтобы перебрать все ключи вручную за вечер, а на компьютере — мгновенно.

Является ли шифр Цезаря разновидностью аффинного шифра?

Да. При a = 1 формула превращается в x + b, то есть сдвиг Цезаря на b; ROT13 — это a = 1, b = 13. Атбаш тоже аффинный, с a = 25 и b = 25. Оба входят в 312 ключей, которые перебирает полный перебор.

Надёжен ли аффинный шифр?

Нет. Он поддаётся полному перебору, частотному анализу и даже двум буквам известного открытого текста, как показывает алгебра выше. Это отличная практика в модульной арифметике, но для всего, что действительно важно, нужно современное шифрование.