Easing Coppersmith Methods Using Analytic Combinatorics: Applications to Public-Key Cryptography with Weak Pseudorandomness

详细信息    查看全文

• 关键词：Coppersmith methods ; Analytic combinatorics ; Cryptanalysis ; Pseudorandom generators ; RSA key Generation ; Encryption padding
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9615
• 期：1
• 页码：36-66
• 全文大小：426 KB
• 参考文献：1.Bauer, A., Coron, J.-S., Naccache, D., Tibouchi, M., Vergnaud, D.: On the broadcast and validity-checking security of pkcs #1 v1.5 encryption. In: Zhou, J., Yung, M. (eds.) ACNS 2010. LNCS, vol. 6123, pp. 1–18. Springer, Heidelberg (2010)CrossRef
  2.Bauer, A., Vergnaud, D., Zapalowicz, J.-C.: Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith’s methods. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 609–626. Springer, Heidelberg (2012)CrossRef
  3.Bellare, M., Brakerski, Z., Naor, M., Ristenpart, T., Segev, G., Shacham, H., Yilek, S.: Hedged public-key encryption: how to protect against bad randomness. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 232–249. Springer, Heidelberg (2009)CrossRef
  4.Bellare, M., Goldwasser, S., Micciancio, D.: “Pseudo-random” number generation within cryptographic algorithms: the DSS case. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 277–291. Springer, Heidelberg (1997)CrossRef
  5.Blackburn, S.R., Gómez-Pérez, D., Gutierrez, J., Shparlinski, I.: Predicting nonlinear pseudorandom number generators. Math. Comput. 74(251), 1471–1494 (2005)CrossRef MATH
  6.Blackburn, S.R., Gómez-Pérez, D., Gutierrez, J., Shparlinski, I.: Reconstructing noisy polynomial evaluation in residue rings. J. Algorithms 61(2), 47–59 (2006)CrossRef MathSciNet MATH
  7.Bleichenbacher, D.: Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 1–12. Springer, Heidelberg (1998)CrossRef
  8.Blömer, J., May, A.: A tool kit for finding small roots of bivariate polynomials over the integers. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 251–267. Springer, Heidelberg (2005)CrossRef
  9.Boyar, J.: Inferring sequences produced by a linear congruential generator missing low-order bits. J. Cryptology 1(3), 177–184 (1989)CrossRef MathSciNet MATH
  10.Boyar, J.: Inferring sequences produced by pseudo-random number generators. J. ACM 36(1), 129–141 (1989)CrossRef MathSciNet MATH
  11.Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178–189. Springer, Heidelberg (1996)CrossRef
  12.Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155–165. Springer, Heidelberg (1996)CrossRef
  13.Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10(4), 233–260 (1997)CrossRef MathSciNet MATH
  14.Coron, J.-S., Joye, M., Naccache, D., Paillier, P.: New attacks on PKCS#1 v1.5 encryption. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 369–381. Springer, Heidelberg (2000)CrossRef
  15.Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)CrossRef MATH
  16.Fouque, P.-A., Tibouchi, M., Zapalowicz, J.-C.: Recovering private keys generated with weak PRNGs. In: Stam, M. (ed.) IMACC 2013. LNCS, vol. 8308, pp. 158–172. Springer, Heidelberg (2013)CrossRef
  17.Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)CrossRef MathSciNet MATH
  18.Herrmann, M., May, A.: Attacking power generators using unravelled linearization: when do we output too much? In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 487–504. Springer, Heidelberg (2009)CrossRef
  19.Hofheinz, D., Jager, T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 590–607. Springer, Heidelberg (2012)CrossRef
  20.Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
  21.Jager, T., Schinzel, S., Somorovsky, J.: Bleichenbacher’s attack strikes again: breaking PKCS#1 v1.5 in XML encryption. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012. LNCS, vol. 7459, pp. 752–769. Springer, Heidelberg (2012)CrossRef
  22.Jochemsz, E., May, A.: A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 267–282. Springer, Heidelberg (2006)CrossRef
  23.Joux, A., Stern, J.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptology 11(3), 161–185 (1998)CrossRef MathSciNet MATH
  24.Kaliski, B.: PKCS #1: RSA Encryption Version 1.5. RFC 2313, Internet Engineering Task Force, March 1998. http://​www.​rfc-editor.​org/​rfc/​rfc2313.​txt
  25.Koshiba, T.: On sufficient randomness for secure public-key cryptosystems. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 34–47. Springer, Heidelberg (2002)CrossRef
  26.Lipton, R.J., Regan, K.W.: People, Problems, and Proofs - Essays from Gödel’s Lost Letter: 2010. Springer, Berlin (2013)CrossRef
  27.May, A.: Using lll-reduction for solving RSA and factorization problems. In: Nguyen, P.Q., Vallée, B. (eds.) The LLL Algorithm - Survey and Applications. Information Security and Cryptography, pp. 315–348, Springer, Heidelberg (2010). http://​dx.​org/​10.​1007/​978-3-642-02295-1
  28.May, A., Ritzenhofen, M.: Solving systems of modular equations in one variable: how many RSA-encrypted messages does eve need to know? In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 37–46. Springer, Heidelberg (2008)CrossRef
  29.May, A., Ritzenhofen, M.: Implicit factoring: on polynomial time factoring given only an implicit hint. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 1–14. Springer, Heidelberg (2009)CrossRef
  30.Ritzenhofen, M.: On efficiently calculating small solutions of systems of polynomial equations: lattice-based methods and applications to cryptography. Ph.D. thesis, Ruhr University Bochum (2010). http://​www
  s.​ub.​ruhr-uni-bochum.​de/​netahtml/​HSS/​Diss/​RitzenhofenMaike​/​
  31.Stern, J.: Secret linear congruential generators are not cryptographically secure. In: 28th FOCS, pp. 421–426. IEEE Computer Society Press, October 1987
  
• 作者单位：Fabrice Benhamouda (17)
  Céline Chevalier (18)
  Adrian Thillard (17) (19)
  Damien Vergnaud (17)
  
  17. ENS, CNRS, INRIA, and PSL, Paris, France
  18. CRED, Université Panthéon-Assas, Paris, France
  19. ANSSI, Paris, France
  
• 丛书名：Public-Key Cryptography ᾿PKC 2016
• ISBN：978-3-662-49387-8
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

The Coppersmith methods is a family of lattice-based techniques to find small integer roots of polynomial equations. They have found numerous applications in cryptanalysis and, in recent developments, we have seen applications where the number of unknowns and the number of equations are non-constant. In these cases, the combinatorial analysis required to settle the complexity and the success condition of the method becomes very intricate.