Лабораторная работа №11. Криптоанализ многоалфавитных шифров (шифр Виженера)

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

порядковый № символа	0	1	2	3	4		22	23	24	25
алфавит исходного текста	a	b	c	d	e		w	x	y	z
						…				
алфавит шифра	d	e	f	g	h		z	a	b	c
порядковый № символа	3	4	5	6	7		25	0	1	2

Рис.46. Пример шифра Цезаря

Пронумеровав буквы алфавита, начиная с нуля, получим математическое описание этого шифра:

c_i = (a_i+S) mod L,

где a_i, c_i – i-тый элемент открытого текста и шифр-текста соответственно, L – мощность (количество различных символов) нормативного алфавита, S – сдвиг, одинаковый для всех символов, 0 ≤ S ≤ L-1. При S=0 алфавит шифрования совпадает с нормативным.

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

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

Далее выбирается ключ или ключевая фраза. После чего шифрование осуществляется следующим образом:

• под каждой буквой исходного сообщения последовательно записываются буквы ключа;

• если ключ оказался короче сообщения, его последовательно используют несколько раз;

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

На рис.47 показана таблица Виженера для русского языка (алфавит без буквы «Ё», содержит пробел). В таблице выделены строки – алфавиты шифрования, используемые, если выбрано ключевое слово «МАЯК».

Пример шифрования. Пусть требуется зашифровать открытый текст «ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ», выбрано ключевое слово «МАЯК»:

Исходное сообщение

Г

Р

У

З

И

Т

Е

_

А

П

Е

Л

Ь

С

И

Н

Ы

_

Б

О

Ч

К

А

М

И

Ключ

М

А

Я

К

М

А

Я

К

М

А

Я

К

М

А

Я

К

М

А

Я

К

М

А

Я

К

М

Криптограмма

П

Р

С

С

Ф

Т

Г

Й

М

П

Г

Х

З

С

Ж

Ч

Ж

_

_

Ш

В

К

Я

Ц

Ф

В многоалфавитных шифрах один и тот же символ шифр-текста может заменять разные символы открытого текста. Так, в рассмотренном примере буква «С» заменяет в разных случаях буквы «У», «З» и «С»; символ «_» – букву «Б» и символ «_».

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

c_i = (a_i+S_i ) mod L,

где a_i, c_i – i-тый элемент открытого текста и шифр-текста соответственно, L – мощность (количество различных символов) нормативного алфавита, S_i – сдвиг, определяемый i-тым символом гаммы.

Рис.47. Пример таблицы Виженера

Гамма получается периодическим повторением некоторого ключевого слова. Например, ключевое слово «МАЯК» порождает гамму вида «МАЯКМАЯКМАЯК…». S_i – числовой эквивалент соответствующей буквы ключа, 0 ≤ S_i ≤ L-1.

Шифр Цезаря является частным случаем шифра Виженера с периодом гаммы, равным единице.

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

Пусть М – длина ключевого слова. Если ключевое слово короче шифруемого текста, то ключевое слово будет последовательно повторяться, поэтому М – период гаммы.

Разобьем криптограмму на блоки, равные по длине периоду гаммы. Символы криптограммы, занимающие одинаковое положение в таких блоках, имеют одинаковое смещение относительно символов исходного текста, то есть для их получения использован один и тот же алфавит шифрования. Этот алфавит шифрования задает шифр простой замены, а именно, простейший случай замены – шифр Цезаря.

Описанное свойство дает возможность применить частотный анализ для каждой группы символов криптограммы, соответствующих определенной букве ключа. Такие группы символов называют группами периода. Число групп периода равно длине ключа M.

Частотный анализ символов, составляющих группу периода, позволяет криптоаналитику определить величину смещения нормативного алфавита для каждой группы, то есть ключ шифрования. Такой метод криптоанализа может быть эффективен, если длина криптограммы N превышает 20*M (N > 20M), М – длина ключа.

Обычно криптоанализ шифра Виженера проводится в два этапа. На первом этапе определяется число M, на втором этапе – само ключевое слово.

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

Пусть d₁, d₂, ... – найденные расстояния между повторениями и d – наибольший общий делитель (НОД) этих чисел. Тогда M должно быть cреди делителей d. Чем больше повторяющихся фрагментов имеется в шифр-тексте, тем более вероятно, что M совпадает с d.

