Анализ псевдослучайных последовательностей на эллиптической кривой | Статья в журнале «Молодой ученый»

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

Бабенко М. Г., Карнаухова Е. С., Кучуков В. А., Кучеров Н. Н. Анализ псевдослучайных последовательностей на эллиптической кривой // Молодой ученый. — 2011. — №11. Т.1. — С. 12-14. — URL https://moluch.ru/archive/34/3929/ (дата обращения: 22.09.2018).

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

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

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

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

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

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


Похожие статьи

О построении формул аппроксимации периодических функций...

Приведен пример представления функции y = sin x последовательностью составных двухточечных многочленов, построенных для этой функции.

Литература: Романовский П. И. Ряды Фурье. Теория поля. Аналитические и специальные функции.

О представлении функции многочленом, имеющим заданные...

Приведен пример представления функции y= cos x последовательностью двухточечных многочленов Эрмита, построенных для заданного

Наличие существенной неравномерности аппроксимации функции f(x) многочленом Тейлора отмечено также в работе [6, c. 30].

К вопросу применения метода инкрементального группового...

В порядке возрастания элементов вектора сортировки установить последовательность изменения нагрузки объектов как функции S, согласно формуле

Функционирование алгоритма поясним на примере параллельной работы трех судовых дизель-генераторных агрегатов (ДГА).

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

Приближение функций с использованием частного вида многочленов Эрмита, именно двухточечных многочленов, когда значения функции и ее производных заданы только в двух концевых точках отрезка, рассмотрено в [4]. Целью данной работы является построение...

Анализ применения гомоморфных схем шифрования в алгоритмах...

Но даже в этом случае работа таких алгоритмов будет относительно медленной и ресурсозатратной, а размеры

Открытый ключ, , представляет собой вектор, содержащий два многочлена

О методике применения теоремы о пределе последовательности.

Алгоритмы расщепления для задачи о пропозициональной...

kol. Функция, подсчитывающая количество элементов вектора, не равных -1. main().

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

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

К вопросу об алгоритмической сложности задачи Рейдемейстера

Узлом называется гладкая замкнутая несамопересекающаяся кривая в пространстве, которую можно

Однако, из процедуры, которую она выполняет, последовательность движений

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

Периодические решения разностного уравнения третьего порядка

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

Обсуждение

Социальные комментарии Cackle

Похожие статьи

О построении формул аппроксимации периодических функций...

Приведен пример представления функции y = sin x последовательностью составных двухточечных многочленов, построенных для этой функции.

Литература: Романовский П. И. Ряды Фурье. Теория поля. Аналитические и специальные функции.

О представлении функции многочленом, имеющим заданные...

Приведен пример представления функции y= cos x последовательностью двухточечных многочленов Эрмита, построенных для заданного

Наличие существенной неравномерности аппроксимации функции f(x) многочленом Тейлора отмечено также в работе [6, c. 30].

К вопросу применения метода инкрементального группового...

В порядке возрастания элементов вектора сортировки установить последовательность изменения нагрузки объектов как функции S, согласно формуле

Функционирование алгоритма поясним на примере параллельной работы трех судовых дизель-генераторных агрегатов (ДГА).

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

Приближение функций с использованием частного вида многочленов Эрмита, именно двухточечных многочленов, когда значения функции и ее производных заданы только в двух концевых точках отрезка, рассмотрено в [4]. Целью данной работы является построение...

Анализ применения гомоморфных схем шифрования в алгоритмах...

Но даже в этом случае работа таких алгоритмов будет относительно медленной и ресурсозатратной, а размеры

Открытый ключ, , представляет собой вектор, содержащий два многочлена

О методике применения теоремы о пределе последовательности.

Алгоритмы расщепления для задачи о пропозициональной...

kol. Функция, подсчитывающая количество элементов вектора, не равных -1. main().

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

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

К вопросу об алгоритмической сложности задачи Рейдемейстера

Узлом называется гладкая замкнутая несамопересекающаяся кривая в пространстве, которую можно

Однако, из процедуры, которую она выполняет, последовательность движений

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

Периодические решения разностного уравнения третьего порядка

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

Задать вопрос