RSA's Core Idea: Why Factoring Large Numbers Is So Hard

1. Why Should You Care?

In 1977, three MIT researchers—Rivest, Shamir, and Adleman—published something seemingly impossible: an encryption method that lets you publicly publish the encryption key, while only you can decrypt.

This completely changed the game of secure communication.

Before RSA, if Alice wanted to communicate securely with Bob, they had to meet in person to exchange keys. Now, Bob can publish his public key on a website, anyone can send him encrypted messages, and only Bob can read them.

How is this possible? The answer lies in the asymmetry of a mathematical problem.

2. Definition

RSA is an asymmetric encryption algorithm using a pair of mathematically related but different keys:

• Public Key: Can be published, used to encrypt data or verify signatures
• Private Key: Must be kept secret, used to decrypt data or create signatures

RSA’s security is based on the integer factorization problem: given two large primes p and q, computing n = p × q is easy, but given n, finding p and q is extremely hard.

3. Core Intuition: One-Way Functions

Multiplication vs Factorization

Forward (easy):
p = 61
q = 53
n = p × q = 3233

Reverse (hard):
n = 3233
p = ?
q = ?

For small numbers, you can compute by hand. But when numbers get large:

n = 25195908475657893494027183240048398571429282126204
    03202777713783604366202070759555626401852588078440
    69182906412495150821892985591491761845028084891200
    72844992687392807287776735971418347270261896375014
    97182469116507761337985909570009733045974880842840
    17974291006424586918171951187461215151726546322822
    16869987549182422433637259085141865462043576798423
    38718477444792073993423658482382428119816381501067
    48104516603773060562016196762561338441436038339044
    14952634432190114657544454178424020924616515723350
    77870774981712577246796292638635637328991215483143
    81678998850404453640235273819513786365643912120103
    97122822120720357

This is an RSA-2048 modulus
Nobody has been able to factor it

Why Factoring Is So Hard

Try factoring n = 15:
15 ÷ 2 = 7.5 ✗
15 ÷ 3 = 5 ✓ → 15 = 3 × 5

Try factoring n = 2048-bit number:
Need to try approximately √n candidate primes
√(2^2048) ≈ 2^1024
Even trying 10^18 times per second
Would take 10^290 years
The universe is only 1.4 × 10^10 years old

4. How RSA Keys Are Generated

Step 1: Choose Two Large Primes

p = a large prime (e.g., 1024 bits)
q = another large prime (similar size)

Step 2: Compute Modulus n

n = p × q

This n is public
Its bit length is the "2048" in "RSA-2048"

Step 3: Compute Euler’s Totient φ(n)

φ(n) = (p - 1) × (q - 1)

This value must be kept secret!
Knowing φ(n) is equivalent to knowing p and q

Step 4: Choose Public Exponent e

e must satisfy:
1 < e < φ(n)
gcd(e, φ(n)) = 1 (e and φ(n) are coprime)

Common value: e = 65537 = 2^16 + 1
Why? Binary has only two 1s, fast to compute

Step 5: Compute Private Exponent d

d × e ≡ 1 (mod φ(n))

i.e., d is the modular multiplicative inverse of e modulo φ(n)
Can be computed efficiently using extended Euclidean algorithm

The Key Pair

Public key = (n, e)
Private key = (n, d)

In practice, private key also stores p, q, and precomputed values for speed

5. RSA Encryption and Decryption

Encryption (Using Public Key)

Ciphertext C = M^e mod n

M = plaintext (must be less than n)
e = public exponent
n = modulus

Decryption (Using Private Key)

Plaintext M = C^d mod n

C = ciphertext
d = private exponent
n = modulus

Why This Works