Для определения значения M, можно использовать автокорреляционный метод. Текст криптограммы выписывается в строку, под ним выписываются строки, в которых текст сдвинут влево на 1, 2, 3, 4 и так далее позиции (t=1,2,3,…). Затем для каждой строки подсчитывается число позиций (столбцов), в которых символ совпал с символом исходной строки в той же позиции (c_i = c_i+t). Для каждой строки вычисляются автокорреляционные коэффициенты, равные отношению числа совпадений к длине строки. Для t, кратных периоду гаммы, автокорреляционные коэффициенты должны быть заметно больше, чем для сдвигов, не кратных периоду.

Для проверки правильности выбора значения М, может быть использован метод индекса совпадения, введенный в практику в 1920 году американским криптологом и криптоаналитиком У. Фридманом, впервые успешно применившим вероятностно-статистические методы в криптологии.

Индексом совпадения I_С (х) для последовательности х = (x₁,...,x_m), составленной из букв алфавита A, называется вероятность того, что две случайно выбранные буквы из этой последовательности совпадают.

Пусть A – алфавит мощностью L, состоящий из символов a_i, i = 0,…,L-1; A = {a₁,...,a_L-1}. Значение индекса совпадения экспериментально может быть получено как:

где f_i – число появлений буквы a_i в последовательности x.

Пусть х – строка осмысленного текста на естественном языке. Допустим, что буквы в х появляются в любом месте текста с вероятностями р₀,...,р_L-1 независимо друг от друга, р_i – вероятность появления буквы a_i в осмысленном тексте. Тогда, при достаточно больших m и определении p_i как p_i = f_i / m получаем приближённую формулу:

.

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

Таблица 11. Индексы совпадения европейских языков

Язык	Русский	Русск. с пробелом	Алгл.	Франц.	Нем.	Итал.	Испан.
	0,055	0,068	0,066	0,078	0,076	0,074	0,077

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

В то же время, если последовательность х – реализация независимых испытаний случайной величины, имеющей равномерное распределение, то индекс совпадения вычисляется по формуле:

.

Таким образом, если х является случайной последовательностью букв алфавита А мощностью L, значение индекса соответствия будет ощутимо ниже – около 1/L. Для русского языка это значение составляет 0,030.

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

Пусть у = (у₁,у₂,…,у_N) – криптограмма, полученная шифром Виженера, и пусть высказано предположение относительно периода гаммы (длины ключевого слова) M. Выпишем символы шифр-текста y построчно с периодом M и обозначим столбцы получившейся таблицы через Y^↓_i, i = 1,…,M:

Y↓1	Y↓2	…	Y↓M
y1	y2	…	yM
yM+1	yM+2	…	y2M
y2M+1	y2M+2	…	y3M
…	…	…	…

Если M – это истинная длина ключевого слова, то каждый столбец Y^↓_i, i = 1,…,M, представляет собой группу периода – участок открытого текста, зашифрованный простой заменой – шифром Цезаря со сдвигом S_i, определяемым i символом ключевого слова. Поэтому, из таблицы 11, I_С(Y^↓_i) ≈ 0,055 при любом i (для русского текста).

С другой стороны, если M было выбрано неверно и отлично от длины ключевого слова, то столбцы Y^↓_i будут более похожи на случайные последовательности букв, поскольку они являются результатом зашифрования фрагментов открытого текста некоторым многоалфавитным шифром. Тогда значения I_С(Y^↓_i) будут ближе к числу 1/L (для русского языка ≈ 0,030).

Предположим, что на первом этапе мы нашли длину ключевого слова M. Теперь требуется найти само ключевое слово, то есть определить сдвиги S_i, i = 1,…,M каждой из групп периода.

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

Пусть х = (х_],...,х_m), у = (у₁,...,у_т) – две последовательности (строки) букв алфавита А.

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

Пусть f₀, f₁,…, f_L-1 и f₀, f₁,…, f_L-1 – частоты вхождений букв алфавита A в строки х и у соответственно. Тогда:

.

Рассмотрим относительные сдвиги S_i-S_j групп периода Y^↓_i и Y^↓_j.

При нулевом сдвиге между столбцами – группами периода индекс MI_c(x,y) близок к индексу совпадения в естественном языке (табл.11). Ненулевые относительные сдвиги дают более низкие значения индекса взаимного совпадения. Это наблюдение позволяет определить величины относительных сдвигов S_i-S_j столбцов Y^↓_i и Y^↓_j.

Используя изложенный метод, можно связать системой уравнений относительные сдвиги различных пар столбцов Y^↓i и Y^↓_j. В результате останется 33 (для русского языка) варианта для ключевого слова, из которых можно выбрать наиболее предпочтительный вариант (если ключевое слово является осмысленным).

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

Задание

Дешифровать криптограмму, полученную шифром Виженера. Известно, что алфавит открытого текста совпадает с алфавитом русского языка без буквы ё с добавлением символа пробела (33 буквы).

