Иванов Криптографические методы засчиты информации в компютерных 2012

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

выбирается случайное целое число d = 3; вычисляется точка Q d υG = 3(13, 7) = (17, 3).

Секретным ключом пользователя является число d = 3, открытым ключом – точка Q = (17, 3). Пусть сообщение M = 9.

Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B):

А выбирает случайное целое число k = 4;
А вычисляет точку	x1, y1	k υG = 4(13, 7) = (17, 20);
А вычисляет точку	x2 , y2	k υQ = 4(17, 3) = (5, 19);

А вычисляет c1 M x2 = 9 5 = 12; закрытые данные: C x1, y1,c1 = (17, 20, 12).

Расшифрование информации (абонент B восстанавливает закрытые данные C x1, y1,c1 = (17, 20, 12), полученные от або-

нента A):

В вычисляет точку x2 , y2 d υ x1, y1 = 3(17, 20) = (5, 19);

В восстанавливает исходное сообщение

Mc1 x2 = 12 5 = 9.

12.3.Схема электронной цифровой подписи на эллиптических кривых

Выбор параметров и процедура генерации ключей описаны в разделе 12.2.

Формирование подписи (абонент A подписывает сообщение M):
А вычисляет хеш-образ сообщения e h M ;
А выбирает случайное целое число k, 1 k n 1;
А вычисляет точку x1, y1		k υG ;
А вычисляет r	x1 e mod n ;
А вычисляет s	k r υ d mod n , используя свой секретный

ключ d. В том случае, если r = 0 или s = 0, выбор k осуществляется заново;

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

Проверка подписи (абонент B проверяет подпись (r, s) абонента A на сообщении M):

331

В вычисляет точку x1, y1 s υG r υQ , используя откры-

тый ключ Q абонента A;	h M ;
В вычисляет хеш-образ сообщения e
В вычисляет r1 x1 e mod n ;
подпись считается верной, если r1 r .
Пример
Параметры:
конечное поле GF(23);
эллиптическая кривая E (GF(23)) вида	y2 x3 x 1 ;

базовая точка G = (13, 7); порядок n = 7.

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

выбирается случайное целое число d = 3; вычисляется точка Q d υG = 3(13, 7) = (17, 3).

Секретным ключом пользователя является число d = 3, открытым ключом – точка Q = (17, 3). Пусть сообщение M = 10111001.

Формирование подписи (абонент A подписывает сообщение M):
А вычисляет хеш-образ сообщения e h M = 6;
А выбирает случайное целое число k = 4;
А вычисляет точку x1, y1		k υG = 4(13, 7) = (17, 20);
А вычисляет r	x1 e mod n = (17 + 6) mod 7 = 2;
А вычисляет s	k r υ d mod n = 4 – (2 υ 3) mod 7 = 5;

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

абонента A на сообщении M): В вычисляет точку

x1, y1 s υ G r υ Q = 5(13, 7) + 2(17, 3) = (17, 20);

В вычисляет хеш-образ сообщения e h M = 6;

В вычисляет r1 x1 e mod n = (17 + 6) mod 7 = 2;

подпись считается верной в случае r1 = 2.

332

12.4. Схема ЭЦП на эллиптических кривых (ECDSA)

Выбор параметров и процедура генерации ключей описаны в разделе 12.2.

Формирование подписи (абонент A подписывает сообщение M):
A вычисляет хеш-образ сообщения e		h M ;
А выбирает случайное целое число k, 1 k n 1;
А вычисляет точку x1, y1	k υG и r	x1 mod n ;

A вычисляет s k-1 υ e r υ d mod n , используя свой сек-

ретный ключ d; в случае, если r = 0 или s = 0, повторяется выбор k;

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

Проверка подписи (абонент B проверяет подпись сообщения

(r, s) абонента A под сообщением M):
B вычисляет хеш-образ сообщения e h M ;
B вычисляет u	s-1 υ e mod n и v	s-1 υ r modn ;
B вычисляет точку x1, y1 u υG v υQ , используя от-
крытый ключ Q абонента А;
B вычисляет r1	x1 mod n ;	r .
подпись считается верной, если r1
Пример
Параметры:
конечное поле GF(23);

эллиптическая кривая E (GF(23)) вида y2 x3 x 1;

базовая точка G = (13, 7); порядок n = 7.

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

выбирается случайное целое число d = 3; вычисляется точка Q d υG = 3(13, 7) = (17, 3).

Секретным ключом пользователя является число d = 3, от-

крытым ключом – точка Q = (17,	3). Пусть сообщение
M = 10111001.
Формирование подписи (абонент A подписывает сообщение M):
A вычисляет хеш-образ сообщения e	h M = 6;

A вычисляет случайное целое число k = 3;

333

A вычисляет точку x1, y1 k υG = 3(13, 7) = (17, 3) и

r x1 mod n = 17 mod 7 = 3;

A вычисляет

