Учебное пособие: Криптоанализ классических шифров

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

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

Шифры замены

Большое влияние на развитие криптографии оказали появившиеся в середине XX века работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также был разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 году после публикации работы К. Шеннона «Математическая теория связи» (см. приложение).

В своей работе «Теория связи в секретных системах» Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания.

Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Легко дать математическое описание шифра замены. Пусть X и Y – два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также g: X —> Y — взаимнооднозначное отображение Х в Y. Тогда шифр замены действует так: открытый текст х1х2...хп преобразуется в шифрованный текст g(x1)g(x2)... g(хп).

Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна п и σ — взаимнооднозначное отображение множества {1,2,..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х1...хп преобразуется в отрезок шифрованного текста

Математическая модель шифра замены

Определим модель А =(X,K,Y,E,D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: XA*, YВ*, |А|=п, |В| = т . Здесь и далее С* обозначает множество слов конечной длины в алфавите С.

Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в шифртексте, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из А * и В * соответственно.

Пусть U = {u1,..,иN} — множество возможных шифрвеличин, V = {v1,...,vM} множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты хX, yY можно было представить словами из U*, V * соответственно. Требование однозначности расшифрования влечет неравенства Nп, Мт, МN. Для определения правила зашифрования Еk(х) в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.

Поскольку МN, множество V можно представить в виде объединения  непересекающихся непустых подмножеств V(i). Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V :

,

и соответствующее семейство биекций

для которых .

Рассмотрим также произвольное отображение где , такое, что для любых

Назовем последовательность (к,1) распределителем, отвечающим данным значениям кK, lN.

Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть

xX, x = x1...xl, xiU, i = 1,l; kK

и (к,I) = а1(k)...а1(k). Тогда Ек(х) = у, где у = у1...уl,

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

Классификация шифров замены

Если ключ зашифрования совпадает с ключом расшифрования: k3 = kp, то такие шифры называют симметричными, если же k3kр — асимметричными.

В связи с указанным различием в использовании ключей сделаем еще один шаг в классификации:

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

Для однозначных шифров замены справедливо свойство:

для многозначных шифров замены:

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

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

В силу инъективности (по k) отображения Еk и того, что |U| = |V|, введенные в общем случае отображения  являются биекциями , определенными равенствами

.

Число таких биекций не превосходит N!.

Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле включение следует заменить равенством

Введем еще ряд определений.

Если для некоторого числа qN выполняются включения viВq, i=1,N, то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае — шифром разнозначной замены:

В подавляющем большинстве случаев используются шифры замены, для которых UАр, для некоторого рN . При р = 1 говорят о поточных шифрах замены, при р > 1 — о блочных шифрах замены:

Следующее определение. В случае r = 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены:

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

Одноалфавитные шифры

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

Шифр Виженера

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

Примером многоалфавитного шифра замены является так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью п X n, где п - число символов используемого алфавита. На рис.4 показана таблица Виженера для русского языка (алфавит Z32- 32 буквы и пробел). Первая строка содержит все символы алфавита. Каждая следующая строка получается из предыдущей циклическим сдвигом последней на символ влево.

Рисунок 4. Таблица Виженера для алфавита Z32

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

ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ ТЧК БРАТЬЯ КАРАМАЗОВЫ ТЧК

С помощью ключа ВЕНТИЛЬ запишем строку исходного текста с расположенной под ней строкой с циклически повторяемым ключом:

         ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ ТЧК БРАТЬЯ КАРАМАЗОВЫ ТЧК

ВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕ

В результате зашифрования, начальный этап которого показан на рисунке 5, получим шифротекст:

ЕХЩРЭАБЕЫЧУДККТИСЙЩРМЕЩЬЗЭРМДОБИЭУАДЧТШЛЕВМЪФГКЛЩП

Рисунок 5. Принцип шифрования по таблице Виженера

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

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

II. Советы по выполнению частотного анализа английских текстов

(1)Начните с подсчета частоты появления каждой из букв шифр-текста. Примерно пять букв должны появляться с частотой менее 1 процента, и они вероятно, представляют собой j, k, q, х и z. Одна из букв должна появляться с частотой более 10 процентов, и она, по-видимому, представляет собой е. Если шифр-текст не подчиняется этому распределению частот, то, возможно, исходное сообщение написано не на английском языке. Вы можете определить, какой это язык, если проанализируете частотное распределение букв в шифр-тексте. К примеру, в итальянском языке обычно ecть, три буквы с частотностью более 10 процентов и 9 букв с частотностью менее 1 процента. В немецком языке буква е имеет чрезвычайно высокую частотность – 19 процентов, поэтому любой шифр-текст, в котором одни из букв встречается столь же часто, является, вполне возможно, немецким. После того как вы определили язык, для выполнения частотного анализа вам следует воспользоваться соответствующей таблицей частотности букв для данного языка. Если у вас есть нужная таблица частотности букв, то нередко удается дешифровать даже шифр-тексты на неизвестном языке.

(2)Если установлена взаимосвязь с английским языком, но, как часто и происходит, сразу же открытый текст не появляется, тогда обратите внимание на пары повторяющихся букв. В английском языке чаще всего повторяющимися буквами будут ss, ее, tt, ff, 11, mm и оо. Если в шифр-тексте имеются какие-либо повторяющиеся символы, то вы можете считать, что они представляют собой одну из этих пар.

(3)Если в шифр-тексте имеются пробелы между словами, то постарайтесь определить слова, состоящие из одной, двух или трех букв. Единственными словами в английском языке, состоящими из одной буквы, являются а и I. Чаще всего встречающимися двухбуквенными словами будут of, to, in, it, is, be, as, at, so, we, he, by, or, on, do, if, me, my, up, an, go, no, us, am. Наиболее часто появляющиеся трехбуквенные слова – the и and.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32