Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

Воронежский государственный УНИВЕРСИТЕТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ Кафедра ИНФОРМАЦ

Работа добавлена на сайт samzan.net: 2015-07-05

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 20.5.2024

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

––––––––––––––––––

ФГБОУ ВПО

«Воронежский государственный УНИВЕРСИТЕТ

ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ»

––––––––––––––––––

Кафедра ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ

‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗‗

Методические указания
к ЛАБОРАТОРНЫМ работам

по ДИСЦИПЛИНЕ

«Криптографические методы защиты информации»

Для студентов, обучающихся по специальностям

090105 - «Комплексное обеспечение информационной

безопасности автоматизированных систем» и 090303 – «Информационная безопасность автоматизированных систем»

Дневной формы обучения

––––––––––––––––––––––––––––

Воронеж

2013

УДК

ББК

Методические указания к лабораторным работам по дисциплине «Криптографические методы защиты информации»/ВГУИТ; Сост. Родин С.В., Перминов Г.В., Кочедыков С.С. Воронеж, 2012. 00с.

Методические указания разработаны в соответствии требованиями ООП подготовки инженеров направлений: 090105 – «Комплексное обеспечение информационной безопасности автоматизированных систем», 090303 – «Информационная безопасность автоматизированных систем» и предназначены для закрепления теоретических знаний дисциплины цикла ОПД.Ф15

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

Составители: доцент Родин С.В., Перминов Г.В., доцент Кочедыков С.С.

Научный редактор: профессор Абрамов Г.В.

Рецензенты: Начальник кафедры информационной безопасности Воронежского института МВД России, кандидат технических наук, доцент Бабкин А.Н.

Старший преподаватель кафедры технических комплексов охраны и связи Воронежского института ФСИН России к.т.н., Четкин О.В.

Печатается по решению редакционно-издательского совета

Воронежского государственного университета инженерных

технологий

Содержание

Общие требования по выполнению лабораторных работ
Часть 1. Краткие теоретические сведения
§1. Криптографические свойства шифров замены и гаммирования
§2. Характеристики стойкости шифров
§3. Методы криптоанализа поточных шифров
§4. Криптографические свойства шифрсистем поточного типа
§5. Криптографические свойства шифрсистем с открытым ключом
§6. Криптографические свойства Шифра эль-гамаля
§7. Протоколы распределения ключей
Часть 2. Лабораторный практикум
Лабораторная работа №1. Исследование криптографических свойств шифров замены и гаммирования
Лабораторная работа №2. Характеристики стойкости шифров
Лабораторная работа №3. Методы криптоанализа поточных шифров
Лабораторная работа №4. Исследование криптографических свойств шифрсистем поточного типа
Лабораторная работа №5. Исследование криптографических свойств шифрсистем с открытым ключом
Лабораторная работа №6. Исследование криптографических свойств шифра Эль-Гамаля
Лабораторная работа №7. Система распределения ключей ЭЦП

ОБЩИЕ ТРЕБОВАНИЯ ПО ВЫПОЛНЕНИЮ

ЛАБОРАТОРНЫХ РАБОТ

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

Выполнение лабораторной работы включает следующие этапы:

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

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

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

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

Отчеты должны содержать:

тему и цель работы;
перечень используемых приборов и оборудования;
основные расчетные формулы;
таблицы и графики экспериментальных данных и рассчитанных величин;
объяснение полученных результатов (выводы).

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

Часть 1. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА ШИФРОВ

ЗАМЕНЫ И ГАММИРОВАНИЯ

1.1 Основные статистическими характеристиками

открытых текстов

Любой метод вскрытия шифра простой замены основан на том обстоятельстве, что с точностью до переобозначений частотные характеристики т -грамм шифртекста и открытого текста одинаковы. При этом используются априорные частотные характеристики предполагаемого открытого текста, получаемые с учетом "характера переписки". Как отмечено в Приложении 1, такие характеристики являются более "рельефными" для литературных текстов и менее "рельефными" для формализованных электронных текстов. Чем менее рельефно распределение знаков текста, тем сложнее задача вскрытия шифра простой замены. Для открытых текстов с "почти равномерным" распределением знаков эта задача становится практически не решаемой. Это следует учитывать и не питать иллюзий о простоте вскрытия шифров простой замены, о которой часто упоминается в популярных книгах по защите информации. Методы "рандомизации" или "сжатия" открытых текстов, например, с использованием компьютерных архиваторов значительно усложняют задачу вскрытия шифра простой замены.

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

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

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

Если длина текста достаточно велика, то найденные на этапе 1 частоты окажутся близкими к табулированным значениям частот знаков (см. табл. 1) [1].

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

Таблица 1.

Частоты букв русского языка (в 32-буквенном алфавите со знаком пробела)

 0,175	O 0,090	Е,Ё 0,072	А 0,062
И 0,062	Т 0,053	Н 0,053	С 0,045
Р 0,040	В 0,038	Л 0,035	К 0,028
М 0,026	Д 0,025	П 0,023	У 0,021
Я 0,018	Ы 0,016	З 0,016	Ь, Ъ 0,014
Б 0,014	Г 0,013	Ч 0,012	Й 0,010
Х 0,009	Ж 0,007	Ю 0,006	Ш 0,006
Ц 0,004	Щ 0,004	Э 0,003	Ф 0,002

При этом учитывается, что каждая буква имеет группу предпочтительных связей (см. табл. 2)[1], которые составляют ее наиболее характерную особенность.

Как правило, такие гипотезы подтверждаются не полностью. Хорошим критерием при этом является "читаемость" восстанавливаемого открытого текста.

Устойчивыми являются также частотные характеристики биграмм, триграмм и четырехграмм осмысленных текстов.

Приведем таблицы частот биграмм для русского языка (табл. 3) (таблица заимствована из книги [2]).

Таблица 2

Сочетаемость букв русского языка

Г	С	Слева		Справа	Г	С
3	97	л, д, к, т, в, р, н	А	л, н, с, т, р, в, к, м	12	88
80	20	я, е, у, и, а, о	Б	о, ы, е, а, р, у	81	19
68	32	я, т, а, е, и, о	В	о, а, и, ы, с, н, л, р	60	40
78	22	р, у, а, и, е, о	Г	о, а, р, л, и, в	69	31
72	28	р, я, у, а, и, е, о	Д	е, а, и, о, н, у, р, в	68	32
19	81	м, и, л, д, т, р, н	Е	н, т, р, с, л, в, м, и	12	88
83	17	р, е, и, а, у, о	Ж	е, и, д, а, н	71	29
89	11	о, е, а, и	З	а, н, в, о, м, д	51	49
27	73	р, т, м, и, о, л, н	И	с, н, в, и, е, м, к, з	25	75
55	45	ь, в, е, о, а, и, с	К	о, а, и, р, у, т, л, е	73	27
77	23	г, в, ы, и, е, о, а	Л	и, е, о, а, ь, я, ю, у	75	25
80	20	я, ы, а, и, е, о	М	и, е, о, у, а, н, п, ы	73	27
55	45	д, ь, н, о, а, и, е	Н	о, а, и, е, ы, н, у	80	20
11	89	р, п, к, в, т, н	О	в, с, т, р, и, д, н, м	15	85
65	35	в, с, у, а, и, е, о	П	о, р, е, а, у, и, л	68	32
55	45	и, к, т, а, п, о, е	Р	а, е, о, и, у, я, ы, н	80	20
69	31	с, т, в, а, е, и, о	С	т, к, о, я, е, ь, с, н	32	68
57	43	ч, у, и, а, е, о, с	Т	о, а, е, и, ь, в, р, с	63	37
15	85	п, т, к, д, н, м, р	У	т, п, с, д, н, ю, ж	16	84
70	30	н, а, е, о, и	Ф	и, е, о, а, е, о, а	81	19
90	10	у, е, о, а, ы, и	Х	о, и, с, н, в, п, р	43	57
69	31	е, ю, н, а, и	Ц	и, е, а, ы	93	7
82	18	е, а, у, и, о	Ч	е, и, т, н	66	34
67	33	ь, у, ы, е, о, а, и, в	Ш	е, и, н, а, о, л	68	32
84	16	е, б, а, я, ю	Щ	е, и, а	97	3
0	100	м, р, т, с, б, в, н	Ы	л, х, е, м, и, в, с, н	56	44
0	100	н, с, т, л	Ь	н, к, в, п, с, е, о, и	24	76
14	86	с, ы, м, л, д, т, р, н	Э	н, т, р, с, к	0	100
58	42	ь, о, а, и, л, у	Ю	д, т, щ, ц, н, п	11	89
43	57	о, н, р, л, а, и, с	Я	в, с, т, п, д, к, м, л	16	84

Таблица 3

Таблица частот биграмм русского языка

	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
А	2	12	35	8	14	7	6	15	7	7	19	27	19	45	5	11	26	31	27	3	1	10	6	7	10	1			2	6	9
Б	5					9	1		6			6		2	21		8	1		6						1	11				2
В	35	1	5	3	3	32		2	17		7	10	3	9	58	6	6	19	6	7		1	1	2	4	1	18	1	2		3
Г	7				3	3			5		1	5		1	50		7			2
Д	25		3	1	1	29	1	1	13		1	5	1	13	22	3	6	8	1	10			1	1	1		5	1			1
Е	2	9	18	11	27	7	5	10	6	15	13	35	24	63	7	16	39	37	33	3	1	8	3	7	3	3			1	1	2
Ж	5	1			6	12			5					6				1
З	35	1	7	1	5	3			4		2	1	2	9	9	1	3	1		2							4				4
И	4	6	22	5	10	21	2	23	19	11	19	21	20	32	8	13	11	29	29	3	1	17	3	11	1	1			1	3	17
Й	1	1	4	1	3		1	2	4		5	1	2	7	9	7	3	10	2				1	3	2
К	24	1	4	1		4	1	1	26		1	4	1	2	66	2	10	3	7	10			1
Л	25	1	1	1	1	33	2	1	36		1	2	1	8	30	2		3	1	6		4		1			2	30		4	9
М	18	2	4	1	1	21	1	2	23		3	1	3	7	19	5	2	5	3	9	1			2			5	1	1		3
Н	54	1	2	3	3	34			58		3		1	24	67	2	1	9	9	7	1		5	2			36	3			5
О	1	28	84	32	47	15	7	18	12	29	19	41	38	30	9	18	43	50	39	3	2	5	2	12	4	3			2	3	2
П	7					15			4			9		1	46		41	1		6							2				2
Р	55	1	4	4	3	37	3	1	24		3	1	3	7	56	2	1	5	9	16		1	1	1	2		8	3			5
С	8	1	7	1	2	25			6		40	13	3	9	27	11	4	11	82	6		1	1	2	2		1	8			17
Т	35	1	27	1	3	31		1	28		5	1	1	11	56	4	26	18	2	10				1			11	21			4
У	1	4	4	4	11	2	6	3	2		8	5	5	5	1	5	7	14	7			1		8	3	2				9	1
Ф	2					2			2						1		1	1
Х	4	1	4	1	3	1		2	3		4	3	3	4	18	5	3	4	2	2	1			1
Ц	3					7			10		2				1					1							1
Ч	12					23			13		2			6					7	1					1			1
Ш	5					11			14		1	2		2	2					1								1
Щ	3					8			6					1						1
Ы		1	9	1	3	12		2	4	7	3	6	6	3	2	10	3	9	4	1		16		1	2
Ь		2	4	1	1	2		2	2		6		3	13	2	4	1	11	3					1	4				1	3	1
Э											1			1				1	9
Ю		2	1	2	1			3	1		1		1	1	1	3	1	1	7				1	1		4
Я	1	3	9	1	3	3	1	5	3	2	3	3	4	6	3	6	3	6	10			2	1	4	1	1			1	1	1

Выделение шифробозначений, отвечающих гласным и согласным, основано на характерных свойствах этих букв, учитывающих устойчивую закономерность открытых текстов, связанную с чередованием гласных и согласных букв. Подсчитаны частоты встречаемости биграмм вида гласная-гласная (г, г), гласная-согласная (г,с), согласная-гласная (с,г), согласная-согласная (с,с) в русском тексте длиной в 105 знаков. Результаты подсчета отражены в Таблице 4[1].

Таблица 4

Чередование гласных и согласных

	Г	С	ВСЕГО
Г	6588	38310	44898
С	38296	16806	55102

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

При проверке гипотез о значениях шифробозначений полезен поиск в шифртексте слов с характерной структурой, которые часто встречаются в открытом тексте. Для русского языка — это, например, слова сколько, которое, что и т. п. Для английского языка — слова every, that, look, theи т. п. Такие слова выделяются в шифртексте посредством интервалов между повторяющимися частыми буквами, характерными сочетаниями гласных и согласных.

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

Алгебраические модели шифров замены.

