Cryptographically Strong Elliptic Curves of Prime Order

Journal title

International Journal of Electronics and Telecommunications




vol. 67


No 2


Barański, Marcin : Military Communication Institute, National Research Institute, Warszawska 22A, 05-130 Zegrze ; Gliwa, Rafał : Military Communication Institute, National Research Institute, Warszawska 22A, 05-130 Zegrze ; Szmidt, Janusz : Military Communication Institute, National Research Institute, Warszawska 22A, 05-130 Zegrze



Mersenne primes ; elliptic curves ; security requirements ; search algorithm ; Magma

Divisions of PAS

Nauki Techniczne




Polish Academy of Sciences Committee of Electronics and Telecommunications


[1] Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe curves for elliptic curve cryptography, 2015. (accessed 27 September 2015).
[2] I. Blake, G. Serroussi, N. Smart. Elliptic curves in cryptography. Cambridge University Press, 1999.
[3] H. Cohen. A course in computational number theory. Springer 1983.
[4] H. Cohen, G. Frey. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman and Hall CRC, 1994.
[5] P. Da˛browski, R. Gliwa, J. Szmidt, R. Wicik. Generation and Implementation of Cryptographically Strong Elliptic Curves. Number-Theoretical Methods in Cryptology. First International Conference, NuTMiC 2017. Warsaw, Poland, 11-13, 2017. Lecture Notes in Computer Sciences, (Eds), Jerzy Kaczorowski, Josef Piprzyk, Jacek Pomykała. Volume 10737, pages 25-36. 2017.
[6] W. Diffie, M. E. Hellman. New Directions in Cryptography. IEEE Trans. Information Theory, IT 22(6), pp. 644-654, 1976.
[7] Jean-Pierre Flori, Jerome Plut, Jean-Rene Reinhard. Diversity and transparency for ECC. NIST Workshop on ECC Standards, June 11-12, 2015.
[8] Gerhard Frey, private communication, 2015.
[9] G. Frey, H. Rück. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Mathematics of Computations, 62 91994), 865-874.
[10] S. D. Galbraith, P. Gaudry. Recent progress on the elliptic curve discrete logarithm problem. Cryptology ePrint Archive, 2015/1022.
[11] Steven D. Galbraith and James McKee. The probability that the number of points on an elliptic curve over a finite field is prime. J. London Math. Soc. (2), 62(3):671–684, 2000.
[12] R. Gliwa, J. Szmidt, R. Wicik Searching for cryptographically secure elliptic curves over prime fields. Science and Military, 2016, nr 1, volume 11, pages 10-13, ISSN 1336-8885 (print), ISSN 2453-7632 (on-line).
[13] R. Granger, M. Scott. Faster ECC over F2521��1. In: Katz, J. ed., PKC 2015. LNCS, vol. 9020, pp. 539–553.[14] D. Johnson, A. Menezes. The Elliptic Curve Digital Signature Algorithm (ECDSA). Technical Report CORR 99-34, University of Waterloo, Canada.
[15] Manfred Lochter and Andreas Wiemers. Twist insecurity, 2015. iacr. ePrint Archive 577 (2015).
[16] A. Menezes, T. Okamoto, S. Vanstone. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE. Transactions on Information Theory, 39 (1993), 1639-1646.
[17] N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48(177), pp. 203- 209, 1987.
[18] V. S. Miller. Use of elliptic curves in cryptography. In Advances in Cryptology - CRYPTO’85, LNCS vol 218, pp. 417-426, 1985.
[19] P. Pohlig, M. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transaction on Information Theory, 24 (1979), 106-110.
[20] J. Pollard. Monte Carlo methods for index computations mod pn: Mathematics of Computations, 32 (1978), 918-924.
[21] R. L. Rivest, A. Shamir, L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21(2), pp. 120- 126, 1978.
[22] T. Satoh, K. Araki. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves, Commentarii Mathematici Universitatis Sancti Pauli, 47 (1998), 81-92.
[23] I. Semaev. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Mathematics of Computations, 67 (1998), 353-356.
[24] N. Smart. The discrete logarithm problem on elliptic curves uf trace one. Journal of Cryptology, 12 (1999), 193-196.
[25] J. H. Silverman. The arithmetic of elliptic curves. Springer 1986.
[26] Elliptic Curve Cryptography (ECC) Brainpool Standard. Curves and Curve Generation, v. 1.0. 2005. Request for Comments: 5639, 2010. 7027, 2013.
[27] Technical and Implementation Guidance on Generation and Application of Elliptic Curves for NATO classified, 2010.
[28] US Department of Commerce. N.I.S.T. 2000. Federal Information Processing Standards Publication 186-2. FIPS 186-2. Digital Signature Standard.
[29] Standards for Efficient Cryptography Group. Recommended elliptic curve domain parameters, 2000.
[30] Mersenne prime.
[31] Magma Computational Algebra System. School of Mathematics and Statistics. University of Sydney.






DOI: 10.24425/ijet.2021.135966


International Journal of Electronics and Telecommunications; 2021; vol. 67; No 2; 207-212