nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Post-quantum RSA

verfasst von : Daniel J. Bernstein, Nadia Heninger, Paul Lou, Luke Valenta

Erschienen in: Post-Quantum Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today’s computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor’s algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Key Recovery Attack for ZHFE

Nächstes Kapitel A Low-Resource Quantum Factoring Algorithm

Nur mit Berechtigung zugänglich

If the goal is merely to protect past traffic against complete key theft (“forward secrecy”) then a user can obtain a speedup by generating many RSA keys in advance, and erasing each key soon after it is first used. But erasing each key soon after it has been generated is sometimes advertised as helping protect future traffic against limited types of compromise. Furthermore, batching across many users provides larger speedups.

— (no editor): Second International Conference on Quantum, Nano, and Micro Technologies, ICQNM 2008, 10–15 February 2008, Sainte Luce, Martinique, French Caribbean. IEEE Computer Society (2008). See [17]

— (no editor): Kernel BUG at mm/huge_memory.c:1798! (2012). http://linux-kernel.2935.n7.nabble.com/kernel-BUG-at-mm-huge-memory-c-1798-td574029.html. Citations in this document: §A

— (no editor): Proceedings of the 23rd USENIX Security Symposium, 20–22 August 2014, San Diego, CA, USA. USENIX (2014). See [19]

Abdalla, M., Barreto, P.S.L.M. (eds.): LATINCRYPT 2010. LNCS, vol. 6212. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14712-8. See [11]MATH

Barbulescu, R., Bos, J.W., Bouvier, C., Kleinjung, T., Montgomery, P.L.: Finding ECM-friendly curves through a study of Galois properties. In: ANTS-X: Proceedings of the Tenth Algorithmic Number Theory Symposium, pp. 63–86 (2013). http://msp.org/obs/2013/1/p04.xhtml. Citations in this document: §2

Beauchemin, P., Brassard, G., Crépeau, C., Goutier, C., Pomerance, C.: The generation of random numbers that are probably prime. J. Cryptol. 1, 53–64 (1988). https://math.dartmouth.edu/~carlp/probprime.pdf. Citations in this document: §3

Bellare, M., Kane, D., Rogaway, P.: Big-key symmetric encryption: resisting key exfiltration. In: [44], pp. 373–402 (2016). https://eprint.iacr.org/2016/541.pdf. Citations in this document: §1

Bernstein, D.J.: How to find small factors of integers (2002). https://cr.yp.to/papers.html#sf. Citations in this document: §3

Bernstein, D.J.: How to find smooth parts of integers (2004). https://cr.yp.to/papers.html#smoothparts. Citations in this document: §3, §3

10.

Bernstein, D.J.: Fast multiplication and its applications. In: [18], pp. 325-384 (2008). https://cr.yp.to/papers.html#multapps. Citations in this document: §3,§3,§3

11.

Bernstein, D.J., Birkner, P., Lange, T.: Starfish on strike. In: LATINCRYPT 2010 [4], pp. 61–80 (2010). https://eprint.iacr.org/2010/367. Citations in this document: §2

12.

Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves (2008). https://eprint.iacr.org/2008/016. Citations in this document: §2, §2

13.

Boneh, D., Durfee, G., Howgrave-Graham, N.: Factoring \(N=p^r q\) for large \(r\). In: [54], pp. 326–337 (1999). http://crypto.stanford.edu/~dabo/abstracts/prq.html. Citations in this document: §3

14.

Bos, J.W., Kleinjung, T.: ECM at work pages. In: ASIACRYPT 2012 [53], pp. 467–484 (2012). https://eprint.iacr.org/2012/089. Citations in this document: §2

15.

Boukhonine, S.: Cryptography: a security tool of the information age (1998). https://pdfs.semanticscholar.org/3932/8253d692f791b37c425e776f6cee0b8c3e56.pdf. Citations in this document: §1

16.

Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., Salvail, L.: Merkle puzzles in a quantum world. In: CRYPTO 2011 [45], pp. 391–410 (2011). https://arxiv.org/abs/1108.2316. Citations in this document: §1,§1

17.

Brassard, G., Salvail, L.: Quantum Merkle puzzles. In: ICQNM 2008 [1], pp. 76–79 (2008). Citations in this document: §1

18.

