DOI: https://doi.org/10.18524/2519-206x.2018.1(31).134622

Суперсингулярність еліптичних кривих і кривих Едвардса над $F_{p^n}$

Р. В. Скуратовський

Анотація


Ми розглядаємо алгебраїчні криві у формі Едвардса і еліптичні криві Монтгомері над скінченим полем $F_ p^n $, які на даний час є одним з найбільш швидких і перспективиих носіїв груп, що на даний час мають багато застосувань. В роботi знайдено умови суперсингулярностi кривих Едвардса і великого класу скручених кривих Едвардса над полем $F_ p^n $ характреистики $p \equiv 3 mod 4$. Показано, що проективна крива Едвардса не є елiптичною. Досліджено деякі цікаві властивості групи точок цих кривих. Побудовано криві заданого порядку з мінімальним кофактором. Підраховано род скрученої кривої Едвардса. Знайдено умови мінімальності кофактора скрученої кривої Едвардса та її род.

Ключові слова


суперсингулярні криві; скінчене поле; еліптична криптографія; крива Едвардса; еліптичні криві з малою степінню занурення в поле

Повний текст:

PDF

Посилання


Samko, S. G., Kilbas, A. A. Marichev, O. I. (1987). Integraly i proizvodnye drobnoho poryadka i nekotorye ih prilozheniya [Fractional integrals and derivatives with some applications]. Minsk: Nauka i tekhnika, 688 p.

Arestov, V. V. (1981). Ob integralnykh neravenstvakh dlya trigonometricheskikh polinomov i ikh proizvodnykh [About integral inequalities for trigonometrical polynomials and theirs derivatives]. Izv. AN USSR. Ser. matem., Vol. 45, P. 3-22.

Fikhtengolz, G. M. (2001). Kurs differentsialnogo i integralnogo ischisleniya [A Course of Differential and Integral Calculus], Vol. II. Moscow: Fizmatlit, 810 p.

Gradshtein, I. S. Ryzhyk, I. M. (1963). Tablitsy sntegralov, sum i proizvedeniy [Tables of integrals, sums and derivatives]. Moscow: GITTL, 1100 p.

