Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptographic Engineering
Published in: Journal of Cryptographic Engineering 4/2016

01-11-2016 | Regular Paper

Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs

Authors: Erich Wenger, Paul Wolfger

Published in: Journal of Cryptographic Engineering | Issue 4/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Computing discrete logarithms takes time. It takes time to develop new algorithms, choose the best algorithms, implement these algorithms correctly and efficiently, keep the system running for several months, and, finally, publish the results. In this paper, we present a highly performant architecture that can be used to compute discrete logarithms of Weierstrass curves defined over binary fields and Koblitz curves using FPGAs. We used the architecture to compute for the first time a discrete logarithm of the elliptic curve sect113r1, a previously standardized binary curve, using 10 Kintex-7 FPGAs. To achieve this result, we investigated different iteration functions, used a negation map, dealt with the fruitless cycle problem, built an efficient FPGA design that processes 900 million iterations per second, and we tended for several months the optimized implementations running on the FPGAs.
previous article Selecting elliptic curves for cryptography: an efficiency and security analysis
next article RunFein: a rapid prototyping framework for Feistel and SPN-based block ciphers

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
1.
Babbage, S., Catalano, D., Cid, C., de Weger, B., Dunkelman, O., Gehrmann, C., Granboulan, L., Güneysu, T., Hermans, J., Lange, T. Lenstra, A., Mitchell, C., Näslund, M., Nguyen, P., Paar, C., Paterson, K., Pelzl, J., Pornin, T., Preneel, B., Rechberger, C., Rijmen, V., Robshaw, M., Rupp, A., Schläffer, M., Vaudenay, S., Vercauteren, F., Ward, M.: ECRYPT II yearly report on algorithms and keysizes (2011-2012). Available online at http://​www.​ecrypt.​eu.​org/​ (2012)
2.
Bailey, D.V., Baldwin, B., Batina, L., Bernstein, D.J., Birkner, P., Bos, J.W., van Damme, G., de Meulenaer, G., Fan, J., Güneysu, T., Gurkaynak, F., Kleinjung, T., Lange, T., Mentens, N., Paar, C., Regazzoni, F., Schwabe, P., Uhsadel, L.: The Certicom Challenges ECC2-X. IACR Cryptology ePrint Archive, Report 2009/466 (2009)
3.
Bailey, D.V., Batina, L., Bernstein, D.J., Birkner, P., Bos, J.W., Chen, H.-C., Cheng, C.-M., van Damme, G., de Meulenaer, G., Perez, L.J.D., Fan, J., Güneysu, T., Gurkaynak, F., Kleinjung, T., Lange, T., Mentens, N., Niederhagen, R., Paar, C., Regazzoni, F., Schwabe, P., Uhsadel, L., Herrewege, A.V., Yang, B.-Y.: Breaking ECC2K-130. IACR Cryptology ePrint Archive, Report 2009/541 (2009)
4.
Barker, E., Roginsky, A.: Recommendation for cryptographic key generation. NIST Special Publ. 800, 133 (2012)
5.
Bernstein, D.J.: Batch binary edwards. In: Advances in Cryptology-CRYPTO 2009, LNCS, vol. 5677, pp. 317–336. Springer, Berlin (2009)
6.
7.
Bernstein, D.J., Lange, T., Schwabe, P.: On the correct use of the negation map in the Pollard rho method. In: Public Key Cryptography—PKC 2011, LNCS, vol. 6571, pp. 128–146. Springer, Berlin (2011)
8.
Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction. Int. J. Appl. Cryptogr. 2(3), 212–228 (2012)MathSciNetCrossRefMATH
9.
Bos, J.W., Kleinjung, T., Lenstra, A.K.: On the use of the negation map in the Pollard rho method. In: Algorithmic Number Theory—ANTS-IX, LNCS, vol. 6197, pp. 66–82. Springer, Berlin (2010)
10.
11.
12.
Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. (eds.): Handbook of Elliptic and Hyperelliptic Curve Cryptography. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton (2006)
13.
de Dormale, G.M., Bulens, P., Quisquater, J.-J.: Collision search for elliptic curve discrete logarithm over GF(\(2^m\)) with FPGA. In: Cryptographic Hardware and Embedded Systems—HES, LNCS, pp. 378–393. Springer, Berlin (2007)
14.
Engels, S.: Breaking ECC2-113: efficient implementation of an optimized attack on a reconfigurable hardware cluster. Master’s thesis, Ruhr Universityät Bochum (2014)
15.
Fan, J., Bailey, D.V., Batina, L., Güneysu, T., Paar, C., Verbauwhede, I.: Breaking elliptic curve cryptosystems using reconfigurable hardware. In: Field Programmable Logic and Applications (FPL), pp. 133–138. IEEE (2010)
16.
Frey, G., Rück, H.-G.: A remark concerning \(m\)-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62(206), 865–874 (1994)
17.
Gallant, R., Lambert, R., Vanstone, S.: Improving the parallelized Pollard lambda search on anomalous binary curves. Math. Comput. Am. Math. Soc. 69(232), 1699–1705 (2000)MathSciNetCrossRefMATH
18.
Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. J. Cryptol. 15(1), 19–46 (2002)MathSciNetCrossRefMATH
19.
20.
Güneysu, T., Paar, C., Pelzl, J.: Attacking elliptic curve cryptosystems with Special-Purpose Hardware. In: ACM/SIGDA Symposium on Field Programmable Gate Arrays (FPGA), pp. 207–215. ACM Press (2007)
21.
Hankerson, D., Vanstone, S., Menezes, A.J.: Guide to Elliptic Curve Cryptography. Springer, Berlin (2004)MATH
22.
23.
Itoh, T., Tsujii, S.: A fast algorithm for computing multiplicative inverses in gf(\(2^m\)) using normal bases. Inf. Comput. 78(3), 171–177 (1988)MathSciNetCrossRefMATH
24.
Judge, L., Mane, S., Schaumont, P.: A Hardware-accelerated ECDLP with high-performance modular multiplication. Int. J. Reconfigurable Comput 2012 (2012)
25.
Mane, S., Judge, L., Schaumont, P.: An integrated prime-field ECDLP hardware accelerator with high-performance modular arithmetic units. In: Reconfigurable Computing and FPGAs—ReConFig, pp. 198–203. IEEE (2011)
26.
Mastrovito, E.D.: VLSI designs for multiplication over finite fields GF(\(2^m\)). In: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp. 297–309. Springer, Berlin (1988)
27.
Menezes, A.J., Okamoto, T., Vanstone, S.A.: Reducing elliptic curve logarithms to logarithms in a finite field. Trans. Inf. Theory 39(5), 1639–1646 (1993)MathSciNetCrossRefMATH
28.
29.
Pohlig, S.C., Hellman, M.E.: An improved algorithm for computing logarithms over \(GF(p)\) and its cryptographic significance. Trans. Inf. Theory 24(1), 106–110 (1978)MathSciNetCrossRefMATH
30.
31.
Rodríguez-Henríquez, F., Koç, Ç.: On fully parallel Karatsuba multipliers for GF(\(2^m\)). J. Comput. Sci. Technol. 1, 405–410 (2003)
32.
Teske, E.: Speeding up Pollard’s rho method for computing discrete logarithms. In: Algorithmic Number Theory, LNCS, vol. 1423, pp. 541–554. Springer, Berlin (1998)
33.
34.
35.
Wenger, E., Wolfger, P.: Solving the discrete logarithm of a 113-bit Koblitz curve with an FPGA cluster. In: Selected Areas in Cryptography—SAC, LNCS, vol. 8781, pp. 363–379. Springer, Berlin (2014)
36.
Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: Selected Areas in Cryptography—SAC, LNCS, vol. 1556, pp. 190–200. Springer, Berlin (1999)
37.
Metadata
Title
Harder, better, faster, stronger: elliptic curve discrete logarithm computations on FPGAs
Authors
Erich Wenger
Paul Wolfger
Publication date
01-11-2016
Publisher
Springer Berlin Heidelberg
Published in
Journal of Cryptographic Engineering / Issue 4/2016
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-015-0108-z

Other articles of this Issue 4/2016

Journal of Cryptographic Engineering 4/2016 Go to the issue

Regular Paper

Hardware attacks: an algebraic approach

Regular Paper

SPA on Rabin variant with public key

Regular Paper

Selecting elliptic curves for cryptography: an efficiency and security analysis

Regular Paper

RunFein: a rapid prototyping framework for Feistel and SPN-based block ciphers

Premium Partner

    Image Credits