Coppersmith Attack

Coppersmith Attack: Method that breaks RSA when only a small part of the message or key is unknown. The attack exploits not a weakness of cryptographyCryptographyMethods for protecting information through encryption, signatures, and hash functions. as such, but the structure of unpadded messages.

How it works and where it fits

Coppersmith’s method finds small roots of a polynomial modulo a composite number, in practice via lattice reduction with LLL. For RSA this means: if most of a message is known and only a short section is unknown, that section can be modelled as a variable and computed as a small root. It requires a small public exponent and a sufficiently small unknown part, roughly below the 1/e-th fraction of the modulus size. Related variants factor the modulus when partial bits of a prime are known.

Practical security relevance

Only raw RSA without randomised padding is affected. Correctly applied OAEP alone makes the message entirely unpredictable and renders the attack ineffective, regardless of the exponent. In practice the preconditions arise wherever messages follow a fixed format with known prefixes and suffixes — tokens, activation codes, structured identifiers. For assessment it is enough to ask whether padding is used and how large the genuinely unknown part is.

Related concepts

• CryptographyCryptographyMethods for protecting information through encryption, signatures, and hash functions.: Methods for protecting information through encryption, signatures, and hash functions.
• Cryptographic AlgorithmCryptographic AlgorithmA formally defined computation used for encryption, signatures, hashing, or key establishment.: A formally defined computation used for encryption, signatures, hashing, or key establishment.
• EncryptionEncryptionConverts plaintext into unreadable ciphertext using a key.: Converts plaintext into unreadable ciphertext using a key.
• Public Key InfrastructurePublic Key InfrastructureA system of certificates, keys, roles, and processes for digital trust relationships.: A system of certificates, keys, roles, and processes for digital trust relationships.