RSA Encryption Explained: Complete Guide to Public Key Cryptography

Introduction to RSA Encryption

RSA encryption, named after its inventors Ron Rivest, Adi Shamir, and Leonard Adleman (1977), is one of the most widely used public-key cryptosystems in the world. It forms the backbone of secure internet communication, digital signatures, and modern cybersecurity infrastructure.

Why RSA Matters:

Enables secure communication over insecure channels
Forms the basis of SSL/TLS protocols (HTTPS)
Used for digital signatures and authentication
Essential for secure email, VPNs, and online banking
Demonstrates practical application of number theory

Public Key

→

Encryption

→

Private Key

→

Decryption

In this comprehensive guide, we'll explore RSA encryption from its mathematical foundations to practical implementations, with interactive examples to help you understand this crucial cryptographic system.

What is RSA Encryption?

RSA is an asymmetric encryption algorithm that uses two different but mathematically linked keys: a public key for encryption and a private key for decryption. This revolutionary approach solved the key distribution problem that plagued symmetric encryption systems.

🔑

Asymmetric Encryption

Uses separate keys for encryption and decryption

Public key can be freely distributed

Private key must be kept secret

Eliminates need for secure key exchange

⚖️

One-Way Function

Easy to compute in one direction

Extremely difficult to reverse without private key

Based on integer factorization problem

Security relies on computational difficulty

🔢

Mathematical Foundation

Based on Euler's theorem

Uses modular arithmetic

Relies on difficulty of prime factorization

Uses large prime numbers (1024-4096 bits)

Historical Context

RSA was publicly described in 1977 by Rivest, Shamir, and Adleman at MIT. The British intelligence agency GCHQ had secretly developed an equivalent system in 1973, but it remained classified until 1997.

The algorithm was patented in the US in 1983 (expired in 2000), allowing it to become widely adopted in commercial applications.

Apply what you’ve learned by exploring the euler-totient-calculator.

Mathematics Behind RSA

RSA encryption relies on several key concepts from number theory and modular arithmetic:

🔢

Modular Arithmetic

Definition: a ≡ b (mod n) if n divides (a-b)

Properties: (a mod n) × (b mod n) ≡ (a×b) mod n

Example: 17 ≡ 2 (mod 5) because 17-2=15 is divisible by 5

Essential for RSA encryption/decryption operations

🔟

Euler's Totient Function

φ(n): Count of integers ≤ n that are coprime to n

For primes: φ(p) = p-1

For n=pq: φ(n) = (p-1)(q-1)

Critical for key generation in RSA

⚡

Euler's Theorem

If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)

Special case (Fermat): a^p-1 ≡ 1 (mod p) for prime p

Forms the mathematical basis for RSA correctness

Ensures encryption/decryption inverses work properly

Core RSA Equation

For any message m and ciphertext c:

Encryption: c ≡ m^e (mod n)

Decryption: m ≡ c^d (mod n)

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

Proof Sketch:

Given e × d ≡ 1 (mod φ(n)), we have e × d = k × φ(n) + 1 for some integer k.

Decryption: c^d ≡ (m^e)^d ≡ m^e×d ≡ m^k×φ(n)+1 ≡ (m^φ(n))^k × m ≡ 1^k × m ≡ m (mod n)

This works when gcd(m, n) = 1 (true for most messages).

Enhance your understanding by trying real-case problems on the euler-totient-calculator.

RSA Key Generation

The security of RSA depends on proper key generation. Here's the step-by-step process:

1

Choose Two Large Primes

Select two distinct large prime numbers p and q.

              // Example with small primes for demonstration

              p = 61 // First prime

              q = 53 // Second prime

              // In practice, these are 1024-4096 bits (300-1200 digits)

2

Compute n and φ(n)

Calculate n = p × q and φ(n) = (p-1)(q-1).

              n = p × q = 61 × 53 = 3233

              φ = (p-1)(q-1) = 60 × 52 = 3120

3

Choose Public Exponent e

Select e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.

              // Common choices: 3, 17, 65537 (2^16 + 1)

              e = 17 // Public exponent

              gcd(17, 3120) = 1 ✓

4

Compute Private Exponent d

Calculate d as the modular multiplicative inverse of e modulo φ(n).

              // Solve: e × d ≡ 1 (mod φ(n))

              17 × d ≡ 1 (mod 3120)

              d = 2753 // Private exponent

              Verification: 17 × 2753 = 46801 ≡ 1 (mod 3120)

Key Generation Calculator

First Prime (p)

Second Prime (q)

Public Exponent (e)

Enter values and click "Generate RSA Keys"

Encryption Process

