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

Анотація

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