Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?
Alexander May, Maike Ritzenhofen
In Practice and Theory in Public Key Cryptography (PKC 2008), Lecture Notes in Computer Science Volume 4939, pages 37-46, Springer-Verlag, 2008.
Abstract:
We address the problem of polynomial time solving univariate modular equations with mutually co-prime moduli. For a given system of equations we determine up to which size the common roots can be calculated efficiently. We further determine the minimum number of equations which suffice for a recovery of all common roots. The result that we obtain is superior to Håstad’s original RSA broadcast attack, even if Håstad’s method is combined with the best known lattice technique due to Coppersmith. Namely, our reduction uses a slightly different transformation from polynomial systems to a single polynomial. Thus, our improvement is achieved by optimal polynomial modelling rather than improved lattice techniques. Moreover, we show by a counting argument that our results cannot be improved in general. A typical application for our algorithm is an improved attack on RSA with a smaller number of polynomially related messages.
BibTex:
@INPROCEEDINGS{DBLP:conf/pkc/MayR08,
author = {May, Alexander and Ritzenhofen, Maike},
title = {Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know?},
booktitle = {Public Key Cryptography},
year = {2008},
pages = {37--46},
doi = {10.1007/978-3-540-78440-1_3},
crossref = {DBLP:conf/pkc/2008},
bibsource={DBLP, http://dblp.uni-trier.de},
}
crossreferenced publications:
@PROCEEDINGS{DBLP:conf/pkc/2008,
editor = {Cramer, Ronald},
title = {Public Key Cryptography - PKC 2008, 11th International Workshop on Practice and Theory in Public-Key Cryptography, Barcelona, Spain, March 9-12, 2008. Proceedings},
booktitle = {Public Key Cryptography},
series = {Lecture Notes in Computer Science},
volume = {4939},
year = {2008},
publisher = {Springer},
isbn = {978-3-540-78439-5},
bibsource={DBLP, http://dblp.uni-trier.de},
}