Определим модель А(Х, К, Y, E, D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитахА и В соответственно: , . Здесь и далееС* обозначает множество слов конечной длины в алфавите С[1].

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

Пусть U = {u1, u2, …, uN} — множество возможныхшифрвеличин, V = {v1, v2, …, vM}— множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты xX, yYможно было представить словами из U*, V* соответственно. Требование однозначности расшифрования влечет неравенства Nп, Мт, МN.

Часто алфавитыА* и В* совпадают, что значительно упрощает модель такого шифра.

Шифр простой замены в алфавите А.

Определение. Пусть , , где S(A) — симметрическая группа подстановок множества А. Для любого ключа kК, открытого текста x = (x1, …xl) и шифрованного текста y = (y1, …yl) правила зашифрования и расшифрования шифра простой замены в алфавите А определяются выражениями

(1)

где k-1 — подстановка, обратная к k.

В более общей ситуации для шифра простои замены , причем , a K представляет собой множество всех биекций множестваА на множество В. Правила зашифрования и расшифрования определяются для kК, хX, уY (и обратной к k биекции k-1) выражениями (1).

Методы бесключевого чтения шифров.

Рассмотрим криптограмму, которая расположена в строках таблицы 5 [1].

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

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

Построим диаграмму встречаемости букв криптограммы.

Подсчет дает следующие значения относительных частот букв (в процентах):

А	Б	В	Г	Д	Е	Ж	З	И	К	Л	М	Н	О
1,80	7,54	6,9	11	2,1	8,9	4,1	6,1	5,1	1,5	3,6	0,2	9,5	2

П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
0	6,4	3,4	4,6	1,2	1	0	1,5	0,5	3,8	0	1	3,8	0,5	1,3	1

Таблица 5.

На основании этих данных получаем диаграмму встречаемости букв криптограммы:

Рис. 1. Диаграмма встречаемости букв криптограммы

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

В матрице биграмм имеется ярко выраженный лидер: биграмма ЗИ встретилась 11 раз. Естественно предположить, что она заменяет биграмму СТ открытого текста (наиболее часто встречающуюся в русском литературном тексте). Явным лидером по частоте встречаемости является буква Г. Предположим, что она заменяет букву О.

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

Обратим внимание на некоторые получившиеся фрагменты открытого текста: 0?0?ОТТ и СТ? (15-я строка), ?СТО (6 - я строка), СОС? (26-я строка), на основании которых можно выдвинуть гипотезы о том, что вторая по частоте буква шифртекста Н — гласная (причем совпадающая с одной из букв И, Е, А), а пятая по частоте буква шифртекста В — согласная (и поэтому она, скорее всего, Н, так как С и Т уже задействованы).

Обратим также внимание на два частых удвоения: ЕЕ (4 раза) и ВВ (6 раз). Самыми частыми в открытом тексте являются удвоения ИИ, НН, 00, СС. Это дает основание полагать, что В заменяет букву Н открытого текста.

Буква Е — третья по частоте в криптограмме, поэтому вполне вероятно, что она заменяет одну из букв И, Е или А открытого текста.

Таблица 6.

Учитывая сделанное замечание об удвоениях, сделаем предположение о том, что Е заменяет букву И.

Дополним последнюю таблицу новыми предположениями о заменах (табл. 7).

Обратим внимание на то, что биграмма ВБ встречается в криптограмме 9 раз. По нашему предположению В заменяет в криптограмме букву открытого текста Н. Согласно таблице биграмм открытого текста, самыми частыми биграммами с первой буквой Н являются НО, НА, НИ. Буквы О и И уже задействованы, поэтому оправдана гипотеза о том, что ВБ заменяет биграмму открытого текста НА.

Мы уже замечали, что Н заменяет одну из букв А, Е, И открытого текста. С учетом предыдущего остается лишь одна возможность: Н заменяет букву Е.

Полученные результаты представлены в таблице 8.

Далеепоследовательно определяются многие другие буквы. Так, из второй строки легко заметить, что Ш заменяет букву Д открытого текста, Т — букву Л. Из рассмотрения четвертой строки следует, что Ь заменяет М, из восьмой строки — что Р заменяет В, а С — букву К, из восемнадцатой — что Ж заменяет Р и т.д. Теперь легко закончить работу, убедившись в том, что наши гипотезы оправдались (см. табл. 9).

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

Ключом использованного в примере шифра является следующий подстановочный алфавит, составленный на основе ключевой фразы БАРЫШНЯ КРЕСТЬЯНКА, совпадающей с названием одноименной повести А.С. Пушкина. Особенности таких (систематически перемешанных) алфавитов существенно помогают в восстановлении текстов.

Таблица 7.

Таблица 8.

Таблица 9.

3. Вопросы к домашним заданиям:

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

§2. ХАРАКТЕРИСТИКИ СТОЙКОСТИ ШИФРОВ

Основные положения теории надежности шифров.

Определение 1. Криптографическая стойкость — фундаментальное понятие криптографии — свойство криптосистемы (криптопротокола), характеризующее ее (его) способность противостоять атакам противника и/или нарушителям, как правило, имеющим целью получить секретный ключ или открытое сообщение.

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

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

Теоретическая стойкость — криптографическая стойкость, определяемая в рамках некоторой математической модели. Основные подходы к теоретической стойкости в настоящее время:

теоретико-информационная стойкость;
теоретико–сложностная стойкость.

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

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

Определение 5. Под имитовводом понимается любое преднамеренное необнаруженное изменение передаваемой информации.

Понятия энтропии и избыточности языка

Глубокие свойства текстов изучаются методами теории информации, разработанной К.Шенноном[3]. Речь идет о "количестве информации", содержащейся в сообщении. Для выяснения этого необходимо ввести меру количества информации.

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

прирост информации равен устраненной неопределенности,

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

К такому выводу можно прийти на примере эксперимента со случайным бросанием монеты. Какова неопределенность того, что в результате очередного бросания монеты выпадет «орел»? Если монета дефектна и при бросании всегда выпадает орлом, никакой неопределенности нет — наоборот, есть полная определенность: обязательно выпадет «орел». Максимальной же неопределенность будет, очевидно, в случае, когда монета не имеет дефектов, то есть с равными вероятностями выпадают обе ее стороны.

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

(1)

энтропия H() формально определяется формулой

(2)

Единицу измерения энтропии вероятностной схемы предлагает так называемая теорема кодирования [4], утверждающая, что любой исход можно закодировать символами 0 и 1 так, что полученная длина кодового слова будет сколь угодно близка сверху к H(). На основании этого единицей количества информации естественно считать 1 бит. Например, количество информации, получаемое при бросании монеты, равно 1 бит, так как «орел» можно закодировать единицей, а «решку» — нулем.

Легко видеть, что если pi = 1/ппри всех i =1,…,n, то H0 = H()=log2n. Кроме того, в общем случае имеет место неравенство H()0, причем H()= 0 в том и только том случае, когда pi=1 для некоторого i и pj=0 для всех ji.

Мерой средней информации, приходящейся на одну букву открытого текста языка  (рассматриваемого как источник случайных текстов), служит величина H, называемая энтропией языка . Естественно вычислять ее последовательными приближениями: Н0, H1, где Н1 — энтропия позначной модели открытого текста, то есть величина (2), в которой pi, совпадает с вероятностью появления буквы аi в открытом тексте. Для английского языка, Н04,70, Н1 =H()4,14.

В качестве следующего, более точного приближения, возьмем энтропию вероятностного распределения биграмм, которую разделим на 2 (нас интересует энтропия на знак). В общем случае следует взять энтропию вероятностной схемы на r-граммах, деленную на r. Соответствующие вычисления для английского языка дают отношения и так далее. Исследования показывают, что с ростом rотношение стремится к некоторому пределу. Этот предел и принимается за определение энтропии Hязыка :

(3)

При этом выражение

(4)

определяет так называемую избыточность языка R.

Термин избыточность языка возник в связи с тем, что максимальная информация, которую в принципе могла бы нести каждая буква сообщения, равна Н0 = Iog2n(где n — число букв в алфавите). Как было отмечено выше, так было бы в случае, если буквы сообщения появлялись случайно и равновероятно. В то же время, средняя энтропия буквы в открытом тексте значительно меньше и, следовательно, буква несет меньше информации, чем log2n. Величина log2n-H характеризует, таким образом, неиспользованные возможности в передаче информации с помощью текста, а отношение

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

К. Шеннон предложил метод оценивания отношения Нr/rдля осмысленных текстов с позиции меры неопределенности опыта, состоящего в угадывании r-й буквы текста, при условии, что предшествующие его буквы известны [3]. Эксперимент по угадыванию r-й буквы текста легко может быть поставлен. Для этого достаточно выбрать осмысленный отрезок открытого текста длины r-1 и предложить кому-либо угадать следующую букву. Подобный опыт может быть повторен многократно, при этом сложность угадывания r-й буквы может быть оценена с помощью среднего значения числа попыток Fr, требующихся для нахождения правильного ответа. Ясно, что величины Fr для разных значений rявляются определенными характеристиками статистической структуры языка. Очевидно, что среднее число попыток Fr с ростом rможет лишь уменьшаться. Прекращение этого уменьшения будет свидетельствовать о том, что соответствующие опыты имеют одинаковую неопределенность, то есть что отвечающая им величина Нr/rпрактически уже достигла своего предельного значения H.

Исходя из этих рассуждений, К. Шеннон произвел ряд подобных экспериментов, в которых rпринимало значения 1,…,15 и 100. При этом он обнаружил, что отгадывание сотой буквы по 99 предшествующим заметно более просто, чем угадывание 15-й буквы по 14-предыдущим. Опыты показали, что с ростом rвеличина Нr/rубывает вплоть до r30, а при дальнейшем росте rона уже практически не меняется.

Согласно исследованиям Б. Б. Пиотровского [4], имеют место следующие приближения величины H:

Таблица 1

	H	R
	Русский язык	Французский язык	Русский язык	Французский язык
Язык в целом	1,37	1,40	72,6	70,6
Разговорная речь	1,40	1,50	72,0	68,4
Литературный текст	1,19	1,38	76,2	71,0
Деловой текст	0,83	1,72	83,4	74,4

Из приведенной таблицы видно, что языки имеют весьма большую избыточность. Однако, избыточность, составляющая 75%не означает буквально то, что любые 3 из 4 букв текста можно вычеркнуть без потери информации. Более точно это означает, что при оптимальном кодировании текста (при использовании, например, кода Хаффмена, кода Фаноили другого оптимального кода [3]) его можно сжать до четверти длины без потери смысла.

Другой,так называемый комбинаторный подход [4] к определению величины H для литературных текстов предложил А. Н. Колмогоров, не согласившись с тем, что теоретико-информационные рассмотрения игнорируют вопрос о смысловом содержании литературных текстов. Суть такого подхода к определению энтропии текста состоит в следующем: Шенноновскую энтропию H, приходящуюся на букву текста, можно определить тем условием, что для n-буквенного алфавита число текстов длины L, удовлетворяющих заданным статистическим ограничениям, равно (при достаточно больших L) не nL=2Llog2n=2LH0, как это было бы, если брать любые наборы из Lбукв, а всего лишь M(L)=2LH(5).

По сути, это и есть асимптотика числа осмысленных открытых текстов длины Lдля данного языка . Исходя из этого, можно определить энтропию H языка выражением

(6)

не зависящим ни от каких теоретико-вероятностных представлений. Величину M(L) можно оценивать с помощью подсчета числа возможных продолжений литературного текста.

Понятия количества ложных ключей и расстояния единственности для шифра

Попытки определения истинного ключа шифра по данной криптограмме путем ее расшифрования на всех возможных, ключах могут привести к тому, что критерий на открытый текст примет несколько претендентов за открытый текст. Это объясняется не только недостатками критерия. При небольших длинах криптограмм результат ихрасшифрования может дать несколько осмысленных текстов. Например, криптограмму WNAJW, полученную при использовании сдвигового шифра для английского языка, порождают два открытых текста RIVER и ARENA, отвечающих ключам F (=5) и W (=22). При этом один из ключей является истинным, а другой — ложным. Аналогичная ситуация может иметь место для любого другого шифра.

Найдем оценку для числа ложных ключей. Для этого рассмотрим связь между энтропиями вероятностных распределений Р(Х), Р(К), P(Y), заданных на компонентах X,K,Yпроизвольного шифра B.

Введем дополнительные понятия об условной энтропии двух вероятностных распределений. Пусть имеются дискретные случайные величины  и , заданные вероятностными распределениями P(), P(). Для них можно вычислить совместное распределение P(,) и условные распределения P(/y), P(/x) для любых фиксированных значений x,y. Определим условную энтропию H(,) выражением:

Усредненная (по всем y) величина H(,) называется условной энтропией двух вероятностных распределений:

(7)

(При этом из (7) исключаются слагаемые, для которых p(x/y)=0)

Величина (7) измеряет среднее количество информации о , обнаруживаемое с помощью . Известно [3], что имеет место неравенство H(/)H(), причем равенство H(/)=H(), выполняется тогда и только тогда, когда , — независимые случайные величины.

Назовем условную энтропию H(K/Y) неопределенностью шифраB по ключу. Она измеряет среднее количество информации о ключе, которую дает шифртекст. Аналогично вводится неопеределенность шифра по открытому тексту H(X/Y). Эти величины являются мерой теоретической стойкости шифра.

Минимально возможным значением неопределенности шифра по открытому тексту H(X/Y) является 0. Равенство H(X/Y)=0 выполняется лишь тогда, когда каждое слагаемое в выражении для H(X/Y) равно нулю:

p(y)p(x/y)log2p(x/y)=0

для всех х,у. Это возможно лишь в случае, когда log2р(х/у) = 0, то есть если p(x/y) = 1 при некоторых х,у. Это означает, что по данному уоднозначно восстанавливается х, что свидетельствует о серьезной слабости шифра. Чем больше H(X/Y), тем меньше информации получает противник об открытом тексте по криптограмме. Идеальной является ситуация, когда H(X/Y) = Н(Х). Именно в этом случае шифр можно было бы назвать идеальным или совершенным. Такое представление полностью соответствует определению совершенного по К.Шеннону шифра.

Связь между энтропиями компонент шифра дает известное [3] выражение для неопределенности шифра по ключу:

H(K/Y)=H(X)+H(K)-H(Y), (8)

полученное К. Шенноном. Этовыражение позволит получить оценку среднего числа ложных ключей. Рассмотрим произвольный поточный шифр замены B, для которого множество Xоткрытых текстов представляет собой множество возможных осмысленных текстов в данном алфавите A (например, русском, английском или некотором другом), состоящем из nбукв. Зафиксируем некоторое число LN, иопределим число ложных ключей, отвечающих данной криптограмме уAL. (предполагается, чтоАслужит также алфавитом шифрованного текста.).

Введем обозначение

K(y)={kK:xX,Ek(x)=y}, (9)

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

Если мы располагаем криптограммой у, то число ложных ключей равно |К(у)| -1, так как лишь один из допустимых ключей является истинным. Определим среднее число ложных ключей kL(относительно всех возможных шифртекстов длины L)выражением,

(10)

которjt легко приводится к виду

(11)

Теорема. Для любого рассматриваемого шифра B с равновероятными ключами при достаточно больших значениях L имеет место неравенство

(12)

где R — избыточность данного языка.

Назовем расстоянием единственности для шифраB натуральное число (которое обозначим L0), для которого ожидаемое число ложных ключей k равно нулю.

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

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

откуда при kL = 0 получаем |K|и, следовательно,

Минимально возможное значение Lв этом неравенстве и принимается за L0. Таким образом

(13)

Несмотря на некоторую некорректность вывода выражения (13), оно тем не менее хорошо согласуется с практикой.

Например, для шифра простойзамены с параметрами п = 26, К =26!, R= 0,75выражение (13) дает оценку

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

Замечания:

1. Следует иметь в виду, что при попытке вскрыть, например, шифр простой замены с использованием только частот букв целесообразно оценивать расстояние единственности с учетом оценки энтропии H величиной H1, вычисленной для позначной модели открытого текста. При этом оценка для расстояния единственности может существенно вырасти. При использовании частот биграмм целесообразно H приблизить величиной Н2и так далее.

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

Основные выражения.

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

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

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

Энтропия языка – мера средней информации, приходящейся на одну букву открытого текста языка.

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

Избыточность языка определяется в соответствии с выражением:

Вопросы к домашним заданиям

Понятие криптографической стойкости
Понятиеатаки на криптосистему
Что такое Практическая и Теоретическая стойкость шифра?
Что такое Хеш-функции? Ключевые и бесключевые хэш-функции.
Понятие энтропии. Формула нахождения. Физический смысл. Понятие энтропии языка.
Понятие избыточность языка. Формула нахождения. Физический смысл.
Понятие расстояния единственности для шифра. Формула нахождения. Физический смысл.
Понятие имитостойкостишифра.

3. МЕТОДЫ КРИПТОАНАЛИЗА ПОТОЧНЫХ ШИФРОВ

Криптоанализ поточных шифрсистем

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

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

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

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

Третий подход основан на подборе у функции усложнения хороших приближений в классе линейных функций.

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

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

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

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

статистических;
аналитических;
комбинаторных свойств используемых преобразований (с учетом возможностей вычислительной техники).

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

Особенности криптоанализа блочных шифров.

Базовым при использовании блочных шифров является режим простой замены[1].

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

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

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

При случайном выборе блоков открытого текста их повторение является не столь уж редким событием. Напомним известный парадокс «дней рождений», который заключается в том, что если имеется выборка объема, сравнимого с , множества из N элементов, то вероятность того, что в ней окажутся два одинаковых элемента, сравнима с 1/2. Этот парадокс показывает, что при случайном выборе блоков открытого текста для получения повтора достаточно взять в среднем порядка блоков, где N — общее число блоков, которые теоретически могут встретиться в открытом тексте.

Применительно к алгоритмам DES и ГОСТ 28147-89, которые оперируют с двоичными векторами длины 64, это означает, что в среднем, уже среди 232 блоков открытого текста, будут встречаться повторяющиеся.

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

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

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

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

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

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

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

Р. Меркль и М. Хеллман на примере DES показали, как, используя метод встречи посередине, можно вскрыть схему двукратного шифрования.

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

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

На первом этапе перебираются все возможные варианты ключа k1. Для каждого варианта k ключа k1 вычисляются значения ADR(k) = Ek(М), после чего значения k помещаются в память по адресу ADR(k).

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

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

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

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

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

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

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

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

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

Криптографическая стойкость ГОСТа.

Надежность современных криптосистем оценивается в соответствии с правилом Кирхгоффа, - секретность зашифрованных сообщений определяется секретностью ключа. Это значит, что даже если сам алгоритм шифрования известен криптоаналитику, тот, тем не менее, не в состоянии расшифровать сообщение, если не располагает соответствующим ключом. Шифр считается хорошим, если нет способа вскрыть его более эффективным способом, чем полным перебором по всему ключевому пространству, т.е. по всем возможным значениям ключа. ГОСТ 28147-89 соответствует этому принципу – за годы интенсивных исследований не было предложено ни одного результативного способа его криптоанализа. В плане стойкости он на много порядков превосходит прежний американский стандарт шифрования, DES.

В ГОСТе используется 256-битовый ключ и объем ключевого пространства составляет 2256. Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем электронном устройстве нельзя подобрать ключ за время, меньшее многих сотен лет. Эта величина стала фактическим стандартом размера ключа для симметричных криптоалгоритмов в наши дни, – так, новый стандарт шифрования США также его поддерживает. Прежний же американский стандарт, DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 256 уже не является достаточно стойким в свете возможностей современных вычислительных средств. Это было продемонстрировано в конце 90-х годов несколькими успешными попытками взлома DES переборным путем. Кроме того, DES оказался подвержен специальным способам криптоанализа, таким как дифференциальный и линейный. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес. В 1998 году его криптографическая слабость была признана официально, – национальный институт стандартов США рекомендовал использовать троекратное шифрование по DES. А в конце 2001 года был официально утвержден новый стандарт шифрования США, AES, построенный на иных принципах и свободный от недостатков своего предшественника.

Замечания по архитектуре ГОСТ 28147-89 г.

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

Архитектура блочного шифраГОСТ 28147-89 г.

Алгоритмы «основных шагов криптопреобразования» для шифров, подобных ГОСТу, построены идентичным образом, и эта архитектура называется сбалансированная сеть Файстеля (balancedFeistelnetwork) по имени человека, впервые предложившего ее. Схема преобразования данных на одном цикле, или, как его принято называть, раунде, приведена на рисунке 1.

Рис.1. Схема преобразования данныхсбалансированной сети Фейстеля.

Содержание основного шага криптопреобразования для блочных шифров, подобных ГОСТу.

На вход основного шага подается блок четного размера, старшая и младшая половины которого обрабатываются отдельно друг от друга. В ходе преобразования младшая половина блока помещается на место старшей, а старшая, скомбинированная с помощью операции побитового «исключающего или» с результатом вычисления некоторой функции, на место младшей. Эта функция, принимающая в качестве аргумента младшую половину блока и элемент ключевой информации (X), является содержательной частью шифра и называется его функцией шифрования. По разным соображениям оказалось выгодно разделить шифруемый блок на две одинаковые по размеру части: |N 1|=|N 2| – именно этот факт отражает слово «сбалансированная» в названии архитектуры.

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

|N||X|

в ГОСТе все три размера равны 32 битам.

Если применить сказанное к схеме основного шага алгоритма ГОСТ 28147-89 г., станет очевидным, что блоки 1,2,3 алгоритма (см. рис. 1) определяют вычисление его функции шифрования, а блоки 4 и 5 задают формирование выходного блока основного шага исходя из содержимого входного блока и значения функции шифрования.

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

Разработчики ГОСТа учли как положительные, так и отрицательные стороны DESа, а также более реально оценили текущие и перспективные возможности криптоанализа. Впрочем, брать DES за основу при сравнении быстродействия реализаций шифров уже не актуально. У нового стандарта шифрования США дела с эффективностью обстоят гораздо лучше – при таком же как у ГОСТа размере ключа в 256 бит AES работает быстрее него примерно на 14% – в сравнении по числу «элементарных операций». Кроме того, ГОСТ практически не удается распараллелить, а у AES возможностей в этом плане намного больше. На некоторых архитектурах это преимущество AES может быть меньше, на других – больше. Так, на процессоре IntelPentium оно достигает 28%.

Требования к качеству ключевой информации и источники ключей.

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

Исчерпывающий ответ на вопрос о критериях качества ключей и таблиц замен ГОСТа если и можно вообще где-либо получить, то только у разработчиков алгоритма. Соответствующие данные не были опубликованы в открытой печати. Однако согласно установленному порядку, для шифрования информации, имеющей гриф, должны быть использованы ключевые данные, полученные от уполномоченной организации. Косвенным образом это может свидетельствовать о наличии методик проверки ключевых данных на «качество». Если наличие слабых ключей в ГОСТе – дискуссионный вопрос, то наличие слабых узлов замены не вызывает сомнения. Очевидно, что «тривиальная» таблица замен, по которой любое значение заменяется им же самим, является настолько слабой, что при ее использовании шифр взламывается элементарно, каков бы ни был ключ.

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

Сведения о ключевой информации

Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. Нельзя полностью исключить при этом, что некоторые конкретные значения ключа могут оказаться «слабыми», то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. По крайней мере, интенсивные исследования шифра до сих пор не выявили ни одного такого ключа, ни для одной из известных (т.е. предложенных ФАПСИ) таблиц замен. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел (СЧ), будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, – не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, – для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Неймана Пирсона («χ квадрат»), а для проверки независимости битов ключа – критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике, например [5].

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

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

Таблица замен

Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. Даже при нарушении конфиденциальности таблицы замен стойкость шифра остается чрезвычайно высокой и не снижается ниже допустимого предела. Поэтому нет особой нужды держать таблицу в секрете, и в большинстве коммерческих применений ГОСТа так оно и делается. С другой стороны, таблица замен является критически важным элементом для обеспечения стойкости всего шифра. Выбор ненадлежащей таблицы может привести к тому, что шифр будет легко вскрываться известными методами криптоанализа. Критерии выработки узлов замен – тайна за семью печатями и ФАПСИ (ФСО) вряд ли ей поделится с общественностью в ближайшем обозримом будущем. В конечном итоге, для того, чтобы сказать, является ли данная конкретная таблица замен хорошей или плохой, необходимо провести огромный объем работ – многие тысячи человеко- и машино-часов. Единожды выбранная и используемая таблица подлежит замене в том и только в том случае, если шифр с ее использованием оказался уязвимым к тому или иному виду криптоанализа. Поэтому лучшим выбором для рядового пользователя шифра будет взять одну из нескольких таблиц, ставших достоянием гласности. Например, из стандарта на хеш-функцию, она же «центробанковская»; сведения об этих таблицах можно найти в открытой печати и даже в интернете.

Для тех же, кто не привык идти легкими путями, ниже приведена общая схема получения качественных таблиц:

С помощью той или иной методики вырабатываете комплект из восьми узлов замен с гарантированными характеристиками нелинейности. Таких методик существует несколько, одна из них – использование так называемых бент-функций.

Проверяете выполнение простейших «критериев качества» – например, тех, что опубликованы для узлов замены DES.

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

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

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

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

Относительно таблицы замен необходимо отметить еще один интересный факт. Для обратимости циклов шифрования «32-З» и «32-Р» не требуется, чтобы узлы замен были перестановками чисел от 0 до 15. Все работает даже в том случае, если в узле замен есть повторяющиеся элементы, и замена, определяемая таким узлом, необратима, – однако в этом случае снижается стойкость шифра.

Возможные атаки на алгоритм A5.

Как и в любой системе шифрования, в системе безопасности GSM наибольший интерес представляет её стойкость к дешифрованию, особенно, если, по крайней мере, один из алгоритмов уже взломан.

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

Лобовая атака A5

Как было указано выше, лобовая атака системы безопасности в реальном времени невозможна. Сложность атаки составляет 254 (264 если 10 битов не были 0). Потребуется слишком много времени, чтобы прослушивание GSM звонков в реальном времени стало возможным. Можно было бы записать кадры между MS и BTS и после этого начать атаку.

Если имеется чип класса Pentium III, который содержит примерно 20 миллионов чипов, а для реализации одного набора LSFR схемы шифрования алгоритма А5 требуется 2000, то в одном чипе можно организовать примерно 10000 реализаций А5/1. При тактовой частоте 600 МГц, и если каждая реализация А5 выдает 1 бит за такт, и необходимо сгенерировать 100+114+114 бит, в реализации А5/1 можно проверять 2 миллиона ключей в секунду. Пространство ключей в 254 требует для перебора 900000 секунд или приблизительно 250 часов при одном чипе. Атака может быть оптимизирована отбрасыванием целых классов ключей после первого плохого бита ключевой последовательности. Это сократит требуемое время на одну треть. Атаку можно распределить между несколькими чипами, и таким образом значительно сократить время.

Атака A5 «Разделяй и Властвуй»

Атака «Разделяй и Властвуй» позволяет уменьшить стойкость алгоритма с 254 при лобовой атаке до 245, и это уже является относительно значительным изменением (29 - это в 512 раз быстрее). Атака «Разделяй и Властвуй» основана на известной атаке открытого текста. Атакующийпытается определить начальные состояния регистров LSFR из известной последовательности гаммы. Атакующий должен знать 64 последовательные бита гаммы, которые можно извлечь, если атакующий знает какой-либо текст шифра и соответствующий открытый текст. Это в большой степени зависит от формата GSM кадров, посылаемых туда и обратно. Кадры GSM содержат большое количество постоянной информации, например, заголовки кадров. Требуемые 64 бита не всегда могут быть получены, но 32 или 48 бит, иногда и больше, обычно известны. Атакующему необходим только сегмент из 64 битов открытого текста.

Одним словом, атака «Разделяй и властвуй» реализуется путем угадывания содержания двух более коротких LSFR, а затем вычисления третьего LSFR из известной гаммы. Это была бы атака 240, если бы синхронизация первых двух регистров не зависела от третьего регистра. Вследствие того, что центральный бит третьего регистра используется для синхронизации, необходимо также угадать почти половину битов третьего регистра между битом синхронизации и LSB. Этот факт увеличивает сложность атаки с 240 до 245.

Однако Дж. Голик[]предложил другую атаку «Разделяй и Властвуй», основанную на этих же предположениях, приблизительная сложность атаки 240. Он описывает, как получить линейное равенство, угадывая n биты в регистрах LSFR. Решив эти линейные уравнения, можно восстановить начальные состояния трех LSFR. Сложность решения линейных уравнений составляет 240. Существует только 50-процентная вероятность решения.

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

Доступ к сигнальной сети

Два примера, приведенные выше, четко доказывают, что криптографически алгоритм А5 ненадежен, учитывая возможность осуществить не только «Лобовую атаку», но и другие атаки. В настоящее время предпринять лобовую атаку не сложно, принимая во внимание доступное сейчас оборудование. Однако, алгоритм достаточно стойкий для предотвращения перехвата в эфире и взлома шифрования в реальном времени. К сожалению, в системе GSM уязвимым участком являются не только радиоволны между MS и BTS.

Как указывалось выше, передачи шифруются только между MS и BTS. За пределами BTS в сети оператора трафик передается открытым текстом. Это открывает новые возможности.

Если злоумышленник может получить доступ к сигнальной сети оператора, он сможет слушать все передачи, включая сами телефонные звонки, а также RAND, SRES и Kc. Сигнальная сеть SS7, используемая операторами GSM сети, абсолютно незащищена, если злоумышленник получает к ней прямой доступ. При другом сценарии злоумышленник может атаковать HLR определенной сети. Если злоумышленник сможет получить доступ к HLR, он сможет извлечь все Ki абонентов данной сети. К счастью, HLR обычно более безопасна, чем вся остальная сеть, таким образом, она является менее очевидным участком для проникновения.

Получить доступ к сети не представляет особой трудности. Хотя все BTS обычно соединены кабелем, у некоторых из них связь микроволновая или спутниковая. Получить доступ к этой связи относительно просто при наличии соответствующего оборудования. Очевидно, именно эта уязвимость используется при прослушивании мобильного телефона с помощью имеющегося в продаже оборудования. К сожалению, я не могу подтвердить это, так как спецификации на это оборудование имеются только у сотрудников правоохранительных учреждений. Однако, микроволновая линия может быть зашифрована, поэтому прослушивать ее немного сложнее. Важно то, намеривается ли злоумышленник взломать шифрование A5, обеспечивающее защищу сеанса связи отдельной MS, или шифрование между BTS и BSC для получения доступа к основной сети. Также не надо исключать и возможность доступа к кабелю, идущему от BTS. Это может быть реальной угрозой, и атаку можно реализовать незаметно долгое время, если делать это аккуратно. Прослушивание информации, передаваемой между BTS и BSC, предоставит возможность злоумышленнику или прослушивать звонок, прослушивая канал, или он сможет извлечь сеансовый ключ, Kc, прослушивая канал, перехватывая звонок в эфире, сразу расшифровывая его. Теперь, когда ему известенKc, шифрование в реальном времени не представляет проблемы.

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

Извлечение ключа из SIM

Вся модель безопасности GSM основана на секретном ключе Ki. Если этот ключ скомпрометирован, будет скомпрометирован и весь счет. Как только злоумышленник извлек Ki, он не только сможет прослушивать звонки абонентов, но и переадресовывать счета за звонки на счет абонентов, потому что теперь он может определить и легального абонента. В сети GSM есть для этого ловушка. Если два телефона с одним и тем же ID включаются одновременно, сеть GSM замечает это, производит запрос о местонахождении этих телефонов, замечает, что один и тот же телефон находится в двух местах одновременно, и закрывает счет, не давая возможность звонить ни злоумышленнику, ни законному абоненту. Но это не происходит, если злоумышленник заинтересован только в прослушивании звонков абонента. В этом случае, злоумышленник может оставаться пассивным и просто прослушивать звонок, оставаясь невидимым для сети GSM.

Ассоциация Разработчиков Смарткарт и исследовательская группа ISAACобнаружили дыру в алгоритме COMP128algorithm, которая позволяла извлекать секретный ключ, Ki, из SIM. Атака предпринималась на SIM, к которой у них был физический доступ, однако, такая же атака применима и в эфире.

Атака основывалась на атаке выбранный вызов, которая выполнима, т.к. алгоритм COMP128 взломан таким образом, что при помощи атаки извлекается информация о Ki, когда соответствующим RAND задаются как аргументы алгоритма A8. Доступ к SIM был получен через Smartcardreader, соединенной с PC. PC делал около 150.000 вызовов SIM, SIM генерировала SRES и сеансовый ключ, Kc, основанный на вызове и секретном ключе. Секретный ключ можно было вычесть из отклика SRES путем дифференциального криптоанализа. Smartcardreader, используемая для реализации атаки, могла произвести 6.25 запросов SIM card в секунду. Для реализации атаки требовалось 8 часов. Ее результаты необходимо было тщательно проверить, но тем не менее, это было относительно быстро по сравнению с настоящей атакой. Таким образом, злоумышленнику требуется доступ к SIM хотя бы в течение 8 часов. Эта уязвимость также имеет социальный сценарий (привлечение инженера). Можно предположить, что коррумпированный GSM дилер клонирует SIM карты таким образом и продаст клонированные карты третьим лицам, которые хотят остаться неизвестными и не желают покупать подлинные SIM карты. Клонированная SIM карта может также быть продана кому-либо с целью прослушивания впоследствии его разговоров. Коррумпированный сотрудник также может предоставить злоумышленнику SIM жертвы, чтобы клонировать SIM и впоследствии прослушивать разговоры владельца карты. Все это очень реалистичные сценарии модели безопасности системы GSM. Уязвимость, обнаруженная в алгоритме COMP128, компрометирует всю модель безопасности системы GSM и оставляет абонентов без защиты.

Извлечение ключа из SIM карты в эфире

Исследователи SDA ISAAC уверены, что такая же атака с клонированием SIM карты может быть реализована и в эфире. К сожалению, они не могут подтвердить свое предположение, потому что оборудование, необходимое для этого, незаконно в США. Атака в эфире основана на следующем. Требуется, чтобы MS откликалась на каждый вызов сети GSM. Если мощность законного сигнала BTS превышена нестандартной BTS злоумышленника, злоумышленник может бомбардировать вызовами целевую MS и реконструировать секретный ключ по откликам. MS должна быть доступна злоумышленнику в эфире все время, необходимое для атаки. Неизвестно, сколько времени продлится атака в эфире. Предположительно от 8 до 13 часов.

Атака может быть предпринята в метро, когда недоступен сигнал законной BTS, но телефон включен. Абонент не заметит атаку, хотя тот факт, что батарейка разрядится быстрее обычного, может озадачить его. Атаку также можно реализовать по частям: вместо того, чтобы атаковать в течение 8 часов, злоумышленник может воздействовать на телефон ежедневно в течение 20 минут, пока жертва идет на работу. Когда SIM карта будет клонирована, SIM-клон можно использовать только до тех пор, пока абонент не воспользуется новой SIM картой, что на практике это случается редко.

При другом сценарии абонент может находиться в рабочей командировке за границей. Злоумышленник каким-то образом заставил местного оператора GSM предпринять атаку на мобильный телефон абонента. Злоумышленник снова сможет реконструировать Ki на основании SRES ответов мобильной станции, и атака, вероятно, не будет замечена, потому что вызовы приходили с законной сети. Помните, локальной сети ничего не известно о Ki, потому что тройки исходят от HLR домашней сети абонента. Таким образом, локальная сеть должна вычесть Ki из откликов A3.

Извлечение ключа из AuC

Такая же атака по извлечению Ki из SIM карты может быть использована для извлечения Ki из AuC. AuC не получает ответ на запросы, сделанные сетью GSM и возвращает действительные тройки для аутентификации MS. Процедура в основном похожа на процедуру получения доступа SIM карты в MS. Различие состоит в том, что AuC гораздо быстрее обрабатывает запросы, чем SIM карта, потому что ему нужно обработать гораздо больше запросов, чем одной SIM карте. Безопасность AuC играет большую роль для предотвращения возможности атаки, но это не является темой данной работы.

3. Вопросы к домашним заданиям.

В чем состоит правило Керкгоффса? Почему это правило является общепринятым в криптографии?
Классификация блочных шифров, - примеры.
Классификация поточных шифров, - примеры.
Перечислите основные методы криптоанализа поточных шифров.
Перечислите основные методы криптоанализа блочных шифров.
На чем основаны методы криптоанализа поточных шифров?
На чем основаны методы криптоанализа блочных шифров?
К какому классу шифров относится алгоритм DES и чем определяется его криптостойкость?
К какому классу шифров относится алгоритм, реализующий стандарт шифрования данных ГОСТ 28147-89, и чем определяется его криптостойкость?
Классификация шифров.
Математические и вероятностные модели шифров.
Схема алгоритма DES.
Стандарт шифрования данных ГОСТ 28147-89.
На чем основанкриптоанализ поточных шифров?
На чем основанкриптоанализ блочных шифров?
На чем основанкриптоанализ шифров гаммирования?
Что такое композиционные шифры?

4. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА ШИФРСИСТЕМ ПОТОЧНОГО ТИПА

Линейные регистры сдвига

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

На базе линейных рекуррентных регистров может быть реализовано множество функциональных зависимостей в той или иной степени используемых при цифровой обработке сигналов.

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

Линейные регистры сдвига

Широкое распространение в криптографических приложениях инейных регистров сдвига над конечными полями и кольцами обусловлено целым рядом факторов. Среди них:

— использование только простейших операций сложения и умножения, аппаратно реализованных практически на всех вычислительных средствах;

— высокое быстродействие создаваемых на их основе криптографических алгоритмов;

— большое количество теоретических исследований свойств линейных рекуррентных последовательностей (ЛРП), свидетельствующих об их удовлетворительных криптографических свойствах.

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

Последовательностью над полем Р будем называть любую функцию u:N0P, заданную на множестве целых неотрицательных чисел и принимающую значения в поле.

Последовательность u называют линейной рекуррентной последовательностью (ЛРП) порядка m>0 над полем Р, если существуют константы f0, …, fm-1Pтакие, что

ЛРП реализуется схемой линейного регистра сдвига, изображенной на рис. 1.

Рис.1 Линейный рекуррентный регистр

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

Равенство, выражающее зависимость между знаками линейной рекуррентной последовательности, называют законом рекурсии, многочлен — характеристическим многочленом ЛРП u, а вектор — начальным вектором ЛРП (или начальным заполнением ЛРР).

Характеристический многочлен ЛРП u, имеющий наименьшую степень, называется ее минимальным многочленом, а степень минимального многочлена — линейной сложностью ЛРП u.

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

Периодом последовательности и называется наименьшее натуральное число t, для которого существует натуральное число > 0 такое, что для всех справедливо равенство u(+i+t)=u(+i).

Из вида закона рекурсии следует, что в случае, когда Р — конечное поле из q элементов, максимальное значение периода ЛРП порядка tравно qm - 1.

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

Значения периодов линейных рекуррентных последовательностей определяются свойствами их минимальных многочленов. В частности, для того чтобы линейная рекуррентная последовательность порядка t над полем из q элементов имела максимальный период, необходимо и достаточно, чтобы ее минимальный многочлен был примитивным многочленом [6]. Так называется неприводимый многочлен, корень которого имеет в мультипликативной группе поля разложения порядок qm- 1.

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

Для конечного поля из q элементов будем использовать стандартное обозначение GF(q).

Утверждение 1. Если F(x) — неприводимый многочлен над полем GF(2) степени t , и 2m-1 — простое число, то F(x) —примитивный многочлен.

Утверждение 2. Неприводимый многочлен F(x) примитивен в том и только в том случае, когда для любого простого числа р, делящего qm -1, многочлен не сравним с 1 по модулю многочлена F(x).

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

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

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

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

Свойства ЛРР

1. Свойство детерминированности.

Символы выходной последовательности ЛРР начиная с n-ого такта полностью определяются своими предыдущими значениями. Это вытекает из рекуррентного соотношения

2. Период рекуррентной последовательности.

Это время, по истечении которого повторится исходное состояние ЛРР. Период ЛРР зависит от полинома, на основе которого он строится. Максимальным периодом обладают ЛРР,построенные на примитивных полиномах. Определим максимальный период ЛРР. Если число разрядов ЛРР n , то максимально возможное число состояний разрядов ЛРР равно

mn=2n

Учитывая, что одно состояние ЛРР является запрещенным, получаем

Т=2n-1

3. Cвойство группового сложения.

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

Например, для ЛРР изображенного на рис.2 имеем

001 1 0 0 1 0 1 1

110 0 1 1 1 0 0 1

111 1 1 1 0 0 1 0

Рис. 2

4.Свойство сдвига.

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

1110010111001 0101110011110

5.Свойство баланса.

Любая последовательность максимального периода содержит

2n-1 единиц и 2n-2 нулей.

6.Свойство окна.

Если по выходной последовательности максимальной длины перемещать "окно" шириной n элементов, то на периоде ЛРР каждая из возможных комбинаций длины n будет зафиксирована только один раз.

7.Свойство серий.

Определим серию, как последовательность одинаковых элементов. Любая выходная последовательность максимальной длины имеет:

-половину всех серий длины в 1 знак

-четверть всех серий длины в 2 знака

-одну восьмую всех серий длины в 3 знака

и так далее, пока доли дают целое число.

1111000100110101111

длина 1----------4

длина 2----------2

длина 3----------1

длина 4----------1

всего серий -----8

Если известна степень примитивного полинома n, но неизвестны его коэффициенты, то они могут быть однозначно определены по любым 2n смежным элементам его выходной последовательности. Поиск коэффициентов hi, i=1, …, n-1 характеристического полинома сводится к решению системы n однородных линейных уравнений с n неизвестными. Это потребует порядка n3 операций типа сложения, умножения. Существуют алгоритмы проверки любой двоичной последовательности на рекуррентность. Эти алгоритмы позволяют найти коэффициенты полинома h(x) при неизвестной длине ЛРР.

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

Рассмотренные выше свойства ЛРР легли в основу широкого применения их для построения цифровых узлов техники связи.

Применение ЛРР

Благодаря уникальным свойствам, ЛРР нашли широкое применение в специальной аппаратуре. На их основе строятся:

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

- датчики временных интервалов (счетчики с произвольным целым коэффициентом деления);

- схемы кодирования и декодирования помехоустойчивых кодов;

- установление синхронизма между взаимодействующими на канале связи аппаратами.

Детерминированность процессов в ЛРР, хорошие статистические свойства последовательности максимальной длины (ПМД) позволили использовать ЛРР в качестве источников квазислучайной импульсной последовательности. Они используются в специальной технике в качестве: датчиков испытательных сигналов (ДИС).

В качестве ДИС в соответствии с МККТТ используется ЛРР с n=9. По своим свойствам выходная последовательность приближается к рабочему сигналу. По испытательному сигналу осуществляется проверка достоверности передаваемой информации перед вхождением в связь, а при необходимости и корректировка канала связи. Схема ДИС реализованого в аппаратуре имеет вид изображенный на рис.2.

ЛРР с n=3 используются для поиска неисправностей в аппаратуре, так как при таком периоде повторения сигнал легко наблюдать на осциллографе. С помощью такого ДИС производится испытание цифровых каналов. В вокодерах для синтеза шумовых звуков в качестве сигнала возбуждения используется шумовой сигнал. В некоторых типах вокодеров этот сигнал формируется с помощью ЛРР.

В соответствии со свойством детерминированности состояния ЛРР изменяются в строго определенном порядке. Если произвести начальную установку разрядов ЛРР, то можно точно определить их состояние на любом такте работы. Данный принцип положен в основу построения счетчиков с произвольным целым коэффициентом деления, датчиков временных интервалов(временных распределителей). Такой счетчик(датчик) состоит из ЛРР, схемы установки исходного состояния и анализаторов. На рисунке 3показан датчик временных интервалов, который формирует команды на 200,1000,1242,1298 и 4000-ом тактах работы.

Рис. 3

С помощью ЛРР производится умножение и деление многочленов. Эти операции выполняются при помехоустойчивом кодировании. Формирование кода 7.4 показано на рисунке 4.

Рис. 4

Деление последовательности кода 7.4 поступающейиз канала связи с помощью ЛРРпредставлено на рисунке 5.

Рис. 5

Синхронизация взаимодействующих в канале связи аппаратов осуществляется путем передачи синхронизирующей посылки (СП), которая представляет собой выходную последовательность ЛРР. Для приема этой последовательности на приемной стороне устанавливается точно такой же ЛРР, однако работает он в режиме приема СП с отключенной обратной связью. Если последовательность приходит из канала связи без искажений, то после поступления 2n элементов, в цепи обратной связи обоих ЛРР будет формироваться одна и та же последовательность. Контроль за идентичностью последовательностей осуществляет сумматор по модулю два. Результат сравнения подсчитывается счетчиком. Как только счетчик заполниться, формируется команда на перевод ЛРР в автономный режим работы (включение обратной связи ЛРР).

Синхронизация по вышеприведенному принципу получила название метода зачетного отрезка (ЗОТ). Схема поясняющая указанный принцип синхронизации показана на рисунке 6.

Рис. 6

Минимальная длина безошибочно принятой последовательности, при которой ЛРР переходит в автономный режим работы, называется зачетным отрезком. Величина его равна

n0=n+m

где:n-длина ЛРР;

m-емкость счетчика.

4. Вопросы к домашним заданиям

1. Структура шифрсистемыгаммирования.

2. Требования к управляющему блоку.

3. Требование к шифрующему блоку.

4. Свойства псевдослучайных последовательностей на основе ЛРР.

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

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

Особенности криптоанализа блочных шифров.

5. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА ШИФРСИСТЕМ С ОТКРЫТЫМ КЛЮЧОМ

Описание алгоритма RSA

В 1978 г. появилась работа, в которой РонРайвест (RonRivest), Ади Шамир (AdiShamir) и Лен Адлеман (LenAdleman) предложили алгоритм с открытым ключом. Схема Райвеста–Шамира–Адлемана (RSA) получила широкое распространение.

Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке [0, N – 1] (о выборе N — см. ниже). Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом x, 0 xN-1.

Каждый абонент вырабатывает свою пару ключей. Для этого он генерирует два больших простых числа p и q, вычисляет произведение N=p·q. Затем он вырабатывает случайное число e, взаимно простое со значением функции Эйлера от числа N, (N)=(p-1)·(q-1) и находит число d из условияe∙d 1(modφ(N)). Так как (e, φ(N))=1, то такое число d существует и оно единственно.

Пару (N, e) он объявляет открытым ключом и помещает в открытый доступ. Пара (N, d) является секретным ключом. Для расшифрования достаточно знать секретный ключ.

Числа p, q, φ(N) в дальнейшем не нужны, поэтому их можно уничтожить.

Пользователь A, отправляющий сообщение x абоненту B, выбирает из открытого каталога пару (N, e) абонента B и вычисляет шифрованное сообщение y=xe(modN).

Чтобы получить исходный текст, абонент B вычисляет yd(modN). Так как e∙d 1(modφ(N)), т. е. e∙d= φ(N)·k+1, где k – целоечисло, то применяя теорему Эйлера, получим: следующее соотношение: .

Пример 1. Пусть p = 7, q = 17. Тогда N = 7∙17 = 119, φ(N)=96.

Выбираем значение е: e< 96, НОД (e, 96) =1.

Пусть в нашем случае e = 5.

Находим d: d=1/e (mod 96).

Получаем d = 77, так как 77∙5 = 4∙96 + 1. Открытый ключ (119,5), личный ключ (119,77).

Пусть х = 19. Для зашифрования число 19 возводим в 5-ю степень по модулю 119, тогда имеем 195 = 2 476 099 и остаток от деления 2 476 099 на 119 равен 66. Итак, y = 195 mod 119 = 66.

Прирасшифрованииполучим x=667mod119=19.

Как шифрование, так и расшифрование в RSA предполагают использование операции возведения целого числа в целую степень по модулю N. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю N, то промежуточные значения окажутся огромными. Здесь можно воспользоваться свойствами арифметики в классах вычетов (amodN)·(bmodN) modN=(a·b) modN.

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

О стойкости криптосистемы RSA

Безопасность алгоритма RSA основана на трудоемкости разложения на большие простые множители больших целых чисел. Современное состояние технических средств разложения на множители таково, что число, содержащее в записи 193 десятичных знака, факторизовано в 2005 г. Следовательно, выбираемое значение N должно быть больше. Большинство общепринятых алгоритмов вычисления простых чисел p и q носят вероятностный характер.

О выборе чисел p и q

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

Кроме разрядности p и q, к ним предъявляются следующие дополнительные требования:

– числа не должны содержаться в списках известных больших простых чисел;

– они не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма и решить уравнение .

– в алгоритме RSA всегда есть эквивалентные по расшифрованию показатели степеней, например d и . При этом эквивалентных решений тем больше, чем больше (p – 1, q – 1).

В лучшем случае (p – 1, q – 1) = 2,p = 2t + 1, q = 2s + 1, где s, t – нечетные числа с условием, - НОД (s, t) = 1.

Чтобы исключить возможность применения методов факторизации накладывают следующее ограничение: числа p – 1, p + 1, q – 1, q + 1 не должны разлагаться на сомножители в виде произведения малых простых множителей, должны содержать в качестве сомножителя хотя бы одно большое простое число.

В 1978 г. Райвест сформулировал наиболее сильные требования.

Числа должны быть простыми, причем числа p1 – 1 и q1 – 1 не должны разлагаться в произведение малых простых чисел.

О выборе параметров e и d

Рассмотрим вопрос о выборе экспонент шифрования и расшифрования.

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

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

Если малым является секретный параметр d, то можно применить метод перебора малых значений до получения искомого числа d. А если малым является параметр е, то достаточно большое число открытых сообщений, удовлетворяющих неравенству будут зашифровываться простым возведением в степень y=xe(modN) и поэтому их можно найти путем извлечения корня степени е.

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

Подготовка текста к шифрованию

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

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

Пусть наша таблица замен имеет вид:

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С
10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
28	29	30	31	32	33	34	35	36	37	38	39	40	41

Пробел между словами будем заменять числом 99.

Например, пусть открытый текст – это девиз «ПОЗНАЙ СЕБЯ». Тогда его цифровое представление имеет вид: 2524172310199927151141.

Пусть в нашем примере p = 149, q = 157, тогда N = 23393. Поэтому цифровое представление открытого текста нужно разбить на блоки, меньшие, чем 23393. Одно из таких разбиений выглядит следующим образом:

2524 – 1723 – 10199 – 9271 – 511 – 41.

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

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

Обратим внимание на то, что в этом примере каждую букву кодируем двузначным числом. Это сделано для предотвращения неоднозначности. Если бы мы пронумеровали буквы не по порядку, начиная с 1, т. е. А соответствует 1, Б соответствует 2 и т. д., то было бы непонятно, что обозначает блок 12: пару букв АБ или букву Л, двенадцатую букву алфавита. Конечно, для кодирования можно использовать любые однозначные соответствия между буквами и числами, например ASCII-кодировку, что чаще всего так и делается.

Продолжим пример:

- выбирается p = 149, q = 157,

- вычисляетсяφ(N) = 23088.

- выбрается число e, взаимно простое с φ(N). Наименьшее простое число, не делящее φ(N), равно5. Примемe = 5.

Зашифруем первый блок сообщения:

вычисляем 25245 mod 23393 = 22752;

17235 mod 23393 = 6198.

101995 mod 23393 = 14204,

92715 mod 23393 = 23191,

5115 mod 23393 = 10723,

415 mod 23393 = 14065.

Теперь шифрованный текст имеет вид

22752619814204231911072314065

В нашем примере N = 23393, e = 5. Применив алгоритм Эвклида к числам φ(N) =23088 и e=5, найдем d=e-1mod 23088 = 13853.

Значит для расшифровки блоков шифртекста мы должны возвести этот блок в степень 13583 по модулю 23393.

В примере первый блок шифртекста – число 22752, тогда получим 2275213853 mod 23393 = 2524.

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

Основные атака и на алгоритм RSA

Для расшифрования необходимо по известным N, e и шифртекстуy найти такое x((Z/N))*, чтоy=xemodN.

Попытаемся решить сравнение при конкретных y, затем использовать гомоморфность отображения D(x).

Один из возможных способов следующий: пусть имеется набор пар {(x1, y1)…(xk, yk)} с условием, что xie= yimodN, 1 <y<N, НОД (y, N) = 1. Если каким-либо образом удалось представить y в виде с целыми sk, то будет решением сравнения y=xemodN.

Пример 3.

В наличии имеется открытый ключ N = 31459, e = 5 и набор пар соответствующих друг другу исходных и зашифрованных сообщений:

(23, 18707), (755, 26871), (631, 6384).

Требуется расшифровать шифртекстy = 11 638. Для этого представим y в виде y=18707-1·268713·6384-2=11638

Отсюда легко вычислить исходное сообщение: x=23-1·7553·631-2=28260.

Заметим, что этот подход не менее труден, чем поиск алгоритма решения сравнения y=xemodN.

Взлом криптосистемы RSA при неудачном выборе параметров криптосистемы

Само по себе использование RSA не обеспечивает безопасности. Дело еще в деталях реализации. Приведем ряд примеров. Для простоты вычислений будем работать с небольшими числами. Цель – показать особенности, не зависящие от размера.

Пример 4.

Пусть пользователь выбрал N = 2047, e = 179, d = 411.

Так как 2047 = 23×89, а φ(23) =22, φ(89) =88 имеют наименьшее общее кратное 88, то любое число, обратное к 179 по модулю 88, например 59, будет действовать как d.

Пример 5.

Число N = 536813567 является произведением простого числа Мерсенна 8191 и простого числа Ферма 65537. Это очень плохой выбор.

Пример 6.

Число 23360947609 является очень плохим выбором для N из-за того, что два его простых делителя слишком близки друг к другу.

Пусть p>q, тогда имеем .

Обозначим: .

Так как S мало, то t – целое число, лишь немного большее причем t2 – N является полным квадратом.

Проверяем подряд целые числа В нашем примере t1 = 152843, t2 = 152844, t3 = 152845 и t3 - N=8042, тогда р = 152845 + 804, р = 152845 – 804. Таким образом, мы с третьей попытки нашли p и q.

Количество попыток, необходимых для факторизации N, можно при известных p и q вычислить по следующей формуле: , где [x] – операция округления x до ближайшего целого числа.

Атака повторным шифрованием

Строим последовательность: .

, а так как НОД (e, φ(N)), то существует такое натуральное число m, что em1(modφ(N)). Но тогда , отсюда следует, что , значит, ym-1 – решение сравнения y=xe(modN).

Пример 7.

Пусть имеется открытый ключ N =84517 , e = 397 и зашифрованное им сообщение y = 8646. Необходимо найти исходный текст x.

Возведем y в степень e и получим y2 = 37043. Будем повторять операцию до тех пор, пока не получим yn = y. yn-1 – искомое сообщение: y3 = 5569, y4 = 61833,y5 = 83891, y6 = 16137, y7 = 8646. y6 является решением сравнения y=xe(modN), а, следовательно, искомым сообщением x.

Замечание. Анализ метода повторного шифрования хорошо показывает необходимость соблюдения требований на выбор p и q для обеспечения стойкости. В данном примере d = 82 225. Неудачный выбор криптосистемы привел к тому, что атака методом повторного шифрования дала результат почти сразу, тогда как нахождение d потребовало бы на порядок больших вычислений.

Бесключевое чтение

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

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

Выбираютсяr, s такие, что re1+se2=1. Отсюда получается:

Пример 9.

Два пользователя применяют общий модуль N = 137759, но разные взаимно простые экспоненты e1 = 191 и e2 = 233. Пользователи получили шифртекстыy1 = 60197 и y2 = 63656, которые содержат одно и то же сообщение.

Исходное сообщение находится методом бесключевого чтения.

Так как e1 и e2 взаимно просты, то выбираются такие r и s, что re1+se2=1 С помощью расширенного алгоритма Евклида выбираетсяr = 61, s = –50. Искомое сообщение

Выводы

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

В частности, необходимо обеспечить каждому пользователю уникальные значения p, q и уникальное значение e, удовлетворяющие требованиям, приведенным выше.

Описание программы «BCalc», используемой для криптоанализаRSA

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

– преобразование числа в данные и обратно;

– возведение в степень по модулю;

– вычисление обратных значений по модулю;

– нахождение целых корней любых натуральных степеней;

– нахождение подходящих дробей для цепной дроби.

Описание интерфейса программы

В окне программы находятся следующие элементы интерфейса:

– поля ввода, помеченные латинскими буквами A, B, C, D;

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

– нижняя группа кнопок, предназначенных для очистки полей и таблицы;

– таблица для хранения промежуточных результатов.

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

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

– «To [поле ввода]» – копирует значение ячейки таблицы в соответствующее поле ввода;

– «From [поле ввода]» – копирует значение соответствующего поля ввода в выбранную ячейку таблицы.

Кнопки «Clear D», «Clear A, B, C», «Cleargrid» очищают соответственно поле D, поля A, B, C – таблицу.

Кнопка «Increasenumberofrows» увеличивает количество строк в таблице на пять.

Кнопка «D – > A» копирует значение, находящееся в данный момент в поле D, в поле A. Кнопка «D – >» копирует значение поля D в первую сверху пустую ячейку второй колонки таблицы.

Остальные кнопки запускают математические функции, описанные ниже.

Математические функции программы

«D = A + B» – значения A и B складываются, результат помещается
в поле D.

«D = A ∙ B» – значения A и B перемножаются, результат помещается
в поле D.

«D = A div B» – в D помещается результат целочисленного деления A на B.

«D = A mod B» – в D помещается остаток от целочисленного деления
A на B.

«D = A^B mod C» – в D помещается результат возведения A в степень B по модулю C. Экспонента может быть отрицательным числом. Если поле C = 0, то возведение в степень будет происходить не по правилам модульной арифметики. В таком случае не стоит задавать в качестве экспоненты большие числа, так как вычисления могут занять слишком много времени. Невозможно также вычислять обратные значения, если в качестве модуля задан ноль.

«D = A^(1/B)» – в поле D помещается корень B степени от A. Если в результате извлечения корня получилось нецелое число, то в D помещается ближайшее бόльшее целое число, а в первой строке таблицы появится надпись «[error]».

«A ∙ D – B ∙ C = N», где – A – числитель дроби; B – знаменатель подходящей дроби n порядка. В поле C будет помещен числитель, а в D – знаменатель подходящей дроби n-1 порядка. В первую строку таблицы будет помещено значение выражения A ∙ D – B ∙ C. Если после начала вычисления дроби поля C и D равны нулю, то это значит, что числа A и B не взаимно просты.

«D = text(A)» – число A интерпретируется как строка из символов в ANSI- кодировке. Строка помещается в поле D.

«D = number(A)» – строка A, состоящая из символов, интерпретируется как число и помещается в поле редактирования D.

В программе используется модернизированный модуль «BigNum v2.0»
(Jes R. Klinke).

Описание программы «PS», используемой для криптоанализаRSA

Программа PS предназначена для нахождения порядка чисел в конечном поле и дешифрации сообщений методом перешифрования.

Нахождение порядка чисел

Для нахождения порядка числа методом перешифрования следует указать в поле редактирования N значение модуля, в поле e – экспоненты, а в поле Y – произвольное число, меньшее чем модуль. При нажатии кнопки Запуск повторного шифрования программа начнет возводить число Y в степень e (т. е. ) до тех пор, пока Yi не будет равен Y. Значение , а число шагов повторного шифрования является порядком числа e в конечном поле ZPhi(N). При завершении работы алгоритма в поле i будет записано количество шагов повторного шифрования, а в поле X – значение Yi-1 . Во время работы программы кнопка Pause приостанавливает работу алгоритма. Для продолжения работы следует нажать кнопку Pause еще раз. Флаг «Showresults» указывает, будут ли отображаться результаты промежуточных вычислений. Его отключение увеличивает скорость работы приблизительно на 20 %.

Дешифрации сообщений методом перешифрования

Для дешифрации сообщения необходимо указать в поле редактирования N значение модуля, в поле e – экспоненты, в поле i – порядок экспоненты, а в область редактирования C поместить блоки зашифрованного текста (разделитель – символ конца строки). При нажатии кнопки Дешифрация начнется процесс вычисления исходного сообщения. Результат будет помещен в область редактирования M.

В программе используется модернизированный модуль «BigNum v2.0» автор (Jes R. Klinke).

3. Вопросы к домашним заданиям

Определение криптосистемы с открытым ключем (асимметричной криптосистемы).
Обобщенная схема асимметричной криптосистемы с открытым ключом.
Характерные особенности асимметричных криптосистем.
Требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы.
Определение однонаправленной функции.
Перечислите шифрсистемы с открытым ключом.
На чем основана стойкость шифрсистемы RSA?
На чем основана стойкость шифрсистемы Эль-Гамаля?
На чем основана стойкость шифрсистемы Мак Элиса?
Моделирование и синтез шифров RSA, их достоинства и недостатки.
Моделирование и синтез шифров Эль - Гамаля, их достоинства и недостатки.
Чем определяется стойкость шифра RSA?
Чем определяется стойкость шифра Эль – Гамаля?

6. КРИПТОГРАФИЧЕСКИЕ СВОЙСТВА

ШИФРА ЭЛЬ-ГАМАЛЯ

Общий принцип работы криптографической системы Эль-Гамаля.

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом,основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России (ГОСТ Р 34.11-94).

Схема была предложена Тахером Эль-Гамалем в 1984 году.Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Генерация ключей

Генерируется случайное простое число длины битов.
Выбирается произвольное целое число , являющееся первообразным корнем по модулю .
Выбирается случайное целое число такое, что .
Вычисляется .
Открытым ключом является тройка , закрытым ключом — число .

1.1. Работа алгоритма Эль-Гамаля в режиме шифрования

Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Шифрование

Сообщение шифруется следующим образом:

Выбирается сессионный ключ — случайное целое число такое, что
Вычисляются числа и .
Пара чисел является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое.

Расшифрование

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

При этом нетрудно проверить, что

и поэтому

Схема шифрования.

Пример.

Шифрование
1. Допустим что нужно зашифровать сообщение .
2. Произведем генерацию ключей :
  1. пусть . Выберем - случайное целое число такое,что.
  2. Вычислим .
  3. Итак , открытым является тройка ,а закрытым ключом является число .
3. Выбираем случайное целое число такое, что 1 < k < (p − 1). Пусть .
4. Вычисляем число .
5. Вычисляем число .
6. Полученная пара является шифротекстом.
Расшифрование
1. Необходимо получить сообщение по известному шифротекстуи закрытому ключу .
2. Вычисляем M по формуле :
3. Получили исходное сообщение .

Так как в схему Эль-Гамаля вводится случайная величина ,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины для шифровки различных сообщений и . Если использовать одинаковые , то для соответствующих шифротектови выполняется соотношение . Из этого выражения можно легко вычислить , если известно .

1.2. Работа алгоритма Эль-Гамаля в режиме подписи

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

Подпись сообщений

Для подписи сообщения выполняются следующие операции:

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

Подписью сообщения является пара .

Проверка подписи

Зная открытый ключ , подпись сообщения проверяется следующим образом:

Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.
Вычисляется дайджест
Подпись считается верной, если выполняется сравнение:

Пример

Подпись сообщения.
1. Допустим,что нужно подписать сообщение .
2. Произведем генерацию ключей:
  1. Пусть переменные, которые известны некоторому сообществу. Секретный ключ — случайное целое число такое, что .
  2. Вычисляем открытый ключ : .
  3. Итак,открытым ключом является тройка .
3. Теперь вычисляем хэш-функцию: .
4. Выберем случайное число такое, что выполняется условие 1 <k<p − 1. Пусть .
5. Вычисляем .
6. С помощью расширенного алгоритма Евклида находим число из уравнения . Такое существует, так как НОД(k,p-1)=1. Получим что .
7. Итак, мы подписали сообщение: .
Проверка подлинности полученного сообщения.
1. Вычисляем хэш-функцию: .
2. Проверяем сравнение .
3. Вычислим левую часть по модулю 23: .
4. Вычислим правую часть по модулю 23: .
5. Так как правая и левая части равны, то это означает что подпись верна.

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

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

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

Использование свертки объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значению подписи. Пример: если выбрать случайные числа ,удовлетворяющие условиям , НОД(j,p-1)=1 и предположить что

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

Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: , в котором тройка принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при ,, .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (DigitalSignatureStandard), используется значения , ,, а в Российском стандарте: , , .
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел на пару чисел ),где является каким-то простым делителем числа . При этом сравнение для проверки подписи по модулю нужно заменить на новое сравнение по модулю : . Так сделано в американском стандарте DSS (DigitalSignatureStandard).

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

