Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
Download-PDF
Abstract:
We address the problem of polynomial time factoring RSA moduli N1 = p1q1 with the help of an oracle. As opposed to other approaches that require an oracle that explicitly outputs bits of p1, we use an oracle that gives only implicit information about p1. Namely, our oracle outputs a different N2 = p2q2 such that p1 and p2 share the t least significant bits. Surprisingly, this implicit information is already sufficient to efficiently factor N1, N2 provided that t is large enough. We then generalize this approach to more than one oracle query.
BibTex:
@INPROCEEDINGS{DBLP:conf/pkc/MayR09,
author = {May, Alexander and Ritzenhofen, Maike},
title = {Implicit Factoring: On Factoring Given Only an Implicit Hint},
booktitle = {Public Key Cryptography},
year = {2009},
pages = {1--14},
crossref = {DBLP:conf/pkc/2009},
bibsource={DBLP, http://dblp.uni-trier.de},
}
crossreferenced publications:
@PROCEEDINGS{DBLP:conf/pkc/2009,
editor = {Jarecki, Stanislaw and Tsudik, Gene},
title = {Public Key Cryptography - PKC 2009, 12th International Workshop on Practice and Theory in Public-Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings},
booktitle = {Public Key Cryptography},
series = {Lecture Notes in Computer Science},
volume = {5443},
year = {2009},
publisher = {Springer},
isbn = {978-3-642-00467-4},
bibsource={DBLP, http://dblp.uni-trier.de},
}