Основные расчетные соотношения

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

Виженера ключ k^d задается набором из d символов. Такие наборы подписываются под открытым текстом х\,Х2,...,х_п, х;еА_т, до получения

периодической ключевой последовательности к = к_ък₂,...,к_п, n = sd + r, где s

- число полных периодов к , r — n mod d.

Уравнение шифрования для криптосистемы Виженера:

у I = %j + kj jnod m. При дешифровании криптосистемы Виженера решаются две взаимосвязанные задачи:

- задача определение периода d ключевой последовательности к ;

- задача дешифрования криптограммы Y при известном периоде d длине

ключевой последовательности к.

Основным инструментом решения задачи определения периода ключевой последовательности криптосистемы Виженера являются методы Фридмана, основанные на понятии индекса совпадения. Индексом совпадения последовательности Х = xi,х₂,...,х_п называется величина

_аХ₌££М(1)

₇tin(n-\)

где Х е А_т - некоторая последовательность; Fj- частота встречаемости

(число мест в тексте) / - буквы в последовательности Х.

Для криптосистемы Виженера, получаемого шифрованием открытого

текста X = а₁,а₂,...,а_п с помощью равновероятного выбора ключа к из

множества всех локально-периодических последовательностей К_п периода d и п = sd + r справедливо

^ -^(s + \)sr +s{s - \){d -г) у 2,(, (s +\)sr +s(s-\)(d-r)}\

(2) т

w(w-l)

+ w(w-l)

Первый метод Фридмана состоит в том, что вычисляется индекс совпадения 3(7) для имеющейся криптограммы в соответствии с выражением

(1) и затем его значение сравнивается с (2) при d = 1,2,3,.... При достаточной близости индекса совпадения к одному из значений (2), при некотором d, предполагают, что период равен этому значению d. Первый метод Фридмана эффективен для d<5, т.к. значение М Щ{У) для фиксированного периода d совпадает со значениями целого ряда различных периодов ключевой последовательности.

Суть второго метода Фридмана состоит в опробовании возможных периодов d по следующей схеме. Из исходной криптограммы Y = yi,y₂,...,y_n для предполагаемого периода d ключевой последовательности выписывается d подпоследовательностей:

1) У1>У1+с1>У1+2с1>---

2) y2>y2+d>y2+2d>---

d) yd,yd + d,yd + 2d

Для каждой подпоследовательности подсчитывается ее индекс совпадения 3(7^). Если все индексы совпадения в среднем близки к значению

— У Pi (среднее значение индекса совпадения случайных криптограмм,

полученных с помощью гамм периода 1), то принимают величину d за истинный период, в противном случае опробуется следующая величина периода. Второй метод Фридмана позволяет эффективно определять периоды d<30.

Метод «протяжки» вероятного слова. При известном периоде ключевой последовательности d выписываются две подпоследовательности исходной криптограммы:

У₁,У2,...,У1,.. .У(к-1)с1+г ;

У₁й,У2+й,...,У\+й,...,Укй+г, п = kd + r. Формируется называемое «множество вероятных слов», которые, по мнению криптоаналитика, могут быть началом искомого открытого текста.

Для слова a1,d2,...,a_r из этого множества, находятся первые символы

ключевой последовательности к*,к2,...,к*. Правильность угадывания

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

/-} (j₁), /-} (y₂₊d),..., I'! (w) .

Если полученная последовательность символов «читаемая», то полагают,

что k*,k2,...,k*=k1,k₂,..,k_r, те. найдены первые г символов ключевой

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

k*₊,k*₊2,...,k_d=k_r+,k_r+2,...,k_d.

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

Метод чтения в колонках. Рассмотрим два случая:

- априорные вероятности символов ключевой последовательности не
известны;

- априорные вероятности символов ключевой последовательности
известны.

Априорные вероятности символов ключевой последовательности не известны. Пусть дана криптограмма Y = у₁,У2,...,Уп. Известен период ключевой последовательности d. Сформируем две подпоследовательности исходной криптограммы

У₁,У2,...,У1,.. .У(к-1)с1+г ;

У1+с1,У2+с1,...,У1+с1,...,Укс1+г, n = kd + r. Будем полагать, что открытыми текстами, подлежащими шифрованию, являются содержательные тексты с известными вероятностями букв алфавита

P(qj) = pj, j = ,jn, где j - порядкоый номер буквы алфавита. Также будем

считать, что на множестве К задано равномерное распределение, т.е. ключом является реализация выборки объемом d из равномерного распределения К. Тогда вероятность того, что / -я и (/ + d)-я буквы открытого текста были равны соответственно, Xf=s и x_i₊_d=l, при условии, что /-я и (/ + б/)-я буквы

криптограммы равны соответственно, y_t и y_i₊d определяется выражением

Р(х, = s,x,_+d = 1| y,y,_+d) = P(^Xi⁼,^Xi⁺d⁼;y,y~~'⁺'^l~~)

P(yi,yi+d)

Если числитель не равен нулю, то справедливо равенство

PsPl

P si

X P

P(Xj = s, x_i+d = / | y_t, y_i+d ) =

Г1(Уг)^РГ1(Уг₊а)

Для каждой пары y_t и y_i₊d букв исходной криптограммы упорядочим в соответствии с убыванием полученных значения условных вероятностей (5) пары букв открытого текста s и /. Построив такие колонки для каждого /, в результате получаем таблицу (табл. 1), в которой верхние пары имеют большую условную вероятность, чем нижние.

Таблица 1.

1 = 1	…	i =j	…	i = n
У₁ У₁d	…	y_j+d	…	y (k1)d+r y kd+r
….	…		х ■ = s ~		…	…
_Kx_j+d =,^rsl _y

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

Априорные вероятности символов ключевой последовательности известны. Если априорно известны вероятности символов ключевой последовательности, то задача дешифрования криптограммы аналогична задаче восстановления текста, зашифрованного неравновероятной гаммой. Пусть р_i,

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

р ₁ > р2 ^ ^ рi, Pl+\ = Pl+2 ⁼ ... ⁼ Рт ⁼ 0 , I <tn.

Составим таблицу (см. таблицу 2), в которой по строкам расположены символы, полученные путем расшифровки криптограммы одним символом

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

Таблица 2.

kj/yj	У₁	….	….	Уп
h	У ₁(h)	….	…..	Уп(^к₁)
k₂	У₁(к₂)	….	….	Уп(^к2)
….	….	….	….	….
k	$₁(ki)	….	….	Уп(^кг)

Порядок выполнения работы

2.1. При подготовке к практической работе

На этапе подготовки к практической работе студенты должны, используя литературу [1,2,3,4], материалы лекций углубить свои знания по следующим вопросам: криптосистема Виженера; методы определения периода ключевой последовательности; методы бесключевого чтения (метод «протяжки» вероятного слова, метод чтения в колонках).

Студенты на предстоящее лабораторное занятие готовят алфавиты русского и английского языка со значениями вероятностей встречаемости символов.

2.2. Во время проведения занятия

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

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

последовательности; на основании вычисленного значения периода ключевой
последовательности используя метод «протяжки» вероятного слова

дешифрировать вторую криптограмму.

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

Содержание отчета

Отчет должен включать в себя следующие пункты:

1. Задание на выполнение практической работы (исходные
криптограммы).

2. Основные расчетные соотношения.

3. Результаты расчетов, представленные в виде табл. 1 и 2.

4. Результаты анализа, т.е. дешифрованные криптограммы.

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

1. Основные понятия криптографии и криптоанализа.

2. Методы Фридмана.