On the security properties of Russian standardized elliptic curves

E. K. Alekseev   ; V. D. Nikolaev   ; S. V. Smyshlyaev

Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 3, pp. 5-32

Résumé

In the last two decades elliptic curves have become a necessary part of numerous cryptographic primitives and protocols. Hence it is extremely important to use the elliptic curves that do not weaken the security of such protocols. We investigate the elliptic curves used with GOST R 34.10-2001, GOST R 34.10-2012 and the accompanying algorithms, their security properties and generation process.

Bibliographie

[1] Information technology. Cryptographic data security. Signature and verification processes of [electronic] digital signature, GOST R 34.10-2001, Gosudarstvennyi Standart of Russian Federation, Government Committee of Russia for Standards, 2001 (in Russian)

[2] Popov V., Kurepkin I., Leontiev S., “Additional cryptographic algorithms for use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 algorithms”, CRYPTO-PRO (2006) (in Russian) https://tools.ietf.org/html/rfc4357

[3] Information technology. Cryptographic data security. Signature and verification processes of [electronic] digital signature, GOST R 34.10-2012, Federal Agency on Technical Regulating and Metrology, 2012 (in Russian)

[4] The use of cryptographic algorithms accompanying the usage of standards GOST R 34.10-2012 and GOST R 34.11-2012, Standardization recommendations, Technical Committee 26. Federal Agency on Technical Regulating and Metrology, 2014 (in Russian)

[5] Alekseev E., Oshkin I., Popov V., Leontiev S., Podobaev V., Belyavsky D., Guidelines on the cryptographic algorithms to accompany the usage of standards GOST R 34.10-2012 and GOST R 34.11-2012, RFC 7836, ed. Smyshlyaev S., 2016 (in Russian) https://tools.ietf.org/html/rfc7836.html | MR

[6] Alekseev E. K., Oshkin I. B., Popov V. O., Smyshlyaev S. V., Sonina L. A., “On the perspectives of the usage of twisted Edwards curves with the GOST R 34.11-2012 digital signature and the corresponding key agreement algorithm”, Information Security Problems. Computer Systems, 3 (2014), 60–66 (in Russian)

[7] Information technology. Cryptographic data security. Parameters of elliptic curves for cryptographic algorithms and protocols, Federal Agency on Technical Regulating and Metrology, 2016 (in Russian)

[8] Information technology. Cryptographic Data Security. Hashing function, GOST R 34.11-2012, Federal Agency on Technical Regulating and Metrology, 2012 (in Russian)

[9] Standards for Efficient Cryptography Group: Recommended Elliptic Curve Domain Parameters. Version 1.0, SEC 2, , 2000 www.secg.org/SEC2-Ver-1.0.pdf

[10] Bernstein D. J., Chou T., Chuengsatiansup C., Huelsing A., Lambooij E., Lange T., Niederhagen R., van Vredendaal C., How to manipulate curve standards: a white paper for the black hat,, http://bada55.cr.yp.to/pubs.html

[11] Discrete Math. Appl., 18:4 (2008), 427–437 (in English) | DOI | DOI | MR | Zbl

[12] Alekseev E. K., Oshkin I. B., Popov V. O., Smyshlyaev S. V., “On the cryptographic properties of algorithms accompanying the applications of standards GOST R 34.11-2012 and GOST R 34.10-2012”, Mathematical Aspects of Cryptography, 7:1 (2016), 5–38 (in Russian) | MR

[13] Shoup V., “Lower bounds for discrete logarithms and related problems”, EUROCRYPT 97, Lect. Notes Comput. Sci., 1233, 1997, 256–266 | DOI | MR

[14] Mathematical Notes, 55:2 (1994), 165–172 (in English) | DOI | MR | Zbl

[15] Pollard J. M., “Monte Carlo methods for index computation $\pmod p$”, Math. Comput., 32 (1978), 918–924 | MR | Zbl

[16] Vercauteren F. (ed.), Final Report on Main Computational Assumptions in Cryptography, ECRYPT II, ICT-2007-216676, http://www.ecrypt.eu.org/ecrypt2/documents/D.MAYA.6.pdf

[17] SafeCurves: choosing safe curves for elliptic-curve cryptography, https://safecurves.cr.yp.to/index.html

[18] Semaev I. A., “Evaluation of discrete logarithms in a group of $p$-torsion points of an elliptic curve in characteristic $p$”, Math. Comput., 67 (1998), 353–356 | DOI | MR | Zbl

[19] Menezes A., Vanstone S., “Reducing elliptic curve logarithms to logarithms in a finite field”, IEEE Trans. Inform. Theory, IT, 39:5 (1993), 1639–1646 | DOI | MR | Zbl

[20] Petit C., Kosters M., Messeng A., “Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields”, PKC 2016, v. II, Lect. Notes Comput. Sci., 9615, 2016, 3–18 | DOI | MR | Zbl

[21] Koblitz N., A Course in Number Theory and Cryptography, Springer-Verlag, Berlin–Heidelberg etc., 1987, viii+208 pp. ; Koblits N., Kurs teorii chisel i kriptografii, TVP, M., 2001, 254 pp. | MR | Zbl

[22] Semaev I. A., Summation polynomials and the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive: Report 2004/031

[23] Semaev I. A., New algorithm for the discrete logarithm problem on elliptic curves, Cryptology ePrint Archive: Report 2015/310

[24] Faugere J.-C., “A new efficient algorithm for computing Groebner bases $(F_4)$”, J. Pure Appl. Algebra, 139:1–3 (1999), 61–88 | DOI | MR | Zbl

[25] Crandall R., Pomerance C., Prime Numbers: A Computational Perspective, Springer, N.-Y. etc., 2001, xv+545 pp. | MR

[26] Collins G., “The calculation of multivariate polynomial resultants”, J. Assoc. Comput. Mach., 18:4 (1971), 515–532 | DOI | MR | Zbl

[27] Diem C., “On the discrete logarithm problem in elliptic curves. II”, Algebra Number Theory, 7:6 (2013), 1281–1323 | DOI | MR | Zbl

[28] Huang Y.-J., Petit C., Shinohara N., Takagi T., On generalized first fall degree assumptions, Cryptology ePrint Archive: Report 2015/358