Top

Applicable Algebra in Engineering, Communication and Computing

Published in:

09-04-2016 | Original Paper

Computational hardness of IFP and ECDLP

Authors: Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Tetsuya Izu

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 6/2016

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

search-config

AI-assisted search

Off

Abstract

The RSA cryptosystem and elliptic curve cryptography (ECC) have been used practically and widely in public key cryptography. The security of RSA and ECC respectively relies on the computational hardness of the integer factorization problem (IFP) and the elliptic curve discrete logarithm problem (ECDLP). In this paper, we give an estimate of computing power required to solve each problem by state-of-the-art of theory and experiments. By comparing computing power required to solve the IFP and the ECDLP, we also estimate bit sizes of the two problems that can provide the same security level.

previous article Three classes of binary linear codes with good parameters

next article Undeniable signature scheme based over group ring

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 "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

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

The authors in [8] reported that it needs 218.75 cycles for \(5{\mathbf {M}}\) with their software, which costs more almost 20 cycles than our implementation. This difference is due to the property that our software has much faster processing performance of the multiplication operation than their software (the CPU used in their implementation only has the 16-bit \(\times \) 16-bit \(\rightarrow \) 32-bit multiplication operation).

The authors in [5] reported that it needs 94 cycles per multiplication and hence \(94 \times 5 = 470\) cycles for \(5 {\mathbf {M}}\) with their software. Their implementation costs more almost 90 cycles than our implementation. This seems to be mainly due to the fact that the CPU used in our implementation has three throughputs while the CPU used in their implementation has only two throughputs.

ANSI X9.62: Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA) (1999)

Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K., Osvik, D.A.: A kilobit special number field sieve factorization. In: Advances in Cryptology-ASIACRYPT 2007. Springer LNCS 4833, pp. 1-12 (2007)

Aoki, K., Kida, Y., Shimoyama T., Ueda, H.: GNFS factoring statistics of RSA-100, 110, ..., 150, IACR ePrint Archive, 2004/095. Available at https://eprint.iacr.org/2004/095 (2004)

Bailey, D., Baldwin, B., Batina, L., Bernstein, D., Birkner, P., Bos, J., 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 ePrint Archive, 2009/466. Available at http://eprint.iacr.org/2009/466 (2009)

Bailey et al., D.: Breaking ECC2K-130, IACR ePrint Archive, 2009/541. Available at http://eprint.iacr.org/2009/541 (2009)

Bahr, F., Böhm, M., Franke J., Kleinjung, T.: Factorization of RSA-200. Available at http://www.loria.fr/ zimmerma/records/rsa200 (2005)

Bernstein, D., Chen, H., Cheng, C., Lange, T., Niederhagen, R., Schwabe, P., Yang, B.: ECC2K-130 on NVIDIA GPUs. In: Progress in Cryptology-INDOCRYPT 2010. Springer LNCS 6498, pp. 328-344 (2010)

Bernstein, D., Lange, T., Schwabe, P.: On the correct use of the negation map in the Pollard rho method. In: Public Key Cryptography-PKC 2011. Springer LNCS 6571, pp. 128-146 (2011)

Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)CrossRefMATH

10.

Brent, R., Pollard, J.: Factorization of the eighth Fermat number. Math. Comput. 36, 627–630 (1981)MathSciNetCrossRefMATH

11.

Canfield, E.R., Erdos, P., Pomerance, C.: On a problem of Oppenheim concerning factorisatio numerorum. J. Number Theory 17, 1–28 (1983)MathSciNetCrossRefMATH

12.

Certicom: Certicom ECC challenge. Available at http://www.certicom.jp/images/pdfs/cert_ecc_challenge (1997)

13.

Certicom: Curves list. Available at http://www.certicom.jp/index.php/curves-list (1997)

14.

Childers, G.: Factorization of a \(1061\)-bit number by the special number field sieve. In: IACR ePrint Archive, 2012/144. Available at http://eprint.iacr.org/2012/444 (2012)

15.

CRYPTREC: CRYPTREC Report 2006. Available at http://www.cryptrec.go.jp/report/c06_wat_final (2006)

16.

ECRYPT II: ECRYPT II report on key sizes. Available at http://www.keylength.com/en/3/ (2011)

17.

EPFL IC LACAL.: PlayStation 3 computing breaks \(2^{60}\) barrier 112-bit prime ECDLP solved. Available at http://lacal.epfl.ch/112bit_prime (2009)

18.

Faugère, J.C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Advances in Cryptology-EUROCRYPT 2012 Springer LNCS 7237, pp. 27-44 (2012)

19.

Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)CrossRefMATH

20.

Galbraith, S.D., Ruprail, R.S.: Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval. In: Public Key Cryptography-PKC 2010. Springer LNCS 6056, pp. 368-386 (2010)

21.

Gallant, R., Lambert, R., Vanstone, S.: Improving the parallelized Pollard lambda search on binary anomalous curves. Math. Comput. 69, 1699–1705 (2000)MathSciNetCrossRefMATH

22.

Güneysu, T., Kasper, T., Novotný, M., Paar, C., Rupp, A.: Cryptanalysis with COPACOBANA. Trans. Comput. 57, 1498–1513 (2008)MathSciNetCrossRef

23.

Granlund, T.: Instruction latencies and throughput for AMD and Intel x86 processors (2012-02-13 version). Available at http://gmplib.org/ tege/x86-timing

24.

Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Professional Computing, New York (2004)MATH

