Аутентификация сообщений с помощью блочных шифров

Донецьк-ДонНТУ-2010

 

 

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

 

МЕТОДИЧНІ ВКАЗІВКИ І ЗАВДАННЯ
до лабораторних робіт з курсу
«Моделі та методи інформаційної безпеки»
(Для студентів спеціальності 7.080407 "Комп’ютерний еколого-економічний моніторинг")

 

 

Разглянуто на засіданні кафедри КСМ

протокол № від

Затверджено на засіданні

навчально-видавницької Ради ДонНТУ

протокол № від

 

Донецк –2010

УДК 681.3

 

Методичні вказівки і завдання до лабораторних робіт з курсу «Моделі та методи інформаційної безпеки» (Для магістрів спеціальності 7.080407 "Комп’ютерний еколого-економічний моніторинг") \ Розр.: Губенко Н.Є. – Донецьк, ДонНТУ, 2010 - стр.

 

Наведено методичні вказівки і завдання до виконання лабораторних робіт з курсу «Моделі та методи інформаційної безпеки» для магістрів спеціальності "Комп’ютерний еколого-економічний моніторинг". Викладаються питання, пов'язані з криптографічними і стеганографічними методами захисту інформації. Розглядаються моделі захисту конфедерційності інформації та підтвердження її автентичності за допомогою простіших базових криптоалгоритмів, симетричних і асиметричних криптосистем, моделі перевірки достовірності інформації засобами електронно-цифрового підпису, використання односпрямованих хеш-функцій в криптографії, базові стеганографічні алгоритми для втілення інформації у зображення різних форматів.

Методичні вказівки призначені для засвоєння теоретичних основ і формування практичних навичок з курсу «Моделі та методи інформаційної безпеки».

 

 

Розробник: доцент каф. КСМ, к.т.н. Губенко Н.Є.

 

Рецензент:

Лабораторна робота № 1

Тема: Моделі простіших алгоритмів шифрування.

Мета: познайомитися з моделями базових алгоритмів шифрування, проаналізувати їх особливості з точки зору практичної реалізації і написати програму, що виконує шифрування тексту за допомогою одного з них, виконавши попередньо його модифікацію для підвищення криптосійкості шифрування.

Методические указания к лабораторной работе

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

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

 

К простейшим алгоритмам шифрования относятся:

- шифр Полибия;

- шифр Цезаря;

- шифр Ришелье;

- перестановочный шифр;

- шифр Виженера;

- шифр Плейфера;

- шифрование с ключом;

- шифр Вернама;

- шифр «Люцифер»;

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

Перестановки.

Перестановкой s набора целых чисел (0,1,...,N-1) называется его переупорядочение. Для того чтобы показать, что целое i пере­мещено из позиции i в позицию s(i), где 0 £ (i) < n, будем использовать запись

s=(s(0), s(1),..., s(N-1)).

Число перестановок из (0,1,...,N-1) равно n!=1*2*...*(N-1)*N. Введем обозначение s для взаимно-однозначного отображения (гомо­морфизма) набора S={ s ₀, s ₁,..., s _N-1}, состоящего из n элементов, на себя.

s: S ® S

s: s _i ® s _s(i), 0 £ i < n

Будем говорить, что в этом смысле s является перестановкой элементов S. И, наоборот, автоморфизм S соответствует пере­становке целых чисел (0,1,2,.., n -1).

Криптографическим преобразованием T для алфавита Z_m называется последовательность автоморфизмов: T={T⁽ⁿ⁾:1£n<¥}

T⁽ⁿ⁾: Z_m,n®Z_m,n, 1£n<¥

Каждое T⁽ⁿ⁾ является, таким образом, перестановкой n -грамм из Z_m,n.

Поскольку T⁽ⁱ⁾ и T^(j) могут быть определены независимо при i¹j, число криптографических преобразований исходного текста размерности n равно (mⁿ)! (Здесь и далее m - объем используемого алфавита.). Оно возрастает непропорционально при увеличении m и n: так, при m =33 и n =2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

Практическая реализация криптогра­фических систем требует, чтобы преобразо­вания {T _k: k Î K } были определены алгоритмами, зависящими от относительно небольшого числа параметров (ключей).

Сис­те­мы под­ста­но­вок.

Определение Подстановкой p на алфавите Z_m называется автоморфизм Z_m, при котором буквы исходного текста t замещены буквами шифрованного текста p(t):

Z_m à Z_m; p: t à p(t).

Набор всех подстановок называется симметрической группой Z_m è будет в дальнейшем обозначаться как SYM(Z_m).

Утверждение SYM(Z_m) c операцией произведения является группой, т.е. операцией, обладающей следующими свойствами:

Замкнутость: произведение подстановок p₁p₂ является подста­новкой:

p: tàp₁(p₂(t)).

Ассоциативность: результат произведения p₁p₂p₃ не зависит от порядка расстановки скобок:

(p₁p₂)p₃=p₁(p₂p₃)

Существование нейтрального элемента: постановка i, опре­деляемая как i(t)=t, 0£t<m, является нейтральным элементом SYM(Z_m) по операции умножения: ip=pi для "pÎSYM(Z_m).

Существование обратного: для любой подстановки p существует единственная обратная подстановка p^-1, удовлетворя­ющая условию

pp^‑1=p^‑1p=i.

Число возможных подстановок в симметрической группе Z_m называется порядком SYM(Z_m) и равно m!.

Определение. Ключом подстановки k для Z_m называется последовательность элементов симметрической группы Z_m:

k =(p ₀, p ₁,..., p _n-1,...), p _nÎSYM(Z_m), 0£n<¥

Подстановка, определяемая ключом k, является крипто­гра­фи­ческим преобразованием T _k, при помощи которого осуществляется преоб­разование n -граммы исходного текста (x₀,x₁,..,x_n-1) в n -грамму шифрованного текста (y₀,y₁,...,y_n-1):

y_i= p (x_i), 0£i<n

где n – произвольное (n=1,2,..). T _k называется моноалфавитной под­ста­новкой, если p неизменно при любом i, i=0,1,..., в противном случае T _k называется многоалфавитной подстановкой.

Примечание. К наиболее существенным особенностям подста­новки T _k относятся следующие:

1. Исходный текст шифруется посимвольно. Шифрования n -граммы (x₀,x₁,..,x_n-1) и ее префикса (x₀,x₁,..,x _{s -1}) связаны соотношениями

T _k (x₀,x₁,..,x_n-1)=(y₀,y₁,...,y_n-1)

T _k (x₀,x₁,..,x _{s -1})=(y₀,y₁,...,y _{s -1})

2. Буква шифрованного текста y_i является функцией только i-й компоненты ключа p_i и i-й буквы исходного текста x _i.

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

Гаммирование - наложение на открытые данные гаммы шифра (случайной или псевдослучайной последовательности единиц и нулей) по определенному правилу. Обычно используется "исключающее ИЛИ", называемое также сложением по модулю 2 и реализуемое в ассемблерных программах командой XOR. Для расшифровывания та же гамма накладывается на зашифрованные данные.

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

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

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

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

При использовании генератора ПСЧ возможно несколько вариантов:

1. Побитовое шифрование потока данных. Цифровой ключ используется в качестве начального значения генератора ПСЧ, а выходной поток битов суммируется по модулю 2 с исходной информацией. В таких системах отсутствует свойство распространения ошибок.

2. Побитовое шифрование потока данных с обратной связью (ОС) по шифртексту. Такая система аналогична предыдущей, за исключением того, что шифртекст возвращается в качестве параметра в генератор ПСЧ. Характерно свойство распространения ошибок. Область распространения ошибки зависит от структуры генератора ПСЧ.

3. Побитовое шифрование потока данных с ОС по исходному тексту. Базой генератора ПСЧ является исходная информация. Характерно свойство неограниченного распространения ошибки.

4. Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

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

Конгруэнтные датчики

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

Од­ним из хо­ро­ших кон­гру­энт­ных ге­не­ра­то­ров яв­ля­ет­ся ли­ней­ный кон­гру­энт­ный дат­чик ПСЧ. Он вы­ра­ба­ты­ва­ет по­сле­до­ва­тель­но­сти псев­до­слу­чай­ных чи­сел T(i), опи­сы­вае­мые со­от­но­ше­ни­ем

T(i+1) = (A*T(i)+C)mod m,

где А и С - кон­стан­ты, Т(0) - ис­ход­ная ве­ли­чи­на, вы­бран­ная в ка­че­ст­ве по­ро­ж­даю­ще­го чис­ла. Оче­вид­но, что эти три ве­ли­чи­ны и об­ра­зу­ют ключ.

Та­кой дат­чик ПСЧ ге­не­ри­ру­ет псев­до­слу­чай­ные чис­ла с оп­ре­де­лен­ным пе­рио­дом по­вто­ре­ния, за­ви­ся­щим от вы­бран­ных зна­че­ний А и С. Зна­че­ние m обыч­но ус­та­нав­ли­ва­ет­ся рав­ным 2n, где n - дли­на машинного сло­ва в би­тах. Дат­чик име­ет мак­си­маль­ный пе­ри­од М до то­го, как ге­не­ри­руе­мая по­сле­до­ва­тель­ность нач­нет по­вто­рять­ся. По при­чи­не, от­ме­чен­ной ра­нее, не­об­хо­ди­мо вы­би­рать чис­ла А и С та­кие, что­бы пе­ри­од М был мак­си­маль­ным. Как по­ка­за­но Д. Кну­том, ли­ней­ный кон­гру­энт­ный дат­чик ПСЧ име­ет мак­си­маль­ную дли­ну М то­гда и толь­ко то­гда, ко­гда С - не­чет­ное, и Аmod 4 = 1.

Для шиф­ро­ва­ния дан­ных с по­мо­щью дат­чи­ка ПСЧ мо­жет быть вы­бран ключ лю­бо­го раз­ме­ра. На­при­мер, пусть ключ со­сто­ит из на­бо­ра чи­сел x (j) раз­мер­но­стью b, где j=1, 2,..., n. То­гда соз­да­вае­мую гам­му шиф­ра G мож­но пред­ста­вить как объ­е­ди­не­ние не­пе­ре­се­каю­щих­ся мно­жеств H(j).

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

 

Рассмотрим базовые алгоритмы подробнее.

Шифр Полибия.

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

	А	Б	В	Г	Д	Е
А	А	Б	В	Г	Д	Е
Б	Ж	З	И	Й	К	Л
В	М	Н	О	П	Р	С
Г	Т	У	Ф	Х	Ц	Ч
Д	Ш	Щ	Ъ	Ы	Ь	Э
Е	Ю	Я	.	,	-

Рисунок 1.1 – Доска Полибия

Каждая буква может быть представлена парой букв, указывающих строку и столбец, в которых расположена данная буква. Так, представлением букв П, О будут ВГ, ВВ соответственно, а сообщение ШИФР ПОЛИБИЯ зашифруется как ДАБВГВВДЕЕВГВВБЕБВАББВЕБ. Хоть эта система и является более древней, но устойчивость к раскрытию у нее гораздо выше, несмотря на то, что наблюдается увеличение количества символов зашифрованного текста.

Шифр Цезаря.

Первый документально подтвержденный шифр: Гай Юлий Цезарь, желая защитить свои записи, заменял каждую букву следующей по алфавиту. Можно расширить этот алгоритм, поставив в соответствие каждой букве, какую либо другую букву, разумеется, без повторений. Можно даже заменять буквы совершенно сторонними символами, это не повлияет на криптостойкость.

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

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

Это один из самых старых шифров, имеющий ряд серьезных недостатков. Огромное семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного греческого алфавита со сдвигом в 3 знака и дальнейшей подстановкой. Информация об этом дошла к нам от Светония. Попробуем воспроизвести этот метод шифрования для русского алфавита. Для этого создадим таблицу соответствия (рис. 1.2):

Рисунок 1.2 – Пример таблицы соответствия букв русского алфавита

Шифр Ришелье.

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

Х	Х						Х		Х
Х	Х				Х			Х
						Х
Х		Х	Х	Х					Х
							Х		Х
	Х			Х	Х		Х		Х

Рисунок 1.3 – Пример решетки Ришелье

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

 

Перестановочные шифры.

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

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

Рассмотрим этот метод на несложном алгоритме простой столбцевой перестановки. Предварительно условимся, что число столбцов равно пяти. Допустим, имеется текст, который требуется зашифровать: “ПРОСТЫЕ ПЕРЕСТАНОВКИ ВНОСЯТ СУМЯТИЦУ”. Запишем этот текст слева направо, сверху вниз, заполняя последовательно пять столбцов (рис 1.4):

П	Р	О	С	Т
Ы	Е		П	Е
Р	Е	С	Т	А
Н	О	В	К	И
	В	Н	О	С
Я	Т		С	У
М	Я	Т	И	Ц
У

Рисунок 1.4 – Пример простой столбцевой перестановки

Теперь зададимся ключом, например 35142, и выпишем в ряд столбцы, начиная с третьего, в соответствии с ключом: “О СВН Т ТЕАИСУЦ ПЫРН ЯМУСПТКОСИ РЕЕОВТЯ”. Получилось довольно неплохо. Для расшифровки требуется количество символов зашифрованного текста разделить на 5 и сформировать столбцы в соответствии с ключом.

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

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

Наиболее известной и по праву одной из старейших многоалфавитных (одному шифруемому символу соответствует более одного символа) криптосистем является система известного французского криптографа графа Блейза Виженера (1523-1596).

Для преобразования строится алфавитный квадрат с построчным сдвигом символов в каждом последующем ряду (рисунок 1.5)

Рисунок 1.5 – Квадрат Виженера

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

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

Далее выбирается ключ, например “ГРАФДРАКУЛА”. Затем пишется шифруемая фраза, а под ней циклически записывается ключ. Для примера возьмем фразу “ОТРЯД ЖДЕТ УКАЗАНИЙ” и исключим из нее пробелы:

“ОТРЯДЖДЕТУКАЗАНИЙ” – исходный текст, “ГРАФДРАКУЛАГРАФДР” – циклический ключ. Преобразование производится так: шифруемому символу соответствует символ, находящийся на пересечении буквы ключа (столбец) и буквы исходного текста (строка).

Получим: “СВРУИЦДПЕЮКГЧАБМЩ”. Как видно, одним и тем же буквам исходного текста соответствуют не всегда одинаковые символы, то есть символы могут принимать различные значения, что является несомненным плюсом в плане криптостойкости зашифрованного текста.

Квадрат может быть каким угодно, главное, чтобы он был легко воспроизводимым и левый столбец, так же как и верхний ряд, соответствовали всему алфавиту. В качестве альтернативного варианта это может быть известный квадрат Френсиса Бьюфорта, где строки – зеркальное отражение строк квадрата Виженера. Для усложнения строки могут быть переставлены местами в определенном порядке и т. д. Усложненной разновидностью этого метода является метод шифрования с автоключом, предложенный математиком Дж. Кардано (XVI в.). Суть его в том, что, кроме циклического ключа, есть еще один, записываемый однократно перед циклическим ключом – первичный ключ. Этот нехитрый прием придает дополнительную стойкость алгоритму.

Шифр Плейфейра.

Назван так в честь своего разработчика. Алгоритм заключается в следующем: сначала составляется равносторонний алфавитный квадрат. Для русского алфавита подойдет квадрат 5х6. Задается ключевая фраза без повторов букв, например “БАРОН ЛИС”. Фраза вписывается в квадрат без пробелов, далее последовательно вписываются недостающие буквы алфавита в правильной последовательности. Одну букву придется исключить для выполнения условия равносторонности. Пусть это будет Ъ. Примем допущение, что Ъ=Ь. Итак, получился квадрат, который легко восстановить по памяти:

Теперь условия для преобразования:

1) Текст должен иметь четное количество букв и делиться на биграммы (сочетания по две буквы), недостающую часть текста дополняем самостоятельно одним (любым) символом. Например, текст “ОСЕНЬ” преобразуется в “ОСЕНЬА”.

2) Биграмма не должна содержать одинаковых букв – “СОСНА” – “СО СН АБ”.

Б	А	Р	О	Н
Л	И	С	В	Г
Д	Е	Ж	З	К
М	П	Т	У	Ф
Х	Ц	Ч	Ш	Щ
Ь	Ы	Э	Ю	Я

Рисунок 1.6 – Пример алфавитного квадрата для шифрования методом Плейфера

Правила преобразования:

Если биграмма не попадает в одну строку или столбец, то мы смотрим на буквы в углах прямоугольника, образованного рассматриваемыми буквами. Например: “ДИ” = “ЛЕ”, “ЬУ” = “МЮ” и т. д.

Если биграмма попадает в одну строку (столбец), мы циклично смещаемся на одну букву вправо (вниз). Например, “ЛС”=“ИВ”, “ТЭ”=“ЧР”.

Итак, мы готовы преобразовать текст. Приступим к шифрованию:

“СОВЕЩАНИЕ СОСТОИТСЯ В ПЯТНИЦУ” – первоначально преобразуется в биграммы: “СО ВЕ ЩА НИ ЕС ОС ТО ИТ СЯ ВП ЯТ НИ ЦУ”. Выполнив преобразование по вышеизложенным правилам, получим биграммы: “РВ ЗИ НЦ ГА ИЖ ВР РУ ПС ЭГ УИ ФЭ ГА ПШ”.

Обратите внимание на то, что одинаковые буквы на входе дали разные буквы на выходе криптосистемы, а одинаковые буквы на выходе совсем не соответствуют одинаковым на входе. Таким образом, криптотекст “РВЗИНЦГАИЖВРРУПСЭГУИ” выглядит гораздо более “симпатично”, чем после прямой замены моноалфавитной криптосистемы.

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

 

Шифрование с ключом.

Этот метод относится к современному периоду.

Текст представляется в двоичном формате, создается двоичный код некоторого размера (ключ), двоичный текст разбивается на блоки того же размера и каждый блок суммируется по модулю два с ключом. Обратное преобразование выполняется тем же методом.

Фактически, это «современный шифр Цезаря», просто подстановка выполняется не посимвольно, а словами. Правда, понятие слова здесь несколько иное – это блок заданной длины.

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

 

Система Вернама.

В 1949 году, Шеннон сформулировал и доказал свою «пессимистическую теорему»: шифр является абсолютно криптостойким тогда и только тогда, когда энтропия ключа больше либо равна энтропии исходного текста. Из теоремы следует, что длина ключа должна быть соразмерна с длиной текста. Если быть более точным, длина ключа должна равняться длине текста.

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

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

Рассмотрим это на примере четырех буквенных имен. Пусть зашифровано имя «Даша», а ключ «АБВГ». Если используется кодировка ASCII, то зашифрованный текст выглядит следующим образом: ♦!j#. Как говорилось ранее, единственный способ дешифровать текст, полный перебор всех возможных ключей. Но очевидно, что существует такой ключ, суммирование с которым зашифрованного текста даст в результате «Маша», или даже «Миша». Но действительно, невозможно ответить на вопрос, какое из имен является исходным.

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

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

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

 

Шифры, основанные на системе Вернама.

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

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

Рисунок 1.7 - Генерация ключа, для имитации системы Вернама

 

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

 

Шифр «Люцифера».

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

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

Авторы шифра предложили совместить два основных подхода к шифрованию: подстановки и перестановки.

Сначала, текст разбивается на блоки по n бит. Затем они поступают на вход мультиплексора, который раскладывает блок по модулю 2^n. Биты перемешиваются, и обрабатываются демультиплексором, который собирает биты в блок длиной n бит.

Рисунок 1.8 - Подстановки «Люцифера»

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

Выполнив подстановку, следует выполнить перестановки. Это делается соответствующей схемой, в которой просто перемешиваются биты (рисунок 1.9).

Рисунок 1.9 - Подстановки «Люцифера»

 

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

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

 

Рисунок 1.10 - «Люцифер»

 

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

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

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

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

 

Рисунок 1.11 - «Люцифер» с ключом

 

Действительно криптостойкий шифр на основе «Люцифера» был предложен в 1973 году Хорстом Фейстелем. Этот алгоритм на самом деле является общим случаем «Люцифера».

Рисунок 1.12 - Классическая сеть Фейстеля

Классическая (или простая) сеть Фейстеля (рисунок 1.12) разбивает исходный текст на блок длиной 2n бит, каждый блок разбивается на два потока L (левый) и R(правый). Далее выполняется преобразование по формуле:

где Ki – ключ, Fi – функция преобразования.

Каждое такое действие называется раундом. Обычно используется 8-16 раундов. При этом, ключ в каждом раунде может быть как частью общего ключа, так и ее модификацией по некоторому правилу: следует отметить, что это в значительной мере влияет на криптостойкость. Также важным является правило, по которому текст разбивается на потоки.

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

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

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

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

Рисунок 1.13 - Примеры сетей Фейстеля с большим числов потоков

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

Рисунок 1.14 - Способы перемешивания потоков

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

В последнее время появились упоминания так называемых Микро Декоррелированных Сетей Фейстеля. Суммируя текст с ключом, криптограф автоматически помещает информацию о ключе в зашифрованный текст, а получение ключа есть конечная цель любого криптоаналитика. Дэвид Вагнер, в своем труде «Атака бумерангом» описал способ уменьшить количество информации в тексте, зашифрованным сетью Фейстеля. Он предложил рассмотреть функции Fi как функции от текста, так, как если бы ключ был частью функции.

Рассмотрим для примера функцию f(x)=ax+b по одной паре х и f(x) нельзя ничего сказать об а и b. Чем больше пар необходимо, тем лучше такая функция. Но в сетях Фейстеля, криптоаналитик в худшем случае знает исходный текст и зашифрованный тексты, то есть исходные данные и результат последней функции, что делает задачу криптоанализа в случае микро декоррелирующих сетей почти невыполнимой.

Существуют также динамические сети Фейстеля, причем существует несколько их вариантов.

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

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

Рассматривают также и объединение двух видов динамических сетей Фейстеля. Когда каждый блок суммируется с результатом своей собственной функции, и количество блоков изменяется в зависимости от раунда.

 

Задание к лабораторной работе

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

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

Варианты заданий:

№ по журналу Базовый алгоритм

- 1-3 Шифр Полибия;

- 4-6 Шифр Цезаря;

- 7-9 Шифр Ришелье;

- 10-12 Перестановочный шифр;

- 13-15 Шифр Виженера

- 16-18 Шифрование с ключем

- 19-21 Шифр Вернама

21 – 25 Шифр Плейфейра.

-

Контрольные вопросы к лабораторной работе:

1) Что такое криптоанализ?

2) Что такое криптоскойкость алгоритма?

3) В чем суть перестановочных шифров?

4) В чем суть подстановочных шифров?

5) Назначение гаммирования.

6) Какой из рассмотренных базовых алгоритмов является по Вашему мнению наиболее криптостойким? Объяснить, почему.

7) Как, по Вашему мнению, можно увеличить криптостойкость алгоритма с использованием перестановок?

 

Лабораторная работа №2

Тема: Симметричные криптосистемы.

Цель работы: Изучение принципов шифрования в симметричных криптосистемах. Изучение классов преобразований в симметричных криптосистемах.

Методические указания к выполнению лабораторной работы

Криптографическая система это семейство преобразований шифра и совокупность ключей (т.е. алгоритм + ключи). Само по себе описание алгоритма не является криптосистемой. Только дополненное схемами распределения и управления ключами оно становится системой. Примеры алгоритмов – описания DES, ГОСТ28147-89. Дополненные алгоритмами выработки ключей, они превращаются в криптосистемы. Современные криптосистемы классифицируют следующим образом (рис. 2.1):

Рисунок 2.1 – Классификация криптосистем

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

Симметричные криптосистемы (с секретным ключом - secret key systems) данные криптосистемы построены на основе сохранения в тайне ключа шифрования. Процессы зашифрования и расшифрования используют один и тот же ключ. Секретность ключа является постулатом. Основная проблема при применении симметричных криптосистем для связи заключается в сложности передачи обоим сторонам секретного ключа. Симметричные криптосистемы принято подразделять на блочные и поточные.

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

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

 

Устройство блочных шифров.

Само преобразование шифра должно использовать следующие принципы (по К. Шеннону):

Рассеивание (diffusion) - т.е. изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;

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

Практически все современные блочные шифры являются композиционными - т.е. состоят из композиции простых преобразований или F=F₁ o F₂ o F₃ o F₄ o .. o F _n, где F - преобразование шифра, F_i - простое преобразование, называемое также i-ым циклом шифрования. Само по себе преобразование может и не обеспечивать нужных свойств, но их цепочка позволяет получить необходимый результат. Например, стандарт DES состоит из 16 циклов. Если же используется одно и то же преобразование, т.е. F_i постоянно для i, то такой композиционный шифр называют итерационным шифром.

Наибольшую популярность имеют шифры, устроенные по принципу шифра Фейстеля (Файстеля - Feistel), в которых:

1. Входной блок для каждого преобразования разбивается на две половины: p=(l,r), где l - левая, a r - правая;

2. Используется преобразование вида F_i (l,r)=(r,lÄf_i(r)), где f_i – зависящая от ключа K_i функция, а Ä - операция XOR или некая другая.

Функция f_i называется цикловой функцией, а ключ K_i, используемый для получения функции f_i называется цикловым ключом. Как можно заметить, с цикловой функцией складывается только левая половина, а правая остается неизменной. Затем обе половины меняются местами. Это преобразование прокручивается несколько раз (несколько циклов) и выходом шифра является получившаяся в конце пара (l,r) Графически все выглядит следующим образом (рис. 2.2):

Рисунок 2.2 – Пример одного цикла преобразований

В качестве функции f_i выступает некая комбинация перестановок, подстановок, сдвигов, добавлений ключа и прочих преобразований. Так, при использовании подстановок информация проходит через специальные блоки, называемые S-блоками (S-боксами, S-boxes), в которых значение группы битов заменяется на другое значение. По такому принципу (с небольшими отличиями) построены многие алгоритмы: DES, ит.п. В других алгоритмах используются несколько иные принципы. Так, например, алгоритмы, построенные по SP-принципу (SP-сети) осуществляют преобразование, пропуская блок через последовательность подстановок (Substitutions) и перестановок (Permutations). Отсюда и название– SP-сети, т.е. сети "подстановок-перестановок". Примером такого алгоритма является очень перспективная разработка Rijndael. Саму идею построения криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований была высказана Шенноном (идея многократного шифрования).

