Автоключевой шифр

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

История

Автоключевые шифры известны с XVI века. Первое описание такого шифра принадлежит итальянскому математику и криптографу Джованни Баттисте делла Порта (1535–1615). В 1563 году он опубликовал трактат «De Furtivis Literarum Notis», где предложил метод, при котором ключ шифрования формируется из самого сообщения. Порта использовал начальный ключ (обычно одно слово или фразу), а затем для каждого следующего символа шифротекста ключом служил предыдущий символ открытого текста.

В 1586 году французский дипломат и криптограф Блез де Виженер (1523–1596) в своей книге «Traicté des Chiffres» описал более совершенный вариант — шифр Виженера с автоключом. Этот метод, известный как «шифр Виженера с автоключом», использовал начальный ключ, а затем для каждого последующего символа ключом служил предыдущий символ открытого текста (или шифротекста). Шифр Виженера с автоключом считался невзламываемым до середины XIX века, пока не был разработан метод криптоанализа, основанный на поиске уязвимостей в начальном ключе.

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

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

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

Автоключ по открытому тексту

В этом варианте начальный ключ (обычно короткое слово или фраза) используется для шифрования первых символов сообщения. Затем каждый следующий символ ключа вычисляется как предыдущий символ открытого текста. Формально:

• Пусть \( K_0 \) — начальный ключ (длиной \( n \) символов).
• Для \( i \geq n \): \( K_i = P_{i-n} \), где \( P_j \) — j-й символ открытого текста.

Шифрование выполняется по формуле: \( C_i = (P_i + K_i) \mod m \), где \( m \) — мощность алфавита (например, 26 для латиницы).

Автоключ по шифротексту

В этом варианте ключ для следующего символа вычисляется из предыдущего символа шифротекста:

• \( K_0 \) — начальный ключ.
• Для \( i \geq n \): \( K_i = C_{i-n} \).

Шифрование: \( C_i = (P_i + K_i) \mod m \).

Пример

Рассмотрим пример шифрования на русском языке (алфавит из 33 букв, пробел не учитывается). Пусть начальный ключ — «КЛЮЧ», открытый текст — «ПРИВЕТ». Используем автоключ по открытому тексту. Сопоставим буквы числам: А=0, Б=1, ..., Я=32.

1. Начальный ключ: К=11, Л=12, Ю=31, Ч=23.
2. Открытый текст: П=16, Р=17, И=9, В=2, Е=5, Т=19.
3. Шифрование:

• C1 = (16 + 11) mod 33 = 27 → Ъ
• C2 = (17 + 12) mod 33 = 29 → Ы
• C3 = (9 + 31) mod 33 = 7 → З
• C4 = (2 + 23) mod 33 = 25 → Х
• Для C5 ключ = P1 = 16 → C5 = (5 + 16) mod 33 = 21 → Ф
• Для C6 ключ = P2 = 17 → C6 = (19 + 17) mod 33 = 3 → Г

1. Шифротекст: ЪЫЗХФГ.

Расшифровка выполняется аналогично, с использованием того же начального ключа.

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

Автоключевые шифры можно классифицировать по нескольким признакам:

• По типу автоключа:
• С автоключом по открытому тексту (plaintext autokey).
• С автоключом по шифротексту (ciphertext autokey).
• По способу генерации ключа:
• Линейные (ключ вычисляется простым сдвигом).
• Нелинейные (ключ вычисляется с использованием дополнительных преобразований, например, XOR с константой).
• По алфавиту:
• Буквенные (латиница, кириллица).
• Цифровые (двоичные, десятичные).
• По методу шифрования:
• Аддитивные (сложение по модулю).
• Мультипликативные (умножение по модулю).
• Комбинированные (например, шифр Виженера с автоключом).

Устройство и характеристики

Автоключевой шифр как алгоритм состоит из следующих компонентов:

• Начальный ключ (затравка): короткая последовательность символов, известная отправителю и получателю. Длина начального ключа обычно составляет от 1 до 10 символов. Чем длиннее начальный ключ, тем выше стойкость шифра.
• Функция генерации ключа: правило, по которому из предыдущих символов открытого текста или шифротекста вычисляется следующий ключевой символ. В простейшем случае это просто копирование предыдущего символа.
• Функция шифрования: операция, преобразующая символ открытого текста и символ ключа в символ шифротекста. Чаще всего используется сложение по модулю размера алфавита.
• Функция расшифрования: обратная операция, восстанавливающая открытый текст из шифротекста с использованием того же ключа.

Характеристики:

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

Применение

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

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

Критика

Основные недостатки автоключевых шифров:

• Уязвимость к атакам на начальный ключ: если злоумышленник перехватит или угадает начальный ключ (например, через социальную инженерию или анализ трафика), всё сообщение будет раскрыто. Длина начального ключа обычно мала, что делает его перебор возможным при современной вычислительной мощности.
• Распространение ошибок: в варианте с автоключом по шифротексту одна ошибка при передаче делает нечитаемым всё последующее сообщение.
• Отсутствие аутентификации: автоключевые шифры не обеспечивают проверку целостности сообщения, что позволяет злоумышленнику модифицировать шифротекст без обнаружения.
• Низкая стойкость к известным атакам: при наличии достаточного количества известного открытого текста (например, стандартных фраз в переписке) можно восстановить весь ключ.

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

• Шифр Виженера с автоключом был описан в 1586 году, но его криптоанализ был опубликован только в 1854 году британским математиком Чарльзом Бэббиджем, который также разработал метод взлома шифра Виженера без автоключа.
• В 1920-х годах американский криптограф Уильям Фридман использовал автоключевые шифры в своей работе по дешифровке дипломатических сообщений.
• Принцип автоключа лёг в основу некоторых ранних версий шифровальной машины «Энигма», где начальная установка роторов играла роль начального ключа, а дальнейшее вращение роторов зависело от предыдущих символов.

Источники

• Книга: «Криптография. Введение в криптографию» под редакцией В.В. Ященко, 2012.
• Статья: «Autokey cipher» в энциклопедии «Encyclopedia of Cryptography and Security», 2011.
• Трактат: Блез де Виженер, «Traicté des Chiffres», 1586.
• Лекции: «История криптографии» МГУ, курс лекций, 2020.