Алгоритм	Ключ	Назначение	Криптостойкость, MIPS	Примечания
RSA	До 4096 бит	Шифрование и подпись	2,7•1028 для ключа 1300 бит	Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
ElGamal	До 4096 бит	Шифрование и подпись	При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•1028 для ключа 1300 бит	Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
DSA	До 1024 бит	Только подписание		Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
ECDSA	До 4096 бит	Шифрование и подпись	Криптостойкость и скорость работы выше, чем у RSA	Современное направление. Разрабатывается многими ведущими математиками

3. Вопросы к домашним заданиям.

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

7. ПРОТОКОЛЫ РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ

Протоколы сертификации и распределения ключей.

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

Система установки ключей определяет алгоритмы и процедуры генерации, распределения, передачи и проверки ключей.

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

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

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

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

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

Пересылка ключей

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

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

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

Открытое распределение ключей

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

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

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

Схема разделения секрета

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

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

Задачу построения схемы разделения секрета можно обобщить:

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

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

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

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

Описание алгоритма

Предположим, что обоим абонентам известны некоторые два числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение A = gamodp и пересылает его второму, а второй вычисляет B = gbmodp и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение Bamodp = gabmodp, а второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение Abmodp = gabmodp. Как нетрудно видеть, у обоих абонентов получилось одно и то же число: K = gabmodp. Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления gabmodp по перехваченным gamodp и gbmodp, если числа p,a,b выбраны достаточно большими.

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

