Транспозиционный шифр

Пошаговый процесс создания шифра двойного столбчатого транспонирования.

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

Общий принцип

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

Например, открытый текст «ЭТО ВИКИПЕДИЯ» можно зашифровать как «TWDIP SIHII IKASE». Чтобы расшифровать зашифрованное сообщение без ключа, злоумышленник может попытаться угадать возможные слова и фразы, такие как DIATHESIS, DISSIPATE, WIDTH и т. д., но ему потребуется некоторое время, чтобы восстановить открытый текст, поскольку существует множество комбинаций букв и слов. Напротив, тот, у кого есть ключ, может легко восстановить сообщение:

C I P H E R     Key
1 4 5 3 2 6     Sequence (key letters in alphabetical order)
T H I S I S     Plaintext
W I K I P E
D I A * * *

Ciphertext by column:
  #1 TWD, #2 IP, #3 SI, #4 HII, #5 IKA, #6 SE
Ciphertext in groups of 5 for readability:
  TWDIP SIHII IKASE

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

Однако при правильных условиях — длинные сообщения (например, более 100–200 букв), непредсказуемое содержание, уникальные ключи для каждого сообщения, надежные методы транспозиции и т. д. — угадывание правильных слов может оказаться вычислительно невозможным без дополнительной информации. В своей книге о взломе исторических шифров Илонка Дунин и Клаус Шме описывают двойную столбчатую транспозицию (см. Ниже) как «один из лучших известных ручных шифров».

Шифр железнодорожного забора

Основная статья: Шифр ​​железнодорожного забора

Шифр Rail Fence — это форма транспозиционного шифра, получившая свое название от способа его кодирования. В шифре рельсового забора открытый текст записывается вниз и по диагонали на последовательных «рельсах» воображаемого забора, а затем перемещается вверх, когда мы добираемся до низа. Затем сообщение считывается по строкам. Например, используя три «рельса» и сообщение «МЫ ОБНАРУЖЕНЫ БЕГАМИ СРАЗУ», шифровщик записывает:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Затем зачитывает:

WECRL TEERD SOEEF EAOCA IVDEN

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

Скайтейл

Шифр железнодорожного забора повторяет шаблон, аналогичный шифру скитале ( произносится как «SKIT-uhl-ee») — механической системе создания транспозиционного шифра, используемой древними греками . Система состояла из цилиндра и ленты, которая была обернута вокруг цилиндра. Сообщение, которое нужно было зашифровать, было написано на свернутой ленте. Буквы исходного сообщения менялись местами, когда ленту разматывали из цилиндра. Однако сообщение было легко расшифровано, когда лента намоталась на цилиндр того же диаметра, что и шифрующий цилиндр. Используя тот же пример, что и предыдущий, если цилиндр имеет такой радиус, что по его окружности могут поместиться только три буквы, шифровщик записывает:

W . . E . . A . . R . . E . . D . . I . . S . . C
. O . . V . . E . . R . . E . . D . . F . . L . .
. . E . . E . . A . . T . . O . . N . . C . . E .

В этом примере цилиндр движется горизонтально, а лента наматывается вертикально. Следовательно, шифровальщик затем считывает:

WOEEV EAEAR RTEEO DDNIF CSLEC

Шифр маршрута

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

W R I O R F E O E 
E E S V E L A N J 
A D C E D E T C X 

Ключ может указывать «по спирали внутрь по часовой стрелке, начиная с правого верхнего угла». Это даст зашифрованный текст:

EJXCTEDEC DAEWRIORF EONALEVSE

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

Разновидностью шифра маршрута был шифр маршрута Союза, который использовался силами Союза во время Гражданской войны в США . Это работало так же, как обычный маршрутный шифр, но вместо отдельных букв переносились целые слова. Поскольку это приведет к тому, что некоторые очень чувствительные слова останутся открытыми, такие слова сначала будут скрыты кодом . Шифровщик также может добавлять целые пустые слова, которые часто выбирались, чтобы сделать зашифрованный текст юмористическим.

Столбчатое транспонирование

В середине 17 века Сэмюэл Морланд представил раннюю форму столбчатого транспонирования. Дальнейшее развитие он получил намного позже и стал очень популярным в конце 19 и 20 веков, когда этот принцип использовали французские военные, японские дипломаты и советские шпионы.

При столбчатом транспонировании сообщение записывается строками фиксированной длины, а затем снова считывается столбец за столбцом, причем столбцы выбираются в некотором зашифрованном порядке. И ширина строк, и перестановка столбцов обычно определяются ключевым словом. Например, ключевое слово ZEBRAS имеет длину 6 (то есть строки имеют длину 6), а перестановка определяется алфавитным порядком букв в ключевом слове. В этом случае порядок будет «6 3 2 4 1 5».

В обычном столбчатом шифре транспонирования все свободные места заполняются нулями; в нерегулярном столбчатом шифре транспонирования пробелы остаются пустыми. Наконец, сообщение считывается по столбцам в порядке, указанном ключевым словом. Например, предположим, что мы используем ключевое слово ЗЕБРЫ и послание НАС ОТКРЫЛИ. БЕГИТЕ НЕМЕДЛЕННО . При обычном столбчатом транспонировании мы записываем это в сетку следующим образом:

6 3 2 4 1 5
W E A R E D
I S C O V E 
R E D F L E 
E A T O N C 
E Q K J E U 

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

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

В нерегулярном случае столбцы не заполняются нулями:

6 3 2 4 1 5
W E A R E D 
I S C O V E 
R E D F L E 
E A T O N C 
E 

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

EVLNA CDTES EAROF ODEEC WIREE

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

6 3 2 4 1 5
. . . . E .
. . . . V .
. . . . L .
. . . . N .
.

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

Столбчатое транспонирование продолжало использоваться в серьезных целях как компонент более сложных шифров, по крайней мере, до 1950-х годов.

Двойная транспозиция

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

Наглядная демонстрация двойной транспозиции

В следующем примере мы используем ключи JANEAUSTEN и AIRPLANES для шифрования следующего открытого текста: « Шифры транспозиции перемешивают буквы, как кусочки головоломки, чтобы создать не поддающуюся расшифровке структуру».

• 
  Шаг 1: Открытое текстовое сообщение записывается в первую сетку (которая имеет ключ JANEAUSTEN).
• 
  Столбцы считываются в алфавитном порядке по ключу в следующую сетку (см. шаг 2).
• 
  Шаг 2: Столбцы из шага 1 записываются во вторую сетку (которая имеет ключ САМОЛЕТЫ).
• 
  Столбцы считываются в алфавитном порядке по ключу в следующую сетку (см. шаг 3).
• 
  Шаг 3: Зашифрованный текст часто записывается блоками по 5, например RIAES NNELI EEIRP и т. д.

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

Другой пример

В качестве примера мы можем взять результат нерегулярного столбчатого транспонирования из предыдущего раздела и выполнить второе шифрование с другим ключевым словом: STRIPE , что дает перестановку «564231»:

5 6 4 2 3 1 
E V L N A C
D T E S E A
R O F O D E
E C W I R E
E

Как и раньше, это считывается по столбцам, чтобы получить зашифрованный текст:

CAEEN SOIAE DRLEF WEDRE EVTOC

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

Во время Первой мировой войны немецкие военные использовали двойной столбчатый транспозиционный шифр, нечасто меняя ключи. Систему регулярно решали французы, назвав ее Убчи, которые обычно могли быстро найти ключи после перехвата нескольких сообщений одинаковой длины, что обычно занимало всего несколько дней. Однако успех французов стал широко известен, и после публикации в Le Matin 18 ноября 1914 года немцы перешли на новую систему.

Во время Второй мировой войны шифр двойной транспозиции использовался голландскими группами Сопротивления , французскими маки и британским Управлением специальных операций (SOE), которое отвечало за управление подпольной деятельностью в Европе. Его также использовали агенты американского Управления стратегических служб. и в качестве экстренного шифра для немецкой армии и флота.

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

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

Шифр с двойной транспозицией можно рассматривать как одинарную транспозицию с ключом, длина которого равна произведению длин двух ключей.