Encryption in RSA is straightforward: anyone with the public key can encrypt a message, but only the holder of the private key can decrypt it.

Encryption Steps

Convert message to number: The message must be converted to a numeric representation (typically using ASCII or Unicode).
Ensure m < n: The numeric message m must be less than the modulus n.
Compute ciphertext: c ≡ m^e (mod n)

Example: Encrypt message "HI" with public key (n=3233, e=17)

1. Convert "HI" to numbers: H=8, I=9 (A=1, B=2, ...)

2. Combine: m = 809 (8×100 + 9)

3. Compute: c ≡ 809¹⁷ (mod 3233)

4. Result: c = 1990

            // RSA Encryption Algorithm

            function rsaEncrypt(message, publicKey) {

              const { n, e } = publicKey;

              // Convert message to integer m

              const m = stringToInteger(message);

              // Ensure m < n (use padding if needed)

              if (m >= n) {

                throw new Error('Message too long');

              }

              // Compute ciphertext: c = m^e mod n

              const c = modPow(m, e, n);

              return c;

            }

⚠️ Important Security Note

In practice, RSA is not used directly to encrypt messages. Instead:

RSA encrypts a symmetric key (AES key)
The symmetric key encrypts the actual message
This hybrid approach combines RSA's key exchange with symmetric encryption's speed
Proper padding (OAEP) must be used to prevent attacks

Decryption Process

Decryption uses the private key to recover the original message from the ciphertext.

Decryption Steps

Receive ciphertext c
Compute message: m ≡ c^d (mod n)
Convert number to text: Convert the numeric message back to text

Example: Decrypt ciphertext 1990 with private key (n=3233, d=2753)

1. Compute: m ≡ 1990²⁷⁵³ (mod 3233)

2. Result: m = 809

3. Convert: 809 → 8,9 → "HI"

            // RSA Decryption Algorithm

            function rsaDecrypt(ciphertext, privateKey) {

              const { n, d } = privateKey;

              // Compute message: m = c^d mod n

              const m = modPow(ciphertext, d, n);

              // Convert integer to string

              const message = integerToString(m);

              return message;

            }

RSA Encryption/Decryption Demo

Message to Encrypt

Prime p

Prime q

Public Exponent e

Enter values and click "Run RSA Demo"

Measure your knowledge through practical exercises using the euler-totient-calculator.

Security Analysis

The security of RSA relies on the computational difficulty of certain mathematical problems:

Integer Factorization

Given n = p × q, find p and q

Best known algorithm: General Number Field Sieve

Sub-exponential time complexity

RSA Problem

Given n, e, and c ≡ m^e (mod n), find m

Believed to be as hard as factorization

No efficient solution known

Discrete Logarithm

Security Level	RSA Key Size	Equivalent Symmetric	Year Secure Until
Basic	1024 bits	80 bits	2010
Standard	2048 bits	112 bits	2030
High	3072 bits	128 bits	2040
Ultra	4096 bits	192 bits	2050+

⚠️ Common Attacks and Mitigations

Brute Force: Try all possible keys → Use large key sizes
Mathematical Attacks: Factor n → Use strong primes
Timing Attacks: Measure computation time → Use constant-time implementations
Padding Oracle Attacks: Exploit padding errors → Use OAEP padding
Quantum Attacks: Shor's algorithm → Migrate to post-quantum cryptography

Real-World Applications

RSA encryption is ubiquitous in modern digital infrastructure:

🌐

SSL/TLS (HTTPS)

Secures web browser connections

Used in certificate validation

Establishes secure sessions

Protects against eavesdropping

📧

Secure Email

PGP and S/MIME email encryption

Digital signatures for authentication

Message integrity verification

Non-repudiation of messages

💳

Digital Payments

Credit card transaction security

Mobile payment authentication

Cryptocurrency wallets

Secure banking applications

🔏

Digital Signatures

Software distribution verification

Document authentication

Code signing certificates

Legal document signing

How HTTPS Uses RSA

Client Hello

→

Server Certificate

→

Client Key Exchange

→

Encrypted Session

RSA is used during the TLS handshake to establish a symmetric session key

Interactive RSA Demo

Complete RSA Simulation

Generate keys, encrypt, and decrypt messages with real RSA calculations.

Enter Message (text or number)

Prime p

Prime q

Public Exponent e

Click "Run Full Simulation" to see RSA in action

Challenge: Given n=3233 and e=17, encrypt the message "NO" (N=14, O=15 → m=1415).

Solution:

1. Message: "NO" → N=14, O=15 → m=1415

2. Public key: (n=3233, e=17)

3. Encryption: c ≡ 1415¹⁷ (mod 3233)

4. Compute: 1415² ≡ 2002 (mod 3233)

