3- І 5-ІЗОГЕНІЇ СУПЕРСІНГУЛЯРНИХ КРИВИХ ЕДВАРДСА
DOI:
https://doi.org/10.28925/2663-4023.2020.8.621Ключові слова:
крива в узагальненій формі Едвардса, повна крива Едвардса, скручена крива Едвардса, квадратична крива Едвардса, порядок кривої, порядок точки, ізоморфізм, ізогенія, ступінь ізогенії, ядро ізогенії, квадратичний відрахування, квадратичний невирахуванняАнотація
Дан аналіз властивостей і умов існування 3- і 5-ізогеній повних і квадратичних суперсінгулярних кривих Едвардса. Для завдання інкапсуляції ключів на основі алгоритму SIDH запропоновано використовувати ізогенії мінімальних непарних ступенів 3 і 5, що дозволяє обійти проблему особливих точок 2-го і 4-го порядків, характерну для 2-ізогеній. Наведено огляд основних властивостей класів повних, квадратичних і скручених кривих Едвардса над простим полем. Формули для ізогеній непарних ступенів приведені до вигляду, адаптованому до кривих в формі Вейєрштрасса. Для цього використовується модифікований закон складання точок кривої в узагальненій формі Едвардса, який зберігає горизонтальну симетрію зворотних точок кривої. Наведені приклади обчислення 3- і 5-ізогенна повних суперсінгулярних кривих Едвардса над малими простими полями і обговорюються властивості композиції ізогеній для їх обчислення з ядрами високих порядків. Отримано формули верхніх оцінок складності обчислень ізогеній непарних ступенів 3 і 5 в класах повних і квадратичних кривих Едвардса в проективних координатах побудовано алгоритми обчислення 3- і 5-ізогеній кривих Едвардса зі складністю 6M + 4S і 12M + 5S відповідно. Знайдено умови існування суперсінгулярних повних і квадратичних кривих Едвардса порядку 4·3m·5n і 8·3m·5n. Визначено деякі параметри криптосистеми при реалізації алгоритму SIDH на рівні квантової безпеки 128 біт
Завантаження
Посилання
D. Jao and L. De Feo, “Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies,” Lecture Notes in Computer Science, pp. 19–34, 2011. doi: 10.1007/978-3-642-25405-5_2.
D. J. Bernstein and T. Lange, “Faster Addition and Doubling on Elliptic Curves,” Lecture Notes in Computer Science, pp. 29–50, 2007. doi: 10.1007/978-3-540-76900-2_3.
D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters, “Twisted Edwards Curves,” Lecture Notes in Computer Science, pp. 389–405, 2008. doi: 10.1007/978-3-540-68164-9_26.
D. Moody and D. Shumow, “Analogues of Velu’s formulas for isogenies on alternate models of elliptic curves,” Mathematics of Computation, vol. 85, no. 300, pp. 1929–1951, Sep. 2015. doi: 10.1090/mcom/3036.
O. Ahmadi and R. Granger, “On isogeny classes of Edwards curves over finite fields,” Journal of Number Theory, vol. 132, no. 6, pp. 1337–1358, Jun. 2012. doi: 10.1016/j.jnt.2011.12.013.
A. V. Bessalov and O. V. Tsygankova, “Edwards supersingular complete curves over a simple field” [“Supersinguljarnye polnye krivye Jedvardsa nad prostym polem”], Radio engineering, pp. 88–98, vol. 191, 2017. (In Russian).
A. V. Bessalov, Edwards elliptic curves and cryptography [Jellipticheskie krivye v forme Jedvardsa i kriptografija], p. 272, 2017. ISBN 978-966-622-808-9. (In Russian).
A. V. Bessalov and O. V. Tsygankova, “Number of curves in the generalized Edwards form with minimal even cofactor of the curve order,” Problems of Information Transmission, vol. 53, no. 1, pp. 92–101, Jan. 2017. doi: 10.1134/S0032946017010082. (In Russian).
A. V. Bessalov and O. V. Tsygankova, “Interrelation of families of points of high order on the Edwards curve over a prime field,” Problems of Information Transmission, vol. 51, no. 4, pp. 391–397, Oct. 2015. doi: 10.1134/S0032946015040080. (In Russian).
A. V. Bessalov, “Calculation of Parameters of Cryptic Criviae Edwards over the Fields of Characteristics 5 and 7,” Cybersecurity: Education, Science, Technique, no. 1, pp. 94–104, 2018. doi: 10.28925/2663-4023.2018.1.94104. (In Ukrainian).
L. Washington, “Elliptic Curves,” Discrete Mathematics and Its Applications, Apr. 2008. doi: 10.1201/9781420071474.
S. Kim, K. Yoon, J. Kwon, S. Hong, and Y.-H. Park, “Efficient Isogeny Computations on Twisted Edwards Curves,” Security and Communication Networks, vol. 2018, pp. 1–11, Jul. 2018. doi: 10.1155/2018/5747642..
