Abstract
Let N 1 = p 1 q 1 and N 2 = p 2 q 2 be two different RSA moduli. Suppose that
for some t, and q 1 and q 2 are α bit primes. Then May and Ritzenhofen showed that N 1 and N 2 can be factored in quadratic time if
In this paper, we improve this lower bound on t. Namely we prove that N 1 and N 2 can be factored in quadratic time if
Further our simulation result shows that our bound is tight as far as the factoring method of May and Ritzenhofen is used.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
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)
Crépeau, C., Slakmon, A.: Simple backdoors for RSA key generation. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 403–416. Springer, Heidelberg (2003)
Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press (2012)
Lenstra Jr., H.W.: Factoring Integers with Elliptic Curves. Ann. Math. 126, 649–673 (1987)
Lenstra, A.K., Lenstra Jr., H.W.: The Development of the Number Field Sieve. Springer, Heidelberg (1993)
Maurer, U.M.: Factoring with an oracle. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 429–436. Springer, Heidelberg (1993)
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)
Meyer, C.D.: Matrix Analysis and Applied Linear Algebra. Cambridge University Press, Cambridge (2000)
Minkowski, H.: Geometrie der Zahlen. Teubner-Verlag (1896)
Pomerance, C.: The quadratic sieve factoring algorithm. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 169–182. Springer, Heidelberg (1985)
Rivest, R.L., Shamir, A.: Efficient factoring based on partial information. In: Pichler, F. (ed.) EUROCRYPT 1985. LNCS, vol. 219, pp. 31–34. Springer, Heidelberg (1986)
Sarkar, S., Maitra, S.: Approximate Integer Common Divisor Problem Relates to Implicit Factorization. IEEE Transactions on Information Theory 57(6), 4002–4013 (2011)
Young, A., Yung, M.: The prevalence of kleptographic attacks on discrete-log based cryptosystems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 264–276. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kurosawa, K., Ueda, T. (2013). How to Factor N 1 and N 2 When \(p_1=p_2 \bmod 2^t\) . In: Sakiyama, K., Terada, M. (eds) Advances in Information and Computer Security. IWSEC 2013. Lecture Notes in Computer Science, vol 8231. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41383-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-41383-4_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41382-7
Online ISBN: 978-3-642-41383-4
eBook Packages: Computer ScienceComputer Science (R0)