APPROACH TO CHECKING THE SUPERSINGULARITY OF ELLIPTIC CURVES AND CALCULATING THEIR ORDER
DOI:
https://doi.org/10.32689/maup.it.2021.1.7Keywords:
finite field, elliptic curve, Edwards curve, curve order, quadratic excess, Legendre symbol, algebraic curve, group of elliptic curve points, point order, torsion curvesAbstract
Most cryptosystems in modern cryptography can naturally be “translated” into elliptical curves. We consider
algebraic Edwards curves over a finite field, which are currently one of the most promising carriers of sets of points used for
fast group operations [1; 2; 14], which are available in asymmetric cryptosystems, in particular for the construction of random
cryptocurrency sequences.
It is shown that the projective curve Ea d, is not elliptical. The aim of this work is to find a criterion and sufficient conditions
for the supersingularity of the Edwards curve p and an elliptic curve in the form of Montgomery over a simple field and
then generalize this criterion for a finite algebraic extension of this field to Fpn . The obtained result allows us to construct all
supersingular curves of Edwards and Montgomery without factorizing the polynomial from which the curve is present in the
record.
In [10], the proof of the supersingularity of a curve Ed was presented only for the coefficients d 2, d 21 over p , and
our goal is to study all the coefficients at which this curve is supersingular. In our work we found the criteria and sufficient
conditions for the supersingularity of the Edwards curve and the elliptic curve in the form of Montgomery over the field Fpn , ie we investigated at what coefficients a pair of curves with a Frobenius trace equal to 0. The Montgomery curves over the field
of characteristic 2 have zero j-invariant. Not only a specific set of coefficients with the corresponding characteristics of the
fields at which these curves are supersingular is found, but also a general formula by which it is possible to determine whether
the curve is supersingular over a given field or not. The paper summarizes the result on the supersingularity of the curve over
p obtained in [10] for the coefficients d 2, d 21 in the case of arbitrary expansion of a simple field pn and clarifies the
formulation of Theorem 3 from [10]. A similar study was performed for elliptic curves in the form of Montgomery.
References
Edwards H. A normal form for elliptic curves. American Mathematical Society. 2007. Vol. 44. No. 3. P. 393–422.
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, Christiane Peters. Twisted Edwards Curves. IST Programme ECRYPT, and in part by grant ITR-071649. 2008. Р. 1–17.
Menezes A., Okamoto T., Vanstone S. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Transactions On Information Theory. 1993. Vol. 39. No. 5. P. 1603–1646.
Алексеев Е., Ошкин И., Попов В., Смышляев С., Сонина Л. О перспективах использования скрученных эллиптических кривых Эдвардса со стандартом ГОСТ Р 34.10-2012 и алгоритмом ключевого обмена на его основе. Материалы XVI международной конференции «РусКрипто 2014». 2014. С. 24–26.
Hallgren S. Linear congruential generators over elliptic curves. Preprint CS-94-143, Dept. Of Comp. Sci., CornegieMellon Univ. 1994. P. 1–10.
Виноградов И. Основы теории чисел: Учебное пособие. 12-е изд. СПб. : Издательство «Лань», 2009. 271 с.
Белецкий А.Я., Белецкий А.А. Симметричный блочный криптоалгоритм. Захист інформації. 2006. № 2 (29). С. 42–51.
Скуратовський Р., Мовчан П. В., Нормалiзацiя скрученої кривої Едвардса та дослiдження її властивостей над Fp. Збiрник праць 14 Всеукраїнської науково-практичної конференцiї. ФТI НТУУ «КПI». 2016. Том 2. С. 102–104.
Скуратовський Р. Дослiдження властивостей скрученої кривої Едвардса. Конференцiя державної служби спецiального зв’язку та захисту iнформацiї. URL: http://www.dstszi.gov.ua/dstszi/control/uk/publish/article?showHidden=1artid=252312catid=240232 ctime=1464080781894
Бессалов А., Цыганкова О. Взаимосвязь семейства точек больших порядков кривой Эдвардса над простым поле. Захист інформації. 2015. Т. 17. № 1. С. 73–80.
Skuratovskii R. V. Twisted Edwards curve and its group of points over finite field Fp. Лiтня школа «Алгебра, Топологiя, Аналiз». Одеса, 2016. С. 122–124.
Skuratovskii R., Skruncovich U. Twisted Edwards curve and its group of points over finite field Fp. Akademgorodok, Novosibirsk, Russia. Conference. Graphs and Groups, Spectra and Symmetries. URL: http://math.nsc.ru/conference/g2/g2s2/exptext/SkruncovichSkuratovskii-abstract-G2S2.pdf
Рид M. Алгебраическая геометрия для всех. Москва : Мир, 1991. 143 с.
Hisil Huseyin, Koon-Ho Wong Kenneth, Carter Gary. Twisted Edwards Curves Revisited. ASIACRYPT LNCS 5350. 2008. P. 326–343.
Степанов С. Арифметика алгебраических кривых. М. : Наука, 1991. 368 с.
Koblitz N. Eliptic Curve Cryptosystems. Mathematics of Computation. 1987. Vol. 48. No. 177. P. 203–209.
Сергієнко І., Задірака В., Литвин О. Елементи загальної теорії оптимальних алгоритмів та суміжні питання. К. : Наук. думка, 2012. 400 с.
Рибак О. Розкладність рядків та звідність многочленів. У світі математики. 2006. № 12(4). C. 18–29.
Скуратовский Р. Метод быстрого таймерного кодирования текстов. Кибернетика и системный анализ. 2013. Т. 49. № 1. С. 154–160.
Долгов В. Эллиптические кривые в криптографии. Системи обробки інформації. 2008. Вип. 6 (73). С. 3–10.
Болотов С. Б., Гашков А. Б., Фролов А. А. Часовских Элементарное введение в эллиптическую криптографию М. : КомКника, 2006. Том 2. 328 с.
