1 of 16

Lec 6: Small Private Exponent Attacks

2 of 16

Previously: small public exponent attacks

  • Given some ciphertexts, recover plaintext (“break”)

​

  • This time: Given nothing other than public parameters, factor modulus (“complete break”, padding doesn’t help mitigate)

3 of 16

Use continued fractions to approximate rational numbers

  •  

4 of 16

  •  

5 of 16

  •  

6 of 16

Wiener’s Attack

7 of 16

  •  

8 of 16

  •  

9 of 16

  •  

10 of 16

Wiener’s condition

  •  

11 of 16

Mitigations

  •  

12 of 16

Lattice Interpretation of Wiener’s Attack

13 of 16

  •  

14 of 16

  •  

15 of 16

Homework

  •  

16 of 16

References

  • [Wiener90] Michael J. Wiener. Cryptanalysis of short RSA secret exponents. In IEEE Transactions on Information Theory 36(3).