Шифр ​​транспонирования

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

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

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

Содержание

  • 1 Шифр ​​Rail Fence
  • 2 Scytale
  • 3 Шифр ​​маршрута
  • 4 Транспонирование столбцов
  • 5 Двойное транспонирование
    • 5.1 Криптоанализ
  • 6 Транспонирование Мышковского
  • 7 Нарушено транспозиция
  • 8 Решетки
  • 9 Обнаружение и криптоанализ
  • 10 Комбинации
  • 11 Фракционирование
  • 12 См. также
  • 13 Примечания
  • 14 Ссылки

Шифр ​​ограждения ограждения

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

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

Затем считывается:

WECRL TEERD SOEEF EAOCA IVDEN

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

Scytale

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

W.. E.. А.. Р.. E.. D.. Я.. S.. C. О.. 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 S V E L A N J A D C E D E T C X

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

EJXCTEDEC DAEWRIORF EONALEVSE

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

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

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

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

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

6 3 2 4 1 5 WEAREDISCOVEREDFLEEAT ONCEQKJEU

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

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

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

6 3 2 4 1 5 WEAREDISCOVEREDFLEEAT ONCE

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

EVLNA CDTES EAROF ODEEC WIREE

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

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

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

Двойное транспонирование

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

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

5 6 4 2 3 1 EVLNACDTESEAROFODEECW IREE

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

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

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

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

.

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

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

Используем ключ ДЕНЬ РОЖДЕНИЯ

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

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

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

Матрица1:

25674318
BIRTHDAY
WECONFI
R
MTHEDE
LIVER
YO
FTH
EDOC
UMENTSLA

. Матрица2:

25674318
BIRTHDAY
WECONFIt
Rer
MTHEDE
LIVER
YO
FTH
EDOC
UMENTSLA

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

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

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

ILWRMLYFEUFESNDRTEETIOTDMCRHVHOEOEECNTA.

Решетки

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

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

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

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

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

Комбинации

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

Дробление

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

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

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

См. Также

Примечания

Ссылки

  • Кан, Дэвид. Взломщики кодов: история секретного письма. Rev Sub. Scribner, 1996.
  • Ярдли, Герберт. Американская черная палата. Bobbs-Merrill, 1931.
Последняя правка сделана 2021-06-11 10:08:12
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте