В криптографии шифр перестановки (также известный как шифр перестановки) — это метод шифрования, который перетасовывает позиции символов ( перестановка ), не изменяя сами символы. Шифры перестановки переупорядочивают единицы открытого текста (обычно символы или группы символов) в соответствии с регулярной системой для получения шифротекста , который является перестановкой открытого текста. Они отличаются от шифров замены , которые не изменяют позиции единиц открытого текста, а вместо этого изменяют сами единицы. Несмотря на разницу между операциями перестановки и замены, они часто объединяются, как в исторических шифрах, таких как шифр ADFGVX , или сложных высококачественных методах шифрования, таких как современный Advanced Encryption Standard (AES).
Обычные тексты можно перестроить в шифротекст с помощью ключа , перемешивая порядок символов, как перетасованные части головоломки . Полученное сообщение трудно расшифровать без ключа, поскольку существует множество способов расположения символов.
Например, открытый текст "THIS IS WIKIPEDIA" может быть зашифрован как "TWDIP SIHII IKASE". Чтобы расшифровать зашифрованное сообщение без ключа, злоумышленник может попытаться угадать возможные слова и фразы, такие как DIATHESIS, DISSIPATE, WIDTH и т. д., но ему потребуется некоторое время, чтобы восстановить открытый текст, поскольку существует множество комбинаций букв и слов. Напротив, кто-то с ключом может легко восстановить сообщение:
Ключ ШИФРА1 4 5 3 2 6 Последовательность (буквы ключей в алфавитном порядке)ЭТО ОТКРЫТЫЙ ТЕКСТВИКИПЕАСВ * * *Шифрованный текст по столбцам: №1 TWD, №2 IP, №3 SI, №4 HII, №5 IKA, №6 SEШифротекст в группах по 5 для удобства чтения: TWDIP СИХИИ ИКАСЕ
На практике такое короткое сообщение с предсказуемым ключевым словом будет почти мгновенно взломано с помощью методов криптоанализа . Шифры перестановки имеют несколько уязвимостей (см. раздел «Обнаружение и криптоанализ» ниже), и небольшие ошибки в процессе шифрования могут сделать весь шифротекст бессмысленным.
Однако при наличии правильных условий — длинных сообщений (например, более 100–200 букв), непредсказуемого содержания, уникальных ключей на сообщение, сильных методов транспозиции и т. д. — угадывание правильных слов может быть вычислительно невозможным без дополнительной информации. В своей книге по дешифровке исторических шифров Элонка Данин и Клаус Шмех описывают двойную столбчатую транспозицию (см. ниже) как «один из лучших известных ручных шифров». [1]
Шифр Rail Fence — это форма транспозиционного шифра, получившая свое название из-за способа кодирования. В шифре rail fence открытый текст пишется сверху вниз и по диагонали на последовательных «рельсах» воображаемого забора, затем поднимается вверх, когда достигает дна. Затем сообщение считывается по строкам. Например, используя три «рельса» и сообщение «WE ARE DISCOVERED FLEE AT ONCE», шифровальщик записывает:
В . . . Э . . . К . . . Р . . . Л . . . Т . . . Э. Э . Р . Д . С . О . Э . Э . Ф . Э . А . О . Ц .. . А . . . И . . . В . . . Д . . . Е . . . Н . .
Затем зачитывает:
WECRL TEERD SOEEF EAOCA IVDEN
(Шифр разбил этот шифротекст на блоки по пять, чтобы избежать ошибок. Это распространенный прием, используемый для того, чтобы сделать шифр более удобным для чтения. Пробелы не связаны с пробелами в открытом тексте и, таким образом, не несут никакой информации об открытом тексте.)
Шифр ограждения следует образцу, похожему на сциталу ( произносится как «SKIT-uhl-ee»), механическую систему создания транспозиционного шифра, использовавшуюся древними греками . Система состояла из цилиндра и ленты, которая была обернута вокруг цилиндра. Сообщение, которое нужно было зашифровать, было написано на свернутой ленте. Буквы исходного сообщения переставлялись, когда лента разматывалась с цилиндра. Однако сообщение было легко расшифровано, когда лента наматывалась на цилиндр того же диаметра, что и шифрующий цилиндр. [2] Используя тот же пример, что и раньше, если цилиндр имеет такой радиус, что только три буквы могут поместиться по его окружности, шифровальщик записывает:
В . . Е . . А . . Р . . Е . . Д . . И . . С . . К. О . . В . . Э . . Р . . Э . . Д . . Ф . . Л . .. . Е . . Е . . А . . Т . . О . . Н . . С . . Е .
В этом примере цилиндр движется горизонтально, а лента обернута вертикально. Следовательно, шифровальщик затем считывает:
WOEEV EAEAR RTEEO DDNIF CSLEC
В маршрутном шифре открытый текст сначала записывается в сетку заданных размеров, затем считывается по шаблону, заданному в ключе. Например, используя тот же открытый текст, который мы использовали для ограды из рельсов :
WRIORFEOEЭЕСВЕЛАНЬADCEDETCX
Ключ может указывать "спираль внутрь, по часовой стрелке, начиная с правого верхнего угла". Это даст зашифрованный текст:
EJXCTEDEC DAEWRIORF EONALEVSE
Маршрутные шифры имеют гораздо больше ключей, чем ограда из рельсов. Фактически, для сообщений разумной длины число возможных ключей потенциально слишком велико, чтобы их можно было перечислить даже с помощью современной техники. Однако не все ключи одинаково хороши. Плохо выбранные маршруты оставят избыточные куски открытого текста или текст просто перевернутым, и это даст криптоаналитикам подсказку относительно маршрутов.
Разновидностью маршрутного шифра был Union Route Cipher, использовавшийся силами Союза во время Гражданской войны в США . Он работал во многом как обычный маршрутный шифр, но переставлял целые слова вместо отдельных букв. Поскольку это оставило бы некоторые высокочувствительные слова открытыми, такие слова сначала скрывались кодом . Шифровщик также может добавлять целые пустые слова, которые часто выбирались, чтобы сделать шифртекст юмористическим. [ необходима цитата ]
В середине XVII века Сэмюэл Морланд представил раннюю форму столбчатой транспозиции. Она получила дальнейшее развитие гораздо позже, став очень популярной в конце XIX века и в XX веке, причем французские военные, японские дипломаты и советские шпионы использовали этот принцип.
При столбчатой транспозиции сообщение записывается в строках фиксированной длины, а затем снова считывается столбец за столбцом, а столбцы выбираются в некотором перемешанном порядке. Как ширина строк, так и перестановка столбцов обычно определяются ключевым словом. Например, ключевое слово ZEBRAS имеет длину 6 (поэтому строки имеют длину 6), а перестановка определяется алфавитным порядком букв в ключевом слове. В этом случае порядок будет "6 3 2 4 1 5".
В обычном столбчатом шифре перестановки все свободные места заполняются нулями; в нерегулярном столбчатом шифре перестановки пробелы остаются пустыми. Наконец, сообщение считывается по столбцам в порядке, указанном ключевым словом. Например, предположим, что мы используем ключевое слово ZEBRAS и сообщение WE ARE DISCOVERED. FLEE AT ONCE . В обычном столбчатом шифре перестановки мы записываем это в сетку следующим образом:
6 3 2 4 1 5ИЗНОСИЛИISCOVEРЕДФЛEATONCEQKJEU
предоставляя пять нулей ( QKJEU ), эти буквы могут быть выбраны случайным образом, поскольку они просто заполняют неполные столбцы и не являются частью сообщения. Затем шифротекст считывается как:
EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE
В нерегулярном случае столбцы не заполняются нулями:
6 3 2 4 1 5ИЗНОСИЛИISCOVEРЕДФЛEATONCЭ
В результате получается следующий шифртекст:
EVLNA CDTES EAROF ODEEC WIREE
Чтобы расшифровать его, получатель должен определить форму сетки шифрования, разделив длину сообщения на длину ключа, чтобы найти количество строк в сетке. Длина последней строки сетки определяется остатком. Ключ записывается над сеткой, а шифротекст записывается в столбцы сетки в порядке, заданном буквами ключа. Открытый текст появляется в строках. Частичная расшифровка приведенного выше шифротекста после записи в первый столбец:
6 3 2 4 1 5. . . . Э .. . . . . В .. . . . Л .. . . . . Н ..
В варианте сообщение блокируется в сегменты, длина которых равна длине ключа, и к каждому сегменту применяется одна и та же перестановка (заданная ключом). Это эквивалентно столбчатой транспозиции, где считывание осуществляется по строкам, а не по столбцам.
Столбчатая транспозиция продолжала использоваться в серьезных целях как компонент более сложных шифров, по крайней мере, до 1950-х годов.
Одноколоночная транспозиция может быть атакована путем угадывания возможных длин столбцов, записи сообщения в его столбцах (но в неправильном порядке, поскольку ключ еще не известен), а затем поиска возможных анаграмм . Таким образом, чтобы сделать его сильнее, часто использовалась двойная транспозиция. Это просто колоночная транспозиция, примененная дважды. Один и тот же ключ может быть использован для обеих транспозиций, или могут быть использованы два разных ключа.
В следующем примере мы используем ключи JANEAUSTEN и AEROPLANES для шифрования следующего открытого текста: « Транспозиционные шифры перемешивают буквы, как кусочки головоломки, создавая неразборчивую структуру».
Цвета показывают, как буквы перемешиваются на каждом шаге транспозиции. В то время как один шаг вызывает лишь незначительную перестановку, второй шаг приводит к значительному эффекту перемешивания, если последняя строка сетки не завершена.
В качестве примера мы можем взять результат нерегулярной столбчатой транспозиции из предыдущего раздела и выполнить второе шифрование с другим ключевым словом, STRIPE , что даст перестановку «564231»:
5 6 4 2 3 1EVLNACДТЕСЕАРОФОДЕЭКВИРЕЭ
Как и прежде, это считывается по столбцам, чтобы получить зашифрованный текст:
CAEEN SOIAE DRLEF WEDRE EVTOC
Если несколько сообщений абсолютно одинаковой длины зашифрованы с использованием одних и тех же ключей, их можно анаграммировать одновременно. Это может привести как к восстановлению сообщений, так и к восстановлению ключей (так что каждое другое сообщение, отправленное с этими ключами, может быть прочитано).
Во время Первой мировой войны немецкие военные использовали двойной столбчатый транспозиционный шифр, редко меняя ключи. Система регулярно раскрывалась французами, называвшими ее Übchi, которые обычно могли быстро находить ключи, как только перехватывали несколько сообщений одинаковой длины, что обычно занимало всего несколько дней. Однако успех французов стал широко известен, и после публикации в Le Matin немцы перешли на новую систему 18 ноября 1914 года. [3]
Во время Второй мировой войны шифр двойной транспозиции использовался голландскими группами Сопротивления , французскими маки и британским Управлением специальных операций (SOE), которое отвечало за управление подпольной деятельностью в Европе. [4] Он также использовался агентами американского Управления стратегических служб [5] и в качестве экстренного шифра для немецкой армии и флота.
До изобретения шифра VIC двойная транспозиция обычно считалась самым сложным шифром, который агент мог надежно использовать в сложных полевых условиях.
Двойной транспозиционный шифр можно рассматривать как одинарную транспозицию с ключом, длина которого равна произведению длин двух ключей. [6]
В конце 2013 года задача двойной транспозиции, которую ее автор считал не поддающейся расшифровке, была решена Джорджем Ласри с помощью подхода «разделяй и властвуй», при котором каждая транспозиция подвергалась индивидуальной атаке. [7]
Вариант формы столбчатой транспозиции, предложенный Эмилем Виктором Теодором Мышковским в 1902 году, требует ключевого слова с повторяющимися буквами. В обычной практике последующие появления ключевой буквы рассматриваются так, как если бы следующая буква в алфавитном порядке, например, ключевое слово TOMATO, давало числовую ключевую строку "532164".
В транспозиции Мышковского повторяющиеся ключевые буквы нумеруются одинаково, TOMATO дает ключевую строку «432143».
4 3 2 1 4 3ИЗНОСИЛИISCOVEРЕДФЛEATONCЭ
Столбцы открытого текста с уникальными номерами транскрибируются сверху вниз; столбцы с повторяющимися номерами транскрибируются слева направо:
ROFOA CDTED SEEEA CWEIV RLENE
Нарушенный транспозиционный шифр [8] еще больше усложняет схему транспозиции нерегулярным заполнением строк матрицы, т. е. некоторыми пробелами, намеренно оставленными пустыми (или зачерненными, как в Rasterschlüssel 44 ), или заполненными позднее либо другой частью открытого текста, либо случайными буквами. [8]
Этот метод (приписываемый генералу Луиджи Сакко [9] ) начинает новую строку, как только открытый текст достигает столбца, ключевой номер которого равен текущему номеру строки. Это приводит к нерегулярным длинам строк. Например,
FOREVERJIGSAW < Ключ4 8 9 2 12 3 10 7 6 5 11 1 13 Пробелы после номера:СЛОЖНЫЙТЕСТ * 1ГЕТР * * * * * * * * * 2АНСПОС * * * * * * * 3Я * * * * * * * * * * * * * 4ТИОНПАТТЕР * * * 5NLIKEACOM * * * * 6Б _ _ _ _ _ _ _ * * * * * 7
Затем столбцы удаляются в соответствии с обычной транспозицией столбцов: TPRPN, KISAA, CHAIT, NBERT, EMATO и т. д.
Другим простым вариантом [10] было бы использование пароля, который размещает пробелы в соответствии с его числовой последовательностью. Например, «SECRET» будет декодироваться в последовательность «5,2,1,4,3,6» и вычеркивать 5-е поле матрицы, затем снова считать и вычеркивать второе поле и т. д. Следующий пример будет матрицей, настроенной для столбчатой транспозиции с столбчатым ключом «CRYPTO» и заполненной вычеркнутыми полями в соответствии с ключом нарушения «SECRET» (отмеченным звездочкой), после чего сообщение «нас обнаружили, немедленно бегите» помещается в оставшиеся пробелы. Результирующий шифртекст (столбцы, прочитанные в соответствии с ключом транспозиции) будет «WCEEO ERET RIVFC EODN SELE ADA».
КРИПТО1 4 6 3 5 2МЫ* * ДИС *КРЫШКАЭД * ФЛЕЕСТЬОДИН РАЗ *
Другая форма шифра перестановки использует решетки или физические маски с вырезами. Это может производить крайне нерегулярную перестановку в течение периода, указанного размером решетки, но требует от корреспондентов хранить в секрете физический ключ. Решетки были впервые предложены в 1550 году и все еще использовались военными в течение первых нескольких месяцев Первой мировой войны.
Поскольку транспозиция не влияет на частоту отдельных символов, простая транспозиция может быть легко обнаружена криптоаналитиком путем подсчета частот. Если шифртекст демонстрирует распределение частот, очень похожее на распределение открытого текста, скорее всего, это транспозиция.
В целом, методы транспозиции уязвимы для анаграммирования — перемещения фрагментов шифртекста, затем поиска разделов, которые выглядят как анаграммы слов на английском или любом другом языке, на котором был написан открытый текст, и решения анаграмм. После того, как такие анаграммы найдены, они раскрывают информацию о шаблоне транспозиции и, следовательно, могут быть расширены. Более простые транспозиции часто страдают от того свойства, что ключи, очень близкие к правильному ключу, будут раскрывать длинные разделы разборчивого открытого текста, перемежаемые тарабарщиной. Следовательно, такие шифры могут быть уязвимы для алгоритмов оптимального поиска, таких как генетические алгоритмы [11] и алгоритмы восхождения на вершину . [12] [13]
Существует несколько конкретных методов атаки на сообщения, закодированные с помощью транспозиционного шифра. К ним относятся:
Третий метод был разработан в 1878 году математиком Эдвардом С. Холденом и журналистами New-York Tribune Джоном Р. Г. Хассардом и Уильямом М. Гросвенором, которым удалось расшифровать телеграммы между Демократической партией и ее агентами в южных штатах во время президентских выборов 1876 года и таким образом доказать факты подкупа голосов , повлиявшие на выборы в Конгресс 1878-1879 годов . [14]
Подробное описание криптоанализа немецкого транспозиционного шифра можно найти в главе 7 книги Герберта Ярдли «Американская черная палата».
Шифр, используемый убийцей Зодиаком , называемый «Z-340», организованный в треугольные секции с заменой букв на 63 различных символа и диагональной перестановкой «ход коня», оставался неразгаданным более 51 года, пока международная группа частных лиц не взломала его 5 декабря 2020 года, используя специализированное программное обеспечение. [15]
Транспозиция часто сочетается с другими методами, такими как методы оценки. Например, простой шифр замены в сочетании с колоночной транспозицией позволяет избежать слабости обоих. Замена часто встречающихся символов шифртекста на часто встречающиеся буквы открытого текста не раскрывает фрагменты открытого текста из-за транспозиции. Анаграмма транспозиции не работает из-за замены. Этот метод особенно эффективен, если сочетать его с фракционированием (см. ниже). Недостатком является то, что такие шифры значительно более трудоемки и подвержены ошибкам, чем более простые шифры.
Транспозиция особенно эффективна при использовании с дроблением, то есть предварительным этапом, который делит каждый символ открытого текста на два или более символов шифртекста. Например, алфавит открытого текста может быть записан в сетке, а каждая буква в сообщении заменена ее координатами (см. Квадрат Полибия и Шахматная доска с разбросом ). [16] Другой метод дробления — просто преобразовать сообщение в код Морзе с символом для пробелов, а также точек и тире. [17]
Когда такое фракционированное сообщение транспонируется, компоненты отдельных букв становятся широко разделенными в сообщении, таким образом достигая диффузии Клода Э. Шеннона . Примерами шифров, которые сочетают фракционирование и транспозицию, являются двураздельный шифр , трехраздельный шифр , шифр ADFGVX и шифр VIC .
Другим вариантом было бы заменить каждую букву ее двоичным представлением, транспонировать ее, а затем преобразовать новую двоичную строку в соответствующие символы ASCII. Многократное повторение процесса скремблирования двоичной строки перед ее преобразованием в символы ASCII, вероятно, усложнит ее взлом. Многие современные блочные шифры используют более сложные формы транспозиции, связанные с этой простой идеей.