генерирует случайное натуральное число a — закрытый ключ
совместно с удалённой стороной устанавливает открытые параметрыp и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

p является случайным простым числом

g является первообразным корнемпо модулюp

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

A = gamod p

обменивается открытыми ключами с удалённой стороной
вычисляет общий секретный ключK, используя открытый ключ удаленной стороны B и свой закрытый ключ a

K = Bamod p

К получается равным с обеих сторон, потому что:

Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p

В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Протоколы выработки сеансовых ключей.

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

Предположим, что противнику известны, кроме транскрипции диалога законных участников в текущем сеансе выполнения протокола выработки сеансовых ключей, транскрипция диалога этих участников и соответствующий общий секретный ключ в некотором прошлом сеансе. В этом случае он может провести атаку, названную в работе Якоби атакой с известным ключом (knownkeyattack). Атаку с использованием только транскрипции диалога законных участников в текущем сеансе мы назовем атакой с известным шифртекстом. В приведен пример протокола типа Диффи -- Хеллмана, (гипотетически) стойкого против атаки с известным шифртекстом, но нестойкого против атаки с известным ключом (в случае пассивного противника). Существование таких протоколов названо в этой статье "парадоксом распределения ключей".

В той же работе предлагается модификация протокола типа Диффи -- Хеллмана по составному модулю, стойкость которой против атаки с известным ключом даже в случае активного противника такая же, как и стойкость исходного протокола против атаки с известным шифртекстом в случае пассивного противника. Пусть и -- различные простые числа, -- модуль исходного протокола, а -- его база. Считается, что и секретны (они могут быть выбраны центром доверия и храниться им в секрете), а и общедоступны. Предполагается также, что участники A и B имеют секретные ключи и соответственно и открытые ключи и соответственно. Модифицированный протокол заключается в следующем:

