Шифр транспонирования - Transposition cipher

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

Ниже приведены некоторые реализации.

Шифр Rail Fence

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

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

W. . . E. . . C. . . Р . . . L. . . Т. . . Э. Р . D. S. О. E. E. F. E. А. О. C ... А. . . Я. . . V. . . D. . . E. . . N. .

Затем читает:

WECRL TEERD SOEEF EAOCA IVDEN

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

Scytale

Шифр ограждения рельсов следует шаблону, аналогичному шаблону скитале, механическая система создания транспозиционного шифра, используемого древние греки. Система состояла из цилиндра и ленты, намотанной на цилиндр. Сообщение, которое нужно зашифровать, было написано на спиральной ленте. Буквы исходного сообщения будут переставлены, когда лента будет разматываться с цилиндра. Однако сообщение было легко дешифровано, когда лента была намотана на цилиндр того же диаметра, что и цилиндр шифрования.[1]. Используя тот же пример, что и раньше, если цилиндр имеет такой радиус, что по его окружности могут уместиться только три буквы, шифр пишет:

W. . E. . А. . Р . . E. . D. . Я. . S. . С. О. . V. . E. . Р . . E. . D. . F. . L. ... E. . E. . А. . Т. . О. . 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

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

Вариантом шифра маршрута был шифр Union Route Cipher, который использовался силами Союза во время американская гражданская война. Он работал так же, как обычный маршрутный шифр, но заменял целые слова вместо отдельных букв. Так как это оставит некоторые очень чувствительные слова открытыми, такие слова сначала будут скрыты код. Шифровальщик может также добавлять целые нулевые слова, которые часто выбирались для придания шифрованному тексту юмора.[нужна цитата ]

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

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

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

6 3 2 4 1 5W E A R E DI 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

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

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

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

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

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

В качестве примера мы можем взять результат нерегулярной столбчатой ​​транспозиции из предыдущего раздела и выполнить второе шифрование с другим ключевым словом, ПОЛОСКА, что дает перестановку "564231":

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

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

CAEEN SOIAE DRLEF WEDRE EVTOC

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

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

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

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

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

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

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

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

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

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

4 3 2 1 4 3 W E A R E DI S C O V ER E D F L EE A T O N CE

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

ROFOA CDTED SEEEA CWEIV RLENE

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

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

символы.

Обычный текст:

«Подтверждаем доставку документов позже»

Используем ключ BIRTHDAY

На матрице1: после заполнения первой области

На матрице2: видим ту же матрицу

заполнено полностью:

Матрица1:

25674318
BярТЧАСDАY
WECОNFя
р
MТЧАСEDE
LяVEр
YО
FТЧАС
EDОC
UMENТSLА


Матрица2:

25674318
BярТЧАСDАY
WECОNFят
рер
MТЧАСEDE
LяVEр
YО
FТЧАС
EDОC
UMENТSLА

После заполнения матрицы мы считываем ее по столбцам,

согласно последовательности ключевых слов.

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

ILWRMLYFEUFESNDRTEETIOTDMCRHVHOEOEECNTA

Решетки

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

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

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

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

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

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

Комбинации

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

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

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

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

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

Смотрите также

Заметки

  1. ^ Смит, Лоуренс Дуайт (1955) [1943], Криптография / Наука секретного письма, Нью-Йорк: Довер, стр. 16, 92–93.
  2. ^ Кан, стр. 301-304.
  3. ^ Кан, стр. 535 и 539.
  4. ^ Кан, стр. 539.
  5. ^ Баркер, Уэйн (1995). Криптоанализ шифра двойной транспозиции: включает задачи и компьютерные программы. Aegean Park Press.
  6. ^ Ласри, Джордж (13.06.2014). «Решение проблемы двойного транспонирования с помощью подхода« разделяй и властвуй »». Криптология. 38 (3): 197–214. Дои:10.1080/01611194.2014.915269. S2CID  7946904.
  7. ^ Дои:10.1080/0161-119391867863 Роберт А. Дж. Мэтьюз, страницы 187-201
  8. ^ Даниэль Родригес-Кларк.«Транспонирование дробного зашифрованного текста».
  9. ^ Джеймс Лайонс.«Фракционированный шифр Морзе».

использованная литература

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