Нові алгоритми знаходження базової точки на еліптичних кривих у формі Едвардса

Abstract

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

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

Transformations on elliptic curves which are used in the national digital signature standard DSTU 4145 2002, satisfy modern requirements. However, the fast development of computer technologies and a significant interest in cryptology worldwide have led to an increase in research, the constant emergence of new powerful cryptanalysis methods and, as a consequence, to the possible shortening of the lifetime of existing and new algorithms. This article addresses the current scientific and practical problem of investigating the properties of elliptic curves in the Edwards form over a finite field , p ≠ 2, suitable for use in asymmetric cryptosystem, in particular, digital signature algorithms. Based on the research completed, new ways of determination of a base point on Edwards curves were outlined and described. Three new algorithms were proposed for determination of the base point for constructing a cryptosystem on the full and twisted Edwards curves. In this work the comparative analysis of the performance of the developed algorithms of the Edwards curves base point determination and the performance of crypto-algorithms on the non-perpendicular elliptic curves in the Weierstrass form over the fields of characteristic 2 was carried out. The analysis shows that proposed algorithms are faster than the standard Weirstrass digital signature curve algorithm – respectively, the first algorithm – 180 times, the second– times, and the third algorithm– ( times. It is proved that the use of elliptic curves in the form of Edwards over finite field , instead of Weierstrass curves, can increase the speed of operations of adding points in asymmetric cryptosystems. The results of the work can be applied to the analysis of existing problems and creation of new algorithms and standards of asymmetric cryptography.