Buhler, J.P., Stevenhagen, P.: Surveys in Algorithmic Number Theory. Mathematical Sciences Research Institute Publications, vol. 44. Cambridge University Press, New York (2008). See [10]MATH

19.

Checkoway, S., Fredrikson, M., Niederhagen, R., Everspaugh, A., Green, M., Lange, T., Ristenpart, T., Bernstein, D.J., Maskiewicz, J., Shacham, H.: On the practical exploitability of Dual EC in TLS implementations. In: USENIX Security 2014 [3] (2014). https://projectbullrun.org/dual-ec/index.html. Citations in this document: §1

20.

Ekert, A.: Quantum cryptoanalysis–introduction (2010). http://www.qi.damtp.cam.ac.uk/node/69. Citations in this document: §1

21.

Fürer, M.: Faster integer multiplication. In: [30], pp. 57–66 (2007). https://www.cse.psu.edu/~furer/. Citations in this document: §3

22.

Gélin, A., Kleinjung, T., Lenstra, A.K.: Parametrizations for families of ECM-friendly curves (2016). https://eprint.iacr.org/2016/1092. Citations in this document: §2

23.

Goldwasser, S. (ed.): 35th Annual IEEE Symposium on the Foundations of Computer Science. Proceedings of the IEEE Symposium Held in Santa Fe, NM, 20–22 November 1994. IEEE (1994). ISBN 0–8186-6580-7. MR 98h:68008. See [48]

24.

Goodin, D.: Symantec employees fired for issuing rogue HTTPS certificate for Google (2015). https://arstechnica.com/security/2015/09/symantec-employees-fired-for-issuing-rogue-https-certificate-for-google/. Citations in this document: §1

25.

Granlund, T.: GMP integer size limitation (2012). https://gmplib.org/list-archives/gmp-discuss/2012-April/005020.html. Citations in this document: §A

26.

Granlund, T., The GMP Development Team: GNU MP: The GNU Multiple Precision Arithmetic Library (2015). https://gmplib.org/. Citations in this document: §4

27.

Harvey, D., van der Hoeven, J., Lecerf, G.: Even faster integer multiplication. J. Complex. 36, 1–30 (2016). https://arxiv.org/abs/1407.3360. Citations in this document: §3MathSciNetCrossRefMATH

28.

Harvey, D., van der Hoeven, J., Lecerf, G.: Fast polynomial multiplication over \({ F}_{2^{60}}\). In: Proceedings of ISSAC 2016 (2016, to appear). https://hal.archives-ouvertes.fr/hal-01265278. Citations in this document: §4, §4

29.

ID Quantique: Future-proof data confidentiality with quantum cryptography (2005). https://classic-web.archive.org/web/20070728200504/, http://www.idquantique.com/products/files/vectis-future.pdf. Citations in this document: §4

30.

Johnson, D.S., Feige, U. (eds.): Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, 11–13 June 2007. Association for Computing Machinery, New York (2007). ISBN 978-1-59593-631-8. See [21]

31.

Kim, S.H., Pomerance, C.: The probability that a random probable prime is composite. Math. Comput. 53, 721–741 (1989). https://math.dartmouth.edu/~carlp/PDF/paper72.pdf. Citations in this document: §4MathSciNetCrossRefMATH

32.

Krawczyk, H. (ed.): CRYPTO 1998. LNCS, vol. 1462. Springer, Heidelberg (1998). doi:10.1007/BFb0055715. ISBN 3-540-64892-5. MR 99i:94059. See [52]MATH

33.

Lehmer, D.H., Powers, R.E.: On factoring large numbers. Bull. Am. Math. Soc. 37, 770–776 (1931). Citations in this document: §2MathSciNetCrossRefMATH

34.

Lenstra, A.K., Lenstra Jr., H.W. (eds.): The Development of the Number Field Sieve. LNM, vol. 1554. Springer, Heidelberg (1993). doi:10.1007/BFb0091534. ISBN 3-540-57013-6. MR 96m:11116. Citations in this document: §2MATH

35.

Lenstra Jr., H.W.: Factoring integers with elliptic curves. Ann. Math. 126, 649–673 (1987). MR 89g:11125. Citations in this document: §2MathSciNetCrossRefMATH

36.

Lenstra Jr., H.W., Tijdeman, R.: Computational Methods in Number Theory I. Mathematical Centre Tracts, vol. 154. Mathematisch Centrum, Amsterdam (1982). ISBN 90-6196-248-X. MR 84c:10002. See [41]MATH

37.

Leprévost, F.: The end of public key cryptography or does God play dices? PricewaterhouseCoopers Cryptogr. Centre Excell. Q. J. (1999). http://tinyurl.com/jdkkxc3. Citations in this document: §2

38.

Maurer, U.M.: Fast generation of prime numbers and secure public-key cryptographic parameters. J. Cryptol. 8, 123–155 (1995). http://link.springer.com/article/10.1007/BF00202269. Citations in this document: §2MathSciNetCrossRefMATH

39.

Pollard, J.M.: Theorems on factorization and primality testing. Proc. Camb. Philos. Soc. 76, 521–528 (1974). MR 50 #6992. Citations in this document: §2MathSciNetCrossRefMATH

40.

Pollard, J.M.: A Monte Carlo method for factorization. BIT 15, 331–334 (1975). MR 52 #13611. Citations in this document: §2MathSciNetCrossRefMATH

41.

Pomerance, C.: Analysis and comparison of some integer factoring algorithms. In: [36], pp. 89–139 (1982). MR 84i:10005. Citations in this document: §2

42.

Rabin, M.O.: Digitalized signatures and public-key functions as intractableas factorization. Technical report 212, MIT Laboratory for Computer Science (1979). https://archive.org/details/bitsavers_mitlcstrMI_457188. Citations in this document: §3

43.

Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978). ISSN 0001-0782. Citations in this document: §3MathSciNetCrossRefMATH

44.

Robshaw, M., Katz, J. (eds.): CRYPTO 2016. LNCS, vol. 9814. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53018-4. ISBN 978-3-662-53017-7. See [7]MATH

45.

Rogaway, P. (ed.): CRYPTO 2011. LNCS, vol. 6841. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22792-9. See [16]MATH

46.

Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7, 281–292 (1971). http://link.springer.com/article/10.1007/BF02242355. Citations in this document: §3MathSciNetCrossRefMATH

47.

Shamir, S.: RSA for paranoids. CryptoBytes 1 (1995). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.5763&rep=rep1&type=pdf. Citations in this document: §1,§3

48.

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: [23], pp. 124–134 (1994). See also newer version [49]. MR 1489242. Citations in this document: §1

49.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer (1995). See also older version [48]; see also newer version [50]. https://arxiv.org/abs/quant-ph/9508027v2

50.

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484–1509 (1997). See also older version [49]. MR 98i:11108MathSciNetCrossRefMATH

51.

Shoup, V.: A proposal for an ISO standard for public key encryption (version 2.1) (2001). http://www.shoup.net/papers. Citations in this document: §3

52.

Takagi, T.: Fast RSA-type cryptosystem modulo \(p^{k}q\). In: [32], pp. 318–326 (1998). http://imi.kyushu-u.ac.jp/takagi/takagi/publications/cr98.ps. Citations in this document: §1, §3

53.

Wang, X., Sako, K. (eds.): ASIACRYPT 2012. LNCS, vol. 7658. Springer, Heidelberg (2012). doi:10.1007/978-3-642-34961-4. ISBN 978-3-642-34960-7. See [14]

54.

Wiener, M. (ed.): CRYPTO 1999. LNCS, vol. 1666. Springer, Heidelberg (1999). doi:10.1007/3-540-48405-1. ISBN 3-540-66347-9. MR 2000h:94003. See [13]MATH

55.

Williams, H.C.: A \(p+1\) method of factoring. Math. Comput. 39, 225–234 (1982). MR 83h:10016. Citations in this document: §2MathSciNetMATH

56.

Zalka, C.: Fast versions of Shor’s quantum factoring algorithm (1998). https://arxiv.org/abs/quant-ph/9806084. Citations in this document: §2, §4

57.

Zimmermann, P.: About memory-usage of mpz_mul (2016). https://gmplib.org/list-archives/gmp-discuss/2016-June/006009.html. Citations in this document: §A

Titel: Post-quantum RSA
verfasst von: Daniel J. Bernstein
Nadia Heninger
Paul Lou
Luke Valenta
Verlag: Springer International Publishing
Buch: Post-Quantum Cryptography
Print ISBN: 978-3-319-59878-9

Electronic ISBN: 978-3-319-59879-6

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-59879-6_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner