Полиграммная замена

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

История

Полиграммная замена известна с древности. Первые упоминания о замене групп символов встречаются в криптографических трактатах арабских учёных IX–X веков. Однако систематическое развитие этот метод получил в эпоху Возрождения.

Шифр Плейфера

В 1854 году английский физик Чарльз Уитстон предложил шифр, который стал известен как шифр Плейфера (по имени лорда Лайона Плейфера, популяризировавшего его). Этот шифр использует биграммную замену: открытый текст разбивается на пары букв, которые затем заменяются на другие пары с помощью квадратной таблицы (обычно 5×5, где буквы I и J объединяются). Шифр Плейфера применялся британской армией в Первую мировую войну и оставался в употреблении до середины XX века.

Шифр Виженера

Хотя шифр Виженера (опубликован в 1586 году) часто относят к полиалфавитным шифрам, он также может рассматриваться как разновидность полиграммной замены, поскольку каждый символ шифруется с помощью своего алфавита, определяемого ключевым словом. В отличие от простой замены, где один символ всегда заменяется одним и тем же, здесь один и тот же символ открытого текста может быть зашифрован по-разному в зависимости от позиции. Это делает шифр более стойким к частотному анализу.

XX век

В XX веке полиграммная замена использовалась в механических шифровальных машинах (например, «Энигма»), где вращающиеся роторы реализовывали сложную полиалфавитную замену. С появлением электронных вычислительных машин полиграммная замена уступила место блочным шифрам (например, DES, AES), которые, по сути, являются её современной реализацией, но оперируют битами и байтами, а не буквами.

Классификация

Полиграммные замены можно классифицировать по нескольким признакам:

По размеру полиграммы

• Биграммная замена — шифрование парами символов (например, шифр Плейфера).
• Триграммная замена — шифрование тройками символов (используется реже, так как требует больших таблиц).
• N-граммная замена — общий случай, где N — длина блока.

По способу формирования алфавитов

• Табличная замена — используется фиксированная таблица (например, квадрат Полибия).
• Ключевая замена — алфавиты формируются на основе ключевого слова (шифр Виженера).
• Матричная замена — преобразование выполняется с помощью умножения матриц (например, шифр Хилла).

По типу преобразования

• Подстановочная замена — каждый блок заменяется на другой блок из того же алфавита.
• Перестановочная замена — символы внутри блока переставляются, но не заменяются (строго говоря, это не замена, а перестановка, однако часто комбинируется с заменой).

Устройство и принцип работы

Общий алгоритм

1. Разбиение текста на блоки (полиграммы) фиксированной длины. Если длина текста не кратна длине блока, добавляются символы-заполнители (например, «X»).
2. Преобразование каждого блока в соответствии с правилом замены. Правило может быть задано таблицей, ключом или математической формулой.
3. Сборка шифротекста из преобразованных блоков.

Пример: шифр Плейфера

• Используется таблица 5×5, заполненная буквами алфавита (без «J»).
• Открытый текст разбивается на пары. Если в паре две одинаковые буквы, между ними вставляется «X».
• Каждая пара заменяется по правилам:
• Если буквы в одной строке — каждая заменяется на следующую справа (с циклическим переносом).
• Если в одном столбце — каждая заменяется на следующую снизу.
• Иначе — образуется прямоугольник, и буквы заменяются на противоположные по углам.

Пример: шифр Хилла

• Открытый текст представляется в виде вектора чисел (например, A=0, B=1, …, Z=25).
• Вектор умножается на обратимую матрицу (ключ) по модулю 26.
• Полученный вектор преобразуется обратно в буквы.

Применение

Историческое

• Военная связь — шифры Плейфера и Виженера использовались армиями многих стран до середины XX века.
• Дипломатическая переписка — полиграммная замена применялась для защиты секретных сообщений.

Современное

• Криптография — принципы полиграммной замены лежат в основе блочных шифров (AES, DES, ГОСТ 28147-89). В них блоки фиксированной длины (например, 128 бит) преобразуются с помощью ключа.
• Хеширование — некоторые хеш-функции используют полиграммные замены для перемешивания данных.
• Стеганография — замена символов в тексте может использоваться для скрытия сообщений.

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

Полиграммная замена более устойчива к частотному анализу, чем моноалфавитная, поскольку частота появления отдельных символов маскируется. Однако она уязвима для:

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

Для шифра Плейфера существует эффективный метод криптоанализа, основанный на поиске «шаблонов» в биграммах. Шифр Виженера взламывается с помощью теста Касиски (поиск повторяющихся последовательностей) или индекса совпадений.

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

• Шифр Плейфера был назван в честь лорда Плейфера, который активно пропагандировал его, хотя фактическим автором был Чарльз Уитстон.
• В 1914 году британское Адмиралтейство использовало шифр Плейфера для связи с экспедиционными силами. Немецкие криптоаналитики смогли его взломать, но не сразу.
• Шифр Хилла, предложенный в 1929 году, был одним из первых шифров, использующих линейную алгебру. Он оставался нераскрытым до появления компьютеров.
• В современных блочных шифрах (например, AES) полиграммная замена реализуется через S-блоки (substitution boxes), которые заменяют байты или группы битов.

Критика

Полиграммная замена, особенно в классических вариантах, имеет ряд недостатков:

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

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

Источники

1. Кан, Дэвид. «Взломщики кодов: история тайной связи». — М.: Центрполиграф, 2000.
2. Шнайер, Брюс. «Прикладная криптография». — М.: Триумф, 2002.
3. Сингх, Саймон. «Книга шифров: тайная история шифров и их расшифровки». — М.: АСТ, 2007.
4. ГОСТ 28147-89. «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования».
5. «История криптографии: от древности до наших дней». — Энциклопедия криптографии, под ред. В. И. Нечаева. — М.: Наука, 2010.