C^d mod n
= (M^e)^d mod n
= M^(e×d) mod n
= M^(1 + k×φ(n)) mod n  (because e×d ≡ 1 mod φ(n))
= M × M^(k×φ(n)) mod n
= M × (M^φ(n))^k mod n
= M × 1^k mod n         (Euler's theorem: M^φ(n) ≡ 1 mod n)
= M

6. Numerical Example

# Small number example (for understanding only, real RSA uses much larger numbers)

# Step 1: Choose primes
p = 61
q = 53

# Step 2: Compute n
n = p * q  # n = 3233

# Step 3: Compute φ(n)
phi_n = (p - 1) * (q - 1)  # φ(n) = 60 × 52 = 3120

# Step 4: Choose e
e = 17  # gcd(17, 3120) = 1 ✓

# Step 5: Compute d
# d × 17 ≡ 1 (mod 3120)
# d = 2753 (verify: 17 × 2753 = 46801 = 15 × 3120 + 1)

d = 2753

# Public key: (n=3233, e=17)
# Private key: (n=3233, d=2753)

# Encrypt message M = 123
M = 123
C = pow(M, e, n)  # C = 123^17 mod 3233 = 855

# Decrypt
M_decrypted = pow(C, d, n)  # 855^2753 mod 3233 = 123
print(M_decrypted)  # 123 ✓

7. Why Keys Keep Getting Longer

RSA Key Length Evolution

Why So Long

Symmetric key vs RSA key security levels:

AES-128 (128 bits) ≈ RSA-3072 (3072 bits)
AES-256 (256 bits) ≈ RSA-15360 (15360 bits)

RSA keys need to be much longer than symmetric keys
Because factoring complexity is not exponential
But sub-exponential (number field sieve)

Quantum Threat

Shor's algorithm can factor large numbers in polynomial time
If large-scale quantum computers become reality:
- RSA will be completely broken
- Need to migrate to post-quantum cryptography

Currently:
- Practical quantum computers don't exist yet
- But "harvest now, decrypt later" is a real threat
- Sensitive data should consider post-quantum schemes

8. Practical Limitations of RSA

Message Size Limit

RSA can only encrypt numbers less than n
For RSA-2048:
Maximum plaintext = 2048 bits = 256 bytes

Actually smaller due to padding
After OAEP padding: 256 - 42 = 214 bytes

Performance Issues

RSA encryption: O(e × log³n)
RSA decryption: O(d × log³n)

Because d is large (close to n), decryption is slow
About 1000x slower than AES

This is why RSA doesn't encrypt data directly
Instead encrypts symmetric keys (hybrid encryption)

Importance of Padding

Textbook RSA (without padding) is insecure:

1. Deterministic encryption
   Same plaintext → same ciphertext
   Attackers can build lookup tables

2. Malleability
   C' = C × 2^e mod n
   Decrypts to 2M
   Attackers can manipulate ciphertext

Correct approach: Use OAEP padding
RSA-OAEP is semantically secure

9. Code Example

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

# Generate RSA key pair
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
)
public_key = private_key.public_key()

# Encrypt (using public key)
message = b"Hello, RSA!"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# Decrypt (using private key)
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(f"Original: {message}")
print(f"Ciphertext length: {len(ciphertext)} bytes")
print(f"Decrypted: {plaintext}")

10. Common Misconceptions

11. Summary

Three things to remember:

1. RSA’s security comes from the difficulty of factoring. Multiplication is easy, factoring is hard. This asymmetry allows public keys to be published without revealing private keys.

2. RSA keys need to be much longer than symmetric keys. RSA-2048 provides only about 112 bits of security, equivalent to AES-128 level.

3. RSA isn’t suitable for encrypting data directly. It has size limits and is slow. Real systems use RSA to encrypt symmetric keys, then use symmetric keys to encrypt data.

12. What’s Next

We understand RSA’s mathematical foundation. But in modern systems, RSA’s role is changing. TLS 1.3 even completely removed RSA key exchange.

In the next article, we’ll explore: RSA’s real role in modern systems—why not use RSA to encrypt data directly, RSA’s history and retirement from TLS, and real security issues.