Abstract
In this last decade, Elliptic Curve Cryptography (ECC) has gained increasing acceptance in the industry and the academic community and has been the subject of several standards. This interest is mainly due to the high level of security with relatively small keys provided by ECC. Indeed, no sub-exponential algorithms are known to solve the underlying hard problem: the Elliptic Curve Discrete Logarithm.
The aim of this work is to explore the possibilities of dedicated hardware implementing the best known algorithm for generic curves: the parallelized Pollard’s ρ method. This problem has specific constraints and requires therefore new architectures. Four different strategies were investigated with different FPGA families in order to provide the best area-time product, according to the capabilities of the chosen platforms. The approach yielding the best throughput over hardware cost ratio is then fully described and was implemented in order to estimate the cost of an attack. Such results should help to improve the accuracy of the security level offered by a given key size, especially for the shorter parameters proposed for resource constrained devices.
Chapter PDF
Similar content being viewed by others
Keywords
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
Agnew, G.B., et al.: An Implementation of Elliptic Curve Cryptosystems over \(F_{{2}^{155}}\). IEEE Journal on Selected Areas in Communications 11(5), 804–813 (1993)
Ansari, B., Hasan, M.A.: High Performance Architecture of Elliptic Curve Scalar Multiplication, CACR Research Report 2006-01 (2006)
Blake, I.F., Seroussi, G., Smart, N.P.: Elliptic Curves in Cryptography, London Mathematical Society. Lecture Notes Series, vol. 265. Cambridge University Press, Cambridge (1999)
Bulens, P., de Dormale, G.M., Quisquater, J.-J.: Hardware for Collision Search on Elliptic Curve over GF(2m). In: SHARCS, Ecrypt Workshop (2006)
Cohen, H.: A course in computational algebraic number theory. Graduate Text in Mathematics, vol. 138. Springer, New York (1993)
Certicom: http://www.certicom.com
Denning, D.E.: Cryptography and Data Security. Addison-Wesley, Reading (1982)
von zur Gathen, J., Shokrollahi, J.: Fast arithmetic for polynomials over \(\mathbb{F}_2\) in hardware. In: IEEE ITW 2006, pp. 107–111 (2006)
Gaudry, P., Hess, F., Smart, N.P.: Constructive and Destructive Facets of Weil Descent on Elliptic Curves. Journal of Cryptology 15(1), 19–46 (2002)
Giry, D., Bulens, P.: http://www.keylength.com
Güneysu, T., Paar, C., Pelzl, J.: Attacking elliptic curve cryptosystems with special-purpose hardware. In: FPGA 2007, pp. 207–215. ACM/SIGDA (2007)
Gutub, A.A.-A.: New Hardware Algorithms and Designs for Montgomery Modular Inverse Computation in Galois Fields GF(p) and GF(2n). Ph.D. Thesis (2002)
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Professional computing. Springer, Heidelberg (2004)
Itoh, T., Tsujii, S.: A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Bases. Information and Computation 78, 171–177 (1988)
Pollard, J.M.: Monte Carlo Methods for Index computation (mod p). Mathematics of computation 32(143), 918–924 (1978)
Kaliski Jr., B.S.: The Montgomery Inverse and its Applications. IEEE Transactions on Computers 44(8), 1064–1065 (1995)
Kumar, S., Paar, C., Pelzl, J., Pfeiffer, G., Schimmler, M.: Breaking Ciphers with COPACOBANA - A Cost-Optimized Parallel Code Breaker. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 101–118. Springer, Heidelberg (2006)
Kim, C.H., Kwon, S., Kim, J.J., et al.: A New Arithmetic Unit in GF(2m) for Reconfigurable Hardware Implementation. In: Cheung, P.Y.K., Constantinides, G.A. (eds.) FPL 2003. LNCS, vol. 2778, pp. 670–680. Springer, Heidelberg (2003)
Kim, M.G., Yu, S.J., Lee, Y.S., Song, J.S.: A Fast Hybrid Arithmetic Unit for Elliptic Curve Cryptosystem in Galois Fields with Prime and Composite Exponents. IEICE Electronics Express 1(1), 13–18 (2004)
Koblitz, N.: Elliptic curve cryptosystems. Math. of computation 48, 203–209 (1987)
Kuon, I., Rose, J.: Measuring the Gap Between FPGAs and ASICs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 62(2) (2007)
Menezes, A.: Elliptic Curve Public Key Cryptosystems. Kluwer, Dordrecht (1993)
Menezes, A., Okamoto, T., Vanstone, S.A.: Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. In: ACM Symp. Theory Computing, pp. 80–89 (1991)
Menezes, A., Teske, E., Weng, A.: Weak fields for ECC. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 366–386. Springer, Heidelberg (2004)
de Dormale, G.M., Quisquater, J.-J.: Iterative Modular Division over GF(2m): Novel Algorithm and Implementations on FPGA. In: Bertels, K., Cardoso, J.M.P., Vassiliadis, S. (eds.) ARC 2006. LNCS, vol. 3985, pp. 370–382. Springer, Heidelberg (2006)
Miller, V.: Uses of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer, Heidelberg (1986)
U.S. Department of Commerce/National Institute of Standards and Technology (NIST), Digital Signature Standard (DSS), FIPS PUB 182-2change1 (2000)
NTL : A Library for doing Number Theory, http://www.shoup.net/
Pelzl, J.: Exact Cost Estimates for Attacks on ECC with Special-Purpose Hardware. In: Workshop on Elliptic Curve Cryptography - ECC 2006 (2006)
Rodríguez-Henríquez, F., Koç, Ç.K.: On Fully Parallel Karatsuba Multipliers for GF(2m). Computer Science and Technology 2003. 394 (2003)
Rodríguez-Henríquez, F., et al.: Parallel Itoh-Tsujii Multiplicative Inversion Algorithm for a Special Class of Trinomials (2006), http://eprint.iacr.org/2006/035.pdf
Certicom Research, SEC 2: Recommended Elliptic Curve Domain Parameters, v1.0 (2000)
Smart, N.P.: A note on the x-coordinate of points on an elliptic curve in characteristic two. Technical Report CSTR-00-019, University of Bristol (December 2000)
Song, L., Parhi, K.K.: Low energy digit-serial/parallel finite field multipliers. Journal of VLSI Signal Processing 19(2), 149–166 (1998)
Stein, J.: Computational problems associated with Racah algebra. Journal of Computational Physics 1, 397–405 (1967)
SWIG : Simplified Wrapper and Interface Generator, http://www.swig.org/
Teske, E.: On Random Walks for Pollard’s rho method. Mathematics of computation 70(234), 809–825 (2000)
van Oorschot, P.C., Wiener, M.J.: Parallel Collision Search with Cryptanalytic Applications. Journal of Cryptology 12, 1–28 (1999)
Wiener, M.J., Zuccherato, R.: Faster Attacks on Elliptic Curve Cryptosystems. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 190–200. Springer, Heidelberg (1999)
Wu, C.H., et al.: High-Speed, Low-Complexity Systolic Designs of Novel Iterative Division Algorithms in GF(2m). IEEE Transaction on Computers 53(3), 375–380 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meurice de Dormale, G., Bulens, P., Quisquater, JJ. (2007). Collision Search for Elliptic Curve Discrete Logarithm over GF(2m) with FPGA. In: Paillier, P., Verbauwhede, I. (eds) Cryptographic Hardware and Embedded Systems - CHES 2007. CHES 2007. Lecture Notes in Computer Science, vol 4727. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74735-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-74735-2_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74734-5
Online ISBN: 978-3-540-74735-2
eBook Packages: Computer ScienceComputer Science (R0)