103

4.12. DSA (DSS).

В основе DSA(DSS) (Digital Signature Algorithm (Digital Signature Standard )) [DSS 94] лежит подпись El Gamal. Пусть p – простое число, q – простое число, такое, что q|(p-1) и g имеет мультипликативный порядок q,

то есть g q = 1(modp).

Лемма. Мультипликативные вычисления степеней g по модулю p эквивалентны арифметическим вычислениям в показателе g по модулю q.

Д о к а з а т е л ь с т в о.

g x g y (modp) = g x+ y (modp)= g (x+ y)(mod q)+qn (modp)= = g (x+ y)(mod q) g qn (modp) = g (x+ y)(mod q) (modp).

Аналогично

(g x ) y (modp)= g xy(mod q) (modp),

что и требовалось доказать.

В DSS выбирают р~ 512 бит, q~ 160 бит. Пусть х случайное число, x< p-1. Тогда х – секретный ключ, а

у = g x (modp) –

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

1. Выбирается случайное число k<q. Так как НОД(k,q) = 1, то

k −1(mod q).

2.Вычисляется

r = [g k (modp)](modq). 3. Вычисляется

s = k −1(M + xr)(modq).

Подписью сообщения М является пара (r,s).

Проверка подписи осуществляется следующим образом. Вычисляется w = s−1(mod q).

Это можно сделать, так как q простое число. u1 = (Mw)(modq),

u2 = (rw)(modq),

v= [(g u1 y u2 )(modp)](modq).

Если выполняется равенство v = r, то подпись подтверждена.

Д о к а з а т е л ь с т в о.

v = [(g u1 y u2 )(modp)](modq).

Тогда по лемме

v = [(g M s −1 (mod q) g xr s −1 (mod q) )(modp)](modq) =

104

=[(g s −1 (M +xr)(mod q) )(modp)](modq) =

=[g k (modp)](modq)= r.

4.13. ГОСТ 3410.94.

Пусть р – простое число размера 509÷512 бит, q простое число такое, что q|(p-1). Число g<p-1 имеет мультипликативный порядок q, то есть

g q = 1(modp). p, q, g открыты. Число х, х <q, –секретный ключ, открытым

ключом является у= g x (modp). Алгоритм подписи [ГОСТ 94] сообщения М выглядит следующим образом.

1.Выбирается случайное число k.

2.Вычисляется

r= [g k (modp)](modq). 3. Вычисляется

s= (Mk + xr)(modq).

Подписью сообщения М является пара (r,s).

Проверка подписи осуществляется следующим образом. Вычисляются v = Мq −2 (modq),

z1 = (sv)(modq),

z 2 = ((q-r)v)(modq),

u = [(g z1 y z2 )(modp)](modq).

Если выполняется равенство u = r, то подпись подтверждена.

Д о к а з а т е л ь с т в о.

u = [(g z1 y z2 )(modp)](modq) =

=[(g (xr +kM )M q−2 (mod q)+x(q −r)M q−2 (mod q) )(modp)](modq) =

=[(g xrM q−2 (mod q)+k −xrM q−2 (mod q) )(modp)](modq) =

=[g k (modp)](modq)= r.

4.14. Схема идентификации Schnorr - Shamir.

Пусть n большое нечетное число. Выбирается случайное число k так, что НОД(n,k) = 1. Вычисляется

h= -k −2 (modn) = - (k −1) 2 (modn).

Вэтой схеме n, h открытый ключ, k- секретный ключ. Алгоритм подписи сообщения М <n выглядит следующим образом.

1.Выбирается случайное число r, НОД(r,n) = 1.

2.Вычисляется

										105
	s1 =		1		[		M		+ r]	(modn).
		2					r
	3. Вычисляется
	s 2 =	k			[	M			− r]	(modn).
		2
							r

Подписанное сообщение (М, s1 , s 2 ).

Проверка подписи осуществляется следующим образом. Вычисляется

u =[ s12 + hs 22 ](modn).

Если выполняется равенство u = M, то подпись подтверждена.

Д о к а з а т е л ь с т в о.

[ s12 + hs 22 ]( modn)=

[

1

[

M 2

+ 2M + r 2 ] -

4

2 k 2

M 2

r 2

- (k

−1

)

[

−

2M + r

2

]]( modn) = M(modn).

4

r 2

4.15. Схема аутентификации Feige – Fiat – Shamir.

Это протокол аутентификации с нулевым разглашением. V, P - участники протокола, P доказывает V, что он Р. Р выбирает модуль n = p q, где p, q – большие простые числа. На практике n ≥ 512 бит. Затем

