Course contentsShow
← Mathematics
Lesson 2770 of 3,12154. Number TheoryFree lesson

Security and Practical Considerations

Explore why factoring n is hard, the importance of large primes, and basic attacks and safeguards in RSA.

Security and Practical Considerations

You'll learn why RSA is secure in practice, what makes it vulnerable, and how to protect against attacks.

Why Factoring n is Hard

RSA's security rests on a simple fact: factoring large numbers is computationally infeasible. When you publish n = pq as part of your public key, an attacker who could factor n back into p and q could then compute φ(n) = (p-1)(q-1) themselves. With φ(n) and your public exponent e, they could use the Extended Euclidean Algorithm to find your private key d.

The good news? Factoring a 2048-bit number (about 617 decimal digits) would take current supercomputers billions of years. This is why we call it a one-way function: easy to multiply, astronomically hard to reverse.

The Importance of Large Primes

Size matters. If you choose small primes like p = 61 and q = 53, factoring n = 3233 takes milliseconds. Real RSA uses primes that are each at least 1024 bits long (making n at least 2048 bits). These primes must also be randomly chosen and truly prime (verified by probabilistic tests).

Basic Attacks and Safeguards

Common vulnerabilities:

  • Small d attack: If your private exponent is too small, the Wiener attack can recover it. Always ensure d is large.
  • Common modulus attack: Never encrypt the same message to multiple recipients using the same n.
  • Timing attacks: Measuring how long decryption takes can leak information about d. Use constant-time algorithms.
  • Padding: Never encrypt raw messages—always use padding schemes (like OAEP) to prevent mathematical attacks.

Key Takeaway: RSA's security depends on using sufficiently large, randomly chosen primes and following best practices like proper padding and avoiding key reuse—the mathematical elegance means nothing without careful implementation.