Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Шифр Rail Fence [ править ]

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

Шифр 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 [ править ]

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

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

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

WOEEV EAEAR RTEEO DDNIF CSLEC

Шифр маршрута [ править ]

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

WRIORFEOE ЭСВЕЛАНЖ ADCEDETCX

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

EJXCTEDEC DAEWRIORF EONALEVSE

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

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

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

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

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

6 3 2 4 1 5ИЗНОШЕННЫЙISCOVE REDFLE EATONC EQKJEU

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

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

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

6 3 2 4 1 5ИЗНОШЕННЫЙ ISCOVE REDFLE EATONC E

Это приводит к следующему зашифрованному тексту:

EVLNA CDTES EAROF ODEEC WIREE

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

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

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

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

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

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

5 6 4 2 3 1 ЭВЛНАКDTESEAROFODEЭКВИРE

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

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ИЗНОШЕННЫЙISCOVEREDFLEEATONCE

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

ROFOA CDTED SEEEA CWEIV RLENE

Нарушенная транспозиция [ править ]

Нарушенный шифр транспозиции [7] еще больше усложняет шаблон транспонирования с нерегулярным заполнением строк матрицы, то есть с некоторыми пробелами, намеренно оставленными пустыми (или закрашенными черным, как в Rasterschlüssel 44 ), или заполненными позже любой другой частью открытого текста или случайные буквы. Один из возможных алгоритмов [7] - начинать новую строку всякий раз, когда открытый текст достигает символа пароля. Еще один простой вариант [8]было бы использовать пароль, который ставит пробелы в соответствии с его числовой последовательностью. Например, "СЕКРЕТНО" будет декодировано в последовательность "5,2,1,4,3,6" и вычеркнет 5-е поле матрицы, затем снова посчитает и вычеркнет второе поле и т. Д. В следующем примере будет быть матрицей, настроенной для столбцового транспонирования с столбцовым ключом «CRYPTO» и заполненной перечеркнутыми полями в соответствии с ключом нарушения «СЕКРЕТНО» (отмеченным звездочкой), после чего сообщение «мы обнаружены, бегите немедленно» помещается в оставшиеся места. Результирующий зашифрованный текст (столбцы, считываемые в соответствии с ключом транспонирования): «WCEEO ERET RIVFC EODN SELE ADA».

КРИПТО1 4 6 3 5 2МЫ* * DIS *ПОКРЫТИЕED * FLEЕСТЬОДНАЖДЫ *

Решетки [ править ]

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

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

Обнаружение и криптоанализ [ править ]

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

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

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

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

Комбинации [ править ]

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

Фракционирование [ править ]

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

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

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

См. Также [ править ]

  • Подстановочный шифр
  • Запрет (единица)
  • Темы в криптографии

Заметки [ править ]

  1. ^ Смит, Лоуренс Дуайт (1955) [1943], Криптография / Наука секретного письма , Нью-Йорк: Довер, стр. 16, 92–93
  2. ^ Кан, стр. 301-304.
  3. ↑ Кан, стр. 535 и 539.
  4. ^ Кан, стр. 539.
  5. ^ Баркер, Уэйн (1995). Криптоанализ шифра двойной транспозиции: включает задачи и компьютерные программы . Aegean Park Press.
  6. ^ Ласри, Джордж (2014-06-13). «Решение проблемы двойного транспонирования с помощью подхода« разделяй и властвуй »». Cryptologia . 38 (3): 197–214. DOI : 10.1080 / 01611194.2014.915269 . S2CID 7946904 . 
  7. ^ a b Махалакшми, Б. (июнь 2016 г.). «Обзор нарушенного шифра транспозиции для повышения безопасности» (PDF) . Международный журнал компьютерных приложений . 143 (13) . Проверено 7 января 2021 года .
  8. ^ "Простая прерванная транспозиция" . Проверено 7 января 2021 года . |first1=отсутствует |last1=( помощь )
  9. ^ DOI : 10.1080 / 0161-119391867863 Роберт А. Дж. Мэтьюз, страницы 187-201
  10. ^ "Шифр Зодиака Убийцы взломан после ускользания от сыщиков в течение 51 года" . arstechnica.com . 2020-12-12 . Проверено 12 декабря 2020 .
  11. ^ Даниэль Родригес-Кларк. «Транспонирование дробного зашифрованного текста» .
  12. ^ Джеймс Лайонс. «Фракционированный шифр Морзе» .

Ссылки [ править ]

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