Указания к выполнению лабораторной работы

Для выполнения данной лабораторной работы рекомендуется использовать файл «Шифр Виженера.xlsm».

Технология выполнения задания

1. Скопировать в новый документ MS Word текст криптограммы (без знака конца абзаца) из Приложения 3 в соответствии с номером варианта (выбор варианта осуществляется по порядковому номеру в официальном списке группы).

Выполнить анализ криптограммы аналогично рассмотренному далее примеру.

ПРИМЕЧАНИЕ: Для выполнения лабораторной работы следует использовать файл «Шифр Виженера.xlsm», а для анализа примера – файл «Шифр виженера пример.xlsx», содержащий загруженный шифр-текст.

Пример. Требуется расшифровать криптограмму:

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

На первом этапе следует определить длину ключевого слова (период гаммы).

2. Выполнить тест Казиски, заключающийся в поиске в шифр-тексте повторяющихся фрагментов длиной, не меньшей трех символов, и расстояния между такими фрагментами. Для выполнения теста Казиски рекомендуется использовать возможности текстового редактора MS Word 2010:

• Cкопировать текст криптограммы в новый документ MS Word. Установить курсор в начало текста. Выполнить команду Главная/Найти. В окне команды набрать первые три символа текста криптограммы, будет осуществлен поиск совпадений.

• В случае, если повторения не найдено, выполнить поиск повторений для 2, 3 и 4 символов криптограммы, и так далее, пока не будет найден повторяющийся фрагмент.

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

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

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

Видно, что следующие за повторяющимся фрагментом буквы также повторяются, поэтому фрагмент имеет длину 6 и выглядит как «цхъярр».

Рис.48. Поиск повторений – тест Казиски

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

Так, расстояние между повторяющимися фрагментами «цхъярр» составило 210 знаков.

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

3. Открыть книгу «Шифр Виженера.xlsm», включить выполнение макросов. Занести текст повторяющихся фрагментов и значения расстояния между повторениями в форму на лист «Опред-е периода1».

Найти следующие повторяющиеся фрагменты (всего 3-4 разных фрагмента), занести данные о них на лист «Опред-е периода1».

В примере в результате анализа криптограммы будет выявлены следующие первые восемь повторений (табл.12).

Таблица 12. Определение периода гаммы – тест Казиски

Сочетание	Расстояния				Кол-во повторений
цхъярр	210				2
ъяр	210	610			3
ооэ	270				2
цгбр	40				2
гбр	40	80	550		4
брь	35	85	510		4
брьц	35	595			3
рьц	35	460	135		4

Период гаммы M находится среди делителей НОД расстояний. Желательно, чтобы найденные в тексте повторения позволяли однозначно определить период гаммы, для этого НОД должен быть простым числом (делится нацело только на себя и на 1).

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

В данном случае НОД равен 5, поэтому, скорее всего, период гаммы (длина ключевого слова) M=5.

Отметим, что для однозначного определения периода гаммы в данном примере достаточно было бы найти первые 6 повторяющихся фрагментов.

4. Определить период гаммы методом автокорреляции. Для этого следует:

• Занести текст криптограммы посимвольно в строку 2 на листе «Опред-е периода2» книги «шифр Виженера пример.xlsx». Поскольку криптограмма достаточно длинная, можно занести первые 75-100 ее символов.

ПРИМЕЧАНИЕ: Для удобства занесения символов криптограммы, можно загрузить ее в книгу «Шифр Виженера.xlsm». Для этого следует перейти на лист «Загрузить криптограмму», выделить ячейку E3 и вставить текст криптограммы в адресную строку. Затем перейти в ячейку B3, задать значение периода 7, после чего загрузить криптограмму, нажав кнопку Загрузить криптограмму.

После этого можно осуществлять копирование символов криптограммы построчно с листа «Криптограмма» (столбцы В-Н) и вставлять их в строку 2 на лист «Опред-е периода2».

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

• Скопировать заполненную 2 строку (Криптограмма) листа «Опред-е периода2», начиная со второго символа, и вставить ее в 3 строку (Сдвиг = 1) командой Специальная вставка/Значения. Последний, незаполненный символ строки 3 заполнить следующим символом из текста криптограммы.

• Заполнить строки 4-12, каждый раз копируя предыдущую строку со сдвигом на 1 символ влево, использовать команду Специальная вставка/Значения. Недостающие символы в конце строк дополнить следующими символами криптограммы так, чтобы все строки были одинаковой длины.

