Анализ псевдослучайных последовательностей на эллиптической кривой

Введение. Постановка задачи.

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

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

Анализ генераторов построенных на точках эллиптической кривой

Генератор псевдослучайных последовательностей должен удовлетворять следующим двум требованиям, предложенным в работе []:

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

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

Эллиптическая кривая широко используется для построения криптосистем []. Одним из инструментов построения генераторов псевдослучайных последовательностей является эллиптическая кривая над конечным полем.

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

Халлгрен в 1994 году в работе [] рассмотрел датчик псевдослучайной последовательности, который называется арифметической прогрессией на с начальным членом и разностью и задается следующим рекуррентным соотношением:

, , (1)

где за обозначена групповая операция в .

Выходными значениями датчика (1) могут быть либо точки , либо только их абсциссы , либо только их ординаты .

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

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

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

Последовательность точек , удовлетворяющих рекуррентному соотношению:

, (2),

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

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

О последовательности, заданной формулой (2), известно, что период –последовательности (2) есть делитель периода ее характеристического многочлена []. В работе [] показано, что наибольший период имеет примитивный многочлен над полем.

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

Теорема 1. ([]).Нормированный многочлен , степени является примитивным многочленом над полем в том и только в том случае, если – примитивный элемент поля и наименьшим натуральным числом , для которого степень переменной сравнима по модулю с некоторым элементом поля , является .

Если – примитивный многочлен над , то имеет место сравнение .

В работе [] доказано более сильное утверждения касающаяся многочленов второй степени:

Утверждение 1 []. Если многочлен неприводим в , то

Следствие []. Нормированный неприводимый многочлен , где и – простое число Мерсенна, является примитивным многочленом над полем в том и только в том случае, если – образующий элемент в .

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

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

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

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

Утверждение 2. , где - неприводимый многочлен над .

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

Так как поле характеристики , то , следовательно

Из утверждения 1 следует, что , а , то

Утверждение доказано.

Из утверждения 2 следует критерий выбора двучлена для построения последовательности.

Критерий 1. Двучлен будет образующим элементом в , только если - образующий элемент в .

Выводы

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

Литература:

1. Бабенко М.Г. О выборе коэффициентов для некоторых ЕС-последовательностей порядка 2// Вестник поморского университета. Серия Естественные науки, г. Архангельск, №2, 2010, – С 76-80

2. Лидл Р., Нидеррайтер Г. Конечные поля: Пер. с англ. В 2 – х т.: Т.1. М., Мир, 1988.

3. Рябко Б. Я., Фионов А. Н. Криптографические методы защиты информации: Учебное пособие для вузов. – М.: Горячая линия–Телеком, 2005. – 229 с.

4. Червяков Н.И., Бабенко М.Г. Системы защиты данных на эллиптической кривой. Модулярная арифметика. – M.: LAMBER. – 2011. – 119 c.

5. Gong G., Lam C. Linear recursive sequences over elliptic curves. – In: Sequences and their applications. – London: Springer, 2002, P. 182 – 196.

6. Gutierrez J. and Ibeas A. Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits // Designs, Codes and Cryptography, 41, 2007, P. 199-212.

7. Hallgren S. Linear congruential generators over elliptic curve. // Cornegie Mellon Univ., 1994, CS-94-M3, P. 1-10.

8. Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation, 1987. Vol. 48. No. 177, P. 203-209.

9. Nahassni E.E., Shparlinski I. On the uniformity of distribution of congruential generators over elliptic curves. // In: Sequences and their applications. – London: Springer, 2002, P. 257-261.