s k-1 υ e r υ d mod n = 3–1 υ (6 + (3 υ 3)) mod 7 =

= 5 υ (6 + 9) mod 7 = 5;

подписью сообщения являются (r, s) = (3, 5).

Проверка подписи (абонент B проверяет подпись сообщения

(r, s) = (3, 5) абонента A под сообщением M):
B вычисляет хеш-образ сообщения e h M = 6;
B вычисляет
u	s-1 υ e mod n = 5–1υ 6 mod 7 = 3 υ 6 mod 7 = 4
и	s-1 υ r mod n = 5–1υ 3 mod 7 = 2;
v

B вычисляет точку

x1, y1 u υG v υQ = 4(13, 7) + 2(17, 3) = (17, 3); B вычисляет r1 x1 mod n = 17 mod 7 = 3;

подпись считается верной в случае r1 = 3.

12.5. Протокол выработки общего секретного ключа

(ECKEP)

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

Процедуры определения параметров системы и генерации

ключей аналогичны рассмотренным ранее. Предположим, что
общий секретный ключ вычисляется абонентами A и B. Абонент
A имеет секретный ключ a и открытый ключ QA	a υG	xA, yA ,
аналогично b и QB bυG xB , yB являются	соответственно
секретными и открытыми ключами абонента B.
Общий секретный ключ вычисляется в четыре этапа:
1) абонент A выполняет следующие действия:
выбирает случайное целое число kA ,	1 kA n 1;

334

вычисляет точку RA	kA υG ;
вычисляет точку x1	, y1	kA υQB ;
вычисляет sA kA	a υ xA υ x1 mod n ;

	пересылает RA абоненту B;
2)	абонент B выполняет следующие действия:
	выбирает случайное целое число kB , 1 kB n 1;
	вычисляет точку RB	kB υG ;
	вычисляет точку x2	, y2	kB υ QA ;
	вычисляет sB kB	bυ xB υ x2 mod n ;
	пересылает RB абоненту A;
3)	абонент A выполняет следующие действия:
	вычисляет точку x2 , y2		a υ RB .
	Вычисляет общий секретный ключ
	K sA RB xB υ x2 υ QB ;
4)	абонент B выполняет следующие действия:
	вычисляет точку x1, y1		bυ RA ;

вычисляет общий секретный ключ

K sB RA xAυ x1 υ QA ,

что эквивалентно

K sA RB xB υ x2 υ QB .

Пример Параметры:

конечное поле GF(23);

эллиптическая кривая E (GF(23)) вида y2 x3 x 1;

базовая точка G = (13, 7); порядок n = 7.

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

A выбирает случайное целое число a = 3;
A вычисляет точку QA	a υG	xA, yA = 3(13, 7) = (17, 3);
B выбирает случайное целое число b = 6;
B вычисляет точку	xB , yB = 6(13, 7) = (13, 16).
QB bυG

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

335

выбирает случайное целое число kA = 4;

вычисляет точку RA			kA υG = 4(13, 7) = (17, 20);
вычисляет точку
x1	, y1	kA υQB = 4(13, 16) = (17, 3);
вычисляет
sA	kA a υ xA υ x1		mod n =
= 4 + (3 υ 17 υ 17) mod 7 = 3;

пересылает RA = (17, 20) абоненту B;

2) абонент B выполняет следующие действия: выбирает случайное целое число kB = 2;

вычисляет точку RB kB υG = 2(13, 7) = (5, 4);
вычисляет точку
x2 , y2	kB υ QA = 2(17, 3) = (13, 16);

вычисляет
sB kB bυ xB υ x2	mod n =

= 2 + (6 υ 13 υ 13) mod 7 = 1;

пересылает RB = (5, 4) абоненту A;

3) абонент A выполняет следующие действия:
вычисляет точку x2 , y2	a υ RB = 3(5, 4) = (13, 16);

вычисляет общий секретный ключ

K sA RB xB υ x2 υ QB =

= 3((5, 4) + (13 υ 13 υ (13, 16))) = (17, 3); 4) абонент B выполняет следующие действия:

вычисляет x1, y1 bυ RA = 6(17, 20) = (17, 3);

вычисляет общий секретный ключ

K sB RA xAυ x1 υ QA =

=1((17, 20) + (17 υ 17 υ (17, 3))) = (17, 3).

12.6.Схема гибридного шифрования (ECKAP)

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

Обозначения:

336

M – сообщение;

Q – открытый ключ абонента B; d – секретный ключ абонента B; KS – сеансовый ключ;

CM – шифротекст;

CK – зашифрованный ключ;

ES , DS – соответственно за- и расшифрование с использо-

ванием симметричного криптоалгоритма;

EA , DA – соответственно за- и расшифрование с использо-

ванием асимметричного криптоалгоритма.

Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B):

Авычисляет CM , преобразуя сообщение M на сеансовом ключе KS с использованием алгоритма ES ;

