КРИПТОСИСТЕМИ НА ОСНОВІ ІЗОМОРФНИХ ПЕРЕТВОРЕНЬ ЕЛІПТИЧНИХ КРИВИХ

Анотація

У статті розглянуто напрями розробки та вдосконалення постквантових криптографічних систем, заснованих на ізоморфних перетвореннях еліптичних кривих, потенційно стійких до квантового криптоаналізу. Проведено аналіз недоліків та переваг існуючих асиметричних криптосистем, в тому числі таких, які побудовані на основі ізоморфних перетворень. Досліджено підходи до побудови криптографічних алгоритмів на основі ізогеній еліптичних кривих, що можуть стати основою для створення стійких до квантових атак криптосистем.

У процесі проведених досліджень було розроблено програмні функції для реалізації операцій над ізогеніями еліптичних кривих різного порядку, які забезпечать зазначені в стандарті [12] рівні безпеки: 256, 384, 512. Розроблена програмна реалізація операцій скалярного множення точки кривої та операцій над ізогеніями еліптичної кривої, на основі якої отримано експериментальні значення часу на обчислення скалярного добутку з використанням розпаралелювання. Проведено експерименти порівняння з класичного множення точки кривої з представленням скаляру k у вигляді послідовності 4-бітових слів, що дозволило прискорити операцію скалярного множення в 30 разів, для 8-бітових слів прискорення склало 18,8 разів.

Напрямком подальших досліджень є розробка методів генерації та верифікації цифрового підпису, на основі перетворень над точками ізогенії еліптичної кривої з використанням розпаралелювання операцій скалярного множення точки кривої.

Посилання

1. Rivest, Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. New York City: Association for Computing Machinery. 1978. Vol. 21, Iss. 2. P. 120–126. ISSN 0001-0782; 1557-7317. DOI: 10.1145/359340.359342.
2. Bernstein, Lange T., Niederhagen R. Dual EC: A Standardized Back Door // Cryptology ePrint Archive, Report 2015. P. 767. URL: https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf.
3. Shor W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Foundations of Computer Science: Conference Publications. 1997. P. 1484–1509.
4. Alkim, Ducas L., Pöppelmann T., Schwabe P. Post-quantum key exchange – a new hope // IACR Cryptology ePrint Archive, Report 2015/1092, 2015.
5. Husemöller, Theisen S., Forster O., Lawrence R. Elliptic Curves, Second Edition // Springer. 2002. P. 487.
6. Edwards A normal form for elliptic curves // Bulletin of the American Mathematical Society. Vol. 44, № 3. 2007. P. 393–422.
7. Bernstein J., Lange T. Inverted Edwards coordinates // Applied algebra, algebraic algorithms and error-correcting codes: 17th international symposium, AAECC-17, Bangalore, India, December 16-20, 2007, proceedings. LNCS 4851, Springer. 2007. P. 20–27.
8. Schoof Elliptic curves over finite fields and the computation of square roots modulo p. Bordeaux: Math. Comput. 1985. № 44. P. 483–494.
9. Schoof Counting points on elliptic curves over finite fields. J. Theor. Nombres. Bordeaux 7. 1995. Р. 219–254.
10. Чевардин В. Е. Изоморфные трансформации эллиптической кривой над конечным полем// Международный научно-теоретический журнал «Кибернетика и системный анализ». 2013. Том 49, №  С. 168–171.
11. ChristopheNegre, Jean-Marc  New Parallel Approaches for Scalar Multiplication in Elliptic Curves over Fields of Small Characteristic // IEEE Transactions on Computers. 2015. № 64 (10). 
    Р. 2875–2890. URL: https://hal.science/hal-00908463v1/file/parallelization-ecsm8.pdf.
12. Federal Office for Information Security (BSI). BSI – Technical Guideline. Cryptographic Mechanisms: Recommendations and Key Lengths. BSI TR-02102-1. V. 2023-01.
13. Goubin A Refined Power-Analysis-Attack on Elliptic Curve Cryptosystems, Proceedings of Public-Key-Cryptography – PKC 2003, Lecture Notes in Computer Science 2567, Springer Verlag, 2003.
14. Stolbunov Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Adv. in Math. of Comm. 2010. No. 4(2). P. 215–235.
15. Galbraith S., Stolbunov Improved algorithm for the isogeny problem for ordinary elliptic curves // Applicable Algebra in Engineering, Communication and Computing. 2013. No. 24(2). P. 107–131.
16. DeFeo , Jao D., Plˆut J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies // Journal of Mathematical Cryptology (to appear). 2014. URL: http://eprint.iacr.org/2011/506.
17. CostelloC., Longa P., Naehrig M. Efficient algorithms for supersingular isogeny Diffie-Hellman // CRYPTO 2016. URL: https://eprint.iacr.org/2016/413.pdf.
18. Rostovtsev, Stolbunov A. Public-key cryptosystem based on isogenies. URL: https://eprint.iacr.org/2006/145.pdf.
19. Tate Endomorphisms of abelian varieties over finite fields // Inventiones Mathematica. 1966. No. 2. Р. 134–144.
20. CastryckW., Decru Th. An efficient key recovery attack on SIDH (PDF). In Carmit Hazay; Martijn Stam (eds.). Advances in Cryptology – EUROCRYPT 2023. International Association for Cryptologic Research. Lecture Notes in Computer Science. 14008. Springer. 2023. Р. 423–447. DOI: 10.1007/978-3-031-30589-4_15. ISBN 978-3-031-30589-4.