Шифр одноалфавитной замены

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

История

Шифры одноалфавитной замены являются одними из древнейших криптографических методов. Их использование прослеживается с античных времён.

Древний мир

Одним из первых известных примеров является шифр Цезаря, применявшийся, по свидетельству древнеримского историка Светония, Гаем Юлием Цезарем для переписки с военачальниками. В этом шифре каждая буква открытого текста заменялась на букву, отстоящую от неё на фиксированное число позиций в алфавите (обычно на 3). Шифр Цезаря является частным случаем одноалфавитной замены с циклическим сдвигом.

В Древней Греции использовался шифр «Скитала» (или «Сцитала»), который, хотя и относился к перестановочным шифрам, также мог быть реализован как простая подстановка при определённой записи. Однако именно подстановочные шифры, такие как шифр Цезаря, получили наибольшее распространение в античности.

Средневековье и эпоха Возрождения

В средневековой Европе одноалфавитные шифры активно применялись в дипломатической и военной переписке. Известны так называемые «шифры номенклаторов», где для замены использовались не только буквы, но и целые слова или слоги. Однако с развитием частотного анализа, впервые описанного арабским учёным Аль-Кинди в IX веке в трактате «О расшифровке криптографических сообщений», одноалфавитные шифры стали уязвимыми. Аль-Кинди предложил метод взлома, основанный на подсчёте частоты встречаемости символов в шифротексте и сравнении её с частотой букв в языке открытого текста.

Новое время

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

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

Шифры одноалфавитной замены можно классифицировать по способу построения алфавита подстановки.

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

• Простая подстановка (простой шифр замены): Каждому символу открытого текста ставится в соответствие ровно один символ шифротекста. Отображение является биекцией (взаимно однозначным соответствием). Пример: шифр Цезаря.
• Моноалфавитная подстановка с ключом: Алфавит подстановки строится на основе ключевого слова. Сначала записывается ключевое слово без повторяющихся букв, затем в алфавитном порядке дописываются остальные буквы алфавита. Например, для ключа «КРИПТОГРАФИЯ» алфавит подстановки может выглядеть как «КРИПТОГАФЯБВГДЕЖЗИЙЛМНСУФХЦЧШЩЪЫЬЭЮЯ» (с учётом удаления повторов и порядка букв).

По типу заменяемых элементов

• Буквенные шифры: Заменяются отдельные буквы алфавита. Наиболее распространённый тип.
• Цифровые шифры: Буквы заменяются на цифры или числовые коды. Например, шифр «А1Б2В3» или система, где каждая буква кодируется двузначным числом.
• Символьные шифры: Замена на произвольные символы (иероглифы, знаки пунктуации, специальные символы). Пример — шифр «Атбаш», где буквы заменяются на симметричные им в алфавите (А→Я, Б→Ю и т.д.).

По способу задания отображения

• Табличные шифры: Отображение задаётся в виде таблицы соответствия. Например, таблица подстановки для шифра Цезаря со сдвигом 3: А→Г, Б→Д, В→Е и т.д.
• Формульные шифры: Отображение задаётся математической формулой. Для шифра Цезаря: \( E(x) = (x + k) \mod n \), где \( x \) — номер буквы в алфавите, \( k \) — ключ (сдвиг), \( n \) — мощность алфавита.

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

Шифр одноалфавитной замены состоит из трёх основных компонентов:

1. Алфавит открытого текста: Множество символов, которые могут встречаться в исходном сообщении (например, буквы русского алфавита, цифры, знаки препинания).
2. Алфавит шифротекста: Множество символов, в которые преобразуются символы открытого текста. Обычно имеет ту же мощность, что и алфавит открытого текста.
3. Правило подстановки (ключ): Биективное отображение \( f: A \rightarrow B \), где \( A \) — алфавит открытого текста, \( B \) — алфавит шифротекста. Ключом может быть как само отображение (например, таблица), так и параметр (например, величина сдвига).

Процесс шифрования: для каждого символа \( a \) открытого текста находится соответствующий ему символ \( b = f(a) \) и записывается в шифротекст. Дешифрование производится обратным отображением \( f^{-1} \).

Пример шифрования

Пусть используется русский алфавит (33 буквы) и шифр Цезаря со сдвигом 3. Открытый текст: «ПРИВЕТ». Преобразование:

• П → С (позиция 17 → 17+3=20, буква «С»)
• Р → У (18 → 21)
• И → К (10 → 13)
• В → Е (3 → 6)
• Е → З (6 → 9)
• Т → Х (20 → 23)

Шифротекст: «СУКЕЗХ».

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

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

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

Этот метод основан на том, что в любом естественном языке частоты появления букв различны и подчиняются определённым статистическим закономерностям. Для русского языка наиболее частые буквы — «О», «Е», «А», «И», «Н», «Т», «С». Аналитик подсчитывает частоту каждого символа в шифротексте и сопоставляет её с известными частотами букв языка. Наиболее частый символ шифротекста, скорее всего, соответствует самой частой букве открытого текста («О» или «Е»). После установления нескольких соответствий можно восстановить часть открытого текста и уточнить ключ.

Анализ биграмм и триграмм

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

Атака по известному открытому тексту

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

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

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

Применение

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

• Обучающие цели: Используются в курсах криптографии для демонстрации принципов шифрования и методов частотного анализа.
• Головоломки и развлечения: Шифры замены часто встречаются в кроссвордах, квестах, настольных играх и литературных произведениях (например, в «Золотом жуке» Э.А. По).
• Скрытие информации от случайного наблюдателя: В ситуациях, где не требуется высокая стойкость, например, для записи личных заметок или паролей в простом виде.
• Компьютерные игры: В некоторых играх (например, в жанре point-and-click) используются простые шифры для загадок и квестов.
• Исторические исследования: При изучении древних рукописей и шифровок, где одноалфавитная замена была основным методом.

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

• Шифр Цезаря, несмотря на свою простоту, использовался вплоть до XX века. Например, в 1915 году российская армия применяла его для шифрования некоторых полевых сообщений, что было раскрыто немецкими криптоаналитиками.
• В 1990-х годах шифр одноалфавитной замены использовался в некоторых моделях автомобильных сигнализаций для кодирования радиосигналов, что делало их уязвимыми для перехвата.
• Самый длинный известный шифротекст, взломанный частотным анализом, — это «Шифр Дорабеллы» (XVI век), содержащий около 600 символов.
• В современной криптографии одноалфавитная замена используется как составная часть более сложных алгоритмов, например, в шифре AES (в виде S-блоков), но уже не как самостоятельный метод.

Критика и ограничения

Основной недостаток одноалфавитных шифров — отсутствие стойкости к статистическому анализу. Поскольку каждый символ открытого текста всегда заменяется одним и тем же символом шифротекста, частотные характеристики языка сохраняются. Это позволяет взломать шифр даже при относительно коротких сообщениях (от 50–100 символов). Кроме того, одноалфавитные шифры не защищают от атак по известному или выбранному открытому тексту.

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

Источники

• Криптография: от древности до наших дней. — М.: Наука, 2003.
• Сингх С. Книга шифров: Тайная история шифров и их расшифровки. — М.: АСТ, 2007.
• Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черёмушкин А.В. Основы криптографии. — М.: Гелиос АРВ, 2002.
• Шнайер Б. Прикладная криптография. — М.: Триумф, 2002.
• Материалы лекций по криптографии МГУ им. М.В. Ломоносова, 2020.