RSA Cryptography

Public-Key Cryptography

Symmetric vs. Asymmetric

Symmetric (Private Key):

• Same key for encryption and decryption
• Key must be shared secretly
• Fast but key distribution is hard

Asymmetric (Public Key):

• Different keys: public (encrypt) and private (decrypt)
• Public key can be shared openly
• RSA is the most famous example

RSA Algorithm

Key Generation

1. Choose two large distinct primes $p$ and $q$
2. Compute $n = pq$ (the modulus)
3. Compute $\phi(n) = (p-1)(q-1)$
4. Choose $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$
5. Compute $d = e^{-1} \pmod{\phi(n)}$

Public key: $(n, e)$ Private key: $(n, d)$

Encryption

To encrypt message $M$ (as integer, $0 \leq M < n$): $C = M^e \pmod{n}$

Decryption

To decrypt ciphertext $C$: $M = C^d \pmod{n}$

Why It Works

$C^d = (M^e)^d = M^{ed} \pmod{n}$

Since $ed \equiv 1 \pmod{\phi(n)}$: $ed = 1 + k\phi(n)$

By Euler's theorem (if $\gcd(M, n) = 1$): $M^{ed} = M \cdot M^{k\phi(n)} = M \cdot (M^{\phi(n)})^k \equiv M \cdot 1^k = M \pmod{n}$

Example

Key Generation

• $p = 61$, $q = 53$
• $n = 61 \times 53 = 3233$
• $\phi(n) = 60 \times 52 = 3120$
• Choose $e = 17$ (coprime to 3120)
• $d = 17^{-1} \pmod{3120} = 2753$

Public key: $(3233, 17)$ Private key: $(3233, 2753)$

Encryption

Message: $M = 65$ $C = 65^{17} \pmod{3233} = 2790$

Decryption

$M = 2790^{2753} \pmod{3233} = 65$

Security of RSA

Based on Factoring

Security relies on the difficulty of factoring $n = pq$.

If attacker can factor $n$, they can compute $\phi(n)$ and find $d$.

Key Size

• 512-bit: Insecure (can be factored)
• 1024-bit: Weak, not recommended
• 2048-bit: Currently standard
• 4096-bit: High security

Attacks

Factoring attacks: Number Field Sieve, Quadratic Sieve

Side-channel attacks: Timing, power analysis

Small exponent attacks: If $e$ is too small and same message sent to multiple recipients

Digital Signatures

RSA can also create digital signatures.

Signing

Sign message $M$ with private key: $S = M^d \pmod{n}$

Verification

Verify signature with public key: $M' = S^e \pmod{n}$

If $M' = M$, signature is valid.

Why It Works

Only the private key holder can create $S$ such that $S^e = M$.

Practical Considerations

Message Padding

Never encrypt raw messages. Use padding schemes like:

• OAEP (Optimal Asymmetric Encryption Padding)
• PKCS#1

Hybrid Encryption

RSA is slow for large data. In practice:

1. Generate random symmetric key $K$
2. Encrypt data with $K$ (using AES, etc.)
3. Encrypt $K$ with RSA

Fast Exponentiation

Use square-and-multiply algorithm for $M^e \pmod{n}$.

Chinese Remainder Theorem Speedup

For decryption, compute: $M_p = C^{d \mod (p-1)} \pmod{p}$ $M_q = C^{d \mod (q-1)} \pmod{q}$

Then combine using CRT. About 4× faster.

Mathematical Prerequisites

Euler's Theorem

$a^{\phi(n)} \equiv 1 \pmod{n}$ when $\gcd(a, n) = 1$

Extended Euclidean Algorithm

To find $d = e^{-1} \pmod{\phi(n)}$

Fast Modular Exponentiation

To compute $M^e \pmod{n}$ efficiently

Comparison with Other Systems

System	Security Basis	Key Size (equivalent to 128-bit symmetric)
RSA	Factoring	3072 bits
Diffie-Hellman	Discrete log	3072 bits
ECC	Elliptic curve discrete log	256 bits

ECC provides same security with smaller keys.