Шифры перестановки. Классические шифры перестановки

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

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки

КЛЮЧ: (3, 1, 4, 2, 5)

КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео

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

Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:

Количество столбцов в таблице фиксируется и определяется длиной ключа;

Маршрут вписывания - строго слева-направо сверху-вниз;

Шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).

Рис.5.5. Пример использования шифра вертикальной перестановки

В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3.

При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ».

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

Пример (маршрутной перестановки)

Зашифруем указанным выше способом фразу пример маршрутной перестановки, используя прямоугольную таблицу размером 4х7:

п	р	и	м	е	р	м
н	т	у	р	ш	р	а
о	й	п	е	р	е	с
и	к	в	о	н	а	т

Зашифрованная фраза выглядит следующим образом:

мастаеррешрноермиупвкйтрпнои

Обращение описанных шагов при расшифровании не представляет труда.

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

Пример (вертикальной перестановки)

Зашифруем фразу вот пример шифра вертикальной перестановки, используя прямоугольник размером 6 х 7 и числовой ключ (5,1,4,7,2,6,3).

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

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

ореьекрфийамааеотшрнсивевлрвиркпнпитот

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

В нашем примере 38=7×5+3, поэтому в заполненной таблице имеется 3 длинных и 4 коротких столбца.

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

Блочные шифры

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

Одноключевые блочные шифры подразделяются на 3 группы:

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

Шифры замены (подстановки)

Составные шифры.

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

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

Пример простейшего шифра перестановки представлен на рис. 5.5.

Рис. 5.5. Простейший шифр перестановки.

Как видно из рис. 5.5, для того чтобы зашифровать сообщение «ЮСТАС АЛЕКСУ ВСТРЕЧАЙТЕ СВЯЗНОГО», последнее необходимо записать в виде таблицы, состоящей, например, их 5 строк и 6 столбцов. Текст сообщения записывается по столбцам, исключая пробелы. Если последний столбец оказывается неполным, он заполняется произвольно любыми буквами. Для получения зашифрованного сообщения исходный текст считывается построчно (слева направо) и записывается группами, например, по 5 цифр. Последняя

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

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

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

«ЗАСЕДАНИЕ СОСТОИТСЯ ЗАВТРА ЮСТАС».

Для шифрования этого открытого текста запишем его без пробелов (участие последних в процедуре шифрования, из-за их высокой частоты повторения, значительно ослабляет криптостойкость шифра) и выберем ключ шифрования, например, 245 136. Согласно этому ключу, состоящему из 6 цифр, поделим все информационное сообщение на блоки, каждый из которых будет содержать по 6 букв текста. После деления на блоки у нас получилось 4 блока, содержащих по 6 букв в каждом, и 1 блок - по 5 букв. В таких случаях последняя группа букв исходного сообщения произвольно дополняется различными символами до получения полного блока. В нашем случае не достает только одной буквы, поэтому выбираем любую букву, например Ъ, и добавляем ее в конце пятого блока.

Рис. 5.6. Шифр простой перестановки

Далее, используя ключ 245 136, производится перестановка букв исходного открытого текста. Например, первая цифра ключа - 2, указывает на то, что в новом блоке первой буквой зашифрованного текста будет вторая буква блока открытого текста, вторая цифра ключа - 4, показывает, что вторая буква шифротекста - это четвертая буква в блоке открытого текста и т. д.

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

Для упрощения запоминания ключа обычно используется ключевое слово. В данном случае - это слово «КОРЕНЬ». В нем цифре 1 ключа соответствует буква Е, так как она первой из всех букв этого слова встречается в нашем алфавите, цифре 2 - буква К (по той же причине) и т. д.

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

Рис. 5.7. Шифрование с помощью таблицы

Основным недостатком данного шифра является его невысокая криптостойкость. Разложив зашифрованный текст на множители (не так уж много получается вариантов), можно легко определить вероятную длину кодового слова, которое использовалось при шифровании.

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

