КіСА | Зміст

Том 59 >>> № 6 ЛИСТОПАД — ГРУДЕНЬ 2023

-->

УДК 621.391.15:519.7

А.В. БЕССАЛОВ
Київський університет імені Бориса Грінченка, Київ, Україна,
bessalov@ukr.net

С.В. АБРАМОВ
Київський університет імені Бориса Грінченка, Київ, Україна,
s.abramov.asp@kubd.edu.ua

АЛГОРИТМ PQC CSIKE НА НЕЦИКЛІЧНИХ КРИВИХ ЕДВАРДСА

Анотація. Запропоновано оригінальний алгоритм постквантової криптографії CSIKE як модифікацію CSIDH, але з одним відкритим ключем замість двох. Обґрунтовано умови його імплементації на двох класах нециклічних кривих Едвардса. Розглянуто властивості квадратичних та скручених суперсингулярних кривих Едвардса, що утворюють пари квадратичного кручення порядку p +1 ≡ 0 mod 8 над простим полем F_p . Наведено модифікацію алгоритму CSIDH і алгоритм CSIKE, які побудовані на ізогеніях цих кривих замість традиційної арифметики кривих у формі Монтгомері. Для ізогеній ступенів 3, 5, 7 розраховано і табульовано параметри ізогенних ланцюжків нециклічних суперсингулярних кривих Едвардса, якщо p = 839. Розглянуто імплементацію схеми інкапсуляції ключа за умови, що Аліса шифрує його відкритим ключем Боба. Запропоновано новий рандомізований алгоритм CSIKE з випадковим рівноймовірним вибором кривої з двох класів на кожному кроці ланцюжка ізогеній. Наведено оцінку ймовірності успішної атаки побічного каналу в рандомізованому алгоритмі, у якому запропоновано можливість відмови від обчислення ізогенної функції φ( R) випадкової точки R, що істотно прискорить алгоритм.

Ключові слова: крива в узагальненій формі Едвардса, повна крива Едвардса, скручена крива Едвардса, квадратична крива Едвардса, порядок кривої, порядок точки, ізоморфізм, ізогенія, w-координати, квадратичний лишок, квадратичний нелишок.

повний текст

СПИСОК ЛІТЕРАТУРИ

Castryck W., Lange T., Martindale C., Panny L., Renes J. CSIDH: An efficient post-quantum commutative group action. In: Advances in Cryptology — ASIACRYPT 2018. Peyrin T., Galbraith S. (Eds.). Lecture Notes in Computer Science. Cham: Springer, 2018. Vol. 11274. P. 395–427. https://doi.org/10.1007/ 978-3-319-59870-3_21.

Kim S., Yoon K., Kwon J., Hong S., Park Y.-H. Efficient isogeny computations on twisted Edwards curves. Security and Communication Networks. 2018. Vol. 2018. Article ID 5747642. https://doi.org/10.1155/2018/5747642.

Moody D., Shumow D. Analogues of VБlu’s formulas for isogenies on alternate models of elliptic curves. Mathematics of Computation. 2016. Vol. 85, N 300. P. 1929–1951.

Bessalov A., Sokolov V., Skladannyi P., Zhyltsov O. Computing of odd degree isogenies on supersingular twisted Edwards curves. CEUR Workshop Proceedings. 2021. Vol. 2923. P. 1–11.

Moriya T., Onuki H., Takagi T. How to construct CSIDH on Edwards curves. In: Topics in Cryptology — CT-RSA 2020. Jarecki S. (Ed.). Lecture Notes in Computer Science. Cham: Springer, 2020. Vol. 12006. P. 512–537. https://doi.org/10.1007/978-3-030-40186-3_22 .

Bessalov A.V. On correctness of implementation conditions CSIDH algorithm on Edwards curves. Радиотехника. 2022. Вып. 208. С. 16–27.

Bernstein D.J., Lange T. Faster addition and doubling on elliptic curves. In: Advances in Cryptology — ASIACRYPT 2007. Kurosawa K. (Eds.). Lecture Notes in Computer Science. Berlin; Heidelberg: Springer, 2007. Vol. 4833. P. 29–50. 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. Vaudenay S. (Eds.). Lecture Notes in Computer Science. Berlin; Heidelberg: Springer, 2008. Vol. 5023. P. 389–405. https://doi.org/10.1007/ 978-3-540-68164-9_26.

Бессалов А.В. Эллиптические кривые в форме Эдвардса и криптография. Киев: Политехника, 2017. 272 с.

Bessalov A.V., Tsygankova O.V. Number of curves in the generalized Edwards form with minimal even cofactor of the curve order. Problems of Information Transmission. 2017. Vol. 53, N 1. P. 92–101. https://doi.org/10.1134/S0032946017010082.

Bessalov A.V., Kovalchuk L.V. Supersingular twisted Edwards curves over prime fields. I. Supersingular twisted Edwards curves with j-invariants equal to zero and . Cybernetics and Systems Analysis. 2019. Vol. 55, No. 3. P. 347–353. https://doi.org/10.1007/s10559-019-00140-9.

Bessalov A.V., Kovalchuk L.V. Supersingular twisted Edwards curves over prime fields. II. Supersingular twisted Edwards curves with the j-invariant equal to . Cybernetics and Systems Analysis. 2019. Vol. 55, N 5. P. 731–741. https://doi.org/10.1007/s10559-019-00183-y .

Azarderakhsh R., Campagna M., Costello C., Feo L.D., Hess B., Jalali A., Jao D., Koziel B., LaMacchia B., Longa P., Naehrig M., Renes J., Soukharev V., and Urbanik D. Supersingular isogeny key encapsulation — Submission to the NIST’s post-quantum cryptography standardization process. 2017. URL: https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum -Cryptography .

Washington L.C. Elliptic curves. Number theory and cryptography. 2nd ed. CRC Press, 2008. 513 p.

Onuki, H., Aikawa, Y., Yamazaki, T., Takagi, T. (2019). (Short paper) A faster constant-time algorithm of CSIDH keeping two points. In: Attrapadung, N., Yagi, T. (eds) Advances in Information and Computer Security. IWSEC 2019. Lecture Notes in Computer Science, vol 11689. P. 23–33. Springer, Cham. https://doi.org/10.1007/978-3-030-26834-3_2.

Jalali A., Azarderakhsh R., Kermani M.M., Jao D. Towards optimized and constant-time CSIDH on embedded devices. IACR Cryptology ePrint Archive 2019/297. URL: https://eprint.iacr.org/2019/297 . (to apper at COSADE 2019).