Yarmolik_S_V_Kriptografia_i_okhrana_kommer_inf

4.3. Алгоритм Шнорра

Алгоритм Шнорра является альтернативой алгоритмам Фиата−Шамира и Гиллу−Кискатра. Его особенностью является то, что позволяет проводить предварительные вычисления, что удобно при малых вычислительных ресурсах. Надежность данного алгоритма основывается на сложности вычисления дискретного логарифма.

Доверенный центр выбирает два простых числа p и q таких, что p − 1 делится без остатка на q, и выбирается элемент g ≠ 1 такой, что для него верно g =

= h(p−1)/q mod p, где h − некоторое произвольное число из интервалаР(1, p − 1).

Параметры (p, q, g) являются открытой информацией и свободно публикуются. Они могут быть общими для группы пользователей. Также выбирается пара-

метр t (40 ≤ t < q), определяющий уровень безопасности.

v = g−s(mod p),							И	(4.7)
где v является открытым ключом A, который посылается доверенномуУ								центру и
там публикуется как открытое значение пользователя A.
						Г
Для доказательства знания секрета s проверяющему B, пользователь A
выполняет следующие действия:						Б
1. A выбирает случайное r
				[1, q − 1] и вычисляет
r					а
x = g (mod p).								(4.8)
					к
Далее, доказывающая сторона
					т x стороне B.
2. Сторона B отсылает случайноееe, где 1 ≤ e ≤ 2t.
3. A возвращает B y = (s*e + r) (mod q).
4. B вычисляет			отсыла
z = gy*ve (mod p).		о						(4.9)
	и
Если z = x, то идентификация считается успешной.
	, выберем простые р = 643 и q = 107, при этом выполняется
	л
услов е, что 107|642. Далее вычислим g из условия g = h(p−1)/q mod p, где h − не-
которое пробзвольное число из интервала (1, p − 1). В данном случае для h = 2

Далее доказывающая сторона A выбирает секрет s [1, q − 1] и вычисляет

получ м g = 64.
Например
Сторона А выбирает закрытый ключ s = 43 и вычисляет по формуле (4.7)
открытый ключ v = g−s (mod p) = 64−43	mod 643 = 623.
Б

Доказательство происходит следующим образом:

1.Сторона А случайным образом выбирает доказательство r = 27 и отсы-

лает x = gr(mod p) = 6427 mod 643 = 231 стороне B.

2.В отсылает A вызов e = 19.

3.A отсылает B y = (s*e + r) (mod q) = (43*19 + 27) (mod 107) = 95.

4. B вычисляет gy*ve(mod p) = 6495*62319 (mod 643) = 231, что равно x.

31

Задание для выполнения лабораторной работы №4

1.Изучить теоретический материал по лабораторной работе.

2.Реализовать алгоритм доказательства с нулевым знанием по алгоритму согласно своему варианту (табл. 4.1)

Таблица 4.1

Вариант

№1

№2

№3

Алгоритм

Фиата−Шамира

Гиллу−Кискатра

Шнорра

ЛИТЕРАТУРА

Р

И

1.

Венбо, М. Современная криптография: теория и практика / М. Венбо. – М. :

Изд. дом «Вильямс», 2005. – 768 с.

У

2.

Виноградов, И. М. Основы теории чисел / И. М. Виноградов. – М. : Наука,

1981. – 176 с.

И. В. Туринцев. – М. : СОЛОН-Пресс, 2002. – 272 с. Гинзбург

3.

Гинзбург, А. И. Пластиковые карты / А. И.

. – СПб. : Питер, 2004. –

128 с.

Б

4.

Грибунин, В. Г.

Цифровая стеганография / В.

. рибунин, И. Н. Оков,

а

5.

Деднев, М. А. Защита информации в банковском деле и электронном бизне-

се / М. А. Деднев, Д. В. Дыльнов. − М. : Кудиц-Обр з, 2004. – 512 с.

6.

Кнут, Д. Искусство программиров ния для ЭВМ. В 3 т. Т. 2: Получисленные

методы / Д. Кнут. – М. : Мир, 1977. – 724 с.

7.Лидл, Р. Конечные поля / Р. Лидл, Т. Нидеррайтер. – М. : Мир, 1988. – 820 с.

8.

Математические и

косновы криптологии / Ю. С. Харин [и др.]. –

БХВ–Петербург, 2005. – 288компьютс.

Минск : Новое знание, 2003. – 382 с.

9.

Молдовян, Н. А. Введениерныев криптосистемы с открытым ключом: Пробле-

о

матика криптографии; элемен ы еории чисел; двухключевые криптосистемы и др. :

учеб. пособие для вуз в /

Н. А. Молдовян, А. А. Молдовян. – СПб. : Издательство

л

10. Романец, Ю. В. Защита информации в компьютерных системах и сетях /

Ю. В. Романец, П. А. Т мофеев, В. Ф. Шаньгин. – М. : Радио и связь, 1999. – 328 с.
	б
11.	Смарт, Ни. Криптография / Н. Смарт. – М. : Техносфера, 2005. – 528 с.
12.	Харин, Ю. С. Компьютерный практикум по математическим методам защи-

ты нформац / Ю. С. Харин, С. В. Агиевич. – Минск : БГУ, 2001. – 190 с.

13.Хар н, Ю. С. Математические основы криптологии / Ю. С. Харин, В. И. Берник, Г. В. Матвеев. – Минск : БГУ, 1999. – 319 с.

14.Шеннон, К. Работы по теории информации и кибернетике / К. Шеннон. – М. : Издательство иностранной литературы, 1963. – 830 с.

15.Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнаейр. – М. : ТРИУМФ, 2002. – 816 с.

16.Ярмолик, В. Н. Элементы теории информации : практикум для студ. спец. «Программное обеспечение информационных технологий» / В. Н. Ярмолик, А. П. Занкович, С. С. Портянко. – Минск : БГУИР, 2007. – 40 с.

17.Ярмолик, В. Н. Криптография, стеганография и охрана авторского права / В. Н. Ярмолик, С. С. Портянко, С. В. Ярмолик. – Минск : Изд. центр БГУ, 2007.и

32

Св. план 2011, поз. 52

				Учебное издание
		Ярмолик Светлана Вячеславовна
		Ярмолик Вячеслав Николаевич									Р
								Г		И
КРИПТОГРАФИЯ И ОХРАНА КОММЕРЧЕСКОЙ
							Б		У
			ИНФОРМАЦИИ
						а
					к
	Методическое пособие по выполнению л бораторных работ
				е
для студентов специальностей 1-40 01 02-02 «Информационные системы
	и технологии в экономи » и 1-26 02 03 «Маркетинг»
			т
		дневной и заочной форм обучения
		о
	б	и
Редактор Т. Н. Крюкова
и
Корректор А. Вл. Тюхай
Компьютерная верстка Ю. Ч. Клочкевич
Б
Подп сано в печать			Формат 60×84 1/16.						Бумага офсетная.
Гарнитура «Таймс».			Оптечатано на ризографе.						Усл. печ. л. 2,0.
Уч.-изд. л. 2,0.			Тираж 100 экз.						Заказ 673.

Издатель и полиграфическое исполнение: учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» ЛИ №02330/0494371 от 16.03.2009. ЛП №02330/0494175 от 03.04.2009.

220013, Минск, П. Бровки, 6

33