Нир: «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» - 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.

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


Пример 5.2. Эллиптическая кривая задается уравнением:

, где , , , , , , , , , , .

Результат представлены в таблице 5.6.


Таблица 5.6 – Разложения на простые множители





Разложения числа на простые множители

1

1279

1279

2

3327

3∙1109

3

5119

5119

4

6143

6143

5

7679

7∙1097

6

8191

8191

7

8447

8447

8

9727

71∙137

9

9983

67∙149


Тогда с помощью точек эллиптической кривой можно закодировать алфавит, содержащий слов.

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

1. При большой мощности алфавита вероятность его не закодировать возрастает и становиться больше, чем вероятность его закодировать.

2. С помощью данного метода возможно закодировать алфавит в раз меньше, чем количество точек на эллиптической кривой.

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

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

6 Разработка пороговой схемы разделения секрета на эллиптической кривой над конечным кольцом
Современные информационные системы требуют особого подхода к сохранению секрета: люди не могут целиком доверять своему окружению, так как кто-то может быть подкуплен конкурентами. В этом случае проблему сохранения секрета в тайне решают с помощью схемы разделения секрета [51-52]. Первыми пороговую схему разделения секрета рассмотрели в своих работах Г. Блейкли [53] и А. Шамир [54] в 1979 году.

Схема Шамира позволяет секрет разделить на частей , ,…, так, что выполняются следующие два условия:

1. С помощью любых и более частей можно восстановить секрет ;

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

Пороговые схемы, удовлетворяющие условию 2, называются совершенными пороговыми схемами разделения секрета. В работе [55] предложен алгоритм многоточечного разделения точек на эллиптической кривой, в котором используется спаривание из работы [56]. В работе [55] показано, что эта схема является совершенной и криптостойкой, если выполняются следующие четыре условия:

1. Честных пользователей в схеме должно быть не менее ;

2. Задача нахождения дискретного логарифма в группе точек эллиптической кривой должна быть трудно вычислимой;

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

4. Распространено не более точек.

Из условия 3 и условия применимости алгоритма Полига-Хеллмана-Зильбера, изложенного в работах [57], следует, что порядок группы точек эллиптической кривой при разложении на множители должен содержать большое простое число. Таким образом, нам необходим алгоритм, с помощью которого можно эффективно находить порядок группы точек эллиптической кривой. Одним из наиболее известных алгоритмов является алгоритм Шуфа, изложенный в работах [57], и его усовершенствование Элкисаном и Аткиным, известное как алгоритм SEA, изложенное в работах [58-59]. Сложность этих алгоритмов составляет и соответственно. Для выполнения условия 2 требуется, чтобы , из чего следует, что, используя самый быстрый универсальный алгоритм SEA для нахождения , требуется операций, что приблизительно равно , а, так как современная вычислительная техника может выполнять операций в секунду, то потребуется 55 часов для нахождения порядка одной эллиптической кривой. Это делает данный алгоритм неприемлемым для использования в практических целях.

Альтернативным решением данной проблемы является построение криптосистемы на эллиптической кривой , заданной конечным кольцом , , – различные простые числа и для всех .

Билинейное спаривание

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



Теорема 6.1 [60] Если , то группа циклическая. Если , то группа изоморфна в случае , или изоморфна в случае . Если , , то группа циклическая. Если , , то группа или циклическая или изоморфна .

Из теоремы 6.1 следует, что в случае, когда и – четное число, группа точек представляется в виде прямой суммы или . Обозначим эти группы , где или .

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

и . Исключая тривиальный случай, когда и одновременно равны нулю.

Пусть , и – три Абелевы группы. Билинейное спаривание является отображением среди этих трех групп, и отображение должно удовлетворять свойству билинейности: для , , , .

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

Теорема 6.2 [56] Функция обладает следующими свойствами:


  1. Тождественность.

Для всех ,

  1. Билинейность.

Для всех .

и

  1. Антисимметричность.

Для любых , .

  1. Невырожденность.

Для всех , . Кроме того, если для всех , тогда .

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

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



Замечание. Значения , , представляются в системе остаточных классов числами , , по основаниям .

Приведем небольшой пример для построения билинейного спаривания.



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

Схема разделения точек на эллиптической кривой

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



Начальная фаза

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

1. Дилер выбирает эллиптическую кривую над , где , – попарно различные простые числа, так, чтобы . выбирает целое четное число и вычисляет множество чисел ;

2.  выбирает образующую пару и целые числа , которые задают спаривание ;

3. Дилер опубликовывает , что является открытым ключом.

Фаза секретного распределения

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

1.  вычисляет матрицу :

;

(6.1)

2.  выбирает случайных чисел каждое для и ;

3.  вычисляет и ;

4. В завершении сообщает пар (секретный ключ) пользователю для всех , где .

Фаза разбиения точек

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

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

2.  вычисляет для всех , и публикует (открытый ключ).



Алгоритм восстановления точки

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

1. Каждый берет массив целых чисел из открытого ключа, где , ;

2. Каждый вычисляет , где и , где и ;

3. Каждый группой псевдосекрет к , где ;

4. Каждый вычисляет , где и ;

5. Каждый загружает точку из открытого ключа и восстанавливает , как ;

6. Из множества восстанавливается точка , где и .



Анализ безопасности

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



Теорема 6.3:. Если, по крайней мере пользователей честных, тогда любые пользователей ничего не узнают о , где – зафиксированное целое число, принадлежащее отрезку .

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

Пусть произвольных пользователей знают и , , , , , , где . Пусть

,

(6.2)

тогда .

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

Теорема доказана.

Приведем лемму из работы [55], в которой говорится о том случае, когда и которая потребуется при доказательстве теоремы о вероятности выбора случайной точки.



Лемма 6.1: [55]. Если и , то тогда и только тогда, когда принадлежит множеству .

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

Теорема о случайном выборе точки.

Теорема 6.4: [55]. Не зная точку , вероятность выбора случайной точки такой, чтобы выполнялось для всех , равна .

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

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

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

Теорема доказана.

Итак, предложенная схема разделения секрета является безопасной при выполнении двух условий:

1. По крайней мере пользователей в схеме честных.

2. Распространено не более, чем точек.

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



7 Разработка рекомендаций по использованию результатов проведенной НИР
Результаты работы могут быть использованы для разработки типовых процессов передачи данных на основе современных информационных технологий в региональных компаниях телекоммуникаций; для реализации эффективных алгоритмов передачи информации в распределенных вычислительных сетях; в качестве прототипа для разработки систем передачи информации с использованием эллиптической кривой, заданной над конечным кольцом, обладающих параллелизмом машинным операций

Результаты исследования могут быть использованы на предприятиях и в организациях, занимающихся разработкой информационных систем для решения задач передачи информации в распределенных вычислительных четях, входящих в состав холдинга ОАО «Связьинвест» (ОАО «Волгателеком», ОАО «Центральная телекоммуникационная компания», ОАО «Северо-Западный Телеком», ОАО «Южная телекоммуникационная компания», ОАО «Уралсвязьинформ», ОАО «Сибирьтелеком», ОАО «Дальневосточная компания электросвязи») и альтернативных операторов (ОАО «ТрансТелеком»), а также ВУЗах, где имеются телекоммуникационные специальности.



Заключение
В результате научно-исследовательской работы по теме «Разработка программного комплекса шифрования данных, на основе использования точек эллиптической кривой» были проведены следующие исследования:

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

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

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

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

5. Разработана схема разделения секрета на точках эллиптической кривой и показана, что разработанная схема является совершенной схемой разделения секрета.

Как видно из отчетных материалов, все исследовательские задачи по проекту выполнены полностью с должным качеством.

При плановых показателях публикации в изданиях 2 публикаций по факту опубликованы 2 публикации.



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


  1. Бабенко, М.Г. Классификация криптографических алгоритмов / Бабенко М.Г., Савченко А.Н. // Актуальные проблемы и инновации в экономике, управлении, образовании, информационных технология: Материалы международной научной конференции. – Ставрополь: 2009. – С. 19-21.

  2. Needham, R.M. Using Encryption for Authentication in Large Networks of Computers / Needham R.M., Schroeder M.D. // Comm. of the ACM. v21 (12). 1978. P. 993-999.

  3. Балашов, Ю.Х. Модель криптографической системы / Балашов Ю.Х. // Управляющие системы и машины. Т. 48. №4, 1980. С. 13-18.

  4. Бияшев, Р.Г. Основные направления развития и совершенствования криптографического закрытия информации / Бияшев Р.Г., Диев С.И., Размахнин М.К. // Зарубежная радиоэлектроника. №12, 1989. – С. 76-91.

  5. Диева, С.А. Организация и современные методы защиты информации / Диева, С.А., Шаваева, А.Г. – М.: Концерн «Банковский Деловой Центр», 1998. – C. 472.

  6. Панасенко, С.П. Назначения и структура алгоритмов шифрования / Панасенко С.П. / Электронные данные. – С. 8. http://www.ixbt.com (20.12.2006).

  7. ГОСТ 28147-89. Система обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. — М.: Госстандарт СССР, 1989. – C. 28.

  8. Kohl, J. The Kerberos Network Authentication Service / Kohl J., Neuman C. / Электронные данные. – С. 20. http://www.kerberos.info/ (10.09.2004).

  9. Диффи, У.Защищенность и криптостойкость: Введение в криптографию / Диффи У., Хеллман М.Э. // ТИИЭР. Т. 67. №3, 1979. – С. 71-109.

  10. Гундарь, К.Ю. Защита информации в компьютерных системах/ Гундарь, К.Ю., Гундарь, А.Ю., Янишевский, Д.А. – К.: Корнейчук, 2000. – C. 152.

  11. Диффи, У. Первые десять лет криптографии с открытым ключом / Диффи У. // ТИИЭР. Т.76 №5. 1988. – С. 54-74.

  12. Баричев, С.Г. Основы современной криптографии / Баричев, С.Г., Гончаров В.В., Серов Р.Е. – М.: Горячая линия – Телеком, 2001. – C. 120.

  13. Герасименко, В.А. Защита информации в вычислительных, информационных и управляющих системах и сетях / Герасименко В.А., Размахнин М.К. // Зарубежная радиоэлектроника. №8. 1985. – С. 41-60.

  14. Тайли, Э. Безопасность персонального компьютера: Пер. с англ. – М.: ООО «Попурри», 1997. – С. 480.

  15. Герасименко, В.А. Защита информации в автоматизированных системах обработки данных. В 2-х кн.: Кн. 2. – М.: Энергоатомиздат, 1994. – С. 176.

  16. Герасименко, В.А. Новые направления применения криптографических методов защиты информации / Герасименко В.А., Скворцов А.А., Харитонов И.Е. // Зарубежная радиоэлектроника. №12. 1989. – С. 92-101.

  17. Нечаев, А. А. Цикловые типы линейных подстановок над конечными коммутативными кольцами // Матем. сб. Т. 184. №3, 1993. – C. 21-56.

  18. Дориченко, С.А., Ященко, В.В. 25 этюдов о шифрах. – М: ТЭИС, 1994. –C. 70.

  19. Молдовян, А.А., Молдовян, Н.А., Советов, Б.Я. Криптография. – СПб.: Изд-во «Лань», 2000. – C. 224.

  20. Бабенко, М. Г. О точках, относящихся к ряду рациональных чисел на эллиптической кривой / Бабенко М. Г. // Инфокомуникационные технологии в науке, производстве и образование: Третья международная научно-техническая конференция. – Ставрополь, 2008. – С. 222-224.

  21. Lercier, R. Computing isogenies in . Algorithmic number theory / Lercier R. // Lecture Notes in Computer Science. v1122. 1996. P. 197-212.

  22. Williams, H. C. A Modification of the RSA Public-Key Encryption Procedure / Williams H. C. // IEEE Transactions on Information Theory. v26 (6). 1980. P. 726-729.

  23. Левин, Л. А. Односторонние функции / Левин Л. А. // Пробл. передачи информ. Т.39. №1, 2003. – С. 103-117.

  24. Koyama, K. New Public-Key Schemes Based on Elliptic Curves over the Ring / Koyama K., Maurer U.M., Okamoto T., Vanstone S.A. // Advances in Cryptology. v91. 1992. Р. 252-266.

  25. Петров, А.А. Компьютерная безопасность. Криптографические методы защиты. – М.: ДМК, 2000. – C. 448.

  26. Rabin, M. O. Digital Signatures and Public-Key Functions as Intractable as Factorization / Rabin M. O. // MIT Laboratory for Computer Science, Technical Report. v212. 1979. P.115-143.

  27. Menezes, A., Oorschot, P., Vanstone, S. Handbook of Applied Cryptography – CRC Press, 1996. – P. 661.

  28. Win, E. D. On the Performance of Signature Schemes based on Elliptic Curves / Win E. D., Mister S., Preneer B., Wiener M. // Springer-Verlang Lecture Notes in Computer Science. v1423. 1998. P. 252-266.

  29. Герасименко, В.А., Малюк, А.А. Основы защиты информации: Учеб. пособие. – М.: МГИФИ, 1997. – C. 537.

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

  31. Бондарь, В.В. Математические модели периодического обновления секретной информации в системах активной безопасности / Бондарь В.В. // Проблемы физико–математических наук: Материалы 46 научно-математической конференции преподавателей и студентов. – Ставрополь, 2001. – С. 36-41.

  32. Жельников, В. Криптография от папируса до компьютера. – М.: АВF, 1997. – C. 336.

  33. Hallgren, S. Linear congruential generators over elliptic curve. / Hallgren S. // Cornegie Mellon Univ. 1994. P. 1-10.

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

  35. Gong, G. Linear recursive sequences over elliptic curves / Gong G., Lam C. // In: Sequences and their applications. 2002. P. 182-196.

  36. Тараканов, В. Е. Линейные рекуррентные последовательности на эллиптических кривых и их применения в криптографии / Тараканов В. Е. // Тр. По диск. Матем. № 10, 2007. – С. 301-313.

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

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

  39. Михелович, Ш.Х. Теория чисел. – М.: Высшая школа, 1962. – C. 260.

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

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

  42. Ростовцев, А. Г., Маховенко, Е. Б. Теоретическая криптография. – СПб.: АНО НПО «Профессионал», 2005. – C. 720.

  43. Романец, Ю.В., Тимофеев, П.А., Шаньгин, В.Ф. Защита информации в компьютерных системах и сетях. – М.: Радио и связь, 1999. – C. 328.

  44. Мафтик, С. Механизмы защиты в сетях ЭВМ: Пер. с англ. – М.: Мир, 1993. – C. 216.

  45. Блейкли, Р.Г. Обобщение идеальные схемы, разделяющие секрет, и матроиды / Блейкли Р.Г., Кабатянский Г.Р. // Проблемы передачи информации. Т33 (3) 1997. С. 102-110.

  46. Червяков, Н.И. Построение системы остаточных классов специального вида / Червяков Н.И., Бабенко М.Г. // 20 лет нового пути России: политика, общество, экономика, международное сотрудничество. Сборник материалов международной научно-практической конференции Дружбы народов Кавказа. – Ставрополь, 2011. – C. 416-418.

  47. Бабенко, М. Г. Анализ методов скалярного умножения на эллиптической кривой / Бабенко М. Г. // Молодой ученый. №4. 2010. С. 24-29.

  48. Коблиц, Н. Курс теории чисел и криптографии. – М.:ТВП, 2001. – С. 254.

  49. Лёвин, В. Ю. Кодирование алфавитов точками эллиптических кривых. / Лёвин В. Ю. // Интеллектуальные системы. № 11. 2007. C. 171-183.

  50. Recommended elliptic curves for federal government use. // Электроные. данные С. 43. http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf (20.10.2011).

  51. Чмора, Д. Л. Современная прикладная криптография. – М.: Гелиос АРВ, 2001. – C. 256.

  52. Blake, I.F., Seroussi G., Smart N.P. Elliptic curves in cryptography. – С.: Cambridge Univ. Press, 1999. – P. 298.

  53. Blakley, G. R. Safeguarding cryptographic keys / Blakley G. R. // Proc. AFIPS 1979 National Computer Conference. v48. 1979. P. 313-317.

  54. Shamir, A. How to Share a Secret / Shamir A. // Comm. ACM. v22 (1). 1979 P. 612-613.

  55. Червяков, Н. И. Пороговая схема разделения секрета на эллиптической кривой / Червяков Н. И., Бабенко М. Г. // Информационные технологии. №2. 2011. С. 41-44.

  56. Lee, H.S. A self-pairing map and its applications to cryptography / Lee H.S. // Applied Mathematics and Computation. v151. 2004. P. 671–678.

  57. Василенко, О.Н. Теоретико-числовые алгоритмы в криптографии. – М.: МЦНМО, 2003. – C. 326.

  58. Elkies, N.D. Elliptic and modular curves over finite fields and related computaional issues / Elkies N.D. // Computational perspectives in number theory. v7. 1998. P. 21-76.

  59. Atkin, A.O.L., Morain, F. Elliptic curves and primality proving / Atkin A.O.L., Morain F. // Math Comp. v61 (203). 1993. P. 29-68.

  60. Болотов, А.А, Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. – М.:КомКнига, 2006. – C. 280.






<< предыдущая страница