This paper reports on a chosen ciphertext attack on the use of the RSA algorithm for digital signatures. It also describes a related attack on RSA-based privacy, but the main interest is in signatures. This attack is applied to a working encryption standard, ISO/IEC 9796-2, which has been revised in light of this attack.

The main idea is to choose integers (the messages to be encrypted) with suitable smoothness (small prime divisors) and likelihood. The chosen ciphertexts provide a system of linear equations in exponents tied to the RSA scheme, which can reveal the message. The obstacle to this method is that subexponential running time (in the RSA modulus N) for privacy depends on the nonce &mgr; (m) for the message m being small, which is generally not the case. For signatures, the authors explain how to reduce the nonce size to hash sizes (at most a few hundred bits) by working with !2⁸&mgr;(m) - i ... N, rather than &mgr;(m). All running times are based on the subexponential function L_x(&bgr;) = exp(&bgr;√log(x) ... loglog(x)).

The chief contribution of the paper lies not so much in the analysis of the method discussed, but in the demonstration of its practical limitations.