Шифр простой перестановки с использованием свойств таблиц, называемых магическими квадратами (рис. 5.8), использовался еще в средние века. Магическими квадратами называются равносторонние таблицы, все клетки которых заполнены натуральными числами, начиная от 1. Причем эти числа в сумме дают по каждому столбцу, по каждой строке и по диагоналям магического квадрата одно и тоже число (в нашем случае - это число 34). Исходный текст - ЖДУ ВСТРЕЧИ ЮСТАС, при заполнении магического квадрата, вписывается по порядку следования натуральных чисел, например, число 1 заменялось 1 буквой исходного текста (Ж), число 12 - 12 буквой сообщения (С) и т.п. После записи открытого текста содержимое таблицы считывается по строкам в результате чего и получался шифротскст с перестановкой букв.

Рис. 5.8. Магический квадрат

Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного ``маршрута"", а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой .

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

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

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

Шифр ``Сцитала"" .

Одним из самых первых шифровальных приспособлений был жезл (``Сцитала""), применявшийся еще во времена войны Спарты против Афин в 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

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

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

История

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

Одно из древнейших известных нам шифровальные устройство - Скитала. Бесспорно известно, что скитала использовалась в войне Спарты против Афин в конце V века до н. э.

Прародителем анаграммы считают поэта и грамматика Ликофрона, который жил в Древней Греции в III веке до н. э. Как сообщал византийский автор Иоанн Цец, из имени царя Птоломея он составил первую из известных нам анаграмм: Ptolemaios - Аро Melitos, что в переводе означает «из мёда», а из имени царицы Арсинои - как «Ion Eras » (фиалка Геры).

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

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

1 {\displaystyle 1}	2 {\displaystyle 2}	3 {\displaystyle 3}	...	n {\displaystyle n}
I 1 {\displaystyle I_{1}}	I 2 {\displaystyle I_{2}}	I 3 {\displaystyle I_{3}}	...	I n {\displaystyle I_{n}}

Первая строка - позиция символа в открытом тексте, вторая строка - позиция в шифрограмме. Таким образом, при длине сообщения n {\displaystyle n} символов существует ровно n ! {\displaystyle n!\ } ключей.

Шифры маршрутной перестановки

Широкое распространение получили так называемые маршрутные перестановки, использующие некоторую геометрическую фигуру (плоскую или объемную). Преобразования состоят в том, что отрезок открытого текста записывается в такую фигуру по некоторой траектории, а выписывается по другой траектории. Пример данного шифра - шифр Скиталы.

Шифр табличной маршрутной перестановки

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

п	р	и	м	е
р	м	а	р	ш
р	у	т	н	о
й	п	е	р	е
с	т	а	н	о
в	к	и

КРИПТОГРАММА: ешоеомрнрниатеаирмупткпррйсв

Обращение описанных шагов не представит труда при расшифровании.

Шифр вертикальной перестановки

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки

КЛЮЧ: (3, 1, 4, 2, 5)


п	р	и	м	е
р	м	а	р	ш
р	у	т	н	о
й	п	е	р	е
с	т	а	н	о
в	к	и

КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео

Шифр «поворотная решётка

В 1550 году итальянский математик Джероламо Кардано (1501-1576) в книге «О тонкостях» предложил новую технику шифрования сообщений - решётку.

Изначально решётка Кардано представляла собой трафарет с отверстиями, в которые записывали буквы, слоги или слова сообщения. Затем трафарет убирали, а свободное место заполняли более или менее осмысленным текстом. Такой метод сокрытия информации относится к стеганографии.

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

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

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

Шифрограмму выписывают из получившейся таблицы по определённому маршруту. Ключом являются трафарет, маршрут вписывания и порядок поворотов.

Данный метод шифрования использовался для передачи секретной информации нидерландскими правителями в 1740-х годах. Во время Первой мировой войны армия кайзера Вильгельма использовала шифр «поворотная решётка». Немцы использовали решётки разных размеров, однако очень недолго (четыре месяца), к огромному разочарованию французских криптоаналитиков, которые только-только начали подбирать к ним ключи. Для решёток разных размеров французы придумали собственные кодовые имена: Анна (25 букв), Берта (36 букв), Дора (64 буквы) и Эмиль (81 буква).