1. A выбирает , вычисляет и посылает его B, сохраняя в секрете.

2. B выбирает , вычисляет и посылает его A, сохраняя в секрете.

3. A вычисляет .

4. B вычисляет .

Очевидно, что

Поэтому является искомым общим секретным ключом.

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

Протоколы, основанные на идентификационной информации

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

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

Протокол Гюнтера

Этот протокол появился в работе [G] (см. также [Bur]). Пусть -- большое простое число, а -- некоторый порождающий группы , известные как центру доверия, так и всем абонентам сети связи. Центр доверия выбирает свой секретный ключ и сообщает абонентам открытый ключ . При регистрации абонента (скажем, A) центр доверия вычисляет подпись его идентификатора по схеме Эль Гамаля [EG85], т. е. и , где секретно, а -- некоторая хэш-функция. После этого центр доверия передает (секретный ключ A) только абоненту A, а (открытый ключ A) помещает в общедоступный сертифицированный справочник. Теперь если абоненты A и B хотят выработать общий секретный ключ, они выполняют следующие действия:

1. A выбирает , вычисляет и посылает его вместе с участнику B, сохраняя в секрете.

2. B выбирает , вычисляет и посылает его вместе с участнику A, сохраняя в секрете.

3. A вычисляет .

4. B вычисляет . Из сравнений

следует, что является искомым общим секретным ключом.

Протокол типа Диффи -- Хеллмана, основанный на идентификационной информации

Описание этого протокола, предложенного в работе Окамото и Танаки [OT], взято из работы Л. М. Ухлинова [У2]. Этот протокол разработан (и реализован) для интеллектуальных карточек. Пусть центром доверия выбраны различные большие простые числа и , числа и такие, что , и элемент достаточно большого порядка. Для каждого абонента A центр доверия вычисляет , где -- идентификатор A, и сообщает , , и этому абоненту, сохраняя , и в секрете. Отметим, что является подписью по схеме RSA (см. [RSA]). Считается также, что всем абонентам известна некоторая трехместная хэш-функция . Протокол заключается в следующем:

1. A выбирает , вычисляет , , , где -- текущее время, и посылает , , , абоненту B, сохраняя в секрете.

2. B вычисляет и проверяет истинность сравнения . Если оно истинно, то сообщение, пришедшее от A, признается подлинным. В этом случае B выбирает , вычисляет , , , где -- текущее время, и посылает , , , абоненту A, сохраняя в секрете.

3. A вычисляет и проверяет истинность сравнения . Если оно истинно, то сообщение, пришедшее от B, признается подлинным. В этом случае A вычисляет .

4. B вычисляет . Ясно, что . Поэтому является искомым общим секретным ключом.

Протокол Ингемарссона -- Танга – Вонга.

Мы приведем протокол для конференц-связи, являющийся обобщением протокола Диффи -- Хеллмана и предложенный в работе Ингемарссона, Танга и Вонга [ITW]. Введем обозначения. Пусть -- число абонентов, желающих выработать общий секретный ключ. Обозначим этих абонентов элементами кольца , сложение и вычитание в котором будет обозначаться через и . Предполагается, что всем абонентам известны большое простое число и порождающий группы .

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

I. Если , то выбрать , вычислить и переслать его абоненту .

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

Схема Диффи -- Хеллмана по составному модулю.

В работе Шмуели [S] предлагается использовать в качестве модуля в схеме Диффи -- Хеллмана не простое, а составное число. и -- различные простые числа. Шмуели также доказал, что произвольный алгоритм , находящий с вероятностью, которая не является пренебрежимо малой, общий секретный ключ по данным модулю вышеуказанного вида, базе , являющейся случайным элементом нечетного порядка группы , и открытым ключам и , может быть преобразован в алгоритм факторизации (т. е. нахождения и ) с не пренебрежимо малой вероятностью. Однако этот результат (в виде, приведенном в [McC88]) не позволяет утверждать, что если полиномиален, то и полиномиален. Это можно утверждать, если и выбраны некоторым специальным образом. Но сложность задачи факторизации произведений простых чисел специального вида, вообще говоря, может быть ниже сложности общей задачи факторизации.

В той же работе [McC88] МакКарли, развивая подход Шмуели, построил протокол типа Диффи -- Хеллмана, в котором модуль есть произведение двух различных простых чисел специального (отличного от упомянутого при обсуждении результата Шмуели) вида, а база фиксирована (а именно, ), и доказал его стойкость против пассивного противника в предположении сложности факторизации . Однако это предположение, вообще говоря, может быть сильнее стандартного криптографического предположения о сложности общей задачи факторизации.

Дальнейшее развитие методов работы [McC88] привело к построению М. И. Анохиным (см. также [Ан]) следующего протокола типа Диффи -- Хеллмана, который мы приведем более подробно. В этом протоколе предполагается наличие центра доверия, который для обеспечения возможности выработки участниками A и B общего секретного ключа выполняет следующие действия:

1) выбирает различные большие простые числа и (например, так, что -- случайный элемент множества всех двухэлементных множеств простых чисел длины, равной параметру безопасности);

2) выбирает случайный элемент нечетного порядка в группе (например, выбрав и и вычислив (единственный) такой, что и ; здесь и таковы, что и , где и нечетны);

3) передает и участникам A и B (по каналу, открытому для прослушивания, но недоступному для изменения данных) или помещает их в сертифицированный справочник, сохраняя и в секрете.

После этого для выработки общего секретного ключа A и B выполняют следующий протокол:

1. A выбирает , вычисляет и посылает его B, сохраняя в секрете.

2. B выбирает , вычисляет и посылает его A, сохраняя в секрете.

3. A вычисляет .

4. B вычисляет . Очевидно, что .

К данному протоколу применим метод аутентификации участников, описанный в п. 1.1.

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

Вопросы:

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

Часть 2. ЛАБОРАТОРНЫЙ ПРАКТИКУМ.

ЛАБОРАТОРНАЯ РАБОТА №1
ИССЛЕДОВАНИЕ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ ШИФРОВ ЗАМЕНЫ И ГАММИРОВАНИЯ.

Время 4 ч.

1. Общие указания по выполнению работы.

1.1. Цели работы: Закрепить теоретические сведения по теме “Шифры перестановки, замены, гаммирования”, ознакомить студентов с элементами криптоанализа шифров замены, принципами исследования и оценки криптографических свойств шифров.

Образовательные:

закрепление теоретических сведений по теме “Шифры перестановки, замены, гаммирования”;
1. ознакомление студентов с элементами криптоанализа шифров замены, принципами исследования и оценки криптографических свойств шифров.

Развивающие:

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

Воспитательные:

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

1.2. В процессе выполнения работы студенты должны изучить следующие вопросы:

- статистические характеристики открытых текстов;

- синтез шифров замены, гаммирования;

- бесключевое чтение шифровзамены.

1.3. Техническое обеспечение:

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

2. Лабораторные задания и методические указания по их выполнению

2.1. Лабораторное задание № 1.

Синтез шифров замены.

2.1.1. Запустить программу «статистика.exe».

2.1.2. В данной программе открыть один из контрольных текстов, находящихся в одной папке с программой.

2.1.3. Выбрать пункты меню Действие – Зашифровать – Простая замена и нажать кнопку Далее.

2.1.4. Сгенерировать ключ простой замены и зашифровать на этом ключе открытый контрольный текст.

2.1.5. Полученную криптограмму сохранить в отдельном текстовом документе.

2.1.6. Обменяться файлами криптограммами с одним из одногруппников.

2.2. Лаборатоное задание № 2.

Произвести криптоанализ шифра простой замены.

2.2.1. По шифртексту, полученному от одногруппника, определить частоты букв и биграмм. Результаты сравнить со статистическими данными таблиц 1 и 3 данных методических указаний.

2.2.2. Попытаться дешифровать шифртекс.

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

2.2.4. Проверить полученный текст на «читаемость» на русском языке и сравнить с контрольным текстом.

2.2.5. Сделать выводы о криптографической стойкости шифра простой замены.

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

Принципы классификации шифров.
Классификация шифров замены.
Классификация шифров перестановки.
Классификация шифров гаммирования.
Математические модели и правила зашифрования – расшифрования шифров замены (одноалфавитных и многоалфавитных).
Математические модели и правила зашифрования – расшифрования шифров гаммирования (табличного и модульного).
Модели открытых текстов и их использование в криптоанализе.
Критерии распознавания открытых текстов и их использование в криптоанализе.
Бесключевое чтение шифров

ЛАБОРАТОРНАЯ РАБОТА №2.

ХАРАКТЕРИСТИКИ СТОЙКОСТИ ШИФРОВ.

Время 4 ч.

1. Общие указания по выполнению работы

1.1. Цели лабораторной работы

Образовательные:

Решение задач по стойкости шифров.
1. Приобретение навыков алгоритмизации и программирования типовых криптосхем.

Развивающие:

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

Воспитательные:

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

1.2. В процессе выполнения работы студенты должны изучить следующие вопросы:

повторение ранее изученного материала;

изучение свойств, определяющих имитостойкостьшифрсистем;

формирование навыков оценки имитостойкости шифров;

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

1.3 Материально-техническое обеспечение занятия.

Компьютеры под управлением операционной системы Windows XP с установленным программным обеспечением MathCad и MicrosoftExcel.

2. Лабораторные задания и методические указания по их выполнению

Решение задач по определению стойкости шифров

Задача 1.

На основе моделей открытых текстов на русском языке вычислить их энтропии Н0, Н1.

Определение.

Энтропия языка – мера средней информации, приходящейся на одну букву открытого текста языка. Находится в соответствии с выражением:

Решение.

а) Для нахождения H0 выбираемn=32 (с пробелом, но без ъ и ё); pi=1/32.

б) Для нахождения H1 принимаемn=32 (с пробелом, но без ъ и ё); pi берем из [1] (страница 438).

Задача 2.

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

Определение.

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

где: - расстояние единственности для шифра;

- количество возможных ключей;

n - количество букв в алфавите;

- избыточность языка, определяется в соответствии с выражением:

H- энтропия языка. В конкретной данной задаче выбираем полученное значение для H1 из задачи 1.

Решение.

Количество возможных ключей находим из комбинаторики. Здесь мы имеем размещения без повторений 32 из 32

В нашем случае (К=32!). H в примере берем 4,339 (при решении задачи необходимовыбирать значение, полученное в задаче 1, а именно 4.357).

Выводы:

Избыточность языка означает, что при оптимальном кодировании текста его можно сжать на (R*100)%.
Расстояние единственности – средняя длина шифртекста, необходимая для однозначного восстановления истинного ключа (без каких-либо ограничений на время его нахождения). С ростом длины шифротекста число ложных ключей уменьшается.
Расстоянием единственности шифра называют такую длину шифртекста, начиная с которой число ложных ключей становится равным нулю. Другими словами, это средний объем шифротекста, необходимый для однозначного вскрытия ключа атакующим, имеющим неограниченные вычислительные ресурсы. Для абсолютно стойких криптосистем L= ∞.

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

Задача 3.

Рассчитать оценку расстояния единственности для шифра, если известно, что деловое сообщение на русском языке, закодированное байтовым кодом, зашифровано криптоалгоритмом ГОСТ 28147-89 в режиме простой замены (длина блока, используемого для кодирования открытого сообщения составляет 64 бит, длина ключа – 256 бит). Чем объясняется малое расстояние единственности для данного случая? Какими методами можно его увеличить?

Решение.

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

где:

=2256 (256 бит ключа – из комбинаторики);

=264 – шифрование в режиме простой замены;

H=83,4 (деловой текст на русском языке –таблица 1 для данной лабораторной работы). В нашем случае 64 бита открытого текста воспринимаются как один символ. Для его обозначения введем понятие макросимвол. Энтропия, приходящаяся на этот макросимвол равна H*8 бит. n=264 – количество возможных макросимволов.

Расстояние единственности определяется для макросимвола.

От макросимволовнеобходимо перейти к битам.

Т.е. расстояние единственности дляГОСТ 28147-89 в режиме простой замены составляет 285,635 бита.

Повысить L можно уменьшив избыточность сообщения: архивированием, использованием оптимального кодирования (кода Хаффмена, кода Фано). Например, при получении избыточности 0,1% имеем расстояние единственности:

=2,56

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

Задача 4.

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

Подсказка.

Данная задача из области комбинаторики. Основные выражения, необходимые для решения задачи:

а) Число перестановок порядка n равно n!

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

б) Количество размещений с повторениями из n по k равно nk.

Это число указывает на количество различных гамм длины n, которые могут быть составлены из алфавита, состоящего из k символов.

Решение.

В качестве избыточности языка примем избыточность языка в целом 72,6 [1].

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

а) Для текста длиной n=33 символа получим:

Количество ключей вычисляется как количество способов заполнения латинского квадрата плюс количество различных гамм, использующих этот квадрат. При вычислении избыточности принимаем энтропию языка, умноженную на количество символов в макросимволе. Таким образом, получаем энтропию макросимвола. nn - это количество возможныхмакросимволов. Далее вычисляем L. Получаем расстояние единственности.

L=1.373 означает, что расстояние единственности для шифра табличного (модульного) гаммирования, заданного латинским (русским) квадратом равно 1.373 макросимвола, или 45.304 буквы.

б) Для текста длиной 2n=66 символов аналогично имеем:

Макросимвол будет включать в себя 66 букв.

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

Задача 5.

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

Подсказка.

Режим электронной кодовой книги (ECB – ElectronicCodeBook) отвечает обычному использованию DES как блочного шифра, осуществляющего некоторую простую замену блоков открытого текста.

Решение.

См. задачу 3, данная задача решается аналогично.

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

Понятие криптографической стойкости
Понятиеатаки на криптосистему
Что такое Практическая и Теоретическая стойкость шифра?
Что такое Хеш-функции? Ключевые и бесключевые хэш-функции.
Понятие энтропии. Формула нахождения. Физический смысл. Понятие энтропии языка.
Понятие избыточность языка. Формула нахождения. Физический смысл.
Понятие расстояния единственности для шифра. Формула нахождения. Физический смысл.
Понятие имитостойкостишифра.

ЛАБОРАТОРНАЯ РАБОТА №3.

МЕТОДЫ КРИПТОАНАЛИЗА ПОТОЧНЫХ ШИФРОВ

1. Общие указания по выполнению работы

1.1. Цели занятия:

Образовательные:

изучение методов анализа поточных и блочных шифров;
приобретение практических навыков по исследованию криптостойкости алгоритмов DES и Гост 28147-89.

Развивающие:

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

Воспитательные:

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

1.2. В процессе выполнения работы студенты должны изучить следующие вопросы:

определение криптостойкостишифрсистемреализующих алгоритмы DES и Гост 28147-89;
ознакомление с элементами криптоанализатакихшифрсистем;
выработка комплексного представления об обеспечении безопасности информации при помощи криптографических средств;
формирование навыков построения речи с использованием технической терминологии и самостоятельной работы с научно-технической литературой;

2. Лабораторные задания и методические указания по их выполнению

2.1. Лабораторное задание №1

Изучение криптографических свойств алгоритма А5

2.1.1 С помощью пакета MathCad написать программу, моделирующую работу алгоритма A5.

2.1.2. С помошью полученной программы исследовать криптографические свойства полученной с помощью него гаммы (равновероятность, период).

2.1.3. Сделать вывод.

2.2. Лабораторное задание №2

Изучение криптографических свойств алгоритма ГОСТ 28147-89

2.2.1 С помощью пакета MathCad написать программу, моделирующую работу алгоритма ГОСТ 28147-89.

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

2.2.3. Сделать вывод.

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

В чем состоит правило Керкгоффса? Почему это правило является общепринятым в криптографии?
Классификация блочных шифров, - примеры.
Классификация поточных шифров, - примеры.
Перечислите основные методы криптоанализа поточных шифров.
Перечислите основные методы криптоанализа блочных шифров.
На чем основаны методы криптоанализа поточных шифров?
На чем основаны методы криптоанализа блочных шифров?
К какому классу шифров относится алгоритм DES и чем определяется его криптостойкость?
К какому классу шифров относится алгоритм, реализующий стандарт шифрования данных ГОСТ 28147-89, и чем определяется его криптостойкость?
Классификация шифров.
Математические и вероятностные модели шифров.
Схема алгоритма DES.
Стандарт шифрования данных ГОСТ 28147-89.
На чем основанкриптоанализ поточных шифров?
На чем основанкриптоанализ блочных шифров?
На чем основанкриптоанализ шифров гаммирования?
Что такое композиционные шифры?

ЛАБОРАТОРНАЯ РАБОТА №4.

ИССЛЕДОВАНИЕ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ ШИФРСИСТЕМ ПОТОЧНОГО ТИПА.

Время 4 ч.

1. Общие указания по выполнению работы

1.1. Цели лабораторной работы

Образовательные:

закрепление на практике теоретические сведения по теме №7 “Методы анализа криптографических алгоритмов”;
ознакомление студентов с элементами криптоанализа поточных шифров, принципами исследования и оценки их криптографических свойств.

Развивающие:

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

Воспитательные:

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

1.2. В процессе выполнения лабораторной работы студенты должны изучить следующие вопросы

Алгоритмизация типовых криптографических алгоритмов
Синтез линейных рекуррентных регистров сдвига
Исследование свойств линейных псевдослучайных последовательностей

1.3. Техническое обеспечение:

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

2. Домашние задания и методические указания по их выполнению

2. Лабораторные задания и методические указания по их выполнению

2.1. Лабораторное задание №1

Синтез линейных рекуррентных регистров сдвига.

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

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

если полином выбран удачно, то период сформированной им последовательности будет удовлетворять выражению (1), в противном случае порождающий полином выбран неудачно.

, ( 1 )

где n – длина периода последовательности, m – количество элементов памяти ЛРР.

2.2. Лабораторное задание №2

Изучить свойства сгенерированной псевдослучайной последовательности.

Определить основные криптографические качества выбранного ЛРР:

- равновероятность «0» и «1» (путем подсчета их количества);

- определить реальный период полученной последовательности.

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

С целью получить минимально и максимально возможные периоды последовательности.

4. Выбрать другой порождающий полином (неприводимый, примитивный) и повторить операции п.п. 1-3.

5. Сделать выводы о случайном или детерминированном характере линейной рекуррентной последовательности (ЛРП), формируемой ЛРР.

Содержание отчета по данному заданию.

Запись порождающего полинома. Структурная схема ЛРР. Начальное заполнение. Запись сформированной ЛРП.
Результаты подсчета количества «0» и «1» полученной ЛРП.
Кодовые комбинации длиной m - бит, их количество и последовательность чередования.
Результаты исследований по п.п. 1 - 2 с другим начальным заполнением ЛРР.
Результаты исследований по п.п. 1 - 3 с другим порождающим полиномом.
Вывод о случайном или детерминированном характере линейной рекуррентной последовательности (ЛРП), формируемой ЛРР.

2.3. Лабораторное задание №3

Усложнение линейных рекуррентных последовательностей.

Построить два ЛРР на основе двух различных порождающих полиномов, соединить их последовательно через сумматор по модулю два, выполнить операции в соответствии с п.п. 1 – 5 I-го этапа работы.

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

Записать в конспект следующие положения.

Запись порождающих полиномов композиции из 2-х ЛРР.
1. Структурная схема полученной композиции.
2. Начальные заполнения ЛРР.
3. Запись сформированной ЛРП композиции из двух ЛРР.
4. Результаты исследований по п.п. 2 – 5 I–го этапа работы

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

Структура шифрсистемыгаммирования.
Требования к управляющему блоку.
Основные достоинства ЛРР и ЛРП с точки зрения их криптографических качеств.
Основные недостатки ЛРР и ЛРП с точки зрения их криптографических качеств.
Методы усложнения ЛРР.

ЛАБОРАТОРНАЯ РАБОТА №5.

ИССЛЕДОВАНИЕ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ ШИФРСИСТЕМ С ОТКРЫТЫМ КЛЮЧОМ.

Время 4 ч.

1. Общие указания по выполнению работы

1.1. Цели работы:

Образовательные:

закрепление на практике теоретические сведения по теме №5“Системы шифрования с открытым ключом”;
ознакомление студентов с элементами криптоанализа шифров RSA, принципами исследования и оценки их криптографических свойств..

Развивающие:

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

Воспитательные:

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

1.2. В процессе выполнения работы студенты должны изучить

вопросы криптоанализа асимметричных криптосистем на примере RSA

1.3.Техническое обеспечение:

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

2. Лабораторные задания и методические указания по их выполнению.

2.1 Лабораторное задание №1

