НОВІ АЛГОРИТМИ ЗНАХОДЖЕННЯ БАЗОВОЇ ТОЧКИ НА ЕЛІПТИЧНИХ КРИВИХ У ФОРМІ ЕДВАРДСА

  • Оксана Валентинівна Циганкова Національний технічний університет України «КПІ ім. Ігоря Сікорського», Фізико-технічний інститут
Ключові слова: скручені криві Едвардса, повні криві Едвардса, порядок кривої, порядок точки, базова точка, квадратичний лишок, квадратичний нелишок, алгоритм цифрового підпису, криві Вейєрштрасса, швидкодія

Анотація

Перетворення еліптичних кривих, що використовують у національному стандарті цифрового підпису ДСТУ 4145 2002, відповідають сучасним вимогам. Однак, бурхливий розвиток обчислювальної техніки та значне підвищення інтересу до криптології в усьому світі, залучення величезної кількості спеціалістів, у тому числі математиків, до роботи у даній галузі, призвели до зростання об’єму досліджень, постійного виникнення нових, все більш потужних методів  криптоаналізу  і, як наслідок, до можливого зменшення терміну життя існуючих та нових алгоритмів. У данійстатті розв’язано актуальну науково-практичну задачу дослідження властивостей еліптичних кривих у формі Едвардса над простим полем , придатних для використання в алгоритмах асиметричних криптосистем, зокрема, в алгоритмах цифрового підпису (ЦП). На підставі проведених досліджень було знайдено та описано нові способи знаходження базової точки на кривих у формі Едвардса. З застосуванням цих методів запропоновано три нових алгоритми визначення базової точки для побудови криптосистеми на повних та скручених кривих у формі Едвардса. Також у статті проведено порівняльний аналіз швидкодії розроблених алгоритмів знаходження базової точки для побудови криптосистеми на кривих у формі Едвардса та швидкодії криптоалгоритмів на несуперсингулярних еліптичних кривих у формі Вейєрштрасса над полями характеристики 2, перетворення яких використовуються в криптоалгоритмах ЦП ДСТУ 4145 2002. За результатами проведеного аналізу встановлено, що швидкодія трьох запропонованих алгоритмів вища, від стандартного алгоритму цифрового підпису на кривих у формі Вейєрштрасса, для першого алгоритму у 180 раз, другого - у 16log (n) (де  раз та третього алгоритму у 32log (n) (де   раз відповідно. На підставі проведених досліджень, у статті доведено, що використання  еліптичних кривих у формі Едвардса над простими полями, замість кривих Вейєрштрасса, дозволяють підвищити швидкість експоненціювання точки в асиметричних криптосистемах.  Результати роботи можуть бути використані в задачах аналізу існуючих та при розробці нових алгоритмів і стандартів асиметричної криптографії.

Біографія автора

Оксана Валентинівна Циганкова, Національний технічний університет України «КПІ ім. Ігоря Сікорського», Фізико-технічний інститут

асистент кафедри математичних методів захисту інформації Фізико-технічного інституту КПІ ім. Ігоря Сікорського

Посилання

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

Бессалов А.В., Цыганкова О.В. Производительность групповых операций на скрученной кривой Эдвардса над простым полем. // Радиотехника №181, 2015. С.58-63.

Бессалов А.В., Цыганкова О.В. Классификация кривих в форме Эдвардса над простым полем. // Прикладная радиоелектроника, Том 14 № 3, 2015. С.197-203.

Bessalov A.V.,Tsygankova O.V. New properties of the Edwards form elliptic curveover a primefield // Telecommunications and Radio Engineering (English translation of Elektrosvyaz and Radiotekhnika) №180 2015. рр.137-143.

Bessalov A. V., Tsygankova O.V. Interrelation of families of points of highorderon the Edwards curve over a primefield // English translation of Problems of Informati on Transmission, 2015, Vol. 51, № 4, pp. 391-397. sci-hub.tw/10.1134/S0032946015040080

Бессалов А.В., Цыганкова О.В. Метод определения точек максимального порядка на кривой Эд-вардса. // Спеціальні телекомунікаційні системи та захист інформації. Збірник наукових праць, випуск 2(26), 2014. С.18-21.

Bernstein Daniel J.,Birkner Peter, JoyeMarc, Lange Tanja, Peters Christiane. Twisted Edwards Curves.//IST Programme under Contract IST–2002–507932 ECRYPT, and in part by the National Science Foundation under grant ITR–0716498, 2008, РР. 1-17.

Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография: монографія //изд-во «Политехника», КПИ им. Игоря Сикорского, Киев. 2017. – 272с.

Опубліковано
2020-05-23
Як цитувати
[1]
О. Циганкова, НОВІ АЛГОРИТМИ ЗНАХОДЖЕННЯ БАЗОВОЇ ТОЧКИ НА ЕЛІПТИЧНИХ КРИВИХ У ФОРМІ ЕДВАРДСА, ІТКІ, vol 47, № 1, с. 39-47, Трав 2020.
Розділ
Математичне моделювання та обчислювальні методи