В конце 2013 года задача двойной транспозиции, которую автор считал неразборчивой, была решена Джорджем Ласри с использованием подхода «разделяй и властвуй», при котором каждая транспозиция подвергалась индивидуальной атаке.

Транспозиция Мышковского

Вариант формы столбчатого транспонирования, предложенный Эмилем Виктором Теодором Мышковским в 1902 году, требует ключевого слова с повторяющимися буквами. В обычной практике последующие вхождения ключевой буквы обрабатываются так, как будто следующая буква в алфавитном порядке, например, ключевое слово TOMATO дает числовую строку «532164».

При транспозиции Мышковского повторяющиеся ключевые буквы нумеруются одинаково, TOMATO дает строку «432143».

4 3 2 1 4 3
W E A R E D
I S C O V E
R E D F L E
E A T O N C
E

Столбцы открытого текста с уникальными номерами транскрибируются вниз; номера с повторяющимися номерами транскрибируются слева направо:

ROFOA CDTED SEEEA CWEIV RLENE

Нарушенная транспозиция

Нарушенный транспозиционный шифр еще больше усложняет шаблон транспонирования неравномерным заполнением строк матрицы, т.е. некоторыми пробелами, намеренно оставленными пустыми (или затемненными, как в Rasterschlüssel 44 ), или заполненными позже либо другой частью открытого текста, либо случайными буквами.

Гребенчатый подход

Этот метод (приписывается генералу Луиджи Сакко ) начинает новую строку, как только открытый текст достигает столбца, ключевой номер которого равен текущему номеру строки. Это приводит к неправильной длине строк. Например,

F  O  R  E  V  E  R  J  I  G  S  A  W     < Key
4  8  9  2 12  3 10  7  6  5 11  1 13     Blanks after no.:
C  O  M  P  L  I  C  A  T  E  S  T  *     1
H  E  T  R  *  *  *  *  *  *  *  *  *     2
A  N  S  P  O  S  *  *  *  *  *  *  *     3
I  *  *  *  *  *  *  *  *  *  *  *  *     4
T  I  O  N  P  A  T  T  E  R  *  *  *     5
N  L  I  K  E  A  C  O  M  *  *  *  *     6
B  _  _  _  _  _  _  _  *  *  *  *  *     7

Затем столбцы удаляются в соответствии с обычным столбчатым транспонированием: TPRPN, KISAA, CHAIT, NBERT, EMATO и т. д.

Подход числовой последовательности

Еще один простой вариант было бы использовать пароль, в котором пробелы размещаются в соответствии с его числовой последовательностью. Например, «СЕКРЕТ» будет декодирован в последовательность «5,2,1,4,3,6» и вычеркнет 5-е поле матрицы, затем снова посчитает и вычеркнет второе поле и т. д. Следующий пример будет быть матрицей, настроенной на столбчатое транспонирование со столбцовым ключом «КРИПТО» и заполненной перечеркнутыми полями в соответствии с ключом нарушения «СЕКРЕТНО» (отмечено звездочкой), после чего размещается сообщение «нас обнаружили, бегите немедленно» в оставшихся местах. Результирующий зашифрованный текст (столбцы, считываемые в соответствии с ключом транспонирования) — «WCEEO ERET RIVFC EODN SELE ADA».

C R Y P T O
1 4 6 3 5 2
W E A R * E
* * D I S *
C O * V E R
E D * F L E
E * A * * T
O N * C E *

Решетки

Основная статья: Решетка (криптография)

Другая форма транспозиционного шифра использует решетки или физические маски с вырезами. Это может привести к весьма нерегулярному транспонированию в течение периода, определяемого размером решетки, но требует от корреспондентов хранить в секрете физический ключ. Решетки были впервые предложены в 1550 году и все еще использовались в военных целях в течение первых нескольких месяцев Первой мировой войны.

Обнаружение и криптоанализ

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

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

Существует несколько конкретных методов атаки на сообщения, закодированные с использованием транспозиционного шифра. К ним относятся:

