РАНДОМІЗАЦІЯ АЛГОРИТМУ CSIDH НА КВАДРАТИЧНИХ ТА СКРУЧЕНИХ КРИВИХ ЕДВАРДА
DOI:
https://doi.org/10.28925/2663-4023.2022.17.128144Ключові слова:
крива в узагальненому вигляді Едвардса, повна крива Едвардса, скручена крива Едвардса, квадратична крива Едвардса, порядок кривої, точковий порядок, ізоморфізм, ізогенія, рандомізація, w-координати, квадрат, неквадрат.Анотація
Розглянуто властивості квадратичних і кручених суперсингулярних кривих Едвардса, які утворюють пари квадратичних кручень з порядком над простим полем. Розглянуто модифікацію алгоритму CSIDH на основі ізогеній непарного ступеня цих кривих. Побудовано просту модель для реалізації алгоритму CSIDH у 3 мінімальних непарних ступенях ізогенії 3, 5, 7, з простим модулем поля та порядком суперсингулярних кривих. На етапі випадання розраховуються та зводяться в таблицю параметри ізогенних ланцюгів усіх ступенів для цих двох класів суперсингулярних кривих Едвардса. Наведено приклад реалізації алгоритму CSIDH як неінтерактивної схеми обміну секретами на основі секретного та відкритого ключів Аліси та Боба. Запропоновано новий рандомізований алгоритм CSIDH з випадковим рівноімовірним вибором однієї з кривих цих двох класів на кожному кроці ланцюга ізогенії. Вибір ступеня кожної ізогенії є випадковим. Проілюстровано роботу рандомізованого алгоритму на прикладі. Цей алгоритм розглядається як можлива альтернатива "CSIDH з постійним часом". Комбінація двох підходів можлива для протидії атакам на бокових каналах. Наведено оцінки ймовірності успішної атаки побічного каналу в рандомізованому алгоритмі. Зазначається, що всі обчислення в алгоритмі CSIDH, необхідні для обчислення загального секрету, зводяться лише до обчислення параметра ізогенної кривої та виконуються за допомогою польових і групових операцій, зокрема, множення скалярних точок і подвоєння точок ядра ізогенії. У новому алгоритмі ми пропонуємо відмовитися від обчислення ізогенної функції випадкової точки , що значно прискорює роботу алгоритму.
Завантаження
Посилання
Bessalov, A., Sokolov, V., Skladannyi, P., Zhyltsov, O. (2021). Computing of odd degree isogenies on supersingular twisted Edwards curves. CEUR Workshop Proceedings, 2923, 1–11.
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 (pp. 395–427). Springer International Publishing. https://doi.org/10.1007/978-3-030-03332-3_15
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 (pp. 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 (pp. 366–378). Springer International Publishing. https://doi.org/10.1007/978-3-319-59870-3_21.
Kim, S., Yoon, K., Kwon, J., Hong, S., Park, Y.-H. (2018). Efficient Isogeny Computations on Twisted Edwards Curves. Security and Communication Networks, 2018, 1–11. https://doi.org/10.1155/2018/5747642
Moody, D., Shumow, D. (2016). Analogues of Velus formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation, 85(300), 1929–1951.
Bessalov, A.V., Tsyhankova, O.V. Abramov, S.V. (2021). Otsenka vychyslytelnoi slozhnosty alhorytma CSIDH na supersynhuliarnykh skruchennykh y kvadratychnykh kryvykh Edvardsa. Radyotekhnyka, 207, 40-51.
Bernstein, D. J., Lange, T. (2007). Faster Addition and Doubling on Elliptic Curves. In Advances in Cryptology – ASIACRYPT 2007 (pp. 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. (2008). Twisted Edwards Curves. In Progress in Cryptology – AFRICACRYPT 2008 (pp. 389–405). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-68164-9_26
Bessalov, A.V. (2017). Ellyptycheskye kryvye v forme Edvardsa y kryptohrafyia. Monohrafyia. «Polytekhnyka».
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.
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 Analysist, 55(3), 347–353.
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 Analysist, 55(5), 731–741.
Washington, L.C. (2008). Elliptic Curvres. Number Theory and Cryptography. Second Edition. CRC Press.
Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T. (2020). A Faster Constant-time Algorithm of CSIDH keeping Two Points. ASIACRYPT.
Jalali, A., Azarderakhsh, R., Kermani, M. M., Jao, D. (2019). Towards Optimized and Constant-Time CSIDH on Embedded Devices. У Constructive Side-Channel Analysis and Secure Design (с. 215–231). Springer International Publishing. https://doi.org/10.1007/978-3-030-16350-1_12
