Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного ``маршрута"", а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой .
Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево.
Выписывать сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.
При расшифровании надо определить число длинных столбцов, т.е. число букв в последней строке прямоугольника. Для этого нужно разделить число буев в сообщении на длину числового ключа. Остаток от деления и будет искомым числом.
Шифр ``Сцитала"" .
Одним из самых первых шифровальных приспособлений был жезл (``Сцитала""), применявшийся еще во времена войны Спарты против Афин в V веке до н. э.
Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения.
Шифр ``Сцитала"‘ реализует не более n перестановок (n - длина сообщения).
Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения.
Имеются еще и чисто физические ограничения, накладываемые реализацией шифра ``Сцитала"". Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв (10p < 32). Таким образом, число перестановок, реализуемых ``Сциталой"", вряд ли превосходит 32.
Шифр ``Поворотная решетка"".
Для использования шифра, называемого поворотной решеткой, изготавливается трафарет из прямоугольного листа клетчатой бумаги размера клеток.
В трафарете вырезано 2m x 2k клеток так, что при наложении его на чистый лист бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.
Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке.
- Шифры замены. Математическая модель. Примеры.
Поточные шифры (Цезаря)
Блочные шифры (Порта и Пфейфера)
Основа – прямоугольная таблица, в которую записан систематически перемешанный алфавит.
Правило зашифрования:
Буквы биграммы (i ,j ), i ¹ j , находятся в данной таблицк. При зашифровании биграмма (i ,j ) заменяется биграммой (k ,l ), где определяются с правилами:
- Если i и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда k и l – другая пара вершин, причем k –вершина, лежащая в той же строке, что и i .
- Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее «правым соседом» является первая буква той же строки.
- Аналогично если i и j лежат в одном столбце, то они заменяются «соседями снизу.»
Пример шифра Плейфера.
Пусть шифр использует прямоугольник 5х6, в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова «командир».
В качестве «пустышки» будем использовать редкую букву ф .
Представим фразу в виде последовательности биграмм:
АВ ТО РО МФ МЕ ТО ДА ЯВ ЛЯ ЕТ СЯ УИ ТС ТО НФ
Шифртекст:
ВП ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД ОЧ
Криптоанализ шифра Плейфера опирается на частотный анализ биграмм, триграмм и четырехграмм шифртекста и особенности замены шифрвеличин на шифрообозначения, связанные с расположением алфавита в прямоугольнике.
Существенную информацию о заменах дает знание того, что используется систематически перемешанный алфавит.
- Шифры перестановки. Математическая модель. Примеры.
Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки.
Пример
Рассмотрим, предназначенное для зашифрования сообщения длиной n
символов. Его можно представить с помощью таблицы
где i1 - номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, i2 - номер места для второй буквы и т.д.
В верхней строке таблицы выписаны по порядку числа от 1 до, а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени n . Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста.
Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка
и в соответствии с ней зашифровывается слово МОСКВА,
то получится КОСВМА.
Число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины n , меньше либо равно n! (в это число входит и вариант преобразования, оставляющий все символы на своих местах!).
- Шифры гаммирования. Математическая модель. Примеры.
Гамми́рование - симметричный метод шифрования, основанный на «наложении» гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле
Принцип шифрования заключается в формировании генератором псевдослучайных чисел (ГПСЧ) гаммы шифра и наложении этой гаммы на открытые данные обратимым образом, например путем сложения по модулю два. Процесс дешифрования данных сводится к повторной генерации гаммы шифра и наложении гаммы на зашифрованные данные. Ключом шифрования в данном случае является начальное состояние генератора псевдослучайных чисел. При одном и том же начальном состоянии ГПСЧ будет формировать одни и те же псевдослучайные последовательности.
- Принципы построения блочных шифров. Схема Фейстеля.
Сеть Фейстеля:
Сеть Фейстеля - это общий метод преобразования произвольной функции F в перестановку на множестве блоков. Она состоит из циклически повторяющихся ячеек - раундов. Внутри каждого раунда блок открытого текста разделяется на две равные части. Раундовая функция
берет одну половину (на рис. правую), преобразует её с использованием ключа K i и объединяет результат с второй половиной посредством операции исключающее ИЛИ (XOR). Этот ключ задаётся первоначальным ключом K и различен для каждого раунда. Далее половинки меняются местами (иначе будет преобразовываться только одна половина блока) и подаются на следующий раунд. Преобразование сети Фейстеля является обратимой операцией.
Для функции F существуют определенные требования:
· её работа должна приводить к лавинному эффекту
· должна быть нелинейна по отношению к операции XOR
В случае невыполнения первого требования, сеть будет подвержена дифференциальным атакам (похожие сообщения будут иметь похожие шифры). Во втором случае действия шифра линейны и для взлома достаточно решения системы линейных уравнений.
Подобная конструкция обладает ощутимым преимуществом: процедурышифрования/расшифрования совпадают, только производные от первоначального ключи используются в обратном порядке. Это значит, что одни и те же блоки могут использоваться как для шифрования, так и для расшифрования, что, безусловно, упрощает реализацию шифра. Недостаток схемы заключается в том, что в каждом раунде обрабатывается только половина блока, что приводит к необходимости увеличивать число раундов.
Шифрование перестановкой заключается в том, что символы открытого текста переставляются по определенному правилу в пределах некоторого блока этого текста. Рассмотрим перестановку, предназначенную для шифрования сообщения длиной n символов. Его можно представить с помощью таблицы
где i 1 – номер места шифртекста, на которое попадает первая буква открытого текста при выбранном преобразовании, i 2 - номер места для второй буквы и т. д. В верхней строке таблицы выписаны по порядку числа от 1 до n , а в нижней те же числа, но в произвольном порядке. Такая таблица называется перестановкой степени n .
Зная перестановку, задающую преобразование, можно осуществить как шифрование, так и расшифрование текста. В этом случае, сама таблица перестановки служит ключом шифрования.
Число различных преобразований шифра перестановки, предназначенного для шифрования сообщений длины n , меньше либо равно n ! (n факториал). Заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах.
С увеличением числа n значение n ! растет очень быстро. Для использования на практике такой шифр не удобен, так как при больших значениях n приходится работать с длинными таблицами. Поэтому широкое распространение получили шифры, использующие не саму таблицу перестановки, а некоторое правило, порождающее эту таблицу. Рассмотрим несколько примеров таких шифров.
Шифр перестановки "скитала". Известно, что в Vвеке до нашей эры правители Спарты, наиболее воинственного из греческих государств, имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью скитала, первого простейшего криптографического устройства, реализующего метод простой перестановки.
Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения (рис. 1.2). Затем снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположенными хаотично.
Рис. 1.2. Шифр "Скитала"
Такой же результат можно получить, если буквы сообщения писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Сообщение "НАСТУПАЙТЕ " при размещении его по окружности стержня по три буквы дает шифртекст: "НУТАПЕСА_ТЙ ".
Для расшифрования такого шифртекста нужно не только знать правило шифрования, но и обладать ключом в виде стержня определенного диаметра. Зная только вид шифра, но не имея ключа, расшифровать сообщение было непросто.
Шифрующие таблицы. С начала эпохи Возрождения (конец XIV столетия) начала возрождаться и криптография. В разработанных шифрах перестановки того времени применяются шифрующие таблицы, которые, в сущности, задают правила перестановки букв в сообщении.
В качестве ключа в шифрующих таблицах используются:
размер таблицы;
слово или фраза, задающие перестановку;
особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение "ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ "записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 1.3.
После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение: "ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ ".
Рис. 1.3. Заполнение шифрующей таблицы из 5 строк и 7 столбцов
Естественно, отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. Следует заметить, что объединение букв шифртекста в 5-буквенные группы не входит в ключ шифра и осуществляется для удобства записи несмыслового текста. При расшифровании действия выполняют в обратном порядке.
Несколько большей стойкостью к раскрытию обладает метод шифрования, называемый одиночной перестановкой по ключу . Этот метод отличается от предыдущего тем, что столбцы таблицы переставляются по ключевому слову, фразе или набору чисел длиной в строку таблицы.
Применим в качестве ключа, например, слово "ПЕЛИКАН ", а текст сообщения возьмем из предыдущего примера. На рис. 1.4 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица – заполнению после перестановки.
Рис. 1.4. Шифрующие таблицы, заполненные ключевым словом и текстом сообщения
В верхней строке левой таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, они бы были понумерованы слева направо. В правой таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа.
При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение: "ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ ".
Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой . В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным.
Пример выполнения шифрования методом двойной перестановки показан на рис. 1.5. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее: "ТЮАЕ ООГМ РЛИП ОЬСВ ".
Рис. 1.5. Пример выполнения шифрования методом двойной перестановки
Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).
Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:
для таблицы 3x3 36 вариантов;
для таблицы 4x4 576 вариантов;
для таблицы 5x5 14400 вариантов.
Шифрование с помощью магических квадратов. В средние века для шифрования перестановкой применялись и магические квадраты. Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.
Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток. Если затем выписать содержимое такой таблицы по строкам, то получится шифртекст, сформированный благодаря перестановке букв исходного сообщения.
Пример магического квадрата и его заполнения сообщением "ПРИЛЕТАЮ ВОСЬМОГО " показан на рис. 1.6.
Рис. 1.6. Пример магического квадрата 4х4 и его заполнение сообщением
Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид: "ОИРМ ЕОСЮ ВТАЪ ЛГОП ".
Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3x3 (если не учитывать его повороты). Количество магических квадратов 4x4 составляет уже 880, а количество магических квадратов 5x5 – около 250000.
Магические квадраты средних и больших размеров могли служить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную перебор всех вариантов для такого шифра.
Широкое распространение получила разновидность маршрутной перестановки - вертикальная перестановка. В этом шифре также используется прямоугольная таблица, в которую сообщение записывается по строкам слева направо. Выписывается шифрограмма по вертикалям, при этом столбцы выбираются в порядке, определяемом ключом.
ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки
КЛЮЧ: (3, 1, 4, 2, 5)
КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео
Заполнять последнюю строку таблицы «нерабочими» буквами нецелесообразно, так как криптоаналитик, получивший данную криптограмму, получает сведения о длине числового ключа .
Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:
Количество столбцов в таблице фиксируется и определяется длиной ключа;
Маршрут вписывания - строго слева-направо сверху-вниз;
Шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).
Рис.5.5. Пример использования шифра вертикальной перестановки
В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3.
При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ».
(см. также )
Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона "Математическая теория связи".
В своей работе "Теория связи в секретных системах" Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания .
В качестве первичного признака, по которому проводится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в шифртексте, то соответствующий шифр относится к классу шифров замены . Если буквы открытого текста при шифровании лишь меняются местами друг с другом, то мы имеем дело с шифром перестановки . С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помощью другого шифра.
Рис.
6.1.
Всевозможные такие композиции различных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами . Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки ( рис. 6.1).
6.3 Шифры перестановки
Шифр
перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр
"Сцитала". Обычно открытый текст
разбивается на отрезки равной длины и каждый отрезок
шифруется независимо. Пусть, например, длина
отрезков равна и - взаимнооднозначное отображение
множества
в себя. Тогда шифр
перестановки действует так: отрезок
открытого текста преобразуется в отрезок
шифрованного текста.
Классическим примером такого шифра является система, использующая карточку с отверстиями - решетку , которая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. При зашифровке буквы сообщения вписываются в эти отверстия. При расшифровке сообщение вписывается в диаграмму нужных размеров, затем накладывается решетка, после чего на виду оказываются только буквы открытого текста.
Также возможны и другие варианты шифра перестановки, например, шифры столбцовой и двойной перестановки.
6.3.1 Шифр столбцовой перестановки
При расшифровывании буквы шифртекста записываются по столбцам в соответствии с последовательностью чисел ключа, после чего исходный текст считывается по строкам. Для удобства запоминания ключа применяют перестановку столбцов таблицы по ключевому слову или фразе, всем символам которых ставятся в соответствие номера, определяемые порядком соответствующих букв в алфавите.
При решении заданий на криптоанализ шифров перестановки необходимо восстановить начальный порядок следования букв текста. Для этого используется анализ совместимости символов, в чем может помочь таблица сочетаемости (см. ).
| Г | С | Слева | Справа | Г | С | |
|---|---|---|---|---|---|---|
| 3 | 97 | л, д, к, т, в, р, н | А | л, н, с, т, р, в, к, м | 12 | 88 |
| 80 | 20 | я, е, у, и, а, о | Б | о, ы, е, а, р, у | 81 | 19 |
| 68 | 32 | я, т, а, е, и, о | В | о, а, и, ы, с, н, л, р | 60 | 40 |
| 78 | 22 | р, у, а, и, е, о | Г | о, а, р, л, и, в | 69 | 31 |
| 72 | 28 | р, я, у, а, и, е, о | Д | е, а, и, о, н, у, р, в | 68 | 32 |
| 19 | 81 | м, и, л, д, т, р, н | Е | н, т, р, с, л, в, м, и | 12 | 88 |
| 83 | 17 | р, е, и, а, у, о | Ж | е, и, д, а, н | 71 | 29 |
| 89 | 11 | о, е, а, и | 3 | а, н, в, о, м, д | 51 | 49 |
| 27 | 73 | р, т, м, и, о, л, н | И | с, н, в, и, е, м, к, з | 25 | 75 |
| 55 | 45 | ь, в, е, о, а, и, с | К | о, а, и, р, у, т, л, е | 73 | 27 |
| 77 | 23 | г, в, ы, и, е, о, а | Л | и, е, о, а, ь, я, ю, у | 75 | 25 |
| 80 | 20 | я, ы, а, и, е, о | М | и, е, о, у, а, н, п, ы | 73 | 27 |
| 55 | 45 | д, ь, н, о, а, и, е | Н | о, а, и, е, ы, н, у | 80 | 20 |
| 11 | 89 | р, п, к, в, т, н | О | в, с, т, р, и, д, н, м | 15 | 85 |
| 65 | 35 | в, с, у, а, и, е, о | П | о, р, е, а, у, и, л | 68 | 32 |
| 55 | 45 | и, к, т, а, п, о, е | Р | а, е, о, и, у, я,ы, н | 80 | 20 |
| 69 | 31 | с, т, в, а, е, и, о | С | т, к, о, я, е, ь, с, н | 32 | 68 |
| 57 | 43 | ч, у, и, а, е, о, с | Т | о, а, е, и, ь, в, р, с | 63 | 37 |
| 15 | 85 | п, т, к, д, н, м, р | У | т, п, с, д, н, ю, ж | 16 | 84 |
| 70 | 30 | н, а, е, о, и | Ф | и, е, о, а, е, о, а | 81 | 19 |
| 90 | 10 | у, е, о, а, ы, и | X | о, и, с, н, в, п, р | 43 | 57 |
| 69 | 31 | е, ю, н, а, и | Ц | и, е, а, ы | 93 | 7 |
| 82 | 18 | е, а, у, и, о | Ч | е, и, т, н | 66 | 34 |
| 67 | 33 | ь, у, ы, е, о, а, и, в | Ш | е, и, н, а, о, л | 68 | 32 |
| 84 | 16 | е, б, а, я, ю | Щ | е, и, а | 97 | 3 |
| 0 | 100 | м, р, т, с, б, в, н | Ы | Л, х, е, м, и, в, с, н | 56 | 44 |
| 0 | 100 | н, с, т, л | Ь | н, к, в, п, с, е, о, и | 24 | 76 |
| 14 | 86 | с, ы, м, л, д, т, р, н | Э | н, т, р, с, к | 0 | 100 |
| 58 | 42 | ь, о, а, и, л, у | Ю | д, т, щ, ц, н, п | 11 | 89 |
| 43 | 57 | о, н, р, л, а, и, с | Я | в, с, т, п, д, к, м, л | 16 | 84 |
При анализе сочетаемости букв друг с другом следует иметь в виду зависимость появления букв в открытом тексте от значительного числа предшествующих букв. Для анализа этих закономерностей используют понятие условной вероятности.
Систематически вопрос о зависимости букв алфавита в открытом тексте от предыдущих букв исследовался известным русским математиком А.А. Марковым (1856-1922). Он доказал, что появления букв в открытом тексте нельзя считать независимыми друг от друга. В связи с этим А.А. Марковым отмечена еще одна устойчивая закономерность открытых текстов, связанная с чередованием гласных и согласных букв. Им были подсчитаны частоты встречаемости биграмм вида гласная-гласная (г, г ), гласная-согласная (г, с ), согласная-гласная (с, г ), согласная-согласная (с, с ) в русском тексте длиной в знаков. Результаты подсчета отражены в следующей таблице:
| Г | С | Всего | |
| Г | 6588 | 38310 | 44898 |
| С | 38296 | 16806 | 55102 |
Пример 6.2 Открытый текст, сохраняя пробелы между словами, записали в таблицу. Начало было в первой строке, текст записывали слева направо, переходя со строки на следующую, шифрование заключалось в перестановке столбцов. Найдите открытый текст.
Шифрованный текст:
| Д | В | Ы | Т | ||
| Г | О | Е | Р | О | |
| У | Ь | Д | У | Б | |
| М | М | Я | Ы | Р | П |
Решение. Присвоим столбцам номера в порядке их следования. Наша задача - найти такой порядок столбцов, при котором текст будет осмысленным.
Составим таблицу:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | Х | |||||
| 2 | Х | |||||
| 3 | Х | |||||
| 4 | Х | |||||
| 5 | Х | |||||
| 6 | Х |
Клетка (, ) в этой таблице означает, что столбец с номером следует за столбцом с номером . Знаком "Х" отметим невозможные случаи.
Сочетания столбцов 1, 2 и 5, 2 невозможны, так как гласная не может находиться перед мягким знаком. Невозможны и следования столбцов 2, 1 и 2, 5. Теперь из третьей строки следует, что 1, 5 и 5, 1 невозможны, так как УУ - нехарактерная для русского языка биграмма. Далее, два пробела подряд не могут быть в тексте, значит, ставим "Х" в клетках 3, 4 и 4, 3. Снова обратимся к третьей строке. Если бы столбец 2 следовал за столбцом 4, то слово начиналось бы с мягкого знака. Ставим "Х" в клетке 4, 2. Из первой строки: невозможна комбинация 4, 5, невозможна и 3, 5. Итог наших рассуждений представлен в таблице:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | Х | Х | Х | |||
| 2 | Х | Х | Х | |||
| 3 | Х | Х | Х | |||
| 4 | Х | Х | Х | Х | ||
| 5 | Х | Х | Х | |||
| 6 | Х |
Итак, после столбца 6 обязательно следует столбец 5. Но тогда поставим "Х" в клетке 6, 2 и получим: столбец 2 следует за столбцом 3. Далее, мы вычеркнули 5, 1 и 2, 1, следовательно, надо проверить варианты: ...6532... и...65432... . Но (4, 3) вычеркнуто ранее. Итак, остались варианты расположения столбцов:
- 1, 6, 5, 3, 2, 4
- 6, 5, 3, 2, 4, 1
- 4, 1, 6, 5, 3, 2
- 1, 4, 6, 5, 3, 2
Запишем 6, 5, 3, 2 столбцы подряд:
| 6 | 5 | 3 | 2 |
| т | ы | - | в |
| о | р | о | г |
| б | у | д | ь |
| п | р | я | м |
Попытка поставить столбец 1 перед столбцом 6 приведет к биграмме МП в последней строке и сочетанию ДТЫ в первой. Остались варианты: 653241, 146532.
Ответ: 653241 - ключ, открытый текст: ты\_в\_дороге\_будь\_упрямым (строка из популярной в 1970-е годы песни).
Приведем еще один пример криптоанализа шифра столбцовой перестановки.
Пример 6.3 Расшифровать: СВПООЗЛУЙЬСТЬ\_ЕДПСОКОКАЙЗО
Решение. Текст содержит 25 символов, что позволяет записать его в квадратную матрицу 5х5. Известно, что шифрование производилось по столбцам, следовательно, расшифровывание следует проводить, меняя порядок столбцов.
Шифр перестановки «скитала». В V в. до н.э. правители греческого государства Спарты имели хорошо отработанную систему секретной военной связи и шифровали свои послания с помощью скитала, первого простейшего криптографического устройства, реализующего метод простой перестановки (рис. 1.6).
Рис. 1.6.
Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску кожи и писали на ней вдоль стержня несколько строк текста сообщения. Затем снимали со стержня полоску - буквы на ней оказывались расположенными вразнобой.
Вестник обычно прятал сообщение, используя кожаную полосу как пояс, т.е. кроме шифрования применяли также и стеганографию. Чтобы получить исходное сообщение, полоску кожи надо намотать вокруг скиталы того же диаметра. Ключом этого шифра является диаметр стержн я - с к итал ы. Зная только вид шифра, но не имея ключа, расшифровать сообщение непросто. Шифр «скитала» многократно совершенствовался в последующие времена.
Способ взлома этого шифра предложен Аристотелем. Надо изготовить длинный конус и, начиная с основания, обертывать его лентой с шифрованным сообщением, постепенно сдвигая к вершине. В какой-то момент начнут просматриваться куски сообщения. Диаметр конуса в этом месте соответствует диаметру скиталы.
Шифрующие таблицы. Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования в простейшем варианте сходен с шифром «скитала». Например, текст сообщение записывается в таблицу определенного размера в столбик, а считывается но строкам.
Запишем фразу «Терминатор прибывает седьмого в полночь» в таблицу размером 5x7 (рис. 1.7) но столбцам. Выписав текст из таблицы построчно, получим шифр: «тннвеглеарадонртиеьвомобтмнчирысооь».
Рис. 1.7.
Отправитель и получатель сообщения должны заранее условиться об общем ключе в виде размера таблицы. При расшифровке действия выполняют в обратном порядке (построчная запись, чтение по столбцам).
Этот шифр может быть несколько усложнен: например, столбцы могут быть переставлены в некоторой последовательности, определяемой ключом. Возможна двойная перестановка - столбцов и строк.
Решетка Кардано. Решетка Кардано (поворотная решетка) - это прямоугольная или квадратная карточка с четным числом строк и столбцов 2k X 2т. В ней проделаны отверстия таким образом, что при последовательном отражении или поворачивании и заполнении открытых клеток карточки постепенно будут заполнены все клетки листа.
Карточку сначала отражают относительно вертикальной оси симметрии, затем - относительно горизонтальной оси, и снова - относительно вертикальной (рис. 1.8).
Если решетка Кардано - квадратная, то возможен и другой вариант ее преобразований - поворот на 90° (рис. 1.9).
Рис. 1.8.
Рис. 1.9.
При записи обычным способом (слева направо и сверху вниз) словосочетания «шифрование текста» (без пробелов) в свободные клетки поворотной решетки, изображенной на рис. 1.9, получим текст в виде таблицы (рис. 1.10), или, записав текст в одну строку, - «кшииоесвтафатрен».
Рис. 1.10.
Получатель должен знать трафарет и наложить его в той же последовательности, что и при шифровании. Ключом является выбранный тип перемещения решетки (отражение или поворот) и трафарет - расположение отверстий, которые для квадратной решетки размером 2т х 2к могут быть выбраны 4""* способами (с учетом начальной ориентации трафарета). В этом случае среди трафаретов, считающихся различными, будут встречаться такие, которые являются зеркальным отражением или поворотами других трафаретов, т.е. трафареты, различающиеся только начальным расположением (ориентацией). Если пренебречь начальным расположением трафарета, то, очевидно, различных трафаретов будет в 4 раза меньше - 4""*"
Например, для решеток размером 4X4 существует 256 возможных вариантов трафарета (с учетом начальной ориентации) или всего 64 различных трафаретов.
Несмотря на то, что число трафаретов для больших решеток достаточно велико (порядка 4 млн (4- 10 е)), оно все же существенно меньше, чем случайных перестановок элементов таблицы, число которых равно (2т? 2k).
Например, для таблицы размером 4x4 число случайных перестановок составляет порядка 2 ? 10 13 , а для таблиц размером 8x8 - около 10 89 .
Решетки Кардано, так же как и шифрующие таблицы, являются частными случаями шифра маршрутной перестановки.
