šŸ–Šļø
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page

Was this helpful?

  1. RSA
  2. Public Exponent Attacks

Small e

If eee is sufficiently small, the exponent is ineffective at encrypting mmm.

Let's say me<Nm^e<Nme<N; in this case, we can simply take the eeeth root of ccc. For example, if e=3e=3e=3, then we can calculate m=c3m = \sqrt[3]cm=3c​.

If me>Nm^e > Nme>N then this is a bit more secure, but we can progressively add more multiples of NNN until the cube root gives us a valid answer:

m=c+kn3m = \sqrt[3]{c + kn}m=3c+kn​

Python

In Python we can use the gmpy3 iroot function:

from gmpy2 import iroot

m = iroot(ct, e)
Previouse=1NextMulti-party RSA with Small e

Last updated 3 years ago

Was this helpful?