Шифр перестановки «скитала». В 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 .
Решетки Кардано, так же как и шифрующие таблицы, являются частными случаями шифра маршрутной перестановки.
Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов. Рассмотрим некоторые наиболее часто встречающиеся разновидности этого метода, которые могут быть использованы в автоматизированных системах.
Самая простая перестановка - написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы:
ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ,
получится такой шифртекст:
ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП
В последней группе (пятерке) не хватает одной буквы. Значит, прежде чем шифровать исходное выражение, его следует дополнить незначащей буквой (например, О) до числа, кратного пяти:
ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.
Тогда шифрограмма, несмотря на столь незначительное изменение, будет выглядеть по-другому:
ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП
Кажется ничего сложного, но при расшифровке возникнут серьезные неудобства.
Во время Гражданской войны в США использовался был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки ничего не значащими буквами).
После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:
ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП
Вариант этого шифра: сначала исходную фразу записать в столбики:
Потом разбить строки на пятерки букв:
ПСЬУЕ ТКАМХ ТЛАВД УТБДТ АККЫО ЕИБГЕ
Если строки укоротить, а их количество увеличить, то получится прямоугольник-решетка, в который можно записывать исходный текст. Но тут уже требуются предварительные договоренности между адресатом и отправителем посланий, поскольку сама решетка может быть различной длины-высоты, записывать в нее можно по строкам, по столбцам, по спирали туда или по спирали - обратно, можно писать и по диагоналям, а для шифрования можно брать тоже различные направления. В общем, вариантов масса.
Для примера возьмем решетку 6х6 (причем количество строк может увеличиваться или уменьшаться в зависимости от длины исходного сообщения) и заполним ее по строкам:
Если шифровать по стрелкам (диагоналям) сверху вниз с левого верхнего угла, то в итоге получится такая шифрограмма:
П УУ СДК ТЕКХ ЬТАОА БТКТБМ АМЕВЛ ЫЛГК ИДИ ЕЗ Ж
Для окончательного оформления шифртекст может быть разбит на группы по 6 символов:
ПУУСДК ТЕКХЬТ АОАБТК ТБМАМЕ ВЛЫЛГК ИДИЕЗЖ
Очень часто используют перестановки с ключом. Тогда правила заполнения решетки и шифрования из нее упрощаются, становятся стандартными. Единственное, что надо помнить и знать - это ключ, которым может быть любое слово, например, РАДИАТОР. В соответствии с расположением букв в алфавите, буква А получает номер 1, вторая буква А - 2, следующая по алфавиту буква Д - 3, потом И - 4, О – 5; первая буква Р - 6, вторая Р - 7 и буква Т - 8. Заполняем решетку:
Записываем столбики в соответствии с номерами букв ключа:
УТЫ ЬКТ СТХ ТАО УАЛ ПЕМО ДКИ БКЕ
Затем последовательность опять разбивается на пятерки:
УТЫЬК ТСТХТ АОУАЛ ПЕМОД КИБКЕ
Таким шифром простой перестановки колонок пользовались немецкие секретные агенты во время Второй мировой войны. В качестве ключа они использовали первые буквы строк на определенной странице какой-нибудь обыкновенной книги.
Развитием этого шифра является шифр перестановки колонок с пропусками, которые располагаются в решетке тоже в соответствии с ключом (в нашем случае через 6-1-3-4-2-8-5-7 ... символов):
Шифрограмма будет такой:
УДК Ь СЕХЛ ТТОМ АЕП ПКИ УКЛР БТТО
Из рассмотренных примеров видно, что все процедуры шифрования и расшифрования по методу перестановок являются в достаточной степени формальными и могут быть реализованы алгоритмически.
Шифры перестановки
Этот метод заключается в том, что символы шифруемого текста переставляются по определенным правилам внутри шифруемого блока символов, т.е. преобразования приводят к изменению только порядка следования символов исходного сообщения. Рассмотрим некоторые наиболее часто встречающиеся разновидности этого метода - простую, усложненную по таблице и усложненную по маршрутам перестановку.
Шифрование простой перестановкой (вертикальной перестановкой) осуществляется следующим образом:
1) выбирается ключевое слово с неповторяющимися символами;
2) шифруемый текст записывается последовательными строками под символами ключевого слова;
3) зашифрованный текст выписывается колонками в той последовательности, в которой располагаются в алфавите буквы ключа (или в порядке следования цифр в натуральном ряду, если ключ цифровой).
В качестве иллюстрации приведем пример шифрования способом простой перестановки сообщения: «БУДЬТЕ ОСТОРОЖНЫ С ПРЕДСТАВИТЕЛЕМ ФИРМЫ "ФЕНИКС". При этом применим цифровой ключ 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. В исходном тексте вместо пробелов используется буква а.
| Б | У | Д | Ь | Т | Е | а | О |
| С | Т | О | Р | О | Ж | Н | Ы |
| А | С | а | П | Р | Е | Д | С |
| Т | А | В | И | Т | Е | Л | Е |
| М | а | Ф | И | Р | М | Ы | а |
| Ф | Е | Н | И | К | С | а | а |
Выписывая текст по колонкам и группируя символы по пять, получаем зашифрованный текст в виде:
ДО ВФ НОЫСЕ ЬРП ИИИЕЖ ЕЕМСБ С ТМФ НДЛЫ TOPT РКУТС A E .
Расшифрование выполняется в следующем порядке:
1) подсчитываем число знаков в зашифрованном тексте и делим на число знаков ключа;
2) выписываем ключевое слово и под его знаками в соответствующей последовательности выписываем символы зашифрованного текста в определенном выше количестве;
3) по строкам таблицы читаем исходный текст.
Число ключей не более m!, где m - число столбцов таблицы.
Слабость шифрования простой перестановкой обуславливается тем, что при большой длине шифруемого текста в зашифрованном тексте могут проявиться закономерности символов ключа. Для устранения этого недостатка можно менять ключ после зашифровки определенного числа знаков. При достаточно частой смене ключа стойкость шифрования можно существенно повысить. При этом, однако, усложняется организация процесса шифрования и расшифрования.
Для получения и запоминания числового ключа существуют различные методы. Один из самых распространенных состоит в том, чтобы приписывать буквам числа в соответствии с алфавитным порядком букв. Возьмем, например, слово ПЕРЕСТАНОВКА. Присутствующая в нем буква А получает №1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы А получает №2. Буквы Б в этом слове нет, то буква В получает №3, и т.д.:
| П | Е | Р | Е | С | Т | А | Н | О | В | К | А |
Усложнение перестановки по таблице заключается в том, что для записи символов шифруемого текста используется специальная таблица, в которую введены некоторые усложняющие элементы. Усложнение состоит в том, что определенное число клеток таблицы не используется (на рисунке они пусты). Количество и расположение неиспользуемых элементов является дополнительным ключом шифрования. Шифруемый текст блоками по m х n – s элементов (m х n – размеры таблицы,s – число неиспользуемых элементов) записывается в таблицу. Далее шифрование аналогична простой перестановке.
| Б | У | Д | Ь | Т | Е | а | О | С | |
| Т | О | Р | О | Ж | Н | Ы | а | ||
| С | а | О | Р | Е | Д | С | Т | А | |
| В | И | Т | Е | Л | Е | М | а | Ф | |
| И | Р | М | Ы | а | Ф | Е | Н | И | |
| К | С | а | а | а | а | А | а | а |
Зашифрованный текст будет выглядеть так: ДОПР БСВИК РРТМ ОЫ Н ЕНСЕФ УТ И СС АФ И ЬОЕ ЕЫ Т МЕ ТЖ ДЛ .
При расшифровании знаки зашифрованного текста записываются столбцами таблицы в последовательности знаков ключа с пропуском неиспользуемых элементов. Исходный текст считывается по строкам. Варьируя размерами таблицы, последовательностью символов ключа, количеством и расположением неиспользуемых элементов, можно получить требуемую стойкость зашифрованного текста.
Еще один вариант - шифр "Поворотная решетка" . предназначен для сообщений длины 4mk. Берется трафарет размером 2m*2k клеток, вырезается m*k клеток так, что при наложении его на лист бумаги того же размера 4 различными способами (поворачивая на 90°) его вырезы полностью покрывают всю площадь листа. Буквы сообщения последовательно вписываются в вырезы трафарета по строкам, в каждой строке слева направо, при каждом из 4-х его возможных положений в заранее установленном порядке. Число возможных трафаретов, т.е. количество ключей этого шифра составляет 4 mk (при размере трафарета 8*8 число вариантов превосходит 4 миллиарда).
Весьма высокую стойкость шифрования можно обеспечить усложнением перестановок по маршрутам типа гамильтоновских. При этом для записи символов шифруемого текста используются вершины некоторого гиперкуба, а знаки зашифрованного текста считываются по маршрутам Гамильтона, причем используется несколько различных маршрутов. Для примера рассмотрим шифрование по маршругам Гамильтона при n =3. Структура и три маршрута показаны на Рис. 7, а пример шифрования – на Рис. 8.объемной (многомерной) перестановки . В 1992 – 94 гг. идея применения объемной перестановки для шифрования открытого текста получила дальнейшее развитие. Усовершенствованная схема перестановок по принципу кубика Рубика, в которой наряду с открытым текстом перестановке подвергаются и функциональные элементы самого алгоритма шифрования, легла в основу системы «Рубикон». В качестве прообразов пространственных многомерных структур, на основании объемных преобразований которых осуществляются перестановки, в ней используются трехмерный куб и тетраэдр.
Шифр, преобразования из которого изменяют только порядок следования символов исходного текста, но не изменяют их самих, называется шифром перестановки
Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью таблицы
где номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, номер места для второй буквы и т. д. В верхней строке таблицы выписаны по порядку числа от 1 до а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени
Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка
и в соответствии с ней зашифровывается слово то получится Попробуйте расшифровать сообщение полученное в результате преобразования с помощью указанной выше подстановки.
В качестве упражнения читателю предлагается самостоятельно выписать подстановки, задающие преобразования в описанных ниже трех
примерах шифров перестановки. Ответы помещены в конце раздела.
Читатель, знакомый с методом математической индукции, может легко убедиться в том, что существует (обозначается читается факториал») вариантов заполнения нижней строки таблицы (6). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины меньше либо равно (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!).
С увеличением числа значение растет очень быстро. Приведем таблицу значений для первых 10 натуральных чисел:
(см. скан)
При больших для приближенного вычисления можно пользоваться известной формулой Стирлинга
Примером ШП, предназначенного для зашифрования сообщений длины является шифр, в котором в качестве множества ключей взято множество всех подстановок степени а соответствующие им преобразования шифра задаются, как было описано выше. Число ключей такого шифра равно
Для использования на практике такой шифр не удобен, так как при больших значениях приходится работать с длинными таблицами.
Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного «маршрута», а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.
Зашифруем, например, указанным способом фразу:
используя прямоугольник размера
(см. скан)
Зашифрованная фраза выглядит так:
Теоретически маршруты могут быть значительно более изощренными, однако запутанность маршрутов усложняет использование таких шифров.
Ниже приводятся описания трех разновидностей шифров перестановки, встречавшихся в задачах олимпиад.
Шифр «Сцитала». Одним из самых первых шифровальных приспособлений был жезл («Сцитала»), применявшийся еще во времена войны Спарты против Афин в V веке до н. э. Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения.
Шифр «Сцитала», как видно из решения задачи 2.1, реализует не более перестановок по прежнему, - длина сообщения). Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения.
Имеются еще и чисто физические ограничения, накладываемые реализацией шифра «Сцитала». Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв Таким образом, число перестановок, реализуемых «Сцита-лой», вряд ли превосходит 32.
Шифр «Поворотная решетка». Для использования шифра, называемого поворотной решеткой, изготавливается трафарет из прямоугольного листа клетчатой бумаги размера клеток. В трафарете вырезано тк клеток так, что при наложении его на чистый лист бумаги того же размера четырьмя возможными способами его вырезы полностью покрывают всю площадь листа.
Буквы сообщения последовательно вписываются в вырезы трафарета (по строкам, в каждой строке слева направо) при каждом из четырех его возможных положений в заранее установленном порядке.
Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка приведенная на рис. 1.
Зашифруем с ее помощью текст
Наложив решетку на лист бумаги, вписываем первые 15 (по числу
вырезов) букв сообщения: Сняв решетку, мы увидим текст, представленный на рис. 2. Поворачиваем решетку на 180°. В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. 3. Затем переворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. 4, 5).
Получатель сообщения, имеющий точно такую же решетку, без труда прочтет исходный текст, наложив решетку на шифртекст по порядку четырьмя способами.
Можно доказать, что число возможных трафаретов, то есть количество ключей шифра «решетка», составляет (см. задачу 1.1). Этот шифр предназначен для сообщений длины Число всех перестановок в тексте такой длины составит что во много раз
больше числа Однако, уже при размере трафарета число возможных решеток превосходит 4 миллиарда.
Широко распространена разновидность шифра маршрутной перестановки, называемая «шифром вертикальной перестановки» (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,4,1,7,2,6,3), и с его помощью надо зашифровать сообщение:
Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:
(см. скан)
Теперь, выбирая столбцы в порядке, заданном ключом, и выписывая последовательно буквы каждого из них сверху вниз, получаем такую криптограмму:
Число ключей ШВП не более где число столбцов таблицы. Как правило, гораздо меньше, чем длина текста (сообщение укладывается в несколько строк по букв), а, значит, и много меньше
Пользуясь приведенной выше формулой Стирлинга при больших попытайтесь оценить, во сколько раз число возможных перестановок столбцами меньше числа всех перестановок на тексте длины кратном
В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех
пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ:
Перейдем к вопросу о методах вскрытия шифров перестановки. Проблема, возникающая при восстановлении сообщения, зашифрованного ШП, состоит не только в том, что число возможных ключей велико даже при небольших длинах текста. Если и удастся перебрать все допустимые варианты перестановок, не всегда ясно, какой из этих вариантов истинный. Например, пусть требуется восстановить исходный текст по криптограмме и нам ничего не известно, кроме того, что применялся шифр перестановки. Какой вариант «осмысленного» исходного текста признать истинным: или А может быть Приведем пример еще более запутанной ситуации. Пусть требуется восстановить сообщение по криптограмме
полученной шифром перестановки. Возможны, как минимум, два варианта исходного сообщения:
Эти варианты имеют прямо противоположный смысл и в имеющихся условиях у нас нет возможности определить, какой из вариантов истинный.
Иногда, за счет особенностей реализации шифра, удается получить информацию об использованном преобразовании (перестановке). Рассмотрим шифр «Сцитала» из задачи 2.1. Выше уже рассматривался вопрос о количестве перестановок, реализуемых «Сциталой». Их оказалось не более 32. Это число невелико, поэтому можно осуществить перебор всех вариантов. При достаточной длине сообщения, мы, скорее всего, получим единственный читаемый вариант текста. Однако, используя информацию о расположении линий, оставленных шифровальщиком, удается определить диаметр стержня, а значит, и возникающую перестановку букв (см. задачу 2.1).
В рассмотренном примере шифровальщик по неосторожности оставил на папирусе следы, позволяющие нам легко прочитать сообщение. Возможны и другие ситуации, когда не очень «грамотное» использование шифра облегчает вскрытие переписки.
В задаче 5.2 содержится пример текста, зашифрованного ШВП. По условию пробелы между словами при записи текста в таблицу опускались. Поэтому заключаем, что все столбцы, содержащие пробел в последней строке, должны стоять в конце текста. Таким образом, возникает разбиение столбцов на две группы (содержащие 6 букв, и
Аналогичная ситуация возникает и при «неполном» использовании шифра «решетка» (см. задачу 4.1). Пусть имеется решетка размера и зашифрованное с ее помощью сообщение длины к, не содержащее пробелов. Незаполненные к мест в решетке при условии, что к соответствуют вырезам в четвертом положении решетки. На основе такой информации, происходит резкое уменьшение числа допустимых решеток (их будет Читателю предлагается самостоятельно подсчитать число допустимых решеток при
На примере решения задачи 5.2 продемонстрируем еще один подход к вскрытию шифров вертикальной перестановки - лингвистический. Он основан на том, что в естественных языках некоторые комбинации букв встречаются очень часто, другие - гораздо реже, а многие вообще не встречаются (например -
Будем подбирать порядок следования столбцов друг за другом так, чтобы во всех строках этих столбцов получались «читаемые» отрезки текста. В приведенном решении задачи восстановление текста начинается с подбора цепочки из трех столбцов первой группы, содержащей в последней строке сочетание так как естественно предположить, что сообщение заканчивается точкой. Далее подбираются столбцы, продолжающие участки текста в других строках, и т. д.
Сочетание лингвистического метода с учетом дополнительной информации довольно быстро может привести к вскрытию сообщения.
В заключение рассказа о шифрах перестановки приведем историю с зашифрованным автографом А. С. Пушкина, описанную в романе В. Каверина «Исполнение желаний».
Главный герой романа - студент-историк Трубачевский, - занимавшийся работой в архиве своего учителя - академика Бауэра С. И., - нашел в одном из секретных ящиков пушкинского бюро фрагмент недописанной X главы «Евгения Онегина». Это был перегнутый вдвое полулист плотной голубоватой бумаги с водяным знаком 1829 года. На листе было написано следующее.
(см. скан)
(см. скан)
Без особых усилий Трубачевский прочитал рукопись, и ничего не понял. Он переписал ее, получилась бессвязная чепуха, в которой одна строка, едва начавшая мысль, перебивается другой, а та - третьей, еще более бессмысленной и бессвязной. Он попробовал разбить рукопись на строфы, - опять не получилось. Стал искать рифмы, - как будто и рифм не было, хотя на белый стих все это мало похоже. Просчитал строку - четырехстопный ямб, размер, которым написан «Евгений Онегин».
Трубачевский с азартом взялся за рукопись, пытался читать ее, пропуская по одной строке, потом по две, по три, надеясь случайно угадать тайную последовательность, в которой были записаны строки. У него ничего не получалось. Тогда он стал читать третью строку вслед за первой, пятую за третьей, восьмую за пятой, предположив, что пропуски должны увеличиваться в арифметической прогрессии. Все то же! Отчаявшись, он бросил эту затею. Однако, она не давала ему покоя ни на лекции, ни в трамвае... Как шахматист, играющий в уме, он не только знал наизусть каждую строчку, он видел ее в десяти комбинациях сразу.
Прошло время. Однажды, когда он смотрел на светлые пятна окон подходящего к перрону поезда, каким-то внутренним зрением он
увидел перед собой всю рукопись - и с такой необыкновенной отчетливостью, как это бывает только во сне.
(см. также )
Большое влияние на развитие криптографии оказали появившиеся в середине 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. Известно, что шифрование производилось по столбцам, следовательно, расшифровывание следует проводить, меняя порядок столбцов.
