zinet home
home home
home ИНТЕЛЛЕКТ-ПОРТАЛ
home Стартовал прием материалов в сборник XХХIX-й научной конференции. Требования к публикациям - в разделе "Объявления".

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

РЕСУРСЫ ПОРТАЛА:

Тридцать восьмая научно-практическая конференция
(23 - 28 мая 2016 г.)


Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)


Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)


Тридцать пятая научно-практическая конференция
(24-27 ноября 2015 г.)


Тридцать четвертая научно-практическая конференция
(13-17 октября 2015 г.)


Тридцать третья научно-практическая конференция
(20-27 мая 2015 г.)


Тридцать вторая научно-практическая конференция
(2-7 апреля 2015 г.)


Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)


Тридцатая научно-практическая конференция
(19-25 января 2015 г.)


Двадцать девятая международная научно-практическая конференция
(19-25 ноября 2014 г.)


Двадцать восьмая международная научно-практическая конференция
(08-13 октября 2014 г.)


Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)


Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)


Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)


Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)


Двадцать третья научно-практическая конференция
(10-15 декабя 2013 г.)


Двадцать вторая научно-практическая конференция
(4-9 ноябя 2013 г.)


Первая международная научно-практическая конференция
(14-18 мая 2013 г.)


Двадцать первая научно-практическая конференция
(14-18 мая 2013 г.)


Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)


Девятнадцатая научно-практическая конференция
(26 февряля - 3 марта 2013 г.)


Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)


Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)


Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)


Пятнадцатая научно-практическая конференция
(01 - 07 марта 2012 г.)


Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)


Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)


Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)


Одинадцатая научно-практическая конференция
(26 апреля - 04 мая 2011 г.)


Десятая научно-практическая конференция
(15-23 марта 2011 г.)


Девятая научно-практическая конференция
(27-31 декабря 2010 г.)


Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)


Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)


Шестая научно-практическая конференция
(1-15 апреля 2010 г.)


Пятая научно-практическая конференция
(20-27 мая 2009 г.)


Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)


Третья научно-практическая конференция
(20-27 декабря 2008 г.)


Вторая научно-практическая конференция
(1-7 ноября 2008 г.)


Первая научно-практическая конференция
(10-15 мая 2008 г.)



НАШИ ПАРТНЕРЫ:

Студия веб-дизайна www.zinet.info



Студия ландшафтного дизайна Флора-МК


Уникальное предложение!



Сайт-визитка - теперь
всего за 200 грн!

подробнее>>>



КРИВЫЕ ЭДВАРДСА НАД ПРОСТЫМИ ПОЛЯМИ С ПОЧТИ ПРОСТЫМ ЗНАЧЕНИЕМ ПОРЯДКА

 

Бессалов А.В.

Украина, г. Киев, НТУУ «КПИ»

Дихтенко А.А.

Украина, г. Донецк, ДонНУ

 

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

 

Введение. Криптосистемы на эллиптических кривых успешно применяются в современных стандартах и протоколах шифрования. Среди всевозможных форм представления эллиптических кривых, особый интерес вызывает кривая в форме Эдвардса [1, 2]. Она имеет ряд замечательных свойств. Полнота и универсальность закона сложения точек кривой и замена точки на бесконечности точкой в аффинных координатах делает кривые Эдвардса привлекательными с точки зрения практической реализации. Но наиболее важное их преимущество – рекордная скорость выполнения групповой операции по сравнению с прочими формами представления эллиптических кривых [2, 4].

Поскольку кривые Эдвардса не стандартизованы, необходимо осуществить поиск таких кривых, приемлемых для криптографии. Этот процесс, в свою очередь, подразумевает определение порядка кривой, заданной над конечным полем. Аналогичная задача поставлена нами в работе [6] для случая расширенных полей малых характеристик. В [6, 7] приведены кривые приемлемого порядка над расширениями полей F5 и F7. В данной работе мы ставим задачу нахождения кривых в форме Эдвардса с почти простым значением порядка над простыми полями. Далее мы приводим общие сведения о кривых в форме Эдвардса над конечным полем, рассматриваем проблему определения порядка кривой в форме Эдвардса и кратко описываем возможные пути ее решения. При реализации описанного подхода нами было найдено 40 кривых Эдвардса над простыми полями Fр с модулями р длиной 192, 224, 256 и 384 бит[8]. Порядок 4n полученных кривых содержит простой сомножитель n, сравнимый по величине с величиной соответствующего поля. Таким образом, кривые удовлетворяют современным требованиям к порядку генератора криптосистемы и могут применяться на практике.

 

