Шифр транспозиции: метод шифрования, переставляющий символы без их замены. Отличается от шифров подстановки, часто комбинируется с ними для усиления защиты.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Метод шифрования
Method of encryption
В криптографии транспозиционный шифр (также известный как шифр перестановки) — это метод шифрования, который переставляет позиции символов (транспозиция), не изменяя сами символы. Шифры транспозиции переупорядочивают блоки открытого текста (обычно символы или группы символов) в соответствии с определенной системой, чтобы получить шифротекст, являющийся перестановкой открытого текста. Они отличаются от шифров подстановки, которые не меняют положение блоков открытого текста, а изменяют сами блоки. Несмотря на различие между операциями транспозиции и подстановки, они часто комбинируются, как в исторических шифрах, таких как шифр ADFGVX, или в сложных высококачественных методах шифрования, таких как современный стандарт шифрования AES.
In cryptography, a transposition cipher (also known as a permutation cipher) is a method of encryption which scrambles the positions of characters (transposition) without changing the characters themselves. Transposition ciphers reorder units of plaintext (typically characters or groups of characters) according to a regular system to produce a ciphertext which is a permutation of the plaintext. They differ from substitution ciphers, which do not change the position of units of plaintext but instead change the units themselves. Despite the difference between transposition and substitution operations, they are often combined, as in historical ciphers like the ADFGVX cipher or complex high quality encryption methods like the modern Advanced Encryption Standard (AES).
Двойная имплементация
Однократная столбцовая перестановка может быть взломана путем угадывания возможных длин столбцов, записи сообщения по столбцам (но в неправильном порядке, поскольку ключ неизвестен), и последующего поиска возможных анаграмм. Поэтому для повышения надежности часто использовалась двойная перестановка. Это просто столбцовая перестановка, примененная дважды. Для обеих перестановок можно использовать один и тот же ключ, либо два разных ключа.
A single columnar transposition could be attacked by guessing possible column lengths, writing the message out in its columns (but in the wrong order, as the key is not yet known), and then looking for possible anagrams. Thus to make it stronger, a double transposition was often used. This is simply a columnar transposition applied twice. The same key can be used for both transpositions, or two different keys can be used.
Визуальная демонстрация двойного перевода
В следующем примере мы используем ключи JANEAUSTEN и AEROPLANES для шифрования следующего открытого текста: "Шифры транспозиции перемешивают буквы, как детали головоломки, чтобы создать нечитаемую комбинацию. Цвета показывают, как буквы перемешиваются на каждом шаге транспозиции. В то время как один шаг вызывает лишь небольшое изменение порядка, второй шаг приводит к значительному эффекту перемешивания, если последний ряд сетки неполный.
In the following example, we use the keys JANEAUSTEN and AEROPLANES to encrypt the following plaintext: "Transposition ciphers scramble letters like puzzle pieces to create an indecipherable arrangement. "The colors show how the letters are scrambled in each transposition step. While a single step only causes a minor rearrangement, the second step leads to a significant scrambling effect if the last row of the grid is incomplete.
Криптоанализ
Шифр двойной транспозиции можно рассматривать как однократную транспозицию с ключом, длина которого равна произведению длин двух ключей. В конце 2013 года задача двойной транспозиции, которую её автор считал неразрешимой, была решена Джорджем Ласри с использованием подхода "разделяй и властвуй", при котором каждая транспозиция подвергалась отдельной атаке.
The double transposition cipher can be treated as a single transposition with a key as long as the product of the lengths of the two keys. In late 2013, a double transposition challenge, regarded by its author as undecipherable, was solved by George Lasry using a divide and conquer approach where each transposition was attacked individually.
Решетки
Другая форма транспозиционного шифра использует решетки, или физические маски с прорезями. Это может создавать крайне нерегулярную перестановку в течение периода, определяемого размером решетки, но требует от корреспондентов сохранения физического ключа в тайне. Решетки были впервые предложены в 1550 году и еще использовались в военных целях в течение первых нескольких месяцев Первой мировой войны.
Another form of transposition cipher uses grilles, or physical masks with cut outs. This can produce a highly irregular transposition over the period specified by the size of the grille, but requires the correspondents to keep a physical key secret. Grilles were first proposed in 1550, and were still in military use for the first few months of World War One.
Комбинации
Транспозиция часто сочетается с другими техниками, такими как методы анализа. Например, простой шифр подстановки, объединенный с столбцовой транспозицией, позволяет избежать недостатков обоих методов. Замена часто встречающихся символов шифротекста на часто встречающиеся буквы открытого текста не позволяет восстановить фрагменты открытого текста благодаря транспозиции. Попытки анаграммирования транспонированного текста не увенчаются успехом из-за шифра подстановки. Эта техника особенно эффективна в сочетании с фракционированием (см. ниже). Недостатком является то, что создание и использование таких шифров значительно сложнее и чревато ошибками, чем использование более простых шифров.
Transposition is often combined with other techniques such as evaluation methods. For example, a simple substitution cipher combined with a columnar transposition avoids the weakness of both. Replacing high frequency ciphertext symbols with high frequency plaintext letters does not reveal chunks of plaintext because of the transposition. Anagramming the transposition does not work because of the substitution. The technique is particularly powerful if combined with fractionation (see below). A disadvantage is that such ciphers are considerably more laborious and error prone than simpler ciphers.
Фракционирование
Транспозиция особенно эффективна при использовании с фракционированием – то есть, предварительным этапом, который разделяет каждый символ открытого текста на два или более символа шифротекста. Например, алфавит открытого текста можно представить в виде сетки, и каждую букву сообщения заменить на её координаты (см. квадрат Полибия и шахматную доску Страддлинга). Другой способ фракционирования – просто преобразовать сообщение в код Морзе, используя символ для пробелов, а также точки и тире. Когда такое фракционированное сообщение подвергается транспозиции, компоненты отдельных букв широко разрозниваются в сообщении, тем самым обеспечивая диффузию по Клоду Э. Шеннону. Примеры шифров, сочетающих фракционирование и транспозицию, включают бифидный шифр, трифидный шифр, шифр ADFGVX и шифр VIC. Другой вариант – заменить каждую букву её двоичным представлением, выполнить транспозицию, а затем преобразовать полученную двоичную строку в соответствующие символы ASCII. Многократное применение процесса перемешивания к двоичной строке перед преобразованием в символы ASCII, вероятно, усложнит её взлом. Многие современные блочные шифры используют более сложные формы транспозиции, основанные на этой простой идее.
Transposition is particularly effective when employed with fractionation – that is, a preliminary stage that divides each plaintext symbol into two or more ciphertext symbols. For example, the plaintext alphabet could be written out in a grid, and every letter in the message replaced by its co ordinates (see Polybius square and Straddling checkerboard). Another method of fractionation is to simply convert the message to Morse code, with a symbol for spaces as well as dots and dashes. When such a fractionated message is transposed, the components of individual letters become widely separated in the message, thus achieving Claude E. Shannon's diffusion. Examples of ciphers that combine fractionation and transposition include the bifid cipher, the trifid cipher, the ADFGVX cipher and the VIC cipher. Another choice would be to replace each letter with its binary representation, transpose that, and then convert the new binary string into the corresponding ASCII characters. Looping the scrambling process on the binary string multiple times before changing it into ASCII characters would likely make it harder to break. Many modern block ciphers use more complex forms of transposition related to this simple idea.