Нир: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Разработка генератора псевдослучайных чисел на точках эллиптической... 1 58.07kb.
Методические указания к лабораторным работам по курсу «Теория информациии... 3 447.96kb.
Реализация программного комплекса, моделирующего вычислительные комплексы... 1 72.18kb.
Минимизация ошибок и сбоев программного обеспечения 1 62.06kb.
М. М. Степанова Разработка в программном комплексе distolymp подсистем... 1 11.13kb.
Расчётно-графическая работа Новый стандарт симметричного шифрования aes 1 173.9kb.
Программа здесь >>>> система шифрования и встраивания информации... 1 15.61kb.
Инструкция по обработке археологических данных в программном комплексе... 1 313.02kb.
Шифр нир (окр) Наименование нир (окр) 1 113.24kb.
«Защита программного обеспечения от несанкционированного использования... 1 11.48kb.
5 Оценка стоимости разработки программного комплекса 1 71.74kb.
Учебное пособие для студентов Новосибирск 2003 10 3596kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Нир: «Разработка программного комплекса шифрования данных, на основе использования - страница №1/4

Министерство образования и науки Российской Федерации
Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования “Саратовский государственный университет имени Н.Г.Чернышевского” (СГУ)

УДК 681.3




УТВЕРЖДАЮ

Ректор Федерального государственного бюджетного образовательного учреждения высшего профессионального образования “Саратовский государственный

университет имени Н.Г.Чернышевского”

_____________________ Л.Ю.Коссович

«_____» _________________2011г.

МП


ОТЧЕТ

О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ


по Государственному контракту от 7 сентября 2011 года № 07.Р20.11.0029
“Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в Южном и Северо-Кавказском федеральных округах”

Тема НИР: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой»




Научный руководитель



М.Г. Бабенко

Саратов 2011

Список исполнителей


Научный руководитель НИР, начальник отдела разработки программного обеспечения и обработки информации РЦТ ФГБОУ ВПО СтавГУ, канд. физ.-мат. Наук

подпись, дата




М.Г. Бабенко (введение, разделы 5,6,7, заключение)


Исполнители темы







Студентка 4 курса физико-математического факультета, специальности математик СтавГУ

подпись, дата




Е.С. Карнаухова (раздел 1, 2, 3, 4)

Студент 4 курса физико-математического факультета, специальности математик СтавГУ

подпись, дата



В.А.Кучуков (раздел 1, 2, 3, 4)

Студент 4 курса физико-математического факультета, специальности математик СтавГУ

подпись, дата



Н.Н.Кучеров (разделы 1, 2, 3, 4)

Реферат
Отчет 91 с., 20 рис., 7 табл., 60 источников.
Криптография, методы математического моделирования, защита данных, модулярная арифметика

Научно-исследовательская работа по теме «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» выполняется в рамках федеральной целевой программы развития образования на 2011-2015 годы по Государственному контракту от 7 сентября 2011 года №07.Р20.11.0029.

Объектом исследования являются криптографические системы защиты данных на эллиптической кривой.

Цель работы — повышение эффективности выполнения криптографических преобразований с использованием точек эллиптической кривой.

В процессе работы проводились компьютерное моделирование разработанных алгоритмов

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

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

Настоящий отчет является заключительным. Работа в рамках проекта завершена в соответствии с календарным планом Государственного контракта от 7 сентября 2011 года №07.Р20.11.0029.



Содержание


Список исполнителей……………………………………………………………...

2

Реферат………………………………………………………………………………

3

Содержание………………………………………………………………………….

4

Введение……………………………………………………………………………..

5

1 Анализ математических моделей симметричных и ассиметричных криптосистем, построенных на точках эллиптической кривой……………..

6

2 Анализ алгоритмов периодического обновления секрета, построенных на точках эллиптической кривой………………………………………………..

23

3 Анализ методов пространственного разделения секрета…………………...

38

4 Анализ методов и алгоритмов умножения точки эллиптической кривой на скаляр…………………………………………………………………………….

49

5 Разработка алгоритма кодирования алфавита точками эллиптической кривой………………………………………………………………………………..

60

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

77

7 Разработка рекомендаций по использованию результатов проведенной НИР…………………………………………………………………………………..

85

Заключение………………………………………………………………………….

86

Список использованных источников……………………………………………

87

Введение
Основанием для проведения научно-исследовательской работы (НИР) является Государственный контракт от 7 сентября 2011 года № 07.Р20.11.0029. Начало работ: 10 октября 2011 г., окончание работ: 28 ноября 2011 г.

Для решения поставленных задач в рамках проводимой НИР был создан комплекс шифрования данных, на основе использования точек эллиптических кривых.

На этапе НИР была проведена разработка комплекса шифрования данных, на основе использования точек эллиптических кривых.

В ходе реализации проекта были решены следующие основные задачи.

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

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

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

Отчет по НИР состоит из: реферата, введения, шести разделов, заключения и списка литературы.



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

Криптосистемы, прежде всего, делятся на три типа [1-2]:

1. Бесключевые криптосистемы, которые не используют никаких ключей в процессе криптографических преобразований;

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

3. Двуключевые алгоритмы, в которых на различных этапах вычислений применяются два вида ключей: секретный и открытый.

Современные симметричные (одноключевые) криптосистемы базируются на математической модели классической секретной системы, предложенной К.Шенноном [3-5], для зашифровки текста в них используется несколько раундов. Исследования [6] в этой области показали, что алгоритмы симметричного шифрования можно разделить по виду алгоритмов повторяющихся преобразований.

Основными видами являются:

1. Алгоритмы на основе сети Фейстеля;

2. Алгоритмы на основе подстановочно-перестановочных сетей;

3. Алгоритмы со структурой «квадрат»;

4. Алгоритмы с нестандартной структурой.

Рассмотрим подробно алгоритм на основе сети Фейстеля. Этот алгоритм подразумевает разбиение обрабатываемого блока данных на несколько субблоков, один из которых обрабатывается некой функцией и накладывается на один или несколько остальных субблоков. На рисунке 1.1 приведена наиболее часто встречаемая структура алгоритма на основе сети Фейстеля.



Рисунок 1.1 – Сеть Фейстеля

Дополнительный аргумент функции , обозначенный на рисунке 1.1. как , называется ключом раунда. Ключ раунда является результатом преобразования, задача которого – получение ключей из исходного ключа шифрования относительно небольшого размера - 128 бит. В настоящее время для симметричных систем считается достаточным размер секретного ключа 128 бит. В простейшем случае процедура расширения ключа есть просто разбиение ключа на несколько фрагментов, которые поочередно используются в раундах шифрования. Гораздо чаще процедура расширения ключа является достаточно сложной, а ключи зависят от значений большинства битов исходного ключа шифрования.

Наложение обработочного субблока на необрабатываемый чаще всего выполняется с помощью логических операции «исключение или», как показано на рисунке 1.1. Достаточно часто в модуле заменяют операцию на сложение по модулю , где   размер субблока в битах. После наложения субблоки меняются местами, т.е. в следующем раунде алгоритма обрабатываются уже другой субблок данных. Такая структура шифрования получила свое название по имени Хоста Фейстеля – одного из разработчиков алгоритма Lucifer и разработанного на его основе алгоритма DES стандарта шифрования США. Оба этих алгоритма имеют структуру, показанную на рисунке 1.1. Среди других алгоритмов, основанных на сети Фейстеля, можно выделить отечественный стандарт шифрования ГОСТ 28147-89 [7], а также другие известные алгоритмы: RC5, Blowfish, TEA.

На сети Фейстеля основано большинство современных алгоритмов шифрования – благодаря множеству преимуществ подобной структуры, среди которых стоит отметить следующие:

1. При шифровании и расшифровывании может использоваться один и тот же алгоритм – разница между этими операциями может состоять лишь в порядке применения ключей : такое свойство алгоритма наиболее полезно при его аппаратной реализации или на платформах с ограниченным ресурсом, в качестве примера можно привести алгоритм ГОСТ 28147-89.

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

Существует и более сложная обобщенная или расширенная структура сети Фейстеля, пример которой приведен на рисунке 1.2. Такая структура применяется гораздо реже, чем обычная сеть Фейстеля. Примером использования расширенной сети Фейстеля является алгоритм RC6.



Рисунок 1.2 – Расширенная сеть Фейстеля

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

Рисунок 1.3   -сеть



-сеть является менее распространенной, чем сеть Фейстеля. Примером использования -сети могут стать алгоритмы Serpent или SAFER

Рассмотрим алгоритмы со структурой «квадрат».

Для структуры «квадрат» характерно представление шифруемого блока данных в виде двумерного массива. Криптографические преобразования могут выполняться им над отдельными байтами массива, а также над его строками или столбцами. Эта структура получила свое название от алгоритма Square, который был разработан в 1996 г. Винсентом Риджменом и Джоан Деймен. Эти исследователи впоследствии создали алгоритм Rijndael, ставший в США новым стандартом шифрования AES. Алгоритм Rijndael также имеет Square-подобную структуру, также можно отметить и алгоритм SHARK, который был разработан Ридженом и Деймен, и алгоритм Crypton. Недостатком алгоритмов со структурой квадрат является недостаточная изученность.

Существует еще один тип алгоритмов, которые нельзя строго отнести к какой-то структуре. Такие алгоритмы принято относить к алгоритмам с нестандартной структурой. Пример такого алгоритма может служить алгоритм CASE-256, так как его можно отнести и к -сетям, и к расширенным сетям Фейстеля. Другой алгоритм – HPC – его авторы определяют как сеть Фейстеля, но эксперты относят его к алгоритмам с нестандартной структурой [8].

Эффективными системами криптографической защиты передаваемых данных являются асимметричные двуключевые криптосистемы или криптосистемы с открытым ключом. Впервые понятие криптосистем с открытым ключом было введено в 1976 году У.Диффи и М.Хеллманом [9]. В своей статье «Новые направления в криптографии» они предложили новый принцип построения криптосистем и сформулировали ряд требований, выполнение которых обеспечивает безопасность систем такого типа. Характерной особенностью асимметричного шифрования является наличие двух ключей, связанных между собой. Один ключ (открытый) - используется для шифрования данных и является общедоступным для всех пользователей сети. Расшифровать данные с помощью этого ключа невозможно. Для расшифровывания данных получатель информации использует второй ключ - , который является секретным. Если ключ расшифровывания нельзя получить из ключа зашифровывания с помощью вычислений, то секретность информации, зашифрованной на открытом ключе, считается обеспеченной.

Обобщенная схема асимметричной криптосистемы представлена на рисунке 1.4.

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

Рисунок. 1.4 – Схема асимметричной (двуключевой) криптосистемы

Существует ряд требований, предъявляемых к системам с открытым ключом, выполнение которых обеспечивает безопасность асимметричного шифрования [10-11]:

1. Вычисление пары ключей получателем на основе начального условия должно быть простым;

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

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



;

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

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

Основным понятием криптографии с открытым ключом являются понятия однонаправленной функции и однонаправленной функции с «потайным ходом».

Известно следующее определение однонаправленной функции [5, 12].

Пусть и - некоторые произвольные множества.

Однонаправленной или односторонней называется такая функция , которая обладает следующими свойствами:

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

2. Не существует полиномиального алгоритма инвертирования функции , т.е. для любого не существует полиномиального алгоритма решения уравнения относительно .

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

Следует отметить, что типичных односторонних функций не существует, они конструируются в каждом конкретном случае. Исследования односторонних функций [4, 13-14] в основном проводились по трем направлениям:

1. Умножение простых чисел;

2. Дискретное умножение точки эллиптической кривой на скаляр или дискретное возведение в степень;

3. Задача - полноты, в частности задача об укладке ранца.

Очевидно, что однонаправленные функции не могут непосредственно использоваться в качестве криптосистем (когда открытый текст шифруется как ), поскольку тогда даже законный пользователь не сможет раскрыть открытый текст . По этой причине в криптографии более употребимым является понятие однонаправленной функции с «потайным ходом» или с секретом [15-17].

Под однонаправленной функцией с секретом понимается функция , зависящая от параметра , и обладающая тремя свойствами [5, 18-19]:

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

2. При неизвестном не существует полиномиального алгоритма инвертирования .

3. При известном существует полиномиальный алгоритм инвертирования .

Секрет иначе можно назвать «потайным ходом» или «ловушкой».

Использование односторонних функций с «потайным ходом» или «ловушкой» в криптографии позволяет [5]:

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

2. Включить в задачу вскрытия шифра трудную задачу и тем самым повысить обоснованность стойкости шифра.

3. Решать новые криптографические задачи, отличные от шифрования.

Для анализа ассиметричных криптосистем, построенных на точках эллиптической кривой, введем понятие эллиптической кривой [20-21].

Определение 1.1 Пусть   простое число. Пусть такие, что . Эллиптической кривой над полем называется множество решений уравнения




(1.1)

над полем с дополнительной точкой   точка в бесконечности. Представление эллиптической кривой в виде уравнения (1.1) носит название эллиптической кривой в форме Вейерштрассе.

Обозначим количество точек на эллиптической кривой через .

Зададим бинарную операцию на (в аддитивной записи) следующими правилами:

1.

2. ,

3. ,

4. , , где



и

5. , , , где





и

Множество точек эллиптической кривой с заданной таким образом операцией образуют абелевую группу.

В качестве примера однонаправленной функции с «потайным ходом» рассмотрим умножение точки эллиптической кривой на скаляр (с фиксированной точкой эллиптической кривой) [22]. Пусть   целое число,   эллиптическая кривая и точка - образующая аддитивной группы точек эллиптической кривой . Тогда умножение точки эллиптической кривой на скаляр есть функция , определяемая следующим образом:


.

(1.2)

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

Рассмотрим построение криптосистемы на криптографически не стойких эллиптических кривых, криптостойкость которых будет базироваться на разложении числа на простые множители, где ,   различные простые числа с равным количеством знаков в их двоичном представлении. Рассматривать будем при эллиптическую кривую вида , а при - эллиптическую кривую вида . Использование этих кривых для построения криптосистемы позволяет построить криптосистему, аналогичную криптосистеме RSA, описанной в работах [4, 13, 23], но на эллиптической кривой (рисунок 1.5 и рисунок 1.6).



Рисунок 1.5 – Блок-схема алгоритма создания открытого и секретного ключа в криптосистеме RSA на эллиптической кривой [22]


Рисунок 1.6 – Блок-схема алгоритма шифрования в криптосистеме RSA на эллиптической кривой

Используя выше перечисленную последовательность действий, мы находим   открытый и   секретный ключ криптосистемы RSA на эллиптической кривой. Рассмотрим алгоритм шифрования и дешифрования криптосистемы RSA на эллиптической кривой, который представлен на рисунке 1.7.

Рисунок 1.7 – Блок-схема алгоритма дешифрования в криптосистеме RSA на эллиптической кривой

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

Лемма 1.1: Пусть и - два различных простых числа, и . Тогда для всех , где , при или при .

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

Найдем в начале порядок эллиптических кривых и .

Рассмотрим 1 случай, когда , тогда эллиптическая кривая имеет вид . Порядок эллиптической кривой над простым полем вычисляется по формуле , где — символ Лежандра. Так как , то отображение является биекцией поля , следовательно, отображение — тоже биекция, а так как в количество квадратичных вычетов равно количеству квадратичных невычетов, то, следовательно, и , а .

Рассмотрим 2 случай, когда , тогда эллиптическая кривая имеет вид . Порядок эллиптической кривой над простым полем вычисляется по формуле . Так как , то из свойств символа Лежандра получаем следующее соотношение . Формулу для нахождения можно представить в следующем виде , а, так как , то для всех выполняется равенство и, значит, и .

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

Значит, при умножении точки на число , где , получаем точку . Числа равносильны тому, что . Следовательно, лемма доказана.

Криптосистема RSA, построенная на эллиптической кривой, позволяет нейтрализовать один из наиболее известных недостатков криптосистемы RSA, построенной над числовыми полями. Этот недостаток [25] - адаптивная атака с выбором зашифрованных сообщений. Это следует из того, что для любых открытых различных сообщений и и для соответствующих им закодированных точек и выполняется



.

(1.3)

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

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

И операции сложения и удвоения точек задаются следующим образом:

Пусть , , , . Тогда сложение точек формулой из работы [27]:





(1.4)

где и ,

Удвоение формулой из [27] для задается:





(1.5)

где .

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

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

1. — большое простое число, т.е. число, насчитывающее около 256 битов, и числа , такие, что — число точек эллиптической кривой , где - простое число, такое, что , и .

2. — элемент аддитивной группы точек эллиптической кривой , такой, что порядок равен , и выполняются следующие условия: и MOV условия с целью исключения криптографически слабых кривых , ,

Информация об этой группе открыта и используется большим числом пользователей.

После выбора параметров домена определяются открытые и секретные ключи. Секретным ключом априори может быть любое натуральное число , а открытый ключ получается по следующей формуле:

Сообщение в этой системе представляется точкой . Для его шифрования поступают следующим образом:

1. Генерируют случайный эфемерный ключ

2. Вычисляют ,

3. Вычисляют

4. Выдают получившийся шифротекст в виде пары

Чтобы расшифровать пару данных , производятся следующие преобразования:

Достоинства системы Эль-Гамаль:

1. Каждый пользователь системы должен выбрать случайное число и сделать не сложное вычисление, в отличие от системы RSA, которая требует, чтобы каждый пользователь системы находил два больших простых числа, что является сложной вычислительной задачей.

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

На основании анализа наиболее часто используемых ассиметричных систем шифрования мы можем классифицировать их по следующей схеме (рисунок 1.8).

Рисунок 1.8 – Классификация ассиметричных криптосистем на эллиптической кривой
Для определения свойства криптостойкости эллиптической кривой предложим следующий алгоритм (рисунок 1.9).

­­­

Рисунок 1.9 – Блок-схема алгоритма, определяющего криптостойкость эллиптической кривой

2 Анализ алгоритмов периодического обновления секрета, построенных на точках эллиптической кривой
Одним из базовых элементов систем активной безопасности являются методы периодического обновления секретной информации. Основу этих методов составляет управление ключевой системой, которое включает в себя описание всех видов ключей (долговременные, сеансовые и т.д.), а так же алгоритмы их использования [29]. В общем случае под управлением ключами будем понимать набор методов и средств, поддерживающих распределение и обработку ключевого материала между автоматизированными сторонами. Управление ключевой системой состоит из следующих процедур [30]:

1. Инициализация ключевой структуры для пользователей в домене.

2. Создание, распределение и инсталляция ключевого материала.

3. Контроль над использованием ключевого материала.

4. Обновление, восстановление, уничтожение ключевого материала.

5. Хранение ключевого материала.

Рассмотрим основные задачи управления ключевым материалом [31].

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

Для симметричных криптоалгоритмов выделяются два основных класса методов генерации ключей: детерминированный и недетерминированный.

В основе детерминированных методов лежит формирование из случайной последовательности малой длины псевдослучайной последовательности большей длины, которая не отличалась бы по своим статистическим свойствам от первоначальной [32].

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

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



, ,

(2.1)

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

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

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

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



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

,

(2.2)

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

Рассмотрим более подробно -последовательности порядка , где , , и – простое число. Тогда формула (1.8) примет вид:



,

(2.3)

а характеристический многочлен последовательности (2.3): над .

Найдем такие коэффициенты и , при которых последовательность (2.3) имела бы максимальный период.

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

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



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

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

Это утверждение также верно, если и неприводим в . Докажем это в следующей лемме.



Лемма 1.2 [38] Если многочлен неприводим в , то



(2.4).

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

Так как многочлен представляется в виде , то . Возведем обе части сравнения в степень , получим , так как – квадратичный невычет в .

Умножая левую и правую часть сравнения на , получим:


.

(2.5)

Так как – поле характеристики , то выполняется соотношение , следовательно:

.

(2.6)

Из сравнений (2.5) и (2.6), следует, что , значит, .

Лемма доказана.



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

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

Если – примитивный многочлен в , то он является нормированным неприводимым многочленом, а – образующий элемент в , согласно теореме 1.1.

Для доказательства обратного утверждения покажем, что , где - наименьший делитель , такой, что и .

Так как , то , следовательно, .

Пусть , где , тогда , так как , , то .

Если , то приходим к противоречию с тем, что – наименьшая натуральная степень, для которой . Следовательно, , значит, – делитель .

Тогда или

Если , то из рассмотренного нами выше следует, что .

Таким образом, , где – наименьший делитель , для которого . Так как , а – первообразный корень в и , то для всех , иначе являлся бы квадратичным вычетом в , чего не может быть. Следовательно, и , а, значит, многочлен , где , является примитивным в .

Следствие доказано.

Заметим, что для нахождения примитивных многочленов необходимо уметь находить нормированные неприводимые многочлены второй степени в . Предложим метод нахождения последних (рисунок 2.1).



Рисунок 2.1 – Схема метода нахождения нормированных неприводимых многочленов

Докажем корректность метода.

Из того, что – квадратичный невычет в , следует, что многочлен неприводим над [39].

В работе [39] доказано, что из неприводимости многочлена над следует неприводимость многочлена над , где – простое число.

Докажем, что многочлены попарно различны. Для чего покажем, что, если у многочленов и или , то многочлены . Рассмотрим два случая.

Случай 1. Если . Так как , то и , значит, для любого и .

Случай 2. Если , то из доказанного выше нам нужно рассмотреть только такой случай, когда . Так как , то , следовательно, и , значит, .

Таким образом, многочлены неприводимы над и попарно различны, их количество равно и совпадает с количеством нормированных неприводимых многочленов второй степени [37], следовательно, они описывают все нормированные неприводимые многочлены второй степени.

Корректность метода доказана.

Предложим метод нахождения коэффициентов последовательности (2.2), такой, чтобы она имела максимальный период, где – простое число Мерсенна (рисунок 2.2).
Рисунок 2.2 – Схема метода нахождения и

В построенных -последовательностях происходит смена точек а коэффициенты являются константами.

Рассмотрим другую схему, когда меняются коэффициенты, а точки остаются фиксированы.

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

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