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

11.10.1. Эллиптические алгоритмы формирования ПСЧ на основе линейных конгруэнтных генераторов

В 1994 г. S. Hallgren представил линейный конгруэнтный ге-

нератор (LCG, Linear Congruential Generator) над эллиптической кривой. Это – быстрый, но небезопасный генератор. Формируемые на основе LCG последовательности были названы LCG-EC- последовательностями.

Рассмотрим линейный конгруэнтный генератор над Zn. Уравнение линейного конгруэнтного генератора имеет вид

xi + 1 = axi + b (mod n),

где a, b, n – константы; x0 – начальное состояние генератора; a, b, x0, n Zn. Свойства последовательности зависят от выбранных параметров n, a, b и x0.

Линейный конгруэнтный генератор производит последовательность {xi} максимально возможного периода n тогда и только тогда, когда выполняется каждое из следующих условий:

b – простое число относительно n;

a { 1 (mod p) для каждого простого делителя p числа n; a { 1 (mod 4), если n кратно 4.

Рассмотрим линейный конгруэнтный генератор над эллиптической кривой. Переключения генератора LCG-EC-последова- тельности X0, X1, X2, … определяются рекуррентным соотношением Xi + 1 = aXi + B над эллиптической кривой, где a – константа, X0 – начальная точка, B – фиксированная точка. Выходная псевдослучайная последовательность суть последовательность младших бит y-координат точек Xi.

Алгоритм генерации ПСЧ

1.Выбираем конечное поле GF(q).

2.Выбираем кривую E.

3.Выбираем линейный конгруэнтный генератор, например,

Xi 1 aXi B .

4.Выбираем фиксированное целое число a, начальную точку X0 и фиксированную точку B, причем aX0 B ζ X0 .

321

5. Вычисляем последовательность	состояний генератора
X0, X1, X2, …, используя формулу	Xi 1 aXi B .

6.Формируем выходную двоичную ПСП из младших бит y-координат точек Xi.

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

Пример генератора ICG-E-последовательности. Рассмот-

рим эллиптическую кривую y2 = x3 + x + 1 над GF(23). Пусть a = 3, B = (11, 3), и X0= (5, 4). Последовательность точек, про-

изведенных по формуле Xi 1 aXi 1 B , показана в табл. 11.1.

Таблица 11.1

Пример ICG-EC-последовательности

i	Xi 1 aXi 1 B
0	(5, 4)
1	(3, 13)
2	(6, 4)
3	(9, 16)
4	(13, 7)
5	(19, 5)
6	(7, 11)
7	(1, 7)
8	(17, 20)
9	(0, 22)
10	(12, 4)
11	(18, 3)
12	( 5, 4)

Выходная псевдослучайная ICG-EC-последовательность: 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, …

имеет период 12.

322

11.10.2. Эллиптические алгоритмы формирования ПСЧ на основе регистров сдвига с линейными обратными связями

Рассмотрим конструкцию двоичных LFSR-EC-последова- тельностей.

Алгоритм формирования ПСЧ

1.Выбираем конечное поле GF(q) (или GF(2m)).

2.Выбираем эллиптическую кривую E.

3.Выбираем точку P порядка r на кривой Е.

4.Выбираем примитивный многочлен f(x) над GF(q) (или GF(2m)). Строим LFSR, используя f(x) в качестве характеристического многочлена.

5.Вычисляем LFSR-EC-последовательность P с использованием М-последовательности q с выхода LFSR.

6.Преобразуем LFSR-EC-последовательность P в двоичную

последовательность u с использованием оператора отображения GF(q) οGF(2) (или GF(2m) οGF(2)) (блока пространственного сжатия (БПС)).

Рассмотрим кривую E1: y2 = x3 + x + 4 над GF(23). Эта кривая имеет порядок 29. Пусть P = (4, 7) – точка на E1, порядок которой равен 29. Пусть начальное состояние Q = O, P0 = P, P1 = 2P.

Выберем f(x) = x2 – 28x – 26 Z29>x . LFSR-EC-последователь- ность P = {Pk} вычисляется с использованием LFSR, представленного на рис. 11.7. Точки показаны в табл. 11.2.

Pk = 28Pk - 1 + 26Pk - 2 = akP, k = 2, 3, ... ,

где ak = 28ak - 1 + 26ak - 2 (k = 2, 3, ...) – LFSR-последовательность над Z29 с начальным состоянием (a0, a1) = (1, 2).

Последовательность LFSR над Z29 имеет вид

a = (1, 2, 24, 28, 16, 16, 23, 16, 2, 8, 15, 19, 23, 7, 11, 26,

28, 10, 22, 6, 15, 25, 17, 24,12, …).

LFSR-EC-последовательность имеет вид

P = (P, 2P, 24P, 28P, 16P, 16P, 23P, 16P, 2P, 8P, 15P, 19P, 23P, 7P, 11P, 26P, 28P, 10P, 22P, 6P, 15P, 25P, 17P, 24P, 12P, …).

323

	28	26
	Pk-1	Pk-2

Pk

Рис. 11.7. Схема LFSR 1

Пусть g – корень многочлена f(x) = x5 + x2 + 1 и GF(25) – поле,

произведенное g. Рассмотрим несуперсингулярную кривую

E2: y2 + xy = x3 + g9x2 + g15 над GF(25).

Эта кривая имеет порядок 26. Пусть R точка на E2, порядок которой равен 13. Выберем f(x) = x2 – 12x – 11 Z13>x . Пусть начальное состояние Q = O, P0 = R и P1 = 2R. LFSR-EC-последова- тельность P = {Pk} формируется с использованием LFSR, представленного на рис. 11.8. Точки показаны в табл. 11.3.

Pk = 12Pk - 1 + 11Pk - 2 = akR, k = 2, 3, ...,

где ak = 12ak - 1 + 11ak - 2 (k = 2, 3,…) – LFSR-последовательность с начальным состоянием (a0, a1) = (1, 2).

12

11

Pk-1

Pk-2

Pk

Рис. 11.8. Схема LFSR 2

324

					Значения iP							Таблица 11.2
i	iP		i	iP		i		iP			i	iP
1	(4, 7)		9	(9, 12)		16		(0, 21)		23		(1, 12)
2	(10, 18)		10	(11, 9)		17		(14, 5)		24		(8, 15)
3	(13, 11)		11	(17, 9)		18		(17, 14)		25		(15, 17)
4	(15, 6)		12	(14, 18)		19		(11, 14)		26		(13, 12)
5	(8, 8)		13	(0, 2)		20		(9, 11)		27		(10, 5)
6	(1, 11)		14	(22, 5)		21		(18, 14)		28		(4, 16)
7	(7, 20)		15	(22, 18)		22		(7, 3)		29		O
8	(18, 9)
Последовательность LFSR над Z13 имеет вид
	a = (1, 2, 9, 0, 8, 5, 5, 11, 5, 12, 4, 11, 7, 10, 2, 4, 5, 0, 3,
	10, 10, 9, 10, 11, ...).
LFSR-EC-последовательность имеет вид
	P = (R, 2R, 9R, O, 8R, 5R, 5R, 11R, 5R, 12R, 4R, 11R, 7R,
	10R, 2R, 4R, 5R, O, 3R, 10R, 10R, 9R, 10R, 11R, ...).
					Значения iP							Таблица 11.3
i	iP			i		iP			I			iP
1	(g, g7)			10		(g24, g17)			19			(g14, g10)
2	(g21, g)			11		(g2, g18)			20			(g9, g29)
3	(g30, g29)			12		(g22, g5)			21			(g23, g25)
4	(g26, 1)			13		(0, g23)			22			(g26, g28)
5	(g23, g28)			14		(g22, g4)			23			(g30, g16)
6	(g9, g17)			15		(g2, g11)			24			(g21, g9)
7	(g14, g20)			16		(g24, g8)			25			(g, g28)
8	(1, g27)			17		(g28, g2)			26			O
9	(g28, g30)			18		(1, g6)

11.11. Сравнение систем на основе эллиптических кривых с другими асимметричными криптосистемами

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

Долгие годы неофициальным стандартом на шифрование с открытым ключом являлась система RSA, основанная на про-

325

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

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

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

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

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

2.Сравните криптосистемы RSA и ECCS по следующим параметрам: криптостойкость, быстродействие, эффективность программной и аппаратной реализации.

326

3.Приведите пример группы точек на эллиптической кривой над: а) GF(p); б) GF(2m).

4.Приведите пример эллиптического генератора ПСЧ на основе РСЛОС.

5.Перечислите параметры криптографической схемы, основанной на свойствах эллиптической кривой.

327

ГЛАВА 12. КРИПТОСИСТЕМЫ, ОСНОВАННЫЕ НА СВОЙСТВАХ ЭЛЛИПТИЧЕСКИХ КРИВЫХ

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

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

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

12.1. Схема симметричного шифрования на эллиптических кривых

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

Апреобразовывает открытый текст M в точки эллиптической кривой;

Авыбирает секретный ключ K;

Авычисляет закрытый текст С

C = M + K.

328

Расшифрование информации (абонент B преобразует закры-

тый текст С) (рис. 12.2):

Ввычисляет обратный ключ (–K).

Ввосстанавливает открытый текст M M = C + (–K).

y		y
C		C
x	M	x
M		-K
	Q	K
K
Q
Рис. 12.1.		Рис. 12.2.
Прямое преобразование	Обратное преобразование

Пример. Пусть задана кривая E (GF(23)) вида y2 x3 x 1.

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

Апреобразовывает открытый текст M в точку эллиптической кривой

M = (12, 19);

Авыбирает секретный ключ K = (13, 7);

Авычисляет закрытый текст С

C = M + K = (12, 19) + (13, 7) = (4, 0).

Расшифрование информации (абонент B восстанавливает закрытый текст С, полученный от абонента А):

В вычисляет обратный ключ (–K)

–K = (13, –7) mod 23 = (13, 16);

В восстанавливает открытый текст M

M = C + (–K) = (4, 0) + (13, 16) = (12, 19).

329

12.2. Схема асимметричного шифрования на эллиптических кривых

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

конечное поле GF(p); эллиптическая кривая E(GF(p));

порядок n, который является простым числом; базовая точка G порядка n.

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

выбирается случайное целое число d, 1 d n 1; вычисляется точка Q d υG .

Секретным ключом пользователя является число d, открытым ключом – точка Q.

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

А выбирает случайное целое число k, 1 k n 1; А вычисляет точку x1, y1 k υG ;

А вычисляет точку x2 , y2 k υQ , используя открытый ключ

Q пользователя В;

А вычисляет c1 M x2 ; закрытые данные: C x1, y1,c1 .

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

В вычисляет точку x2 , y2 d υ x1, y1 , используя свой сек-

ретный ключ d;	c1 x2 .
В восстанавливает исходное сообщение M
Пример
Параметры:
конечное поле GF(23);
эллиптическая кривая E (GF(23)) вида y2	x3 x 1;
базовая точка G = (13, 7);
порядок n = 7.

330