Авычисляет CK , преобразуя на открытом ключе Q абонента B сеансовый ключ KS с использованием алгоритма EA ; сообщение для абонента В включает закрытый текст CM и преобразованный ключ CK .

Расшифрование информации (абонент B восстанавливает полученное сообщение, включающее закрытый текст CM и преоб-

разованный ключ CK ):

Ввосстанавливает сеансовый ключ KS , преобразуя CK на своем секретном ключе d с использованием алгоритма DA ;

Ввосстанавливает исходное сообщение M, преобразуя CM на полученном сеансовом ключе KS с использованием алго-

ритма DS .

Пример Параметры:

конечное поле GF(23);

эллиптическая кривая E (GF(23)) вида y2 x3 x 1 ;

базовая точка G = (13, 7); порядок n = 7.

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

337

B выбирает секретный ключ d = 6; B вычисляет открытый ключ

Q d υG = 6(13, 7) = (13, 16).

Пусть открытый текст M = 6 и сеансовый ключ KS = (17, 3).

Зашифрование информации (абонент A защищает сообщение M, предназначенное для абонента B):

А вычисляет закрытый текст CM M KS = 6 17 = 23; А вычисляет преобразованный ключ CK :

А выбирает случайное целое число k = 2;
А вычисляет точку	x1, y1	k υG = 2(13, 7) = (5, 4);
А вычисляет точку x2 , y2		k υQ = 2(13, 16) = (5, 19);
А вычисляет CK	KS x2 = (17, 3) 5 = (20, 6);
закрытие данных:	= (20, 6), x1, y1 = (5, 4).
CM = 23, CK

Расшифрование информации (абонент B восстанавливает полученное от абонента A сообщение CM = 23, используя ключ

CK = (20, 6) и x1, y1 = (5, 4)):

абонент В восстанавливает сеансовый ключ KS : вычисляет точку

x2 , y2 d υ x1, y1 = 6(5, 4) = (5, 19);

восстанавливает сеансовый ключ KS

KS CK x2 = (20, 6) 5 = (17, 3);

абонент В восстанавливает исходное сообщение:

MCM KS = 23 17 = 6.

12.7.Российский стандарт на ЭЦП ГОСТ Р 34.10-2001

ГОСТ Р 34.10-2001 – российский стандарт, описывающий алгоритмы формирования и проверки электронной цифровой подписи. Введен в действие вместо ГОСТ Р 34.10-94. Старый стандарт описывал алгоритм ЭЦП на основе проблемы дискретного

338

логарифмирования в конечном поле, новый же предписывает использовать эллиптические кривые над полем GF(p).

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

Обозначения:

V256	– множество всех двоичных векторов длиной 256
	бит;
Vφ	– множество всех двоичных векторов произвольной
Z	конечной длины;
	– множество всех целых чисел;
p	– простое число, p > 3;
GF(p)	– конечное простое поле из p элементов

{0, 1, 2, ..., (p – 1)};

b mod p – минимальное неотрицательное число, сравнимое с b по модулю p;

h– двоичный вектор, например, двоичный вектор длиной 256 бит может быть представлен в виде

	h = (	255 ...	1	0),	i {0, 1},
	числу соответствует вектор h, если выполняется
M	равенство	= 6Δi 2i;
	– сообщение, М Vφ;
(h1, h2)	– конкатенация (объединение) двух двоичных
	векторов, пусть				i {0, 1},
	h1 = (	255 ...	1	0),
	h2 = (Ε255 ... Ε1 Ε0), Εi {0, 1},
a, b	тогда (h1, h2) = ( 255 ...			1	0 Ε255 ... Ε1 Ε0);
	– коэффициенты эллиптической кривой;
m	– порядок группы точек эллиптической кривой;

q– порядок подгруппы группы точек эллиптической кривой;

O– бесконечно удаленная точка эллиптической кривой;

P– точка эллиптической кривой порядка q;

339

d	– целое число, ключ формирования подписи;

Q– точка эллиптической кривой, ключ проверки подписи;

sign (M) – цифровая подпись под сообщением М. Механизм цифровой подписи включает в себя две основные

процедуры:

1)формирование подписи (рис. 12.3);

2)проверку подписи (рис. 12.4).

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

Разрядность цифровой подписи устанавливается равной 512 бит.

Математические предпосылки

Инвариантом эллиптической кривой Е называется величина J(E), удовлетворяющая тождеству

J(E) { 1728 (4a3/(4a3 + 27b2)) mod p.

Коэффициенты a и b эллиптической кривой по известному инварианту J определяются следующим образом:

a{ 3k mod p,

b{ 2k mod p,

где

k { J(E)/(1728 – J(E)) mod p, J(E) z 0, J(E) z 1728.

Для абелевой группы порядка m, которую образуют точки эллиптической кривой E, справедливо неравенство

p + 1 – 2 p d m d p + 1 + 2 p .

Точка Q называется точкой кратности k или просто кратной точкой эллиптической кривой Е, если для некоторой точки Р выполняется равенство Q = kP.

340