Библиографическое описание:

Бабенко М. Г., Карнаухова Е. С., Кучуков В. А., Кучеров Н. Н. Анализ псевдослучайных последовательностей на эллиптической кривой // Молодой ученый. — 2011. — №11. Т.1. — С. 12-14.

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

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

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

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

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

  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.
Основные термины (генерируются автоматически): эллиптической кривой, псевдослучайных последовательностей, псевдослучайных чисел, квадратичных полей Галуа, точках эллиптической кривой, генератора псевдослучайных чисел, elliptic curves, over elliptic curves, генератор псевдослучайных, неприводимый многочлен, генератор псевдослучайных последовательностей, построения псевдослучайных последовательностей, использованием квадратичных полей, точек эллиптической кривой, Анализ псевдослучайных последовательностей, примитивный многочлен, псевдослучайных последовательностей должен, последовательности псевдослучайных чисел, генераторов псевдослучайных последовательностей, псевдослучайных чисел должна.

Обсуждение

Социальные комментарии Cackle
Задать вопрос