25.

Harley, R.: Elliptic curve discrete logarithms project. Available at http://pauillac.inria.fr/ harley/ecdl/

26.

Izu, T., Kogure, J., Shimoyama, T.: CAIRN 2: an FPGA implementation of the sieving step in the number field sieve method. Cryptogr. Hardw. Embed. Syst. 2007, 364–377 (2007)

27.

Kleinjung, T.: Estimates for factoring 1024-bit integers. In: Securing Cyberspace: Applications and Foundations of Cryptography and Computer Security, Workshop IV: Special purpose hardware for cryptography: Attacks and Applications, slides are available at http://www.ipam.ucla.edu/schedule.aspx?pc=scws4 (2006)

28.

Kleinjung, T.: Evaluation of complexity of mathematical algorithms. CRYPTREC technical report No. 0601 in FY2006. Available at http://www.cryptrec.jp/estimation.html (2007)

29.

Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus, Advances in Cryptology-CRYPTO 2010. Springer LNCS 6223, pp. 333-350 (2010)

30.

Kleinjung, T., Bos, J.W., Lenstra, A.K., Osvik, D.A., Aoki, K., Contini, S., Franke, J., Thomé, E., Jermini, P., Thiémard, M., Leyland, P., Montgomery, P., Timofeev, A., Stockinger, H.: A heterogeneous computing environment to solve the 768-bit RSA. Clust. Comput. 15(1), 53–68 (2012)CrossRef

31.

Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)MathSciNetCrossRefMATH

32.

Lenstra, A., Lenstra, H., Manasse M., Pollard, J.: The number field sieve. In: Symposium on Theory of Computing-STOC 1990, ACM, pp. 564-572 (1990)

33.

Lenstra, A., Verheul, E.: Selecting cryptographic key sizes. J. Cryptol. 14, 255–293 (2001)MathSciNetCrossRefMATH

34.

Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39, 1639–1646 (1993)MathSciNetCrossRefMATH

35.

Miller, V.S.: Use of elliptic curves in cryptography. In: Advances in Cryptology-CRYPTO 1985. Springer LNCS 218, pp. 417-426 (1986)

36.

NESSIE: NESSIE security report, February 2003

37.

NIST Special publication 800-57. Available at http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007

38.

Orman, H., Hoffman, P.: Determining strengths for public keys used for exchanging symmetric keys. IETF RFC 3766/BCP 86, April 2004

39.

Pollard, J.: Monte Carlo methods for index computation mod \(p\). Math. Comput. 32, 918–924 (1978)MathSciNetMATH

40.

Rivest, R., Shamir, A., Adelman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978)MathSciNetCrossRefMATH

41.

RSA Laboratories: A cost-based security analysis of symmetric and asymmetric key lengths. RSA Labs Bulletin, no. 13, April 2000 (Revised November 2001)

42.

RSA Laboratories: The RSA challenge numbers. Available at http://japan.emc.com/emc-plus/rsa-labs/historical/the-rsa-challenge-numbers.htm

43.

Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. Sancti Pauli 47, 81–92 (1998)MathSciNetMATH

44.

Semaev, I.: Evaluation of discrete logarithms in a group of \(p\)-torsion points of an elliptic curve in characteristic \(p\). Math. Comput. 67, 353–356 (1998)MathSciNetCrossRefMATH

45.

Shamir, A.: Factoring large numbers with the TWINKLE device (extended abstract). In: Cryptographic Hardware and Embedded Systems-CHES 1999. Springer LNCS 1717, pp. 2-12 (1999)

46.

Shamir, A., Tromer, E.: Factoring large numbers with the TWIRL Device. In: Advances in Cryptology-CRYPTO 2003. Springer LNCS 2729, pp. 1-26 (2003)

47.

Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12, 110–125 (1999)MathSciNetMATH

48.

Teske, E.: Speeding up Pollard’s rho method for computing discrete logarithms. In: Algorithmic Number Theory-ANTS III. Springer LNCS 1423, pp. 541-554 (1998)

49.

Teske, E.: On random walks for Pollard’s rho method. Math. Comput. 70, 809–825 (2001)MathSciNetCrossRefMATH

50.

van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12, 1–28 (1999)MathSciNetCrossRefMATH

51.

Wiener, M.J., Zuccherato, R.J.: Fast attacks on elliptic curve cryptosystems. In: Selected Areas in Cryptology-SAC 1998. Springer LNCS 1556, pp. 190-200 (1999)

52.

Yasuda, M., Izu, T., Shimoyama, T., Kogure, J.: On random walks of Pollard’s rho method for the ECDLP on Koblitz curves. J. Math. Ind. 3(2011B—-3), 107–112 (2011)MathSciNetMATH

53.

Yasuda, M., Shimoyma, T., Kogure, J., Izu, T.: On the strength comparison of the ECDLP and the IFP. In: Security and Cryptography for Networks-SCN 2012. Springer LNCS 7485, pp. 302-325 (2012)

Title: Computational hardness of IFP and ECDLP
Authors: Masaya Yasuda
Takeshi Shimoyama
Jun Kogure
Tetsuya Izu
Publication date: 09-04-2016
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 6/2016
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-016-0291-x

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 6/2016

Undeniable signature scheme based over group ring

Three classes of binary linear codes with good parameters

Dynamics of linear systems over finite commutative rings

Computing Tjurina stratifications of $$\mu $$ μ -constant deformations via parametric local cohomology systems

Premium Partner