5. Continue exponentiation...

6. Final result: c = 1313

Verify: 1313²⁷⁵³ (mod 3233) = 1415

Challenge: Why must p and q be kept secret in RSA? What happens if an attacker knows p?

Solution:

If p is known, the attacker can:

1. Compute q = n ÷ p

2. Calculate φ(n) = (p-1)(q-1)

3. Compute d ≡ e^-1 (mod φ(n))

4. Decrypt any message encrypted with the public key

This is why RSA security depends on the secrecy of p and q, even though n is public.

Strengthen your concepts through hands-on practice using the euler-totient-calculator.

Limitations and Considerations

While RSA is powerful, it has important limitations:

Computational Cost

Slow compared to symmetric encryption

Not suitable for bulk data encryption

Used only for key exchange in practice

Key Size Growth

Keys must grow exponentially for security

2048-bit RSA ≈ 256-bit AES security

Storage and transmission overhead

Quantum Vulnerability

Shor's algorithm breaks RSA on quantum computers

Migration to post-quantum crypto needed

Current RSA deployments at risk long-term

Implementation Pitfalls

Padding oracle attacks

Timing side-channels

Key generation weaknesses

Best Practices

Use hybrid encryption: RSA for key exchange + AES for data
Implement proper padding: Always use OAEP, never textbook RSA
Use sufficient key sizes: Minimum 2048 bits, 3072+ for new systems
Protect private keys: Use HSMs, key management systems
Plan for quantum resistance: Develop migration strategy

Future of RSA and Post-Quantum Cryptography

As quantum computing advances, the cryptographic landscape is evolving:

⚛️

Quantum Threat

Shor's algorithm factors integers in polynomial time

RSA, ECC, and Diffie-Hellman become vulnerable

Quantum computers with sufficient qubits needed

Timeline estimates: 10-30 years

🛡️

Post-Quantum Algorithms

Lattice-based cryptography (Kyber, Dilithium)

Hash-based signatures (SPHINCS+)

Code-based cryptography (McEliece)

Multivariate cryptography

🔀

Transition Strategies

Crypto-agility: design for algorithm updates

Hybrid approaches: RSA + post-quantum

Long-term key protection

Gradual migration timelines

NIST Post-Quantum Cryptography Standardization

NIST is standardizing post-quantum cryptographic algorithms:

CRYSTALS-Kyber: Key encapsulation mechanism
CRYSTALS-Dilithium: Digital signature algorithm
Falcon: Another signature algorithm
SPHINCS+: Stateless hash-based signature

These will eventually replace RSA for new systems.

Put your knowledge into action with the help of the euler-totient-calculator.

RSA Encryption Explained

Table of Contents

RSA Key Components

Introduction to RSA Encryption

What is RSA Encryption?

Asymmetric Encryption

One-Way Function

Mathematical Foundation

Mathematics Behind RSA

Modular Arithmetic

Euler's Totient Function

Euler's Theorem

Core RSA Equation

RSA Key Generation

Key Generation Calculator

Encryption Process

⚠️ Important Security Note

Decryption Process

RSA Encryption/Decryption Demo

Security Analysis

⚠️ Common Attacks and Mitigations

Real-World Applications

SSL/TLS (HTTPS)

Secure Email

Digital Payments

Digital Signatures

How HTTPS Uses RSA

Interactive RSA Demo

Complete RSA Simulation

Limitations and Considerations

Future of RSA and Post-Quantum Cryptography

Quantum Threat

Post-Quantum Algorithms

Transition Strategies

NIST Post-Quantum Cryptography Standardization

Table of Contents

RSA Key Components

Introduction to RSA Encryption

What is RSA Encryption?

Asymmetric Encryption

One-Way Function

Mathematical Foundation

Mathematics Behind RSA

Modular Arithmetic

Euler's Totient Function

Euler's Theorem

Core RSA Equation

RSA Key Generation

Key Generation Calculator

Encryption Process

⚠️ Important Security Note

Decryption Process

RSA Encryption/Decryption Demo

Security Analysis

⚠️ Common Attacks and Mitigations

Real-World Applications

SSL/TLS (HTTPS)

Secure Email

Digital Payments

Digital Signatures

How HTTPS Uses RSA

Interactive RSA Demo

Complete RSA Simulation

Limitations and Considerations

Future of RSA and Post-Quantum Cryptography

Quantum Threat

Post-Quantum Algorithms

Transition Strategies

NIST Post-Quantum Cryptography Standardization

Continue Your Number Theory Journey

Complete Guide to Euler's Totient Function

RSA Encryption Explained

Modular Arithmetic Basics

Primitive Roots and Applications