1. Кривые в форме Эдвардса. Закон сложения точек кривой.

Пусть k – конечное поле . Кривая в форме Эдвардса над полем k задается уравнением в аффинных координатах[1-6]:

E:                                                                   (1)

Ограничение на параметр кривой  в поле k гарантирует полноту закона сложения (2), которым определяется сумма двух точек с координатами , :

,                                         (2)

В этом случае знаменатели  и  при k. [2] и закон (2) корректен для произвольных точек , , включая совпадающие, обратные точки и О = (0,1) – нейтральный элемент группы.

Заметим, что кривая (1) содержит как минимум четыре точки: О =  нуль аддитивной группы точек, D =  – единственную точку 2-го порядка, и Р =  – пару точек 4-го порядка. Отсюда следует, что порядок любой кривой в форме Эдвардса кратен четырем.

В работе [2] доказано, что для любой кривой, вида (1), найдется изоморфная эллиптическая кривая в канонической форме. Поскольку, в известных стандартах шифрования на эллиптических кривых [8] не содержится кривых над простыми полями с порядком, кратным 4, не представляется возможным преобразовать уже используемые кривые непосредственно в форму (1). В этой связи следует провести поиск кривых Эдвардса над простыми полями с приемлемым значением порядка 4n.

 

2. Изоморфизм между кривой в форме Эдвардса и канонической кривой.

Для каждой кривой (1) в форме Эдвардса E найдется изоморфная ей кривая над полем k в форме Вейерштрасса вида

W:                                                                       (3)

Изоморфизм между точками кривых E и W задается правилами [3]:

,   ,           при .                 (4)

Четыре точки пересечения с осями координат преобразуются следующим образом

,

                 при .                              (5)

       при y

Коэффициенты кривой W выражаются через параметр кривой E как [3]:

,       .                                            (6)

Логично утверждать, что определенная таким образом эллиптическая кривая будет содержать единственную точку 2-го порядка, поэтому кубик в правой части (3) должен иметь ровно один корень над полем k. Посредством изоморфного перехода (4)-(5) получим эллиптическую кривую с порядком, который также кратен четырем. Для обратного преобразования справедливо:

,       ,               при ,

,       при ,                              (7)

.

Один из способов расчета порядка кривой Эдвардса это адаптация известных алгоритмов кривых (таких как алгоритмы Скуфа, SEA, Satoh) для случая кривых Эдвардса. Для этого необходимо определить последовательность полиномов деления для кривых Эдвардса [3], посредством которых далее может быть вычислен порядок рассматриваемой кривой. С другой стороны, подсчитать порядок кривой Эдвардса можно с помощью изоморфного перехода к канонической форме с последующим нахождением порядка кривой по известным алгоритмам.

 

3. Расчет порядка кривой в форме Эдвардса. Определение генератора криптосистемы.

Используя формулы изоморфного преобразования нами был проделан поиска кривых Эдвардса над простыми полями различной битовой длины cмодулями рекомендуемыми в стандарте FIPS – 186 – 2 – 2000 [8]:

,                                  ,

,           .

Выбрав произвольно параметр  в поле k и, используя формулы (6), получим изоморфную эллиптическую кривую W с отрицательным дискриминантом. Подсчитать ее порядок можно, например, по алгоритму SEA. Порядок рассматриваемой кривой 4n считаем приемлемым, если число n простое, лежащее приблизительно в пределах 180 – 600бит. Такая кривая может быть рекомендована к применению в криптопротоколах.

Для построения криптографической системы на полученной кривой Эдвардса необходимо определить генерирующую точку порядка . Задавая произвольно координату x и вычисляя из уравнения (1) значение y получим произвольную точку Q кривой Эдвардса. Если  и , порядок точки Q может быть равен ,  или . Тогда генератором криптосистемы будет точка Q, 2Q или 4Q соответственно. Ниже в таблице 1 приведены примеры полученных нами результатов.

 

Таблица 1. Кривые Эдвардса почти простого порядка над полемFр с модулем

, , ,  соответственно.

 

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF

28453E

4000000000000000000000001AEAD1229D137F564D7FF6D5

AE709D07B2D112CECD4A7AE103757F2C101D054ACB1A0F17

8BDF8D5A994AAB1E1455889D28E29CA3EC68548D3F7CA32F

 

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001

3608425

400000000000000000000000000020BBEC47CEDB34DD05BCB6B7E619

C448CA02660F57204FF1BDE2B5CC3E25606A7460399FEA3DA9A06383

319117770D6FC7FE35F6A02905FE1F363156BD2E5B75BB89A64CAFAB

 

 

FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFF

FFFFF

72A38

3FFFFFFFC00000003FFFFFFFFFFFFFFFBA76FA29C30CC3AA4954B53E

DBE54D75

894F8283626AEE6848515DDDC3B8DBB3D5302DEE0EE75080D6753E4D

39BA5AB2

EA612346223F6480CBBAFA39DB95D54D21469DD3074A957EFDA4FD79

FEB630B5

 

 

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

FFFFFFEFFFFFFFF0000000000000000FFFFFFFF

12593A

4000000000000000000000000000000000000000000000005063576B5A9A0C

3A23E9510EA680650B4884E63A2968DD71

1FC0E8E61F599813E376D11F7510D77F177C2F1CDE19FD14D63A2EC5E

AD4D0DED1BD06676CCF365243BF3C0675A31B62

F52B4FA352B257D7A102FA45C56A50CCBDB3DEC053D5610EDBD0188C

11F321F28A43E2FC50395E4A8BD0029AE71D51AA

 

Заключение. В результате проделанной работы было получено по 10 кривых Эдвардса с параметрами  различной битовой длины над простыми полями с модулями , , , . Расчеты производились посредством прикладных программ, основанных на использовании функций библиотеки MIRACL. Порядок найденных кривых имеет минимально возможный кофактор равный 4 и простой кофактор, сравнимый по длине с длиной соответствующего поля. Это делает возможным применение полученных кривых в практических приложениях. Благодаря выигрышу в быстродействии (в среднем в 1.5 раза [4]) и удобству программирования криптосистем кривые Эдвардса могут стать эффективной альтернативой каноническим эллиптическим кривым.

 

Список источников и литературы

1.      Edwards H.M. A normal form for elliptic curves. Bulletin of the American Mathematical Society, Volume 44, Number 3, July 2007, Pages 393-422.

2.      Bernstein Daniel J., Lange Tanja. Faster addition and doubling on elliptic curves. IST Programmeunder Contract IST–2002–507932 ECRYPT, 2007, PP. 1-20.

3.      Moloney R., McGuire G. Twokinds of division polynomials for twisted Edwards curves. Applicable Algebrain Engineering, Communication and Computing, 2011, PP. 321-345.

4.      Бессалов А.В., Дихтенко А.A., Третьяков Д.Б. Сравнительная оценка быстродействия канонических эллиптических кривых и кривых в форме Эдвардса над конечным полем. Сучасний захист інформації, №4, 2011. С.33-36.

5.      Бессалов А.В. Число изоморфизмов и пар кручения кривых Эдвардса над простым полем. Радиотехника, вып. 167, 2011. С. 203-208.

6.      Бессалов А.В., Гурьянов А.И., Дихтенко А.А. Кривые Эдвардса почти простого порядка над расширениями малых простых полей. Прикладная радиоэлектроника, том 11, №2, 2012. С. 225-227.

7.      Бессалов А.В., Дихтенко А.А., Яценко А.И. Параметрыкриптосистемы на кривой Эдвардса над расширениями малых простых полей. Прикладная радиоэлектроника, статья принята к публикации.

8.      Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых: Учеб.пособие. – К.: ІВЦ «Політехніка», 2004. – 224с.



Первая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(10-15 мая 2008 г.)


(отчет)
Вторая научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(1-7 ноября 2008 г.)
(отчет)
Третья научно-практическая конференция
"Инновационный потенциал украинской науки - ХХI век"
(20-27 декабря 2008 г.)
(отчет)
Четвертая научно-практическая конференция
(10-17 апреля 2009 г.)
(отчет)
Пятая научно-практическая конференция
(20-27 мая 2009 г.)
(отчет)
Шестая научно-практическая конференция
(1-15 апреля 2010 г.)
(отчет)
Седьмая научно-практическая конференция
(28 мая - 7 июня 2010 г.)
(отчет)
Восьмая научно-практическая конференция
(05-12 декабря 2010 г.)
(отчет)
Девятая научно-практическая конференция
(27-31 декабря 2010 г.)
(отчет)
Десятая научно-практическая конференция
(15-23 марта 2011 г.)
(отчет)
Одинадцатая научно-практическая конференция
(26 апреля 04 мая 2011 г.)
(отчет)
Двенадцатая научно-практическая конференция
(28 мая - 06 июня 2011 г.)
(отчет)
Тринадцатая научно-практическая конференция
(28 октября - 09 ноября 2011 г.)
(отчет)
Четырнадцатая научно-практическая конференция
(12-20 декабря 2011 г.)
(отчет)
Пятнадцатая научно-практическая конференция
(01-07 марта 2012 г.)
(отчет)
Шестнадцатая научно-практическая конференция
(09-14 апреля 2012 г.)
(отчет)
Семнадцатая научно-практическая конференция
(22-26 октября 2012 г.)
(отчет)
Восемнадцатая научно-практическая конференция
(22-26 декабря 2012 г.)
(отчет)
Девятнадцатая научно-практическая конференция
(26 февраля - 3 марта 2013 г.)
(отчет)
Двадцатая научно-практическая конференция
(20-28 апреля 2013 г.)
(отчет)
Двадцать первая научно-практическая конференция
(13-18 мая 2013 г.)
(отчет)
Первая международная научно-практическая конференция
"Перспективные направления отечественной науки - ХХI век"
(13-18 мая 2013 г.)
(отчет)
Двадцать вторая научно-практическая конференция
(4-9 ноября 2013 г.)
(отчет)
Двадцать третья научно-практическая конференция
(10-15 декабря 2013 г.)
(отчет)
Двадцать четвертая научно-практическая конференция
(20-25 января 2014 г.)
(отчет)
Двадцать пятая юбилейная научно-практическая конференция
(3-7 марта 2014 г.)
(отчет)
Двадцать шестая научно-практическая конференция
(7-11 апреля 2014 г.)
(отчет)
Двадцать седьмая научно-практическая конференция
(20-25 мая 2014 г.)
(отчет)
Двадцать восьмая научно-практическая конференция
(08-13 октября 2014 г.)
(отчет)
Двадцать девятая научно-практическая конференция"
(19-25 ноября 2014 г.)
(отчет)
Тридцатая научно-практическая конференция
(19-25 января 2015 г.)
(отчет)
Тридцать первая научно-практическая конференция
(25 февраля - 1 марта 2015 г.)
(отчет)
Тридцать вторая научно-практическая конференция
(2 - 7 апреля 2015 г.)
(отчет)
Тридцать третья научно-практическая конференция
(20 - 27 мая 2015 г.)
(отчет)
Тридцать четвертая научно-практическая конференция
(13 - 17 октября 2015 г.)
(отчет)
Тридцать пятая научно-практическая конференция
(24 - 27 ноября 2015 г.)
(отчет)
Тридцать шестая научно-практическая конференция
(29 декабря 2015 - 5 января 2016 г.)
(отчет)
Тридцать седьмая научно-практическая конференция
(19 - 22 апреля 2016 г.)
(отчет)
Тридцать восьмая научно-практическая конференция
(23 - 25 мая 2016 г.)
(отчет)

На главную | Объявления | Отчеты предыдущих конференций | История Украины | Контакты

Copyright © Zinet.info. Разработка и поддержка сайта - Студия веб-дизайна Zinet.info