Storozhenko, E. A. (1996). {K odnoi zadache Malera o nulyakh polinoma i ego proizvodnoy [For one Mahler's prooblem about zeros of polinomial and its derivative]. Matem. sbornik, Vol. 187, №5, P. 111-120.

Edwards, H. (2007). A normal form for elliptic curves. American Mathematical Society, Vol. 44, No. 3, July - pp. 393-422.

Bernstein, D. J., Birkner, P., Joye, M., Lange, T. Peters, Ch. Twisted Edwards Curves. IST Programme ECRYPT, and in part by grant ITR-0716498, 2008. РР. 1-17.

Drozd, Yu. A. Vstup do alhebrayichnoyi heometriyi - L.: Vntl-Klasyka. 2004. - 251 p.

Shafarevych, Yu. A. Osnovy alhebraycheskoy heometryy - M.: Nauka, T.1, 1969. - 184~p.

Bernstein, D. J., Lange Tanja. Faster addition and doubling on elliptic curves. IST Programme Contract 2002-507932 ECRYPT, - 2007. - pp. 1-20.

Hisil Huseyin, Koon-Ho Wong Kenneth, Carter Gary. Twisted Edwards Curves Revisited. ASIACRYPT LNCS 5350 - 2008. - pp. 326-343.

Fulton, W. Algebraic curves. An Introduction to Algebraic Geometry - Third Preface - January, 2008. - 121 P.

Rid M. Algebraicheskaya geometriya dlya vsekh. Moskva: Mir, 1991, 143 p.

Bolotov, A. A., Gashkov, S. B., Frolov, A. B. Chasovskikh, A. A. Elementarnoye vvedeniye v ellipticheskuyu kriptografiyu - M.: KomKnika. Tom 2., 2006. - 328 s.

Koblitz, N. [Eliptic Curve Cryptosystems] // Mathematics of Computation. - 1987. - V. 48, № 177. - Р. 203-209.

Menezes, A. J., Okamoto, T. Vanstone, S. A. [Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field]. IEEE Transactions On Information Theory. - 1993. - Vol. 39, No. 5, September. pp. 1603-1646.

Alekseyev, Ye. K., Oshkin, I. B., Popov, V. O., Smyshlyayev, S. V. Sonina, L. A. O perspektivakh ispol'zovaniya skruchennykh ellipticheskikh krivykh Edvardsa so standartom GOST R 34.10-2012 i algoritmom klyuchevogo obmena na yego osnove Conference RusCrypto 2014. pp. 75-79.

Bessalov, A. V. Tsygankova, O. B. Vzaimosvyaz' semeystva tochek bol'shikh poryadkov krivoy Edvardsa nad prostym polem. Zakhist informatsii. 2015. - T. 17, № 1. - pp. 73-80.

Vinogradov, I. M. Osnovy teorii chisel: Uchebnoye posobiye. 12-ye izd. - SPb.: Izdatel'stvo "Lan'", 2009. 271 p.

Stepanov, S. Arifmetika algebraicheskikh krivykh. M.: Nauka., 1991g., 368 p.

Gupta, R., Murty, M. R. Primitive points on elliptic curves. Compos. Math.58, (1986) P. 13–44.

Montgomery, P. L., Speeding the Pollard and Elliptic Curve Methods of Factorizations, Math. Comp. 48, (1987), pp. 243-264.

Skuratovskii, R. Doslidzhennya vlastyvostey skruchenoyi kryvoyi Edvardsa. Konferentsiya derzhavnoyi sluzhby spetsial?noho zvyazku ta zakhystu informatsiyi. http://www.dstszi.gov.ua/dstszi/control/uk/publish/article?showHidden=1art id=252312 cat id=240232 ctime=1464080781894

Skuratovskii, R.~V. Twisted Edwards curve and its group of points over finite field $F_p$. XI Letnia shkola "Algebra, Topoloia, Analys " Odessa. (2016), PP. 122-124.

Skuratovskyy, R. V., Osadchyy,E. O. Kvashuk, D. M. Delenye tochky skruchennoy kryvoy Edvardsa na dva y ee prymenenye v kryptohrafyy. Visnyk natsional?noho tekhnichnoho universytetu "KHPI", №44, st. 90-96.

Skuratovskyy, R. V., Osadchyy,E. O. Kvashuk, D. M. Delenye tochky skruchennoy kryvoy ?dvardsa na dva y ee prymenenye v kryptohrafyy. Visnyk natsionalnoho tekhnichnoho universytetu "KHPI", №44, st. 90-96.

Skuratovskii, R. V. Skruncovich, U.~V. Twisted Edwards curve and its group of points over finite field $F_p$. Akademgorodok, Novosibirsk, Russia. Conference. Graphs and Groups, Spectra and Symmetries. http://math.nsc.ru/conference/g2/g2s2/exptext/SkruncovichSkuratovskii-abstract-G2S2.pdf

Skuratovskii, R. V. Movchan P. Normalizacia skruchennoi krivoi Edwardsa i doslidgennia yy vlastuvostei nad $F_p$. Zbirnuk prac 14 naukovo praktichoy conferencii FTI NRUU "KPI" 2016, Tom 2, p. 102-104.

Skuratovskii, R. V. Constructing of finite field normal basis in deterministic polynomial time(in ukraine). Bulletin of Kiev national university of Tarasa Shevchenka. 2011, P. 49-54.

Paul, S., Barreto, L. M. Naehrig M. Pairing-Friendly Elliptic Curves of Prime Order. International Workshop on Selected Areas in Cryptography SAC, 2005, pp. 319-331.


Пристатейна бібліографія ГОСТ


Edwards H. A normal form for elliptic curves // American Mathematical Society. - 2007. - Vol. 44, No. 3, July - pp. 393-422.

Bernstein D. J.,  Birkner P., Joye M., Lange T., Peters Ch. Twisted Edwards Curves // IST Programme ECRYPT, and in part by grant ITR-0716498, 2008. - pp. 1-17.

Дрозд Ю. А.  Вступ до алгебраїчної геометрії. - Л.: Внтл-Класика. 2004. - 251 c.

Шафаревич Ю. А. Основы алгебраической геометрии. - М.: Наука, 1969. - Т. 1. - 184 с.

Bernstein D. J., Lange T. Faster addition and doubling on elliptic curves // IST Programme Contract 2002-507932 ECRYPT. - 2007. - pp. 1-20.

Hisil H., Koon-Ho Wong Kenneth, Carter G. Twisted Edwards Curves Revisited // ASIACRYPT LNCS 5350. - 2008. - pp. 326-343.

Fulton W. Algebraic curves. An Introduction to Algebraic Geometry. - Third Preface - January, 2008. -  121 P.

Рид M.  Алгебраическая геометрия для всех. Москва: Мир, 1991, 143 с.

Болотов A. А., Гашков С. Б.,  Фролов А. Б., Часовских А. А. Элементарное введение в эллиптическую криптографию. - М.: КомКника, 2006. - Т. 2. - 328 с.

Koblitz N. Eliptic Curve Cryptosystems // Mathematics of Computation. - 1987. - Vol. 48, №~177. - Р. 203-209.

Menezes A. J., Okamoto T., Vanstone S. A. Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field // IEEE Transactions On Information Theory. - 1993. - Vol. 39, No. 5, September. - pp. 1603-1646.

Алексеев Е. К., Ошкин И. Б., Попов В. О., Смышляев С. В., Сонина Л. А. О перспективах использования скрученных эллиптических кривых Эдвардса со стандартом ГОСТ Р 34.10-2012 и алгоритмом ключевого обмена на его основе: Материалы XVI международной конференции "РусКрипто 2014".

Бессaлов A. В., Цыгaнкoва O. B. Взаимосвязь семейства точек больших порядков кривой Эдвардса над простым полем // Захист інформації. - 2015. - Т. 17, № 1. - С. 73-80.

Виноградов И. М. Основы теории чисел: учебное пособие, 12-е изд. - СПб.: "Лань", 2009. - 271 с.

Степанов С.  Арифметика алгебраических кривых. - М.: Наука, 1991. - 368 с.

Gupta R., Murty M. R.  Primitive points on elliptic curves // Compos. Math. - 1986. - 58. - P. 13-–44.

Montgomery P. L., Speeding the Pollard and Elliptic Curve Methods of Factorizations, Math. Comp. 48, (1987), PP. 243-264.

Скуратовський Р. Дослідження властивостей скрученої кривої Едвардса: Конференція державної служби спеціального звязку та захисту інформації. http://www.dstszi.gov.ua/dstszi/control/uk/publish/article?showHidden=1arti id=252312catid=240232ctime=1464080781894.

Skuratovskii R.~V. Twisted Edwards curve and its group of points over finite field $F_p$ // XI Літня школа "Алгебра, Топологія, Аналіз"  Одеса, 2016. - pp. 122-124.

Скуратовский Р. В., Осадчий E. О.,  Квашук Д. М. Деление точки скрученной кривой Эдвардса на два и ее применение в криптографии // Вісник національного технічного університету "ХПІ". - №44. - C. 90-96.

Skuratovskii R.~V., Skruncovich U.~V. Twisted Edwards curve and its group of points over finite field $F_p$ //  Conference "Graphs and Groups, Spectra and Symmetries", Novosibirsk, Russia. http://math.nsc.ru/conference/g2/g2s2/exptext/SkruncovichSkuratovskii-abstract-G2S2.pdf.

Скуратовський Р., Мовчан П. Нормалізація скрученої кривої Едвардса та дослідження її властивостей над $F_p$ // Збірник праць 14-ї Всеукраїнської науково-практичної конференції. ФТІ НТУУ "КПІ" 2016. - Т. 2. - С. 102-104.

Skuratovskii R. V. Constructing of finite field normal basis in deterministic polynomial time // Bulletin of Taras Shevchenko Kiev National University. - 2011. - P. 49-54.

Paulo S., Barreto L. M., Naehrig M. Pairing-Friendly Elliptic Curves of Prime Order // International Workshop on Selected Areas in Cryptography SAC, 2005. - pp. 319-331.





ISSN: 2519-206X (Print)

DOI: 10.18524/2519-206X