Атака на алгоритм шифрования RSA посредством метода Ферма

Для выполнения лабораторного задания рекомендуется использовать программу BCalc.exe.

4.1.1 Получить вариант задания у преподавателя в соответствии с таблицей:

Вариант	Модуль, N	Экспонента, е	Блок зашифрованного текста, C
1	99595193774911	1908299	75790643190143 36869061035180 38422576553598 68899435645717 16193161920958 98487458352335 34167725433806 96613844267045 26583768908805 73052827576371 94695336463618 69092596694070
2	95841214023781	2005229	49190327214217 84609592142386 90112415897890 58321768145112 18048020096041 46703140105758 5914356051570 1805696039350 28838003818624 70062757763886 13846553049563 90432970156505
3	93767386321457	2091619	62984326732858 22123186696272 24425203655789 45995309006047 8176196426076 12816278693250 27474201663022 86909026690842 20469575723850 29205116646939 21002901408912 79168478687790

2.1.2 Используя разложение модуля на простые числа методом Ферма и полученные исходные данные, определить следующие показатели:

– множители модуля (p и q);

– значение функции Эйлера для данного модуля ;

– обратное значение экспоненты по модулю ;

2.1.3 дешифровать зашифрованный текст, исходный текст должен быть фразой на русском языке;

2.1.4 результаты и промежуточные вычисления оформить в виде отчета.

Пример выполнения лабораторной работы c помощью программы BCalc

Исходные данные: N = 65815671868057; e = 7423489; C = 38932868535359. Найти

1. Вычисляем n = [sqrt(N)] + 1. В поле A помещаем N, в поле B – 2; нажимаем кнопку «D = A^(1/B)». В поле D заносится число 8112686, в первую строку таблицы – сообщение «[error]». Это свидетельствует, о том, что N не является квадратом целого числа.

2. t1 = n + 1. Возводим число t1 в квадрат: A: = 8112687, B: = 2, C: = 0 (возведение в квадрат будет производиться не по правилам модульной арифметики), нажимаем «D = A^B mod C» => D = t1^2 = 65815690359969. Вычисляем w1 = t1^2 – N.

Для этого A:= t1^2, B:= –N, затем нажимаем «D = A + B» => D = w1 = 18491912.

Проверяем, является ли w1 квадратом целого числа: A:= w1,
B:= 2, нажимаем «D = A^(1/B)» => в первой строке таблицы появляется сообщение «[error]», следовательно проделываем п. 2 заново с t2 = n + 2 и так далее, пока не найдем, что некое wi является квадратом целого числа.

3. При вычислении квадратного корня w5 первая строка таблицы остается пустой, а D = sqrt(w5) = 9132, что свидетельствует об успехе факторизации. t5 = 8112691.

4. Вычисляем p = t5 + sqrt(w5); A:= t5, B:= sqrt(w5), нажимаем «D = A + B» => D = p = 8121823; q = t5 – sqrt(w5) = 8103559. Вычисляем
Phi(N) = (p – 1)(q – 1), A:= 8121822, B:= 8103558, нажимаем «D = A∙B» => D =
= Phi(N) = 65815655642676. Вычисляем d, как обратный к e: A:= e, B:= –1,
C:= Phi(N), нажимаем «D = A^B mod C» => D = d = 12490789985101.

5. Производим дешифрацию шифрблока С: A:= C; B:= d; C:= N. Нажимаем «D = A^B mod C». В поле D находится исходное сообщение M = 3402418120. Переводим M в текстовый вид. Для этого A:= M, нажимаем «D = text(A)» => D = = «КМЗИ».

Снимок экрана с окном программы «BCalc» приведен ниже.

2.2. Лабораторное задание №2

Атака на алгоритм шифрования RSA методом повторного шифрования

Для выполнения лабораторного задания рекомендуется использовать программу PS.exe.

4.2.1. Получить вариант задания у преподавателя в соответствии с таблицей:

Вариант	Модуль, N	Экспонента, e	Блок зашифрованного текста, С
1	307080138389	358703	150223836156 41077612181 164221721708 163231492773 84606189584 211632968571 76644428054 67904620890 263054305449 31191567018 224545225463 30878012295 216396046580
2	707096259383	928253	6952874554 579478452421 88828702123 225263521086 340528371521 583666721140 254303812163 584762191247 620918717873 52726307774 172435791721 293646690249 323995569099
3	385181864647	938573	331245775481 282425324609 65377570000 89972965825 264803627317 320989226085 324723654667 294634302620 142237555971 221994269576 209958712589 221718426295 163788492835

2.2.2 по полученным исходным данным, используя метод перешифрования, определить порядок числа e в конечном поле ;

2.2.3 используя значение порядка экспоненты, получить исходный текст методом перешифрования;

2.2.4 результаты и промежуточные вычисления оформить в виде отчета.

Пример выполнения лабораторной работыc помощью программы PS

Исходные данные: N = 453819149023; e = 1011817; C = 442511634532.

1. Определить порядок экспоненты. Для этого необходимо ввести значение модуля в поле N, экспоненты в поле e, в поле Y записывается произвольное число, меньше чем N. После этого нужно нажать кнопку Запуск повторного шифрования и дождаться, пока в поле X появится значение, равное корню е степени от числа Y по модулю N, а в поле i – порядок e в конечном поле . В данном примере он составляет 435.

2. Дешифровать зашифрованный текст. Для этого нужно в область редактирования поля C поместить блоки зашифрованного текста, разделенные символом конца строки, значение модуля в поле N, экспоненты в поле e и порядка экспоненты в поле i. Затем нажать на кнопку Дешифрация и дождаться появления исходного текста в области редактирования M. Ответ – открытый текст – «null».

2.3 Лабораторное задание №3

Атака на алгоритм шифрования RSA методом бесключевого чтения

Для выполнения практического задания рекомендуется использовать программу BCalc.exe.

2.3.1Получить вариант задания у преподавателя в соответствии с таблицей:

Вариант	Модуль, N	Экспоненты	Блок зашифрованного текста
		e1	e2	C1	C2
1	420882327013	1372369	961447	373413138774 142492164990 181970101695 71400620884 83588687662 111752930680 154836140461 191336073909 186412386345 303121580659 167437105893 279265271451	105783140624 384545054504 91022339898 266856044417 106548952403 160772152396 128969469496 242028887287 256618243529 47586486979 306022591934 419219258598
2	302296233419	1365787	763067	4735234112 222492941603 91642935786 258679721851 127352436654 270884254827 278389245811 229277148124 143477017416 56472903944 229332603068 60190953676	131720982156 50767819341 146687208678 65444189922 275196580101 21582029531 14338137631 4177778322 75624657756 274012339373 159018739186 49970035122
3	445632735571	1120289	559633	348555354398 351363944134 96907337112 141119651255 317600466893 84967944527 340088880266 311235549494 41838603784 333172824695 89494655477 3256803669	366337925832 29318249989 120058862823 428190500861 322426909958 286841513079 150392378882 441874945028 297137742269 304115257300 123106598046 110955623263

2.3.2 По полученным данным определить значения r и s при условии, чтобы e1∙r – e2∙s =1. Для этого необходимо использовать расширенный алгоритм Евклида;

2.3.3 Используя полученные выше значения r и s, записать исходный текст;

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

Пример выполнения лабораторной работыc помощью программы «BCalc»

Исходные данные: N = 357114156277; e1 = 1025537; e2 = 722983;
C1 = 68639736967; C2 = 204258645263.

1. Решаем уравнение e1∙r – e2∙s = ±1. Для этого в поле A помещаем значение e1, в поле B – значение e2. Нажимаем кнопку «A∙D – B∙C = N», затем – кнопку C = s = 406030; D = r = 286243.

2. Производим дешифрацию: c1 возводим в степень r, а c2 – в степень –s по модулю N, тогда c1^r = 189703239311, c2^(–s) = 104340380259.

После этого результаты перемножаем и получаем, что m^(e1∙r – e2∙s) =
= 19793708126073817161549. Далее берем модуль от полученного значения: (m^(e1∙r – e2∙s) mod N) = 1381187873 и преобразуем в текст «RSA!».

Ниже приведен снимок экрана с окном программы «BCalc».

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

Определение криптосистемы с открытым ключем (асимметричной криптосистемы).
Обобщенная схема асимметричной криптосистемы с открытым ключом.
Характерные особенности асимметричных криптосистем.
Требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы.
Определение однонаправленной функции.
Перечислите шифрсистемы с открытым ключом.
На чем основана стойкость шифрсистемы RSA ?
На чем основана стойкость шифрсистемы Эль-Гамаля ?
На чем основана стойкость шифрсистемы Мак Элиса ?
Моделирование и синтез шифров RSA, их достоинства и недостатки.
Моделирование и синтез шифров Эль - Гамаля, их достоинства и недостатки.
Чем определяется стойкость шифра RSA?
Чем определяется стойкость шифра Эль – Гамаля?

Литература

Основная:

1.Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие. М.: ГелиосАРВ, 2004. 480 с., ил.

Дополнительная:

2. Friedman W. F., Callimahos D. Military cryptanalysis. Part I. Vol. 2. – Aegean Park Press, Laguna Hills CA, 1985.

3. К. Шеннон. Работы по теории информации и кибернетике. ИЛ, 1963.

4. Яглом А.М., Яглом И.М. Вероятность и информация. –М.: Наука, 1973 г.

5. Д. Кнут. Искусство программирования для ЭВМ. 1,2,3 т.,М., Мир, 1977.

6. Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971. - 477с.4.

7. С. Мафтик. Механизмы защиты в сетях ЭВМ. М.,1992.

8. А.А. Варфоломеев, О.С. Домнина, М.Б. Пеленицын. Управление ключами в системах криптографической защиты банковской информации. М.: МИФИ, 1996.

9. А.А. Варфоломеев, М.Б. Пеленицын. Методы криптографии и их применение в банковских технологиях. Учебное пособие. М., МИФИ,1996.

10. В.М. Фомичев. Симметричные криптосхемы. Краткий обзор основ криптологии для шифрсистем с открытым ключом. Учебное пособие., М.: МИФИ, 1996.

11. У. Диффи, М.Э. Хеллман. Защищенность и имитостойкость. Введение в криптографию. ТИИЭР, т. 67,3, 1979.

12. Г. Фролов. Тайны тайнописи. М., 1992.

13. А. Акритас. Основы компьютерной алгебры с приложениями. М.,1994.

14. В. Жельников. Криптография от папируса до компьютера. М, 1996.

15. А. Саломаа. Криптография с открытым ключом. М., 1996.

16. Л. Дж. Хофман. Современные методы защиты информации. М.,1996.

ЛАБОРАТОРНАЯ РАБОТА №6.

ИССЛЕДОВАНИЕ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ

ШИФРА ЭЛЬ-ГАМАЛЯ.

Время 4 ч.

1. Общие указания по выполнению работы

Цели работы:

Образовательные:

закрепление на практике теоретические сведения по теме №2.1.1. “Системы шифрования с открытым ключом ”;

ознакомление студентов с криптографической системой Эль-Гамаля, изучение ее структуры и специфики применения.

Развивающие:

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

Воспитательные:

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

Учебные вопросы:

1. Работа алгоритма Эль-Гамаля в режиме шифрования.

2. Работа алгоритма Эль-Гамаля в режиме подписи.

Задачи:

совершенствование знаний полученных на лекционных занятиях и самоподготовке;

изучение алгоритма криптографической системы Эль-Гамаля;

получение практических навыков работы с криптогарфической системой Эль-Гамаля;

исследование реализации ЭЦП на основе алгоритма Эль-Гамаля;

выработка комплексного представления об обеспечении безопасности информации при помощи криптографических средств;

формирование навыков построения речи с использованием технической терминологии и самостоятельной работы с научно-технической литературой;

проведение контроля качества усвоения лекционного материала.

Форма проведения занятия - самостоятельная работа под руководством преподавателя (с элементами устного опроса по ранее изученному материалу).

2. Лабораторные задания и методические указания по их выполнению.

2.1.Лабораторное задание №1.

По вариантам. Зашифровать открытое сообщение на основе представленных исходных данных. Проверить (дешифровать) результат шифрования.

Вариант 1.

Дано p=11. На его основе выбрать числа g, x и k. Произвести все необходимые вычисления и зашифровать слово ЭЛЕКТРОН. Провести проверку - дешифровать полученный результат.

Вариант 2.

Дано p=17. На его основе выбрать числа g, x и k. Произвести все необходимые вычисления и зашифровать слово НОУТБУК. Провести проверку - дешифровать полученный результат.

Вариант 3.

Дано p=7. На его основе выбрать числа g, x и k. Произвести все необходимые вычисления и зашифровать слово ПОДПИСЬ. Провести проверку - дешифровать полученный результат.

Вариант 4.

Дано p=13. На его основе выбрать числа g, x и k. Произвести все необходимые вычисления и зашифровать слово БРАСЛЕТ. Провести проверку - дешифровать полученный результат.

Вариант 5.

Дано p=19. На его основе выбрать числа g, x и k. Произвести все необходимые вычисления и зашифровать слово КОМПЛЕКС. Провести проверку - дешифровать полученный результат.

2.2.Лабораторное задание №2.

С помощью программы-эмулятора ASI19.04.08.exe проанализировать пошаговый алгоритм работы криптографической системы Эль-Гамаля в режиме шифрования и в режиме подписи.

Режим шифрования.

2.1.1. Запустить ASI19.04.08.exe.

2.1.2. Выбрать «Криптосистема шифрования данных» - «Криптосистема шифрования данных Эль-Гамаля».

2.1.3. Исследовать каждый этап реализации алгоритма.

Режим подписи.

2.2.1. Запустить ASI19.04.08.exe.

2.2.2. Выбрать «Электронная цифровая подпись» - «Метод ЭЦП Эль-Гамаля».

2.2.3. Исследовать каждый этап реализации подписи.

Результаты проведенного исследования записать в лабораторную тетрадь.

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

Определение криптосистемы с открытым ключем (асимметричной криптосистемы).
Обобщенная схема асимметричной криптосистемы с открытым ключом.
Характерные особенности асимметричных криптосистем.
Требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы.
Определение однонаправленной функции.
Перечислите шифрсистемы с открытым ключом.
На чем основана стойкость шифрсистемы RSA ?
На чем основана стойкость шифрсистемы Эль-Гамаля?
На чем основана стойкость шифрсистемы Мак Элиса?
Моделирование и синтез шифров RSA, их достоинства и недостатки.
Моделирование и синтез шифров Эль - Гамаля, их достоинства и недостатки.
Чем определяется стойкость шифра RSA?
Чем определяется стойкость шифра Эль – Гамаля?

Литература

Основная:

1. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: Учебное пособие. М.: Гелиос АРВ, 2004. 480 с., ил.

Дополнительная:

2. Friedman W. F., Callimahos D. Military cryptanalysis. Part I. Vol. 2. – Aegean Park Press, Laguna Hills CA, 1985.

3. К. Шеннон. Работы по теории информации и кибернетике. ИЛ, 1963.

4. Яглом А.М., Яглом И.М. Вероятность и информация. –М.: Наука, 1973 г.

5. Д. Кнут. Искусство программирования для ЭВМ. 1,2,3 т.,М., Мир, 1977.

6. Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971. - 477с.4.

7. С. Мафтик. Механизмы защиты в сетях ЭВМ. М.,1992.

11. У. Диффи, М.Э. Хеллман. Защищенность и имитостойкость. Введение в криптографию. ТИИЭР, т. 67,3, 1979.

12. Г. Фролов. Тайны тайнописи. М., 1992.

13. А. Акритас. Основы компьютерной алгебры с приложениями. М.,1994.

14. В. Жельников. Криптография от папируса до компьютера. М, 1996.

15. А. Саломаа. Криптография с открытым ключом. М., 1996.

16. Л. Дж. Хофман. Современные методы защиты информации. М.,1996.

ЛАБОРАТОРНАЯ РАБОТА №7.

ПРОТОКОЛЫ РАСПРЕДЕЛЕНИЯ КЛЮЧЕЙ.

Время 4 ч.

1. Общие указания по выполнению работы

Цели работы:

Образовательные:

закрепление на практике теоретические сведения по теме №2.1.4. “Алгоритмы распределения ключей”;

ознакомление студентов с криптографической системой Диффи-Хеллмана.

Развивающие:

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

Воспитательные:

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

Учебные вопросы:

1. Протоколы выработки сеансовых ключей.

2. Открытое распределение ключей Диффи-Хеллмана и его модификации.

Задачи:

совершенствование знаний полученных на лекционных занятиях и самоподготовке;

изучение алгоритма Диффи-Хеллмана;

исследование специфики различных протоколов распределения ключей;

проведение контроля качества усвоения лекционного материала.

2. Лабораторные задания и методические указания по их выполнению.

Группа разделяется и работает по парам.

2.1.Лабораторное задание №1.

Требуется выработать общий ключ между двумя абонентами по оригинальному алгоритму Диффи-Хеллмана, имея следующие открытые данные (число g выбирается на основе данных своего варианта и затем производится вся цепочка вычислений, результатом которой должно быть нахождение общего секретного ключа K):

