Криптография

Шифры перестановки

В марте 1918 немецкий шифр ADFGVX был взломан французским лейтенантом Жоржем Пенвеном за несколько дней до последнего крупного наступления Германии. Шифр сочетал замену с columnar transposition - Пенвен восстановил ключ именно через биграммный анализ столбцов. Через несколько недель немцы добавили вторую перестановку (ADFGVX стал ADFGX) - и взлом занял уже недели. Разница в одном слое.

**AES (Advanced Encryption Standard):** каждый раунд = SubBytes (замена) + ShiftRows/MixColumns (перестановка/диффузия) - прямое наследие SPN
**Агенты SOE:** британские агенты во Франции 1940-1944 использовали Double Transposition для связи с Лондоном
**Шифровальные машины:** Hagelin M-209, используемая армией США, реализовывала именно комбинацию замены и перестановки механически

Rail Fence шифр

Железнодорожный забор - именно так выглядит этот шифр при записи. Текст «зигзагом» записывается на нескольких «рельсах», а потом рельсы читаются по очереди. Буквы не меняются - только их порядок.

**Стойкость Rail Fence:** очень низкая. Количество рельсов - единственный ключ. При длине текста N максимум N-1 вариантов ключа. Частотный анализ отдельных рельсов тоже помогает взломщику.

Текст 'HELLO' шифруется Rail Fence на 2 рельсах. Каков шифртекст?

Columnar Transposition

Во время Первой мировой войны немецкий шифр ADFGVX использовал столбцовую перестановку как второй слой. Идея: записать текст в прямоугольник строка за строкой, затем переставить столбцы по ключевому слову и читать по столбцам.

**Атака на Columnar:** зная длину ключа (можно угадать по факторизации длины шифртекста), пробуем перестановки столбцов и ищем читаемые диграммы. При ключе длины 6 и ожидаемом языке - реально за несколько минут вручную.

Текст 'ABCDEF' с ключом 'BA' (2 столбца). Порядок столбцов по ключу?

Double Transposition

В 1916-1918 годах британская разведка взламывала немецкие шифры достаточно быстро. Ответом стал Double Transposition - применить Columnar Transposition дважды, с разными ключами. Эта схема использовалась союзными агентами SOE во Второй мировой до замены на one-time pad.

**Почему двойная перестановка намного сильнее одиночной?** Одиночная перестановка сохраняет все символы на одинаковом расстоянии по столбцам - опытный взломщик может восстановить столбцы через анализ биграмм. После второй перестановки эти паттерны разрушаются: столбцы первого шага перемешиваются снова.

**Атака «coincidence»:** двойная перестановка уязвима к атаке на основе индекса совпадений, если длины ключей известны или угаданы. Но сложность значительно выше, чем у одиночной перестановки.

Double Transposition применяет Columnar Transposition дважды. Что это даёт по сравнению с одиночной перестановкой?

Комбинирование замены и перестановки

Замена (substitution) и перестановка (transposition) - два ортогональных инструмента. Замена скрывает, *что* за символы. Перестановка скрывает, *где* они находятся. По отдельности каждый уязвим. Вместе они образуют основу всей современной симметричной криптографии - AES применяет SubBytes (замену) и ShiftRows/MixColumns (перестановку/диффузию) в каждом раунде.

**Теорема Шеннона (1949):** идеальный шифр должен обладать confusion (непрозрачная связь шифртекста и ключа) и diffusion (каждый бит открытого текста влияет на многие биты шифртекста). Замена даёт confusion, перестановка - diffusion. AES реализует оба принципа через SP-сеть.

Перестановка бесполезна сама по себе - она не меняет буквы, значит частотный анализ всё равно сработает

Верно, одиночная перестановка уязвима к частотному анализу по символам. Но перестановка разрушает биграммные и триграммные статистики - именно это нужно как второй слой после замены

Замена скрывает частоту отдельных символов. Перестановка разрушает позиционные паттерны. Вместе они дают то, что Шеннон назвал confusion + diffusion - и это фундамент AES.

Что обеспечивает 'diffusion' в современных блочных шифрах?