ЯК ПОБУДУВАТИ CSIDH НА КВАДРАТИЧНИХ І СКРУЧЕНИХ КРИВИХ ЕДВАРДСА
DOI:
https://doi.org/10.28925/2663-4023.2022.15.148163Ключові слова:
крива в узагальненій формі Едвардса, повна крива Едвардса скручена крива Едвардса, квадратична крива Едвардса, порядок кривої, порядок точки, ізоморфізм, ізогенія, w--координати, квадратичний лишок, квадратичний не лишокАнотація
В одної з відомих робіт виявлені некоректна постановка і невірне рішення задачі імплементації алгоритму CSIDH на кривих Едвардса . Дана розгорнена критика цієї роботи с доведенням неспроможності її концепції. Розглянуті специфічні властивості трьох неізоморфних класів суперсингулярних кривих в узагальненої формі Едвардса: повних, квадратичних та скручених кривих Едвардса. Визначені умови існування кривих усіх 3-х класів з порядком кривих p+1 над простим полем . Імплементація алгоритму CSIDH на ізогеніях непарних простих степенів базується на застосуванні пар квадратичного кручення еліптичних кривих. З цією метою алгоритм CSIDH можна будувати як на повних кривих Едвардса з квадратичним крученням всередині цього класу, або на квадратичних і скручених кривих Едвардса, які створюють пари квадратичного кручення. В противагу до цього автори відомої роботи намагаються довести теореми, які стверджують о наявності рішення всередині одного класу кривих з параметром , який є квадратом. Проведено критичний аналіз теорем, лем, помилкових стверджень в цієї роботі. Доведено теорема 2 про квадратичне кручення в класах кривих Едвардса. Приведено модифікація алгоритму CSIDH, побудованого на ізогеніях квадратичних і скручених кривих Едвардса, Для ілюстрації коректного рішення задачі розглянуто приклад обчислень Аліси і Боба в схемі розподілу секретів згідно алгоритму CSIDH при p=239 .
Завантаження
Посилання
Moriya, T., Onuki, H., Takagi, T. (2020). How to Construct CSIDH on Edwards Curves. In У Topics in Cryptology – CT-RSA 2020 (p. 512–537). Springer International Publishing. https://doi.org/10.1007/978-3-030-40186-3_22.
Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J. (2018). CSIDH: An Efficient Post-Quantum Commutative Group Action. In Lecture Notes in Computer Science (p. 395–427). Springer International Publishing. https://doi.org/10.1007/978-3-030-03332-3_15.
Bernstein, D. J., Lange, T. (2007). Faster Addition and Doubling on Elliptic Curves. In Advances in Cryptology – ASIACRYPT 2007 (p. 29–50). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_3.
Bernstein, D. J., Birkner, P., Joye, M., Lange, T., Peters, C. (б. д.). Twisted Edwards Curves. In Progress in Cryptology – AFRICACRYPT 2008 (p. 389–405). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-68164-9_26
Kim, S., Yoon, K., Park, Y.-H., Hong, S. (2019). Optimized Method for Computing Odd-Degree Isogenies on Edwards Curves. In Lecture Notes in Computer Science (p. 273–292). Springer International Publishing. https://doi.org/10.1007/978-3-030-34621-8_10
Farashahi, R. R., Hosseini, S. G. (2017). Differential Addition on Twisted Edwards Curves. In Information Security and Privacy (p. 366–378). Springer International Publishing. https://doi.org/10.1007/978-3-319-59870-3_21
Moody, D., Shumow, D. (2015). Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation, 85(300), 1929–1951. https://doi.org/10.1090/mcom/3036
Bessalov, A., Sokolov, V., Skladannyi, P., Zhyltsov, O. (2021). Computing of odd degree isogenies on supersingular twisted Edwards curves. In CEUR Workshop Proceedings, 2923 (p. 1-11).
Bessalov, A.V., Tsygankova, O.V. Abramov, S.V. (2021). Otsenka vychislitel'noy slozhnosti algoritma CSIDH na supersingulyarnykh skruchennykh i kvadratichnykh krivykh Edvardsa. Radiotekhnika, (207), 40-51.
Bessalov, A., Sokolov, V., Skladannyi, P. (2020). Modeling of 3- and 5-Isogenies of Supersingular Edwards Curves. In Proceedings of the 2nd International Workshop on Modern Machine Learning Technologies and Data Science (MoMLeT&DS’2020) (p. 30–39). CEUR.
Bessalov, A.V. (2017). Ellipticheskiye krivyye v forme Edvardsa i kriptografiya. Monografiya. «Politekhnika».
Bessalov, A. V., Tsygankova, O. V. (2017). Number of curves in the generalized Edwards form with minimal even cofactor of the curve order. Problems of Information Transmission, 53(1), 92–101. https://doi.org/10.1134/s0032946017010082
Bessalov, A. V., Kovalchuk, L. V. (2019). Supersingular Twisted Edwards Curves Over Prime Fields. I. Supersingular Twisted Edwards Curves with j-Invariants Equal to Zero and 123. Cybernetics and Systems Analysis, 55(3), 347–353. https://doi.org/10.1007/s10559-019-00140-9.
Bessalov, A. V., Kovalchuk, L. V. (2019). Supersingular Twisted Edwards Curves over Prime Fields.* II. Supersingular Twisted Edwards Curves with the j-Invariant Equal to 663. Cybernetics and Systems Analysis, 55(5), 731–741. https://doi.org/10.1007/s10559-019-00183-y.
Washington, L. C. (2008). Elliptic curves: Number theory and cryptography (2nd view). Chapman & Hall/CRC.
Jalali, A., Azarderakhsh, R., Kermani, M. M., Jao, D. (2019). Towards Optimized and Constant-Time CSIDH on Embedded Devices. In Constructive Side-Channel Analysis and Secure Design (p. 215–231). Springer International Publishing. https://doi.org/10.1007/978-3-030-16350-1_12