Вариант 1. p=13.

Вариант 2. p=11.

Вариант 3. p=17.

Вариант 4. p=27.

Вариант 5. p=23.

Вариант 6. p=19.

Результаты вычислений записать в лабораторную тетрадь.

2.2. Лабораторное задание №2.

Каждая из пар в соответствии со своим вариантом должна реализовать один из предложенных протоколов распределения ключей:

а) Модифицированный протокол типа Диффи-Хеллмана по составному модулю.

б) Протокол Гюнтера.

в) Протокол типа Диффи-Хеллмана, основанный на идентификационной информации.

г) Протокол Ингемарссона-Танга-Вонга.

Результаты записать в тетрадь.

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

1. Понятие протоколов выработки сеансовых ключей.

2 Виды протоколов распределения ключей.

3 Протоколы типа Диффи – Хеллмана.

4 Протоколы для конференц-связи.

5 Иерархические схемы распределения ключей.

6 Схема Диффи - Хеллмана по составному модулю.

Литература

[У2] Ухлинов Л. М., Распределение ключей защиты данных и проблема аутентификации, Автоматика и вычислительная техника, N 5, 1990, 11-17

[AT] Akl S. G., Taylor P. D., Cryptographic solution to a problem of access control in a hierarchy, ACM Trans. Comp. Sci., v. 1, N 1, 1983, 239-248

[Boer] den Boer B., Diffie-Hellman is as strong as discrete log for certain primes, Proc. CRYPTO'88, Lect. Notes in Comp. Sci., v. 403, 1989, 530-539

[Bra1] Brassard G., An optimally secure relativized cryptosystem, Rep. CRYPTO'81, Tech. Rep. N 82-04, 1982, Dep. of ECE, Univ. of California, 54-58; reprinted in SIGACT News, 1983, v. 15, N 1, 28-33

[Bra2] Brassard G., Relativized cryptography, IEEE Trans. on Inform. Theory, 1983, IT-19, 877-894

[Bur] Burmester M., On the risk of opening distributed keys, Proc. CRYPTO'94, Lect. Notes in Comp. Sci., v. 839, 308-317

[CHW] Chang C. C., Hwang R. J., Wu T. C., Cryptographic key assignment scheme for access control in a hierarchy, Inf. Syst., v. 17, N 3, 1992, 243-247

[DH] Diffie W., Hellman M. E., New directions in cryptography, IEEE Trans. on Inform. Theory., v. 22, N 6, 1976, 644-654

[G] G nther C. G., An identity-based key exchange protocol, Proc. EUROCRYPT'89, Lect. Notes in Comp. Sci., v. 434, 1990, 29-37

[Goss] Goss K. C., Cryptographic method and apparatus for public key exchange with authentication, U. S. Patent 4956863, Granted Sept. 11, 1990

[HL] Harn L., Lin H. Y., A cryptographic key generation scheme for multilevel data security, Comput. Sec., v. 9, N 6, 1990, 539-546

[IL] Impagliazzo R., Luby M., One-way functions are essential for complexity based cryptography, Proc. 30th Ann. Symp. on Found. of Comp. Sci., IEEE Comp. Soc., 1989

[IR] Impagliazzo R., Rudich S., Limits on the provable consequences of one-way permutations, Proc. 21st Ann. Symp. on Theory of Computing. ACM, 1989, 44-61

[ITW] IngemarssonI.,Tang D. T., Wong C. K., A conference key distribution system, IEEE Trans on Inform. Theory, v. IT-28, N 5, 1982, 714-720

[LWL] Liaw H. T., Wang S. J., Lei C. L., A dynamic cryptographic key assignment scheme in a tree structure, Comput. Math. Appl., v. 25, N 6, 1993, 109-114

[Mau] Maurer U. M., Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Proc. CRYPTO'94, Lect. Notes in Comp. Sci., v. 839, 271-281

[McKTMA] MacKinnon S. J., Taylor P. D., Meijer H., Akl S. G., An optimal algorithm for assigning cryptographic keys to access control in a hierarchy, IEEE Trans. Comput., v. C-34, N 9, 1985, 797-802

[MTI] Matsumoto T., Takashima Y., Imai H., On seeking smart public key distribution systems, Trans. IECE of Japan, E69(2), 1986, 99-106

[OT] Okamoto E., Tanaka K., Identity-based information security manegement system for personal computer networks, IEEE J. on Selected Areas in Communications, v. 7, N 2, 1989, 290-294

1. Тема- Физиология беременности Разработала- преподаватель Новикова Н
2. то во время домашнего концерта Александру Александровичу пришлось сопровождать одного из приглашённых музы
3. Автоматизация учета продажи товаров в ООО Мастер-СД
4. а 1 день Личность- ~ развитие качеств личности для перехода в индивидуальность
5. Путешествие в страну витаминию Методическая разработка внешкольного мероприятия
6. ТРИГГЕР. Универсальный JKтриггер ~ это последовательностные регенеративные бистабильные устройства с дв.html
7. связь бедствие
8. 1Определение основного удельного сопротивления вагонного состава 1
9. лімфоцити Батьки 5 річного хлопчика на прийомі у лікаря Гіпогамаглобулінемія Брутона Біохімічний аналіз
10. .3013.00 Джаз Body Bllet Ю.
11. Концепция мира и человека в творчестве Генриха фон Клейста
12. ГЕОЛОГОТЕХНИЧЕСКИЙ НАРЯД на бурение скважин Проектная глубина ~ 450 м
13. осадитель g то он прежде всего будет связывать анионы I т
14. совершая экспансию в регионы как говорил дядя Павел они добрались через Поволжье до Челябинска посетили
15. і. Мета задачі склад фінансової звітності і характеристика основних форм чинної фінансової звітності
16. Тема 10а Общие положения налогового права Российской Федерации
17. Татарско-крымская литература
18. і. Взаємозамінність деталей машин забезпечується системою допусків та посадок
19. ЛАБОРАТОРНАЯ РАБОТА 3 ПОЛУПРОВОДНИКОВЫЕ СТАБИЛИЗАТОРЫ Цель работы ' исследование рабочего участка вол
20. Доклад- Виндельбанд Вильгельм

Материалы собраны группой SamZan и находятся в свободном доступе

	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
А	2	12	35	8	14	7	6	15	7	7	19	27	19	45	5	11	26	31	27	3	1	10	6	7	10	1			2	6	9
Б	5					9	1		6			6		2	21		8	1		6						1	11				2
В	35	1	5	3	3	32		2	17		7	10	3	9	58	6	6	19	6	7		1	1	2	4	1	18	1	2		3
Г	7				3	3			5		1	5		1	50		7			2
Д	25		3	1	1	29	1	1	13		1	5	1	13	22	3	6	8	1	10			1	1	1		5	1			1
Е	2	9	18	11	27	7	5	10	6	15	13	35	24	63	7	16	39	37	33	3	1	8	3	7	3	3			1	1	2
Ж	5	1			6	12			5					6				1
З	35	1	7	1	5	3			4		2	1	2	9	9	1	3	1		2							4				4
И	4	6	22	5	10	21	2	23	19	11	19	21	20	32	8	13	11	29	29	3	1	17	3	11	1	1			1	3	17
Й	1	1	4	1	3		1	2	4		5	1	2	7	9	7	3	10	2				1	3	2
К	24	1	4	1		4	1	1	26		1	4	1	2	66	2	10	3	7	10			1
Л	25	1	1	1	1	33	2	1	36		1	2	1	8	30	2		3	1	6		4		1			2	30		4	9
М	18	2	4	1	1	21	1	2	23		3	1	3	7	19	5	2	5	3	9	1			2			5	1	1		3
Н	54	1	2	3	3	34			58		3		1	24	67	2	1	9	9	7	1		5	2			36	3			5
О	1	28	84	32	47	15	7	18	12	29	19	41	38	30	9	18	43	50	39	3	2	5	2	12	4	3			2	3	2
П	7					15			4			9		1	46		41	1		6							2				2
Р	55	1	4	4	3	37	3	1	24		3	1	3	7	56	2	1	5	9	16		1	1	1	2		8	3			5
С	8	1	7	1	2	25			6		40	13	3	9	27	11	4	11	82	6		1	1	2	2		1	8			17
Т	35	1	27	1	3	31		1	28		5	1	1	11	56	4	26	18	2	10				1			11	21			4
У	1	4	4	4	11	2	6	3	2		8	5	5	5	1	5	7	14	7			1		8	3	2				9	1
Ф	2					2			2						1		1	1
Х	4	1	4	1	3	1		2	3		4	3	3	4	18	5	3	4	2	2	1			1
Ц	3					7			10		2				1					1							1
Ч	12					23			13		2			6					7	1					1			1
Ш	5					11			14		1	2		2	2					1								1
Щ	3					8			6					1						1
Ы		1	9	1	3	12		2	4	7	3	6	6	3	2	10	3	9	4	1		16		1	2
Ь		2	4	1	1	2		2	2		6		3	13	2	4	1	11	3					1	4				1	3	1
Э											1			1				1	9
Ю		2	1	2	1			3	1		1		1	1	1	3	1	1	7				1	1		4
Я	1	3	9	1	3	3	1	5	3	2	3	3	4	6	3	6	3	6	10			2	1	4	1	1			1	1	1

П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
0	6,4	3,4	4,6	1,2	1	0	1,5	0,5	3,8	0	1	3,8	0,5	1,3	1

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С
10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
28	29	30	31	32	33	34	35	36	37	38	39	40	41

	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
А	2	12	35	8	14	7	6	15	7	7	19	27	19	45	5	11	26	31	27	3	1	10	6	7	10	1			2	6	9
Б	5					9	1		6			6		2	21		8	1		6						1	11				2
В	35	1	5	3	3	32		2	17		7	10	3	9	58	6	6	19	6	7		1	1	2	4	1	18	1	2		3
Г	7				3	3			5		1	5		1	50		7			2
Д	25		3	1	1	29	1	1	13		1	5	1	13	22	3	6	8	1	10			1	1	1		5	1			1
Е	2	9	18	11	27	7	5	10	6	15	13	35	24	63	7	16	39	37	33	3	1	8	3	7	3	3			1	1	2
Ж	5	1			6	12			5					6				1
З	35	1	7	1	5	3			4		2	1	2	9	9	1	3	1		2							4				4
И	4	6	22	5	10	21	2	23	19	11	19	21	20	32	8	13	11	29	29	3	1	17	3	11	1	1			1	3	17
Й	1	1	4	1	3		1	2	4		5	1	2	7	9	7	3	10	2				1	3	2
К	24	1	4	1		4	1	1	26		1	4	1	2	66	2	10	3	7	10			1
Л	25	1	1	1	1	33	2	1	36		1	2	1	8	30	2		3	1	6		4		1			2	30		4	9
М	18	2	4	1	1	21	1	2	23		3	1	3	7	19	5	2	5	3	9	1			2			5	1	1		3
Н	54	1	2	3	3	34			58		3		1	24	67	2	1	9	9	7	1		5	2			36	3			5
О	1	28	84	32	47	15	7	18	12	29	19	41	38	30	9	18	43	50	39	3	2	5	2	12	4	3			2	3	2
П	7					15			4			9		1	46		41	1		6							2				2
Р	55	1	4	4	3	37	3	1	24		3	1	3	7	56	2	1	5	9	16		1	1	1	2		8	3			5
С	8	1	7	1	2	25			6		40	13	3	9	27	11	4	11	82	6		1	1	2	2		1	8			17
Т	35	1	27	1	3	31		1	28		5	1	1	11	56	4	26	18	2	10				1			11	21			4
У	1	4	4	4	11	2	6	3	2		8	5	5	5	1	5	7	14	7			1		8	3	2				9	1
Ф	2					2			2						1		1	1
Х	4	1	4	1	3	1		2	3		4	3	3	4	18	5	3	4	2	2	1			1
Ц	3					7			10		2				1					1							1
Ч	12					23			13		2			6					7	1					1			1
Ш	5					11			14		1	2		2	2					1								1
Щ	3					8			6					1						1
Ы		1	9	1	3	12		2	4	7	3	6	6	3	2	10	3	9	4	1		16		1	2
Ь		2	4	1	1	2		2	2		6		3	13	2	4	1	11	3					1	4				1	3	1
Э											1			1				1	9
Ю		2	1	2	1			3	1		1		1	1	1	3	1	1	7				1	1		4
Я	1	3	9	1	3	3	1	5	3	2	3	3	4	6	3	6	3	6	10			2	1	4	1	1			1	1	1

П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
0	6,4	3,4	4,6	1,2	1	0	1,5	0,5	3,8	0	1	3,8	0,5	1,3	1

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С
10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
28	29	30	31	32	33	34	35	36	37	38	39	40	41

Воронежский государственный УНИВЕРСИТЕТ ИНЖЕНЕРНЫХ ТЕХНОЛОГИЙ Кафедра ИНФОРМАЦ

Поможем написать учебную работу

Выберите тип работы:

Генерация ключей

1.1. Работа алгоритма Эль-Гамаля в режиме шифрования

Шифрование

Расшифрование

Схема шифрования.

Пример.

1.2. Работа алгоритма Эль-Гамаля в режиме подписи

Подпись сообщений

Проверка подписи

Пример

Протоколы, основанные на идентификационной информации

Протокол Ингемарссона -- Танга – Вонга.

ЛАБОРАТОРНАЯ РАБОТА №2.ХАРАКТЕРИСТИКИ СТОЙКОСТИ ШИФРОВ.

ЛАБОРАТОРНАЯ РАБОТА №2.

ХАРАКТЕРИСТИКИ СТОЙКОСТИ ШИФРОВ.

	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
А	2	12	35	8	14	7	6	15	7	7	19	27	19	45	5	11	26	31	27	3	1	10	6	7	10	1			2	6	9
Б	5					9	1		6			6		2	21		8	1		6						1	11				2
В	35	1	5	3	3	32		2	17		7	10	3	9	58	6	6	19	6	7		1	1	2	4	1	18	1	2		3
Г	7				3	3			5		1	5		1	50		7			2
Д	25		3	1	1	29	1	1	13		1	5	1	13	22	3	6	8	1	10			1	1	1		5	1			1
Е	2	9	18	11	27	7	5	10	6	15	13	35	24	63	7	16	39	37	33	3	1	8	3	7	3	3			1	1	2
Ж	5	1			6	12			5					6				1
З	35	1	7	1	5	3			4		2	1	2	9	9	1	3	1		2							4				4
И	4	6	22	5	10	21	2	23	19	11	19	21	20	32	8	13	11	29	29	3	1	17	3	11	1	1			1	3	17
Й	1	1	4	1	3		1	2	4		5	1	2	7	9	7	3	10	2				1	3	2
К	24	1	4	1		4	1	1	26		1	4	1	2	66	2	10	3	7	10			1
Л	25	1	1	1	1	33	2	1	36		1	2	1	8	30	2		3	1	6		4		1			2	30		4	9
М	18	2	4	1	1	21	1	2	23		3	1	3	7	19	5	2	5	3	9	1			2			5	1	1		3
Н	54	1	2	3	3	34			58		3		1	24	67	2	1	9	9	7	1		5	2			36	3			5
О	1	28	84	32	47	15	7	18	12	29	19	41	38	30	9	18	43	50	39	3	2	5	2	12	4	3			2	3	2
П	7					15			4			9		1	46		41	1		6							2				2
Р	55	1	4	4	3	37	3	1	24		3	1	3	7	56	2	1	5	9	16		1	1	1	2		8	3			5
С	8	1	7	1	2	25			6		40	13	3	9	27	11	4	11	82	6		1	1	2	2		1	8			17
Т	35	1	27	1	3	31		1	28		5	1	1	11	56	4	26	18	2	10				1			11	21			4
У	1	4	4	4	11	2	6	3	2		8	5	5	5	1	5	7	14	7			1		8	3	2				9	1
Ф	2					2			2						1		1	1
Х	4	1	4	1	3	1		2	3		4	3	3	4	18	5	3	4	2	2	1			1
Ц	3					7			10		2				1					1							1
Ч	12					23			13		2			6					7	1					1			1
Ш	5					11			14		1	2		2	2					1								1
Щ	3					8			6					1						1
Ы		1	9	1	3	12		2	4	7	3	6	6	3	2	10	3	9	4	1		16		1	2
Ь		2	4	1	1	2		2	2		6		3	13	2	4	1	11	3					1	4				1	3	1
Э											1			1				1	9
Ю		2	1	2	1			3	1		1		1	1	1	3	1	1	7				1	1		4
Я	1	3	9	1	3	3	1	5	3	2	3	3	4	6	3	6	3	6	10			2	1	4	1	1			1	1	1

П	Р	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ы	Ь	Э	Ю	Я
0	6,4	3,4	4,6	1,2	1	0	1,5	0,5	3,8	0	1	3,8	0,5	1,3	1

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С
10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
28	29	30	31	32	33	34	35	36	37	38	39	40	41