Coppersmith's attack

Class of cryptographic attacks Coppersmith's attack describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method. Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of a prime factor of the secret key is available. RSA basics The public key in the RSA system is a tuple of integers ( N , e ) {\displaystyle (N,e)} , where N is the product of two primes p and q. The secret key is given by an integer d satisfying e d ≡ 1 ( mod ( p − 1 ) ( q − 1 ) ) {\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}} ; equivalently, the secret key may be given by d p ≡ d ( mod p − 1 ) {\displaystyle d_{p}\equiv d{\pmod {p-1}}} and d q ≡ d ( mod q − 1 ) {\displaystyle d_{q}\equiv d{\pmod {q-1}}} if the Chinese remainder theorem is used to improve the speed of decryption, see CRT-RSA. Encryption of a message M produces the ciphertext C ≡ M e ( mod N ) {\displaystyle C\equiv M^{e}{\pmod {N}}} , which can be decrypted using d {\displaystyle d} by computing C d ≡ M ( mod N ) {\displaystyle C^{d}\equiv M{\pmod {N}}} . Low public exponent attack In order to