В криптографии транспозиционный шифр (также известный как шифр перестановки) — это метод шифрования, который шифрует позиции символов ( транспонирование ) без изменения самих символов. Шифры транспозиции переупорядочивают единицы открытого текста (обычно символы или группы символов) в соответствии с обычной системой для создания зашифрованного текста , который представляет собой перестановку открытого текста. Они отличаются от шифров замены , которые не меняют положение единиц открытого текста, а изменяют сами единицы. Несмотря на разницу между операциями транспонирования и замены, их часто комбинируют, как в исторических шифрах, таких как шифр ADFGVX , или в сложных методах высококачественного шифрования, таких как современный расширенный стандарт шифрования (AES).
Открытый текст можно преобразовать в зашифрованный текст с помощью ключа , меняя порядок символов подобно перетасованным кусочкам головоломки . Полученное сообщение трудно расшифровать без ключа, поскольку существует множество способов расположения символов.
Например, открытый текст «ЭТО ВИКИПЕДИЯ» может быть зашифрован как «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 для удобства чтения: ТУДИП СИХИИ ИКАСЭ
На практике такое короткое сообщение с предсказуемым ключевым словом будет почти сразу же взломано с помощью методов криптоанализа . Шифры транспозиции имеют несколько уязвимостей (см. раздел «Обнаружение и криптоанализ» ниже), а небольшие ошибки в процессе шифрования могут сделать весь зашифрованный текст бессмысленным.
Однако при правильных условиях — длинных сообщениях (например, более 100–200 букв), непредсказуемом содержании, уникальных ключах для каждого сообщения, надежных методах транспозиции и т. д. — угадывание правильных слов может оказаться вычислительно невозможным без дополнительной информации. В своей книге о взломе исторических шифров Илонка Дунин и Клаус Шме описывают двойную столбчатую транспозицию (см. Ниже) как «один из лучших известных ручных шифров». [1]
Шифр Rail Fence — это форма транспозиционного шифра, получившая свое название от способа его кодирования. В шифре рельсового забора открытый текст записывается вниз и по диагонали на последовательных «рельсах» воображаемого забора, а затем перемещается вверх, когда мы добираемся до низа. Затем сообщение считывается по строкам. Например, используя три «рельса» и сообщение «МЫ ОБНАРУЖЕНЫ БЕГАМИ СРАЗУ», шифровщик записывает:
В. . . Э. . . С. . . Р . . . Л. . . Т. . . Э. Э. Р . Д. С. О. Э. Э. Ф. Э. А. О. С.. . А. . . Я. . . В. . . Д. . . Э. . . Н. .
Затем зачитывает:
WECRL TEERD SOEEF EAOCA IVDEN
(Шифрование разбило этот зашифрованный текст на блоки по пять, чтобы избежать ошибок. Это распространенный метод, используемый для облегчения чтения шифра. Интервал не связан с пробелами в открытом тексте и поэтому не несет никакой информации о простой текст.)
Шифр железнодорожного забора следует образцу, аналогичному шифру скитале ( произносится как «SKIT-uhl-ee») — механической системе создания транспозиционного шифра, используемой древними греками . Система состояла из цилиндра и ленты, которая была обернута вокруг цилиндра. Сообщение, которое нужно было зашифровать, было написано на свернутой ленте. Буквы исходного сообщения менялись местами, когда ленту разматывали из цилиндра. Однако сообщение было легко расшифровано, когда лента намоталась на цилиндр того же диаметра, что и шифрующий цилиндр. [2] Используя тот же пример, что и раньше, если цилиндр имеет такой радиус, что по его окружности могут поместиться только три буквы, шифровщик записывает:
В. . Э. . А. . Р . . Э. . Д. . Я. . С. . С. О. . В. . Э. . Р . . Э. . Д. . Ф. . Л. .. . Э. . Э. . А. . Т. . О. . Н. . С. . Э.
В этом примере цилиндр движется горизонтально, а лента наматывается вертикально. Следовательно, шифровальщик затем считывает:
WOEEV EAEAR RTEEO DDNIF CSLEC
В маршрутном шифре открытый текст сначала записывается в сетке заданных размеров, а затем считывается по шаблону, заданному в ключе. Например, используя тот же открытый текст, который мы использовали для ограждения :
WRIORFEOEЭЕСВЕЛАНЖADCEDETCX
Ключ может указывать «по спирали внутрь, по часовой стрелке, начиная с правого верхнего угла». Это даст зашифрованный текст:
EJXCTEDEC DAEWRIORF ЭОНАЛЕВСЕ
Шифры маршрутов имеют гораздо больше ключей, чем рельсовое ограждение. Фактически, для сообщений разумной длины количество возможных ключей потенциально слишком велико, чтобы их можно было пересчитать даже с помощью современных машин. Однако не все клавиши одинаково хороши. Плохо выбранные маршруты оставят чрезмерные куски открытого текста или текст просто перевернут, и это даст криптоаналитикам подсказку относительно маршрутов.
Разновидностью шифра маршрута был шифр маршрута Союза, который использовался силами Союза во время Гражданской войны в США . Это работало так же, как обычный шифр маршрута, но вместо отдельных букв переносились целые слова. Поскольку это может привести к тому, что некоторые высокочувствительные слова будут раскрыты, такие слова сначала будут скрыты кодом . Шифровщик также может добавлять целые пустые слова, которые часто выбирались, чтобы сделать зашифрованный текст юмористическим. [ нужна цитата ]
В середине 17 века Сэмюэл Морланд представил раннюю форму столбчатого транспонирования. Дальнейшее развитие он получил гораздо позже и стал очень популярным в конце 19-го и 20-го веков, когда этот принцип использовали французские военные, японские дипломаты и советские шпионы.
При столбчатом транспонировании сообщение записывается строками фиксированной длины, а затем снова считывается столбец за столбцом, причем столбцы выбираются в некотором зашифрованном порядке. И ширина строк, и перестановка столбцов обычно определяются ключевым словом. Например, ключевое слово ZEBRAS имеет длину 6 (то есть строки имеют длину 6), а перестановка определяется алфавитным порядком букв в ключевом слове. В этом случае порядок будет «6 3 2 4 1 5».
В обычном столбчатом шифре транспонирования все свободные места заполняются нулями; в нерегулярном столбчатом шифре транспонирования пробелы остаются пустыми. Наконец, сообщение считывается по столбцам в порядке, указанном ключевым словом. Например, предположим, что мы используем ключевое слово ЗЕБРЫ и сообщение МЫ ОБНАРУЖЕНЫ. БЕГИТЕ НЕМЕДЛЕННО . При обычном столбчатом транспонировании мы записываем это в сетку следующим образом:
6 3 2 4 1 5ИЗНОШЕНИСКОВРЕДФЛЕЕАТОНКEQKJEU
при наличии пяти нулей ( QKJEU ) эти буквы могут быть выбраны случайным образом, поскольку они просто заполняют неполные столбцы и не являются частью сообщения. Затем зашифрованный текст считывается как:
EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE
В нерегулярном случае столбцы не заполняются нулями:
6 3 2 4 1 5ИЗНОШЕНИСКОВРЕДФЛЕЕАТОНКЭ
В результате получается следующий зашифрованный текст:
ЭВЛНА CDTES EAROF ODEEC WIREE
Чтобы его расшифровать, получатель должен определить форму шифровальной сетки, разделив длину сообщения на длину ключа, чтобы найти количество строк в сетке. Длина последней строки сетки определяется остатком. Ключ записывается над сеткой, а зашифрованный текст записывается в столбцах сетки в порядке, заданном буквами ключа. Открытый текст появляется в строках. Частичная расшифровка приведенного выше зашифрованного текста после записи в первом столбце:
6 3 2 4 1 5. . . . Э.. . . . В.. . . . Л.. . . . Н..
В другом варианте сообщение блокируется на сегменты, длина которых равна длине ключа, и к каждому сегменту применяется одна и та же перестановка (задаваемая ключом). Это эквивалентно столбчатому транспонированию, при котором считывание осуществляется по строкам, а не по столбцам.
Столбчатое транспонирование продолжало использоваться в серьезных целях как компонент более сложных шифров, по крайней мере, до 1950-х годов.
Одиночную столбчатую транспозицию можно атаковать, угадывая возможные длины столбцов, записывая сообщение в столбцы (но в неправильном порядке, поскольку ключ еще не известен), а затем ища возможные анаграммы . Поэтому, чтобы сделать его сильнее, часто использовалась двойная транспозиция. Это просто столбчатое транспонирование, примененное дважды. Для обеих транспозиций можно использовать одну и ту же клавишу или можно использовать две разные тональности.
В следующем примере мы используем ключи JANEAUSTEN и AIRPLANES для шифрования следующего открытого текста: « Шифры транспозиции перемешивают буквы, как кусочки головоломки, чтобы создать не поддающуюся расшифровке структуру».
Цвета показывают, как буквы шифруются на каждом этапе транспонирования. В то время как один шаг вызывает лишь незначительную перестановку, второй шаг приводит к значительному эффекту скремблирования, если последняя строка сетки неполная.
В качестве примера мы можем взять результат нерегулярного столбчатого транспонирования из предыдущего раздела и выполнить второе шифрование с другим ключевым словом STRIPE , что дает перестановку «564231»:
5 6 4 2 3 1ЭВЛНАКДТЭСЭАРОФОДЕЭКВАЙРЭ
Как и раньше, это считывается по столбцам, чтобы получить зашифрованный текст:
КАЕН СОИАЭ ДРЛЕФ ВЕДРЕ ЭВТОК
Если несколько сообщений одинаковой длины зашифрованы с использованием одних и тех же ключей, их можно анаграммировать одновременно. Это может привести как к восстановлению сообщений, так и к восстановлению ключей (чтобы можно было прочитать любое другое сообщение, отправленное с этими ключами).
Во время Первой мировой войны немецкие военные использовали двойной столбчатый транспозиционный шифр, нечасто меняя ключи. Систему регулярно решали французы, назвав ее Убчи, которые обычно могли быстро найти ключи после перехвата нескольких сообщений одинаковой длины, что обычно занимало всего несколько дней. Однако успех французов стал широко известен, и после публикации в Le Matin 18 ноября 1914 года немцы перешли на новую систему .
Во время Второй мировой войны шифр двойной транспозиции использовался голландскими группами Сопротивления , французскими маки и британским Управлением специальных операций (SOE), которое отвечало за управление подпольной деятельностью в Европе. [4] Он также использовался агентами американского Управления стратегических служб [5] и в качестве экстренного шифра для немецкой армии и флота.
До изобретения шифра VIC двойная транспозиция обычно считалась наиболее сложным шифром, которым агент мог надежно работать в сложных полевых условиях.
Шифр с двойной транспозицией можно рассматривать как одинарную транспозицию с ключом, длина которого равна произведению длин двух ключей. [6]
В конце 2013 года задача двойной транспозиции, которую ее автор считал неразборчивой, была решена Джорджем Ласри с использованием подхода «разделяй и властвуй», при котором каждая транспозиция подвергалась индивидуальной атаке. [7]
Вариант формы столбчатого транспонирования, предложенный Эмилем Виктором Теодором Мышковским в 1902 году, требует ключевого слова с повторяющимися буквами. В обычной практике последующие вхождения ключевой буквы обрабатываются так, как будто следующая буква в алфавитном порядке, например, ключевое слово TOMATO дает числовую строку «532164».
При транспозиции Мышковского повторяющиеся ключевые буквы нумеруются одинаково, TOMATO дает строку «432143».
4 3 2 1 4 3ИЗНОШЕНИСКОВРЕДФЛЕЕАТОНКЭ
Столбцы открытого текста с уникальными номерами транскрибируются вниз; номера с повторяющимися номерами транскрибируются слева направо:
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Я * * * * * * * * * * * * 4TIONPATTER * * * 5НЛИКЕАКОМ * * * * 6Б _ _ _ _ _ _ _ * * * * * 7
Затем столбцы удаляются в соответствии с обычным столбчатым транспонированием: TPRPN, KISAA, CHAIT, NBERT, EMATO и т. д.
Другой простой вариант [10] — использовать пароль, в котором пробелы располагаются в соответствии с его числовой последовательностью. Например, «СЕКРЕТ» будет декодирован в последовательность «5,2,1,4,3,6» и вычеркнет 5-е поле матрицы, затем снова посчитает и вычеркнет второе поле и т. д. Следующий пример будет быть матрицей, настроенной на столбчатое транспонирование со столбчатым ключом «КРИПТО» и заполненной перечеркнутыми полями в соответствии с ключом нарушения «СЕКРЕТНО» (отмечено звездочкой), после чего размещается сообщение «нас обнаружили, бегите немедленно» в оставшихся местах. Результирующий зашифрованный текст (столбцы, считываемые в соответствии с ключом транспонирования) — «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, скорее всего, затруднит ее взлом. Многие современные блочные шифры используют более сложные формы транспозиции, связанные с этой простой идеей.