# Finding Secure Curves with the Satoh-FGH Algorithm and an Early-Abort Strategy

• Mireille Fouquet
• Pierrick Gaudry
• Robert Harley
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2045)

## Abstract

The use of elliptic curves in cryptography relies on the ability to count the number of points on a given curve. Before 1999, the SEA algorithm was the only efficient method known for random curves. Then Satoh proposed a new algorithm based on the canonical p-adic lift of the curve for p ≥ 5. In an earlier paper, the authors extended Satoh's method to the case of characteristics two and three. This paper presents an implementation of the Satoh-FGH algorithm and its application to the problem of findingcurv es suitable for cryptography. By combining Satoh-FGH and an early-abort strategy based on SEA, we are able to find secure random curves in characteristic two in much less time than previously reported. In particular we can generate curves widely considered to be as secure as RSA-1024 in less than one minute each on a fast workstation.

## Keywords

Elliptic Curve Elliptic Curf Field Size Discrete Logarithm Torsion Point
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

## References

1. FIPS186.
FIPS 186-2. Digital Signature Standard. Federal Information Processing Standards publication, january 2000. U.S. Departement of Commerce/National Institute of Standards and Technology. Available at http://csrc.nist.gov/cryptval/dss.htm.
2. P1363.
IEEE P1363. Standard specifications for public key cryptography. Available at http://www.manta.ieee.org/groups/1363/.
3. Atk92.
A. O. L. Atkin. The number of points on an elliptic curve modulo a prime. Series of e-mails to the NMBRTHRY mailinglist, 1992.Google Scholar
4. BSS99.
I. Blake, G. Seroussi, and N. Smart. Elliptic curves in cryptography, volume 265 of London Math. Soc. Lecture Note Ser. Cambridge University Press, 1999.Google Scholar
5. Coh96.
H. Cohen. A course in algorithmic algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, 1996. Third printing.Google Scholar
6. Cou94.
J.-M. Couveignes. Quelques calculs en théorie des nombres. Thése, Université de Bordeaux I, July 1994.Google Scholar
7. Cou96.
J.-M. Couveignes. Computing l-isogenies using the p-torsion. In H. Cohen, editor, Algorithmic Number Theory, volume 1122 of Lecture Notes in Comput. Sci., pages 59–65. Springer Verlag, 1996. Second International Symposium, ANTS-II, Talence, France, May 1996, Proceedings.Google Scholar
8. Dew98.
L. Dewaghe. Remarks on the Schoof-Elkies-Atkin algorithm. Math. Comp., 67(223):1247–1252, July 1998.
9. DGM99.
I. Duursma, P. Gaudry, and F. Morain. Speeding up the discrete log computation on curves with automorphisms. In Kwok Yan Lam, Eiji Okamoto, and Chaoping Xing, editors, Advances in Cryptology-ASIACRYPT '99, volume 1716 of Lecture Notes in Comput. Sci., pages 103–121. Springer-Verlag, 1999. International Conference on the Theory and Applications of Cryptology and Information Security, Singapore, November 1999, Proceedings.Google Scholar
10. Elk98.
N. Elkies. Elliptic and modular curves over finite fields and related computational issues. In D.A. Buell and eds. J.T. Teitelbaum, editors, Computational Perspectives on Number Theory, pages 21–76. AMS/International Press, 1998. Proceedings of a Conference in Honor of A.O.L. Atkin.Google Scholar
11. FGH00.
M. Fouquet, P. Gaudry, and R. Harley. An extension of Satoh’s algorithm and its implementation. J. Ramanujan Math. Soc., 15:281–318, 2000.
12. FR94.
G. Frey and H.-G. Rück. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comp., 62(206):865–874, April 1994.
13. GHS00.
P. Gaudry, F. Hess, and N. Smart. Constructive and destructive facets of Weil descent on elliptic curves. Submitted to J. Crypt. and available at http://www.cs.bris.ac.uk/~nigel/weil_descent.html, 2000.
14. GLV.
R. Gallant, R. Lambert, and S. Vanstone. Improving the parallelized Pollard lambda search on binary anomalous curves. To appear in Math. Comp. Google Scholar
15. Har00.
16. Has33.
H. Hasse. Beweis des Analogons der Riemannschen Vermutung für die Artinschen und F. K. Smidtschen Kongruenzzetafunktionen in gewissen elliptischen Fällen. Ges. d. Wiss. Narichten. Math.-Phys. Klasse, pages 253–262, 1933.Google Scholar
17. IKNY98.
T. Izu, J. Kogure, M. Noro, and K. Yokoyama. Efficient implementation of Schoof’s algorithm. In K. Ohta and D. Pei, editors, Advances in Cryptology-ASIACRYPT '98, volume 1514 of Lecture Notes in Comput. Sci., pages 66–79. Springer-Verlag, 1998. International Conference on the theory and application of cryptology and information security, Beijing, China, October 1998.
18. JM99.
D. Johnson and A. Menezes. The elliptic curve digital signature algorithm (ECDSA). Technical Report CORR 99-34, U. Waterloo, 1999. Available at http://www.cacr.math.uwaterloo.ca/.
19. Kob87.
N. Koblitz. Elliptic curve cryptosystems. Math. Comp., 48(177):203–209, January 1987.
20. Ler97a.
R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. Thése, École polytechnique, June 1997.Google Scholar
21. Ler97b.
R. Lercier. Finding good random elliptic curves for cryptosystems defined over $$\mathbb{F}_{{\text{2}}^{\text{n}} }$$ . In W. Fumy, editor, Advances in Cryptology-EUROCRYPT '97, volume 1233 of Lecture Notes in Comput. Sci., pages 379–392. Springer-Verlag, 1997. International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 1997, Proceedings.Google Scholar
22. LM95.
R. Lercier and F. Morain. Counting the number of points on elliptic curves over finite fields: strategies and performances. In L. C. Guillou and J.-J. Quisquater, editors, Advances in Cryptology-EUROCRYPT '95, volume 921 of Lecture Notes in Comput. Sci., pages 79–94, 1995. International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 1995, Proceedings.Google Scholar
23. LST64.
J. Lubin, J. P. Serre, and J. Tate. Elliptic curves and formal groups. In Lecture notes prepared in connection with the seminars held at the Summer Institute on Algebraic Geometry, Whitney Estate, Woods Hole, Massachusetts, July 6–July 31, 1964, 1964. Scanned copies available at http://www.ma.utexas.edu/users/voloch/lst.html.
24. LV00.
A. Lenstra and E. Verheul. Selecting cryptographic key sizes, January 2000. Presented at PKC2000.Google Scholar
25. Men93.
A. J. Menezes. Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.Google Scholar
26. Mil87.
V. Miller. Use of elliptic curves in cryptography. In A. M. Odlyzko, editor, Advances in Cryptology-CRYPTO '86, volume 263 of Lecture Notes in Comput. Sci., pages 417–426. Springer-Verlag, 1987. Proceedings, Santa Barbara (USA), August 11–15, 1986.Google Scholar
27. Mor95.
F. Morain. Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques. J. Théor. Nombres Bordeaux, 7:255–282, 1995.
28. MOV91.
A. Menezes, T. Okamoto, and S. A. Vanstone. Reducing elliptic curves logarithms to logarithms in a finite field. In Proceedings 23rd Annual ACM Symposium on Theory of Computing (STOC), pages 80–89. ACM Press, 1991. May 6–8, New Orleans, Louisiana.Google Scholar
29. MP98.
V. Müller and S. Paulus. On the generation of cryptographically strong elliptic curves. Preprint, 1998.Google Scholar
30. Mül95.
V. Müller. Ein Algorithmus zur Bestimmung der Punktanzahl elliptischer Kurven über endlichen Körpern der Charakteristik grö̈ser drei. PhD thesis, University of Saarland, 1995.Google Scholar
31. PH78.
S. Pohlig and M. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Trans. Inform. Theory, IT-24:106–110, 1978.
32. Pol78.
J. M. Pollard. Monte Carlo methods for index computation mod p. Math. Comp., 32(143):918–924, July 1978.
33. SA98.
T. Satoh and K. Araki. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. St. Paul., 47:81–92, 1998.
34. Sat00.
T. Satoh. The canonical lift of an ordinary elliptic curve over a finite field and its point counting. J. Ramanujan Math. Soc., 15:247–270, 2000.
35. Sch85.
R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44:483–494, 1985.
36. Sch95.
R. Schoof. Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux, 7:219–254, 1995.
37. Sem98.
I. A. Semaev. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curves in characteristic p. Math. Comp., 67(221):353–356, January 1998.
38. Ser68.
J. P. Serre. Corps locaux. Hermann, 1968.Google Scholar
39. Sil86.
J. H. Silverman. The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics. Springer-Verlag, 1986.Google Scholar
40. Sil00.
R. Silverman. A cost-based security analysis of symmetric and assymetric key lengths.. Bulletin Number 13 of RSA Security, April 2000.Google Scholar
41. Skj.
B. Skjernaa. Satoh’s algorithm in characteristic 2. Copies available at http://www.imf.au.dk/~skjernaa/.
42. Sma99.
N. Smart. The discrete logarithm problem on elliptic curves of trace one. J. Cryptology, 12:193–196, 1999.
43. Vél71.
J. Vélu. Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. I Math., 273:238–241, July 1971. Série A.
44. vOW99.
P. C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic applications. J. of Cryptology, 12:1–28, 1999.

## Authors and Affiliations

• Mireille Fouquet
• 1
• Pierrick Gaudry
• 1
• Robert Harley
• 2
1. 1.LIX, École polytechniquePalaiseau CedexFrance
2. 2.ArgoTechParisFrance