• Цветом (инструмент Условное форматирование) будут выделены символы в строках, совпадающие с символом первой строки в том же столбце. Для каждой строки вручную подсчитать количество совпадений (число выделенных ячеек в строке) и занести эти значения в ячейки B16-B25 на листе «Опред-е периода2».

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

Полученные значения коэффициентов автокорреляции для рассматриваемого примера приведены в табл.13.

Таблица 13. Определение периода гаммы – метод автокорреляции

Сдвиг	Число совпадений	Коэффициент автокорреляции
1	3	0,040
2	2	0,027
3	1	0,013
4	2	0,027
5	7	0,093
6	1	0,013
7	2	0,027
8	1	0,013
9	2	0,027
10	7	0,093

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

5. Проверить гипотезу о том, что период гаммы равен 5 с помощью индекса совпадения. Рассчитать индексы совпадения для групп периода:

• Очистить данные, занесенные ранее на лист «Криптограмма» (столбцы В-Н) – от этого зависит правильность подсчета индексов совпадения.

• Перейти на лист «Загрузить криптограмму», вставить шифр-текст в ячейку E3 (если это не было сделано ранее), в ячейку В3 занести значение 5, затем нажать кнопку Загрузить криптограмму. Данные будут загружены на лист «Криптограмма», каждый из полученных столбцов представляет группу периода Y^↓_i.

В примере на листе «Криптограмма» будут заполнены пять столбцов символов (четыре – по 198 символов и один – содержащий 197 символ).

• Перейти на лист «Статистика период». Для каждого столбца – группы периода Y^↓_i в строке 38 приведен расчет индекса совпадения I_C(Y^↓_i). В случае, если период гаммы определен правильно, значения индекса должны быть не менее 0,05 и выделяются цветом.

• Если период гаммы определен неправильно, значения индексов совпадения близки к 1/33  0,03. В этом случае следует пересмотреть гипотезу о значении периода гаммы.

В примере значения всех индексов совпадения превышают 0,05, что свидетельствует о правильности определения периода гаммы (табл.14).

Таблица 14. Значения индексов совпадения для групп периода

Номер столбца –группы периода	1	2	3	4	5
Значение индекса совпадения	0,0571	0,0560	0,0634	0,0582	0,0723

На втором этапе анализа определяется само ключевое слово.

6. Определить относительные сдвиги между столбцами – группами периода:

• Перейти на лист «Статистика сдвиги» книги «шифр Виженера пример.xlsx». В диапазоне B4:AH11 приведены частоты встречаемости символов. Строка 4 содержит частоты букв в русском языке, приведенные к размеру групп периода. В строках 5-11 содержатся частоты групп периода рассматриваемой криптограммы. Распределения этих частот «сдвинуты» относительно русского языка и относительно друг друга. Для каждой группы периода цветом (инструмент Условное форматирование) выделены наибольшие значения частот.

• Определить сдвиг второй группы периода (Столбец 2) относительно первой (Столбец 1), для этого можно воспользоваться сопоставлением пиковых частот в строках 5 и 6, либо сопоставлением начала/конца фрагмента алфавита с малыми частотами (рис.49, 50). Сопоставление начала фрагмента с малыми частотами более надежно.

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

Если строку 6 следует сдвигать вправо, то величина сдвига считается положительной (рис.49). Если строку 6 следует сдвигать влево, то величина сдвига отрицательна (рис.50), в этом случае значение следует взять по модулю L (L – число символов алфавита). В примере L=33. Для вычисления значения по модулю можно воспользоваться функцией Excel ОСТАТ().

Рис.49. Пример определения сдвига сопоставлением пиковых частот

Рис.50. Пример определения сдвига по началу фрагмента с малыми частотами

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

• После определения сдвига, его значение заносится в столбец AI (для Столбца 2 – в ячейку AI6). Затем можно сравнить гистограммы Столбца 1 и Столбца 2 с учетом определенного сдвига. Они должны быть схожими.

В рассматриваемом примере сдвиг S Столбца 2 относительно Столбца 1, скорее всего, равен 6. Занесем это значение в ячейку AI6. Распределения частот столбца1 и столбца2 со сдвигом окажутся схожими (рис.51).

Рис.51. Пример визуальной проверки правильности определения относительного сдвига групп периода

• После определения сдвига, в диапазоне B15:AH20 отобразится «сдвинутое» распределение, в столбце AI – значение индекса взаимного совпадения (для Столбца2 – в ячейке AI15). Если сдвиг определен правильно, то значения индекса взаимного совпадения будет выше 0,05.

• В случае, если значение индекса взаимного совпадения ниже 0,05, следует рассмотреть другую гипотезу о значении относительного сдвига и изменить его значение.