выбирается ν такое, что x2 =ν mod n и существует ν −1 (mod n) . Здесь ν - открытый ключ. Тогда вычисляется наименьшее s, для которого

s2 =ν −1(mod n) ( т.е. s =		1 ν (mod n)).Число s – секретный ключ. Р надо
доказать, что ему известно s, не раскрывая секрета.
1)	Р выбирает случайное число r < n и вычисляет y = r 2 ( mod n)
		y
	P	V
2)	V выбирает случайный бит b,
		b
	V	P
3)	Если b = 0	r
	P	V
если b = 1		1
		z = r ν (modn)

P V

		106
	4) Если b = 0, V проверяет, что y = r 2 ( mod n) . Если b = 1, V проверяет,
что	νz2 = y( mod n), что доказывает то, что Р знает	1 .
		ν
	Если бы Р знал бит b до своего первого шага, но не знал бы секрет
s =	1 ν (mod n) , то то он смог бы обмануть V следующим образом.
	При b = 0 Р посылает V на первом шагу число y = r 2 ( mod n), а на

втором шагу он посылает число r. Тогда V убеждается, что y = r 2 ( mod n) .

	Если b= 1, то на первом шагу Р посылает число y =					r 2	( mod n) , а на втором
						ν
				r
	шаге Р посылает число z =				( mod n) . В этом случае V проверяет
		r 2	ν
	νz2 ( mod n) =ν		(mod n) = r 2 ( mod n) = y .
	ν 2				ν

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

равна (0.5) t , что при больших t делает процедуру аутентификации достоверной.

107

ЛИТЕРАТУРА

[Ама.] Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект. М.: Мир, 1993.

[Гилл] Гилл А. Линейные последовательные машины. Анализ, синтез и применение. М.: Наука, 1974.

[ГОСТ 94] Процедура выработки и проверки электронно-цифровой подписи на основе асимметрического, криптографического алгоритма.

ГОСТ 3410-94. М., 1994.

[Гэ.] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., 1982.

[Кол.] Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. М.: Наука, 1976.

[Ре.] Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980.

[Хоф.] Хоффман Л. Дж. Современные методы защиты информации, М.: Сов. Радио, 1980.

[Ш.] Шеннон К. Работы по теории информации и кибернетике, М.: Иностранная литература, 1963.

[Biham 93] Biham E., Shamir A. Differential Cryptanalysis of the Data Encryption Standard, SpringerVerlag, 1993.

[Biham 94] Biham E. Cryptanalysis of Multiple Modes of Operation//Proc. ASIACRYPT’94, SpringerVerlag, 1994, с. 278-291.

[Biham 98] Biham E., Knudsen L. Cryptanalysis of the ANSI X.9.52 CBCM Mode/Technion – Computer Science Department – Technical Report CS 0928, 1998.

[Gol.95] Golic J. Intrinsic Statistical Weakness of Keystream generators//Advances in Cryptology – ASIACRYPT’94, Lecture Notes in Computer Science, SpringerVerlag, 1995, v. 917, с. 91-103.

[Goll.] Gollmann D., Chambers W. Clock Controlled Shift Registers: a Review//IEEE J. Scl. Ar. Commun., 1989, v. 7, N 4, с. 525-533.

[DSS] Digital signature standart (DSS). FIPS PUB 190, 1994, MAY 19. [Massey 94] Massey J. Cryptography: Fundamentals and Applications.

Advanced Technology Seminars, 1994.

[Matsui 93] Matsui M. Linear Cryptanalysis Method for DES Cipher//PreProceedings of Eurocrypt’93, 1993, с. 112-133.

[Meier 89] Meier W., Staffelbach O. Fast Correlation Attacks on Certain Stream Ciphers// J. Cryptology, 1989, v. 1, N 3, с. 159-176.

[Men.] Menzes A., van Oorschot P., Vanstone S. Hadbook of Applied Cryptography, CRC Press, 1997.

[Mey.] Meyer C., Matyas S. Cryptography: a New Dimension in Computer Data Security. John Wiley & Sons, 1982.

108

[Ru.] Rueppel R. Good Stream Ciphers are Hard to Design. ICCST, Zurich, 1989, с. 163-173.

[Schn.96] Schneier B. Applied Cryptography Second Edition: protocols, algorithms and source code in C. John Wiley & Sons Inc., 1996.

[Schnorr 88] Schnorr C. On the Construction of Random Number Generators and Random Function Generators//Advances in Cryptology – Eurocrypt’88, 1988, с. 225-232.

[Simm. 94] Simmons G. Proof of Soundness (Integrity) of Cryptographic Protocols// J. Cryptology, 1994, v. 7, с. 69-77.