Attack on Stereotyped Messages (Menu Individual Procedures \ RSA Cryptosystem \ Lattice Based Attacks on RSA)

You can execute the attack using the Attack on Stereotyped Messages dialog.

The lattice-based attack on stereotyped messages allows to decrypt a message encrypted with the RSA Cryptosystem. In this context "stereotyped" means that the encrypted message follows a scheme which is known to the attacker and only a short part of the message is unknown.

Another condition for this attack is that the public key used for the encryption of this message is small (e.g. 3). The attack can e.g. be mounted if always almost the same message is encrypted and only a small part of it changes. (e.g. the date, a password or a PIN).

As with all the lattice-based attacks the search for the unknown part of the message is transformed into a root-finding task. First we study the encryption-function of the RSA-Cryptosystem:

me = c (mod N)
Where m denotes the plaintext of the message and c is the corresponding ciphertext. N is the RSA-modulus and e denotes the public key. By splitting m into a known part mb and an unknown part x the above equation yields:
(mb + x)e - c = 0 (mod N)

In this equation x is the only onknown. The root x0 represents the unknown part and is found by means of lattice reduction.

Coppersmith [Cop96b] presented this attack in 1996 as an application of the root-finding method developed by him.

Sources:

[Cop96b]
Coppersmith, Don: Finding a Small Root of a Univariate Modular Equation. In: Advances in Cryptology – EUROCRYPT ’96, Lecture Notes in Computer Science 1070 (1996), S. 155–165