Размеры блоков в каждом алгоритме свои. DES использует блоки по 64 бита (две половинки по 32 бита), LOKI97 - 128 бит.

Получение цикловых ключей.

Ключ имеет фиксированную длину. Однако при прокрутке хотя бы 8 циклов шифрования с размером блока, скажем, 128 бит даже при простом прибавлении посредством XOR потребуется 8*128=1024 бита ключа, поскольку нельзя добавлять в каждом цикле одно и то же значение,так как это ослабляет шифр. Поэтому для получения последовательности ключевых бит придумывают специальный алгоритм выработки цикловых ключей (ключевое расписание - key schedule). В результате работы этого алгоритма из исходных бит ключа шифрования получается массив бит определенной длины, из которого по определенным правилам составляются цикловые ключи. Каждый шифр имеет свой алгоритм выработки цикловых ключей.

Режимы работы блочных шифров.

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

­ электронная кодовая книга - ECB (Electronic Code Book);

­ сцепление блоков шифротекста - CBC (Cipher Block Chaining);

­ обратная связь по шифротектсту - CFB (Cipher Feed Back);

­ обратная связь по выходу - OFB (Output Feed Back).

Обозначим применение шифра к блоку открытого текста как E_k(M)=C, где k - ключ, M - блок открытого текста, а C - получающийся шифротекст.

Электронная Кодовая Книга (ECB)

Рисунок 2.3 - Схема электронной кодовой книги

 

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

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

Основным достоинством этого режима является простота реализации.

Сцепление блоков шифротекста (CBC)

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

1. Первый блок складывается побитно по модулю 2 (XOR) с неким значением IV – вектором инициализации (Init Vector), который выбирается независимо перед началом шифрования.

2. Полученное значение шифруется.

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

Рисунок 2.4 - Схема с цепления блоков шифротекста

 

Расшифрование осуществляется в обратном порядке.

В виде формулы, преобразование в режиме CBC можно представить как C_i=E_k(M_iÅC_i-1), где i - номер соответствующего блока. Из-за использования такого сцепления блоков шифротекста с открытым текстом пропадают указанные выше недостатки режима ECB, поскольку каждый последующий блок зависит от всех предыдущих. Если во время передачи один из блоков шифротекста исказится (передастся с ошибкой), то получатель сможет корректно расшифровать предыдущие блоки сообщения. Проблемы возникнут только с этим "бракованным" и следующим блоками. Одним из важных свойств этого режима является "распространение ошибки"– изменение блока открытого текста меняет все последующие блоки шифротекста. Поскольку последний блок шифротекста зависит от всех блоков открытого текста, то его можно использовать для контроля целостности и аутентичности (проверки подлинности) сообщения. Его называют кодом аутентификации сообщения (MAC - Message Authentication Code). Он может защитить как от случайных, так и преднамеренных изменений в сообщениях.

Обратная связь по шифротексту (CFB)

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

Рисунок 2.5 - Схема о братной связи по шифротексту

 

Описание работы схемы:

1. IV представляет собой сдвиговый регистр. Вначале IV заполняется неким значением, которое называется синхропосылкой, не является секретным и передается перед сеансом связи получателю.

2. Значение IV шифруется.

3. Берутся первые k бит зашифрованного значения IV и складываются (XOR) с k битами открытого текста. Получается блок шифротекста из k бит.

4. Значение IV сдвигается на k битов влево, а вместо него становится значение ш.т.

5. Затем опять 2 пункт и т.д до конца цикла шифрования.

Расшифрование происходит аналогично.

Особенностью данного режима является распространение ошибки на весь последующий текст. Рекомендованные значения k: 1 <= k <= 8.

Применяется, как правило, для шифрования потоков информации типа оцифрованной речи, видео.

Обратная связь по выходу (OFB)

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

Рисунок 2.6 - Схема о братной связи по выходу

Расшифрование осуществляется аналогично. То есть, для любого блока длины k операция зашифрования выглядит следующим образом: C_i=M_iÅG_i, где G_i - результат зашифрования некоторого вектора, являющегося заполнением сдвигового регистра. Главное свойство шифра – единичные ошибки не распространяются, т.к. заполнение сдвигового регистра осуществляется независимо от шифротекста.

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

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

Аутентификация (authentication – проверка подлинности чего (или кого-)-либо. Может быть аутентификация пользователя, сообщения и т.д. Необходимо отличать ее от следующего понятия:

Идентификация (identification) – некое описательное представление какого-то субъекта. Так, если кто-то заявляет, что он – Вася Иванов, то он идентифицирует себя как "Вася Иванов". Но проверить, так ли это на самом деле (провести аутентификацию) мы можем только при помощи его паспорта.

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

Отправитель А хочет отправить некое сообщение (a₁,..,a_t). Он зашифровывает на секретном ключе, который знает только он и получатель, в режиме CBC или CFB это сообщение, а затем, из получившегося шифротекста, берет последний блок b_t из к бит (при этом к должно быть достаточно большим).

1. Отправитель А посылает сообщение (a₁,.., a_t, b_t) получателю в открытом виде или зашифровав его на другом ключе.

2. Получатель В, получив сообщение, (a₁,.., a_t, b_t), зашифровывает (a₁,..,a_t) в том же режиме, что и А (должна быть договоренность) на том же секретном ключе (который знает только он и А).

3. Сравнивая полученный результат с b_t он удостоверяется, что сообщение отправил А, что оно не было подделано на узле связи (в случае передачи в открытом виде).

В данной схеме b_t является кодом аутентификации сообщения (МАС). Для российского стандарта шифрования процесс получения кода аутентификации называется работой в режиме имитовставки.

Некоторые комментарии:

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

 

 

Задание к лабораторной работе:

1. Изучить алгоритм и разработать программу реализации алгоритма хеш-функции в соответствии с вариантом:

- алгоритм Электронная Кодовая Книга -

<номер по журналу > MOD 4 = 0;

- алгоритм Сцепление блоков шифротекста -

<номер по журналу > MOD 4 = 1;

- алгоритм Обратная связь по шифротексту -

<номер по журналу > MOD 4 = 2;

- алгоритм Обратная связь по выходу -

<номер по журналу > MOD 4 = 0;

2. Проанализировать алгоритм с точки зрения его безопасности.

 

Контрольные вопросы к лабораторной работе:

1. В чем отличие принципов симметричного и асимметричного шифрования;

2. Каковы основные принципы построения блочных и поточных алгоритмов;

3. В чем принцип рассеивания и перемешивания;

4. Для чего используется вектор инициализации.

 

Лабораторная работа №3

Тема: Однонаправленные хеш-функции в криптографии.

Цель: Изучение алгоритмов построения и использования однонаправленных хеш-функций.

 

Методические указания к выполнению лабораторной работы

Согласно Шнайдеру Б. однонаправленная функция Н (М) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h, то есть

h = Н (М), где h имеет длину т.

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

Зная М, легко вычислить h.

Зная Н, трудно определить М, для которого H(M)=h.

Зная М, трудно определить другое сообщение М’, для которого Н (М) = Н(М').

То есть смысл однонаправленных хэш-функций и состоит в обеспечении для М уникального идентификатора ("отпечатка пальца"). Если Алиса подписала М с помощью алгоритма цифровой подписи на базе Н (М), а Боб может создать М', другое сообщение, отличное от М, для которого Н (М) = Н(М'), то Боб сможет утверждать, что Алиса подписала М'.

В ряде приложений однонаправленности недостаточно, необходимо выполнение другого требования, называемого устойчивостью к коллизиям. Его можно сформулировать так: трудно найти два случайных сообщения М и М', для которых Н (М) = Н(М').

Проанализируем протокол, впервые описанный Гидеоном Ювалом, который показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обмана Боба. Он основан не на поиске другого сообщения М, для которого Н (М) = Н(М'), а на поиске двух случайных сообщений, М и М', для которых Н (М) = Н(М') (метод «дней рождений» смотри в Шнайдере раздел7.4).

1. Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству

2. Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хэш-функции.
(Этими изменениями могут быть действия, подобные следующим: замена ПРОБЕЛА комбинацией ПР О-БЕЛ-ЗАБОЙ-ПРОБЕЛ, вставка одного-двух пробелов перед возвратом каретки, и т.д. Делая или не делая по одному изменению в каждой из 32 строк, Алиса может легко получить 2 ³² различных документов.)

3. Алиса сравнивает хэш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. (Если выходом хэш-функции является всего лишь 64-разрядное значение, Алиса, как правило, сможет найти совпадающую пару сравнив 2³² версий каждого документа.) Она
восстанавливает два документа, дающих одинаковое хэш-значение.

4. Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только хэш-значение.

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

Это серьезная проблема. Одним из советов по ее избежанию является обязательное внесение мелких изменений в подписываемый документ.

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