1. Атака по известному открытому тексту : использование известных или предполагаемых частей открытого текста (например, имен, мест, дат, чисел, фраз) для помощи в обратном проектировании вероятного порядка столбцов, используемых для транспонирования, и/или вероятной темы сообщения. открытый текст.
2. Атака методом перебора . Если ключи получены из словарных слов или фраз из книг или других общедоступных источников, возможно подобрать решение методом перебора, попытавшись использовать миллиарды возможных слов, словосочетаний и фраз в качестве ключей.
3. Атака в глубину: если два или более сообщений одинаковой длины закодированы с помощью одних и тех же ключей, сообщения можно выравнивать и анаграммировать до тех пор, пока сообщения не будут отображать значимый текст в одних и тех же местах, без необходимости знать выполненные шаги транспонирования.
4. Статистическая атака: статистика о частоте комбинаций из 2, 3 букв и т. д. в языке может использоваться для информирования оценочной функции в алгоритме, который постепенно отменяет возможные транспозиции на основе того, какие изменения будут давать наиболее вероятные комбинации. Например, пара из двух букв QU более распространена в английском тексте, чем QT, поэтому криптоаналитик попытается выполнить транспозицию, которая соединит QU вместе.

Третий метод был разработан в 1878 году математиком Эдвардом С. Холденом и New York Tribune журналистами Джоном Р.Г. Хассардом и Уильямом М. Гросвенором, которым удалось расшифровать телеграммы между Демократической партией и ее агентами в южных штатах во время президентских выборов 1876 года и, таким образом, доказать факты подкупа голосов , повлиявшие на выборы в Конгресс 1878-1879 годов .

Подробное описание криптоанализа немецкого транспозиционного шифра. можно найти в главе 7 книги Герберта Ярдли «Американская черная палата».

Шифр, используемый Зодиакальным Убийцей , под названием «Z-340», организованный в треугольные секции с заменой букв на 63 различных символа и диагональной транспозицией «ход коня», оставался неразгаданным более 51 года, пока международная команда частных лиц взломал его 5 декабря 2020 года с помощью специализированного программного обеспечения.

Комбинации

Транспонирование часто комбинируется с другими методами, такими как методы оценки. Например, простой шифр замены в сочетании со столбчатым транспонированием позволяет избежать недостатков обоих. Замена высокочастотных символов зашифрованного текста высокочастотными буквами открытого текста не выявляет фрагменты открытого текста из-за транспонирования. Анаграммирование транспозиции не работает из-за замены. Этот метод особенно эффективен в сочетании с фракционированием (см. ниже). Недостатком является то, что такие шифры значительно более трудоемки и подвержены ошибкам, чем более простые шифры.

Фракционирование

Транспонирование особенно эффективно при использовании фракционирования — то есть предварительного этапа, на котором каждый символ открытого текста разделяется на два или более символов зашифрованного текста. Например, алфавит открытого текста может быть записан в виде сетки, и каждая буква в сообщении будет заменена ее координатами (см. «Квадрат Полибия» и «Шахматная доска» ). Другой метод фракционирования — просто преобразовать сообщение в код Морзе с использованием символов пробелов, а также точек и тире.

Когда такое дробное сообщение транспонируется, компоненты отдельных букв становятся широко разделенными в сообщении, что обеспечивает Клода Э. Шеннона диффузию . Примеры шифров, сочетающих дробление и транспозицию, включают двураздельный шифр , тройной шифр , шифр ADFGVX и шифр VIC .

Другой вариант — заменить каждую букву ее двоичным представлением, транспонировать ее, а затем преобразовать новую двоичную строку в соответствующие символы ASCII. Повторение процесса скремблирования двоичной строки несколько раз перед преобразованием ее в символы ASCII, скорее всего, затруднит ее взлом. Многие современные блочные шифры используют более сложные формы транспозиции, связанные с этой простой идеей.

См. также

• Шифр замены
• В (единице)
• Темы криптографии

Ссылки

• Кан, Дэвид. Взломщики кодов: история тайного письма. Преподобный суб. Скрибнер, 1996.
• Ярдли, Герберт. Американская черная палата. Боббс-Меррилл, 1931 год.