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

Аффинный шифр — это частный случай шифра простой замены, в котором каждая буква открытого текста преобразуется в букву шифротекста с помощью линейной арифметической операции. Метод основан на использовании двух ключей: коэффициента умножения и сдвига, что делает его обобщением шифра Цезаря.

Принцип работы

Аффинный шифр относится к классу моноалфавитных шифров подстановки. В его основе лежит математическая функция, которая ставит в соответствие каждой букве алфавита другую букву по формуле:

\[ E(x) = (a \cdot x + b) \bmod m \]

где:

• \(x\) — числовой эквивалент шифруемой буквы (обычно A=0, B=1, ..., Z=25);
• \(a\) — мультипликативный ключ (коэффициент умножения);
• \(b\) — аддитивный ключ (сдвиг);
• \(m\) — размер алфавита (для латиницы — 26, для кириллицы — 33 или 32);
• \(E(x)\) — числовой эквивалент буквы шифротекста.

Для расшифрования используется обратная функция:

\[ D(y) = a^{-1} \cdot (y - b) \bmod m \]

где \(a^{-1}\) — мультипликативное обратное числа \(a\) по модулю \(m\), то есть такое число, что \(a \cdot a^{-1} \equiv 1 \pmod{m}\).

Условия обратимости

Для того чтобы шифрование было обратимым (то есть каждой букве шифротекста соответствовала ровно одна буква открытого текста), необходимо выполнение двух условий:

1. Взаимная простота \(a\) и \(m\): \(\gcd(a, m) = 1\). Если это условие не выполняется, шифр становится вырожденным — разные буквы открытого текста могут отображаться в одну и ту же букву шифротекста, что делает расшифрование неоднозначным.
2. Ключ \(b\) может быть любым целым числом от 0 до \(m-1\).

Ключевое пространство

Размер ключевого пространства аффинного шифра определяется количеством возможных пар \((a, b)\). Для алфавита из \(m\) букв:

• Количество возможных значений \(a\) равно \(\varphi(m)\) — функции Эйлера от \(m\) (количество чисел, меньших \(m\) и взаимно простых с \(m\)).
• Количество возможных значений \(b\) равно \(m\).

Таким образом, общее число ключей составляет \(\varphi(m) \cdot m\).

Для латинского алфавита (\(m=26\)):

• \(\varphi(26) = 12\) (это числа: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25).
• Общее число ключей: \(12 \times 26 = 312\).

Для русского алфавита (\(m=33\)):

• \(\varphi(33) = 20\) (все числа, не кратные 3 и 11).
• Общее число ключей: \(20 \times 33 = 660\).

Для сравнения: шифр Цезаря (частный случай аффинного шифра при \(a=1\)) имеет всего 26 (или 33) возможных ключей.

История

Аффинный шифр является одним из простейших примеров использования модульной арифметики в криптографии. В отличие от шифра Цезаря, который был известен ещё в Древнем Риме, аффинный шифр как формальная математическая конструкция появился значительно позже — в эпоху развития алгебры и теории чисел. Его систематическое описание встречается в учебных пособиях по криптографии XX века, когда математические методы начали активно применяться для анализа и синтеза шифров.

В древности и средневековье шифры, аналогичные аффинному, не использовались широко, поскольку для их применения требовалось понимание арифметики по модулю и понятия взаимной простоты чисел. Однако отдельные случаи линейных преобразований букв встречаются в некоторых исторических криптосистемах, например, в шифре «Атбаш» (древнееврейский шифр подстановки, основанный на обратном порядке алфавита), который можно рассматривать как частный случай аффинного шифра с коэффициентами \(a = -1\) и \(b = -1\) по модулю 22.

Классификация и варианты

Частные случаи

1. Шифр Цезаря: \(a = 1\). Шифрование сводится к простому циклическому сдвигу на \(b\) позиций.
2. Шифр умножения (мультипликативный шифр): \(b = 0\). Шифрование осуществляется только умножением на \(a\). При \(a = -1\) (или \(a = m-1\)) получается шифр, обращающий порядок алфавита.
3. Шифр Атбаш: для латинского алфавита \(a = -1\), \(b = -1\) (по модулю 26 это \(a = 25\), \(b = 25\)).

Обобщения

Аффинный шифр может быть обобщён на случай, когда вместо одной буквы шифруется блок букв. Такие шифры называются аффинными блочными шифрами и используют матричные операции вместо скалярных. Например, шифр Хилла является линейным блочным шифром, где преобразование задаётся матрицей.

Криптоанализ

Аффинный шифр обладает слабой криптостойкостью и легко взламывается как с помощью атаки по открытому тексту, так и с помощью частотного анализа.

Атака по открытому тексту

Если криптоаналитику известны две пары «открытый текст — шифротекст» (или две буквы открытого текста и соответствующие им буквы шифротекста), он может составить систему из двух линейных уравнений по модулю \(m\) и найти ключи \(a\) и \(b\). Для этого достаточно знать, какие числовые значения соответствуют любым двум различным буквам открытого текста и шифротекста.

Частотный анализ

Поскольку аффинный шифр является моноалфавитным, он сохраняет частотные характеристики исходного языка. Наиболее часто встречающаяся буква в шифротексте (например, «О» в русском или «E» в английском) с высокой вероятностью соответствует наиболее частой букве открытого текста. Зная одну такую пару, можно частично восстановить ключ, а затем проверить его на других буквах.

Полный перебор

Из-за малого размера ключевого пространства (312 для латиницы, 660 для кириллицы) аффинный шифр может быть взломан простым перебором всех возможных ключей. Для современных компьютеров это тривиальная задача, выполняемая за доли секунды.

Применение

В настоящее время аффинный шифр не используется для защиты конфиденциальной информации из-за крайне низкой криптостойкости. Однако он применяется в следующих областях:

• Образование: изучение основ модульной арифметики, криптографии и комбинаторики. Аффинный шифр служит наглядным примером для демонстрации принципов шифрования, ключевого пространства и криптоанализа.
• Математические олимпиады и задачи: часто встречается в задачах на теорию чисел и модульную арифметику.
• Хобби и головоломки: используется в несложных шифровках, квестах и играх.
• Компьютерные науки: пример для реализации простых алгоритмов шифрования на языках программирования.

Интересные факты

• В аффинном шифре ключ \(a = 1\) даёт шифр Цезаря, а ключ \(a = -1\) (или \(a = m-1\)) — шифр, обращающий порядок алфавита (например, A → Z, B → Y и т. д.).
• Если \(a = 0\), то шифр вырождается: все буквы открытого текста шифруются в одну и ту же букву (\(b \bmod m\)), что делает расшифрование невозможным.
• Аффинный шифр является частным случаем более общего класса — линейных конгруэнтных генераторов, используемых в псевдослучайных последовательностях.
• В русском языке при использовании 33-буквенного алфавита (с буквой «Ё») количество возможных ключей \(a\) равно \(\varphi(33) = 20\), а общее число ключей — 660.
• Аффинный шифр может быть использован для шифрования не только букв, но и любых символов, представленных числами по модулю \(m\), например, цифр или знаков препинания.

Источники

• Криптография и теория чисел. — О. Н. Василенко, 2003.
• Handbook of Applied Cryptography. — A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, 1996.
• Elementary Cryptanalysis: A Mathematical Approach. — A. Sinkov, 1966.
• Шифры простой замены и их криптоанализ. — Учебное пособие по криптографии, МГУ, 2010.