Электронная цифровая подпись. Алгоритмы цифровой подписи DSA. Лабораторная работа 4. Традиционные симметричные криптосистемы. Цель работы

• Название: Традиционные симметричные криптосистемы. Цель работы
• Анкор: Электронная цифровая подпись. Алгоритмы цифровой подписи DSA
• Дата: 11.02.2022
• Размер: 329.56 Kb.
• Имя файла: Лабораторная работа 4.docx
• Тип: Документы; #358644

^{Лабораторная} работа №2

Традиционные симметричные криптосистемы.
Цель работы – закрепление теоретических знаний по методам криптоанализа симметричных криптосистем и практическое освоение методов криптоанализа криптосистем гаммирования с периодической гаммой на примере криптосистемы Виженера.

Время - 4 часа.

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

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

Виженера ключ k^d

задается набором из d символов. Такие наборы

подписываются под открытым текстом ^x₁^{, x}₂ ^{,..., x}_n,

^x_i ^A_m, до получения

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

k₁, k₂,..., k_n^{, n sd , где} s

- число полных периодов

k^d, r

nmod d.

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

k_i

mod m
у_i x_i .

При дешифровании криптосистемы Виженера решаются две

взаимосвязанные задачи:

• 
  ^{задача определение периода dключевой последовательности} k^;
  
• 
  ^{задача дешифрования криптограммы} Y^{при известном периоде} d^длине
  

.

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

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

последовательности Х

х₁, х₂ ,..., х_п

называется величина

( Х)

^mF_i (F_ii1 n(n

¹⁾ , (1)

1)

где <sup>Х

A</sup>_m- некоторая последовательность; ^F_i

- частота встречаемости

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

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

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


K

n
1 2 n ^k

множества всех локально-периодических последовательностей справедливо

^dпериода dи

M (Y)

(s 1)sr

s(s

n(n

1)(d

1)

r) ₂


p
i

i

. (2)

Первый метод Фридмана состоит в том, что вычисляется индекс

совпадения

(Y)

для имеющейся криптограммы в соответствии с выражением

(1) и затем его значение сравнивается с (2) при d 1,2,3,... . При достаточной

близости индекса совпадения к одному из значений (2), при некотором d, предполагают, что период равен этому значению d. Первый метод Фридмана

эффективен для d

5, т.к. значение ^M

(Y)

для фиксированного периода d

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

Суть второгометодаФридманасостоит в опробовании возможных

периодов dпо следующей схеме. Из исходной криптограммы ^{Y y}₁^{, y}₂ ^{,..., y}_n

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

dподпоследовательностей:

d
1) y₁, y₁

, y<sub>1

2d</sub>,...

d
2) y₂ , y₂

, y<sub>2

2d</sub>,...

..............

d
d) y_d, y_d

, y<sub>d

2d</sub>,...

Для каждой подпоследовательности подсчитывается ее индекс

совпадения

(Y_d) . Если все индексы совпадения в среднем близки к значению

p

i
^{1 2} (среднее значение индекса совпадения случайных криптограмм,

d_i

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



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

y₁, y₂,..., y_i,...y_(k

1)d r^;

y₁ , y₂

,..., y_i

,..., y_{kd r}, n

kd r.

Формируется называемое «множество вероятных слов», которые, по мнению криптоаналитика, могут быть началом искомого открытого текста.

Для слова

a₁ , a₂ ,..., a_r

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

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

k₁ , k₂ ,..., k_r. Правильность угадывания

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

f ¹( y₁

k<sub>1

d</sub>),

f ¹( y₂

k<sub>2

d</sub>),..., f

¹( y_rk<sub>r

d</sub>) .

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

что

k₁ , k₂ ,..., k_r

k₁ , k₂ ,..., k_r^{, т.е. найдены первые r символов ключевой}

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

k_r1, k<sub>r

2</sub>,..., k_d

k_r1, k<sub>r

2</sub>,..., k_d^.

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

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

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

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

известны. Пусть дана криптограмма Y

y₁, y₂ ,..., y_n. Известен период

ключевой последовательности d. Сформируем две подпоследовательности исходной криптограммы

y₁, y₂,..., y_i,...y_(k

1)d r^;

y₁ , y₂

,..., y_i

,..., y_{kd r}, n

kd r.

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

P(a_j)

p_j, j

, где j- порядкоый номер буквы алфавита. Также будем

считать, что на множестве Kзадано равномерное распределение, т.е. ключом является реализация выборки объемом dиз равномерного распределения K.

Тогда вероятность того, что i-я и ( i d)-я буквы открытого текста были равны

соответственно,

^x_i и

^xi d

, при условии, что i-я и ( i

d)-я буквы

криптограммы равны соответственно,

y_iи y_i

определяется выражением

P(x_i

s, x_i

| y_i, y_i ) .

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

P(x_i

s, x_i

| y_i

, y_i )

sl^.

Для каждой пары

y_i^и y_i

букв исходной криптограммы упорядочим в

соответствии с убыванием полученных значения условных вероятностей (5) ^{пары букв открытого текста} s ^{и l . Построив такие колонки для каждого i , в} результате получаем таблицу (табл. 1), в которой верхние пары имеют большую условную вероятность, чем нижние.
Таблица 1.

i 1	…	i j	…	i n
y1 y1 d	…	yj yjd	…	y(k1)dr ykdr
….	…	xjs, p xj d l sl	…	…

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

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

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

восстановления текста, зашифрованного неравновероятной гаммой. Пусть

р_i,

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

р₁ р₂

...

р_l, p_l

^pl 2

... p_m

⁰ , l m.

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

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

k_i ^, i

. Задача заключается в подборе по

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

таблицы исключают из рассмотрения m наименее вероятных букв алфавита,

дальнейшие действия аналогичны рассмотренным выше. Надежность такого метода меньше, так как не исключена возможность частичной, а может и полной, потери истинного открытого текста.
Таблица 2.

ki yi	y1	….	….	yn
k1	yˆ1(k1)	….	…..	yˆn(k1 )
k2	yˆ1 (k2 )	….	….	yˆn(k2 )
….	….	….	….	….
kl	yˆ1(kl)	….	….	yˆn(kl)

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

   1. 
      При подготовке к лабораторной работе
      

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

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

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

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

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

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

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

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

1. 
   Задание на выполнение лабораторной работы (исходные криптограммы).
   
2. 
   Основные расчетные соотношения.
   
3. 
   Результаты расчетов, представленные в виде табл. 1 и 2.
   
4. 
   Результаты анализа, т.е. дешифрованные криптограммы.
   

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

1. 
   Основные понятия криптографии и криптоанализа.
   
2. 
   Методы Фридмана.
   
3. 
   Метод «протяжки» вероятного слова, метод чтения в колонках.
   
4. 
   Понятие индекса совпадения.
   
5. 
   Криптосистема Виженера.
   
6. 
   Связь криптосистемы Виженера с другими простейшими криптосистемами.
   

Литература

1. 
   Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации. Учебное пособие для вузов. М.: Горячая линия – Телеком, 2005.
   
2. 
   Баричев С.Г, Гончаров В.В., Серов Р.Е. Основы современной криптографии: Учебный курс. – 2-е изд. – М.: Горячая линия – Телеком, 2002.
   
3. 
   Осипян В.О, Осипян К.В. Криптография в задачах и упражнениях. – М.: Гелиос АРВ, 2004.
   
4. 
   Харин Ю.С., Беник В.И, Матвеев Г.В., Агиевич С.В. Математические и компьютерные основы криптологии: Учеб. пособие. – Минск: Новое знание, 2003.