1 of 11

Lec 3: Simple Attacks on RSA

2 of 11

Recap: RSA public-key encryption scheme

  •  

3 of 11

Common Modulus Attack

4 of 11

  •  

5 of 11

Small Public Exponent Attacks

6 of 11

Stereotyped message attack

  •  

7 of 11

Broadcast attack

  •  

8 of 11

Related plaintext attack 1

  •  

9 of 11

Related plaintext attack 2

  •  

10 of 11

  • Both related plaintext attacks assume relation between 2 plaintexts known
  • If relation unknown → can still attack under certain scenarios (later)

​

  • All these attacks can be defeated via random padding
    • No small plaintext anymore
    • Relation between different plaintexts broken

11 of 11

References

  • [Simmons83] Gustavus J. Simmons. A “Weak” Privacy Protocol Using the RSA Crypto Algorithm. In Cryptologia 7(2).
  • [Håstad85] Johan Håstad. On Using RSA with Low Exponent in a Public Key Network. In CRYPTO 1985.
  • [FR95] Matthew K. Franklin and Michael K. Reiter. A Linear Protocol Failure for RSA with Exponent Three. CRYPTO 1995 rump session (oral presentation).
  • [CFPR96] Don Coppersmith, Matthew Franklin, Jacques Patarin, and Michael Reiter. Low-Exponent RSA with Related Messages. In EUROCRYPT 1996.