In this paper we present a new class of attacks against RSA with low encrypting exponent. They enable the recovery of plaintext messages from their ciphertexts and a known polynomial relationship among the messages, provided that the ciphertexts were created using the same RSA public key with low encrypting exponent. These attacks differ from the low-exponent attacks described by Moore and Hastad and the common modulus attack identified by Simmons, which pertaGiven encryptions of $k$ messages under the same RSA public key with exponent $e$, together with knowledge of a polynomial relation among the messages of degree $\delta$, the goal of the attacks is to recover all messages. Our results were influenced by an attack presented by Franklin and Reiter for the case $k=2$, $e=3$, $\delta = 1$. Starting with this case, we generalize the exponent $e$ in Section 2, the degree $\delta$ in Section 3, and the number of messages $k$ in Section 4. Implications of the attack are considered in Section 5. in only to ciphertexts encrypted under different public keys.
By: Don Coppersmith, Matthew Franklin (AT&T Bell Labs.), Jacques Patarin (CPS Transac, France) and Michael Reiter (AT&T Bell Labs.)
Published in: RC20318 in 1995
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .