No Image

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

СОДЕРЖАНИЕ
1 просмотров
22 января 2020

Наибольшее распространение получили шифры маршрутной перестановки, основанные на таблицах.

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

Например, исходное сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» вписывается в прямоугольную таблицу размерами 4х6, маршрут вписывания – слева-направо сверху-вниз, маршрут выписывания – сверху-вниз слева-направо. Шифрограмма в этом случае выглядит «АВ_ЕБ_СВРИЕИАЛР ЧМЬГ_ОЯЕ_».

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

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

– маршрут вписывания строго соответствует маршруту, показанному на рис.12;

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

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

Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо.

В примере первая буква Д получает номер 2, вторая Д – 3.

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

Не нашли то, что искали? Воспользуйтесь поиском:

Шифр перестано́вки — это метод симметричного шифрования, в котором элементы исходного открытого текста меняют местами. Элементами текста могут быть отдельные символы (самый распространённый случай), пары букв, тройки букв, комбинирование этих случаев и так далее. Типичными примерами перестановки являются анаграммы. В классической криптографии шифры перестановки можно разделить на два класса:

  • Шифры одинарной (простой) перестановки — при шифровании символы открытого текста перемещаются с исходных позиций в новые один раз.
  • Шифры множественной (сложной) перестановки — при шифровании символы открытого текста перемещаются с исходных позиций в новые несколько раз.

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

Содержание

История [ править | править код ]

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

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

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

Шифры простой перестановки [ править | править код ]

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

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

Шифры маршрутной перестановки [ править | править код ]

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

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

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

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

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

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

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

3 1 4 2 5
п р и м е
р м а р ш
р у т н о
й п е р е
с т а н о
в к и

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

Шифр «поворотная решётка» [ править | править код ]

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

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

Читайте также:  Соковыжималка с цилиндрическим сепаратором

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

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

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

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

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

Шифры сложной перестановки [ править | править код ]

В данном классе шифров перестановки используется идея многократной перестановки символов или повторного шифрования уже зашифрованного сообщения.

Шифр двойной перестановки [ править | править код ]

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

Ключом к шифру являются размер таблицы, маршруты вписывания и выписывания, порядки перестановки столбцов и строк. Если маршруты являются фиксированными величинами, то количество ключей равно n ! m ! <displaystyle n!m!> , где n <displaystyle n> и m <displaystyle m> — количество строк и столбцов в таблице [8] .

3 1 4 2
3 д в о й
2 н а я п
4 е р е с
1 т а н о
5 в к а
1 2 3 4 3 в й д о 2 а п н я 4 р с е е 1 а о т н 5 к в а
1 2 3 4 1 а о т н 2 а п н я 3 в й д о 4 р с е е 5 к в а

Криптоанализ [ править | править код ]

При дешифровании текста используют частотные характеристики открытого текста. Однако для получения устойчивой картины длина послания должна быть существенно больше ключа. Одной из наиболее устойчивых характеристик осмысленного текста является отсутствие запретных биграмм (пара соседних букв). Например, биграммы «Ъ + Ь», «гласная + Ь», «пробел + Ь». Знание и использование частотной диаграммы открытого текста значительно упростит дешифрование шифра перестановки [9] .

Это описание перестановочных шифров для начинающих составителей головоломок.

Простая перестановка

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

Транспозиция

Допустим, у нас есть фраза: «МОЖНО, НО НЕЛЬЗЯ». И мы хотим её зашифровать. Самый простой способ – это записать всю фразу задом наперёд: «ЯЗЬЛЕН ОН, ОНЖОМ». Можно порядок слов в предложении оставить исходным, но каждое слово записать задом наперёд: «ОНЖОМ, ОН ЯЗЬЛЕН». А можно менять местами каждые две буквы: «ОМНЖ,ООНЕНЬЛЯЗ». Это называется «транспозиция» или простая перестановка в чистом виде.

Транспонирование

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

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

Итак, например, нам нужно зашифровать текст «Я памятник себе воздвиг нерукотворный, к нему не зарастёт народная тропа». В нём 72 символа. 72 – удобное число, оно делится без остатка на 2,4,6,8,12,18,24,36, поэтому можно использовать таблицы 2х36, 3х24, 4х18, 6х12, 8х9, 9х8, 12х6, 18х4, 24х3, 36х2 :). Определяемся с ключом (размером таблицы), вписываем текст по строкам, а затем переписываем его по столбцам.

На рисунке выше показаны варианты с таблицами 9×8, 8×9, 4×18 и 18×4. Для третьего варианта (таблица 4×18) получится вот такой текст:

«Ямиеввнкой у атрар якбоиеор,н зс ояопт езгртн енатнд панс д увыкмерёанта (4:18)»

В данном случае я взял текст «как есть», то есть с пропусками между словами и со знаками препинания. Но если текст осмысленный, то знаки препинания и пропуски между словами можно и не использовать.

Штакетник

Упрощённый вариант транспонирования (с двухстрочной таблицей) – «штакетник». Напоминает «по конструкции» забор-шахматку.

Читайте также:  Что делать если нет uefi

Это очень простой способ шифровки, часто применяемый школьниками. Фраза записывается в две строки: в верхней пишутся нечётные буквы, в нижней – чётные. Затем нужно выписать подряд сначала верхнюю строку, затем нижнюю. Такое шифрование легко проделать и в уме, не выписывая сначала две строки.

«Я памятник себе воздвиг нерукотворный» превращается в «ЯАЯНКЕЕОДИНРКТОНЙ ПМТИСБВЗВГЕУОВРЫ».

Скитала

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

Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который и назывался «скитала», наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения. Затем снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположенными хаотично. Для восстановления текста требовалась скитала такого же диаметра.

По сути скитала – это наша обычная плоская таблица, обёрнутая вокруг цилиндра.

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

Сдвиг

Похожий результат можно получить, если буквы сообщения писать через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Ниже пример готовой головоломки, составленной по таким правилам. «Три дробь четыре» – это подсказка, что зашифровано три слова, читать надо каждую четвёртую букву (4-8-12-16-..), по достижению конца переходить снова к началу со сдвигом на 1 букву влево (3-7-11-15-..) и т.д. На рисунке ниже зашифровано «Идите назначенным маршрутом».

Одиночная перестановка по ключу

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

Например, можно сделать головоломку на основе судоку. Разгадывающему даётся текст «-УРОМКУЛО ЬУЁЗЕБЯДЛ НЗЯАТЛЫЙА ЦЬБАДНЕПУ ЕММДНИТОЁ ИЧТЮКЬНОО УНЁЙВЫЧЁС ХИЕПОТОДЦ ПРМГОУИК-» и предлагается решить судоку, в которой одна из строк помечена.

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

Для детей можно использовать этот же метод, но попроще, даже без цифр, а сразу нарисовав порядок перестановки в виде путей.

Двойная перестановка

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

Маршрутная перестановка

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

На рисунке сверху последовательность символов «АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ. » вписана построчно в таблицу 6×6, а затем считана по маршруту, указанному линиями. Получаются следующие шифровки:

А здесь нужно обходить таблицу «ходом коня», причём маршрут уже нарисован, так что это совсем для маленьких 🙂

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

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

А вот загадать этот маршрут можно, например, вот таким стихотворением:

Разгадывать его придётся так: «Алеет Осень» – это А1 (А Один), «Ценными Дарами» – C2 (Цэ Два), «Ещё Один» – E1 (E Один), «Животворящий День» – G2 (Жэ Два) и т.д.

Читайте также:  Утилизация бытовой техники в 2018 году

Перестановка "Волшебный квадрат"

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

В известном ещё в Древнем Китае квадрате Ло-Шу третьего порядка (3×3) константа квадрата 15 повторяется 8 раз:

Кстати, константу нечетного квадрата легко посчитать, умножив среднее число ряда, из которого составлен квадрат, на порядок квадрата. Для квадрата 3-го порядка (3×3) константа равна 123456789*3=15.

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

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

На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3х3, если не принимать во внимание его повороты и отражения. Счёт волшебным квадратам 4-го порядка уже идёт на сотни, 5-го – на сотни тысяч. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени (в Древнем Китае), так как ручной перебор всех вариантов ключа для этого шифра был немыслим.

Есть очень простой метод составления нечётных волшебных квадратов, т.е. размером 3×3, 5×5, 7×7 и т.д. Это метод «террас» или «пирамидок».

Рисуется квадрат нужного размера и к нему пририсовываются ступенчатые «террасы» (обозначены пунктиром). Далее по диагоналям сверху вниз направо квадрат заполняется последовательными числами. После этого «террасы» переносятся внутрь квадрата: правые – налево, левые – направо, верхние – вниз, а нижние – наверх. Получается волшебный квадрат!

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

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

А если использовать метод наоборот, то получится головоломка типа такой.

Чтобы её решить, надо вытащить соответствующие буквы из квадрата в «террасы».

Для квадратов 4×4, 6×6 и т.д. таких простых способов их составления не существует, поэтому проще использовать готовые. Например, квадрат Дюрера.

Вращающаяся решётка

Классическая решётка Кардано позволяет скрыть шифровку внутри мусорного текста и является хорошим примером стеганографии . Но если решётку Кардано использовать в качестве ключа для перестановочного шифра, то получим новый метод шифрования — вращающуюся решётку или сетку.

Решётка — это квадрат размером NxN клеток, некоторые из которых вырезаны. Вырезанные клетки могут касаться друг друга, в том числе вершинами, и даже сторонами. В одной клетке — одна буква. Вырезанные клетки должны располагаться таким образом, чтобы никакие две из них не оказывались в одном и том же месте при поворотах решётки.

При помощи конструктора, изображённого ниже, можно изготовить 4 16 (4 294 967 296) таких решёток. Для этого нужно вырезать строго одно из четырёх повторяющихся чисел. Для шифрования без мусора нужно вырезать все номера от 1 до 16, всего 16 клеток. Для шифрования с мусором некоторые числа можно не вырезать, оставшиеся места после шифрования заполнить любыми произвольными буквами, это и будет мусор.

Использовать полученную решётку надо следующим образом. Положить решётку на бумагу и в вырезанные клетки по одной букве начать вписывать шифруемый текст. Как только 16 букв будет вписано, решётка поворачивается на 90°, и вписываются следующие 16 букв, и так ещё два раза. В результате будет вписано 64 буквы. Если текст был короче, то в оставшиеся на бумаге пустые места нужно вписать произвольные буквы. Более длинный текст можно разбить на части по 64, и шифровать каждую отдельно. А можно вписывать в окошки и по две буквы.

Есть второй способ перекладывания решётки во время шифрования — не поворачивать решётку на 90° три раза, а в первый раз повернуть её на 180°, второй раз перевернуть обратной стороной относительно горизонтальной оси, в третий раз – снова повернуть на 180°.

Это были перестановочные шифры. А теперь можно почитать про Шифры замены .

Комментировать
1 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock detector