В рассматриваемом примере значение индекса взаимного совпадения MI_C(Y^↓₁,Y^↓₂⁶) Столбца 1 и Столбца 2 с учетом сдвига составляет 0,0548 (ячейка AI15), что свидетельствует о правильном определении величины сдвига.

• Аналогичным образом определить относительные сдвиги остальных столбцов – групп периода относительно Столбца 1. Для визуального определения и проверки правильности определения величины сдвига Столбца 3, Столбца 4 и т.д. с помощью гистограмм, в гистограммах «Столбец 2» и «Столбец 2 сдвиг» следует изменить исходные данные (щелкнуть на гистограмме правой кнопкой мыши и выбрать команду Выбрать данные).

В рассматриваемом примере получили следующие сдвиги и индексы взаимного совпадения (табл.15):

Таблица 15. Относительные сдвиги и индексы взаимного совпадения столбцов

Номер столбца	2	3	4	5
Сдвиг относительно 1 столбца	6	3	16	3
Индекс взаимного совпадения с 1 столбцом	0,0548	0,0581	0,0547	0,0605

7. Определение относительных сдвигов S позволяет составить систему уравнений для определения сдвигов g(i) групп периода Y^↓_i относительно алфавита Столбца 1 (отображается в строках 25-28 на листе «Статистика сдвиги»).

g(1)-g(2)=6, откуда g(2)=g(1)-6,

g(1)-g(3)=3, g(3)=g(1)-3,

g(1)-g(4)=16, g(4)=g(1)-16,

g(1)-g(5)=3. g(5)=g(1)-3.

8. Теперь для определения ключевого слова осталось только вычислить значение g(1), то есть величину сдвига Столбца 1 относительно символов открытого текста. Поскольку возможно всего 33 варианта сдвига (от 0 до 32), сдвиг g(1) нетрудно определить перебором всех вариантов.

Подбор сдвига отображается в строках 33-66 на листе «Статистика сдвиги».

В каждой строке значение первого символа – сдвиг первого символа ключевого слова относительно буквы «А» (значение = 0) на g(1) позиций, остальные символы ключевого слова получаются сдвигами буквы «А» на g(i), i1, которые были определены ранее из полученных уравнений.

Получаем следующие варианты (табл.16) ключевого слова, которые отображаются в диапазоне D34:H66 листа «Статистика сдвиги».

Таблица 16. Определение ключевого слова

Сдвиг g(1)	Ключ	Сдвиг g(1)	Ключ	Сдвиг g(1)	Ключ
0	аъэрэ	11	кезыз	22	xптёт
1	быюсю	12	лёиьи	23	цружу
2	вьятя	13	мжйэй	24	чсфзф
3	гэауа	14	нзкюк	25	штхих
4	дюбфб	15	оилял	26	щуцйц
5	еявхв	16	пймам	27	ъфчкч
6	ёагцг	17	pкнбн	28	ыхшлш
7	жбдчд	18	слово	29	ьцщмщ
8	звеше	19	тмпгп	30	эчънъ
9	игёщё	20	унрдр	31	юшыоы
10	йджъж	21	фосес	32	ящьпь

Поскольку известно, что ключ является осмысленным словом, его можно определить.

В примере лишь один из вариантов является осмысленным: при величине сдвига g(1) = 18 – «слово» (тогда g(2) = 12, g(3) = 15, g(4) = 2, g(5) = 15).

9. Зная ключ, провести дешифровку.

Дешифровка криптограммы проводится по формуле:

a_j = (c_i - S_i ) mod L,

где a_j, c_j – j-тый элемент открытого текста и криптограммы соответственно, j=1,…,N, L – число символов нормативного алфавита A, S_i – сдвиг, определяемый j-тым символом гаммы. S_i определяются, исходя из значений сдвигов g(i), соответствующих найденному ключевому слову.

• Для получения открытого текста на листе «Криптограмма» следует ввести найденное ключевое слово посимвольно в диапазон ячеек K1:Q1. Расшифровка текста содержится в столбцах K-Q (чтение текста осуществляется по строкам).

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

В рассматриваемом примере получен осмысленный текст:

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

10. Показать результат выполнения лабораторной работы преподавателю

Контрольные вопросы:

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

(Шифр Виженера является многоалфавитным, простая замена применена к каждому M-тому символу, где M – длина ключевого слова. Это значит, что сопоставление частот корректно только внутри группы из каждого M-того символа, которые идут не подряд, а значит не образуют осмысленные слова)

2. Из каких этапов состоит вскрытие шифра Виженера?

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

3. Каковы условия успешного вскрытия шифра Виженера статистическим методом?

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