Course contentsShow
← Computer Science
Lesson 2408 of 2,87254. Cryptography FundamentalsFree lesson

RSA Algorithm: Key Generation

Step-by-step process of generating RSA public and private key pairs using prime numbers.

RSA Algorithm: Key Generation

You'll learn: How to generate a matching RSA public and private key pair from prime numbers.

The Process

RSA key generation transforms two secret prime numbers into a powerful cryptographic key pair. Think of it like creating a special lock and key from two master components—the lock (public key) can be shared with everyone, while only you keep the key (private key).

Step-by-Step Key Generation

1. Choose Two Large Primes

Select two distinct prime numbers, p and q. In practice, these are hundreds of digits long, but let's use small examples for clarity.

2. Calculate the Modulus

Compute n = p × q. This modulus becomes part of both your public and private keys. Its size determines encryption strength.

3. Calculate Euler's Totient

Calculate φ(n) = (p - 1) × (q - 1). This value counts how many numbers less than n are coprime to it—crucial for the trapdoor function you learned about.

4. Choose Public Exponent

Select e such that 1 < e < φ(n) and e is coprime to φ(n). Common choice: e = 65537 (it's prime and makes encryption efficient).

5. Calculate Private Exponent

Find d where (d × e) mod φ(n) = 1. This means d is the modular multiplicative inverse of e. This is the trapdoor—easy to create with p and q, nearly impossible to find without them.

The Result

  • Public key: (n, e) — share freely
  • Private key: (n, d) — keep secret
  • Discard p, q, and φ(n) securely

Key Takeaway: RSA key generation uses prime factorization's one-way nature: multiplying primes is easy, but factoring their product back into primes is computationally infeasible, creating the mathematical trapdoor that secures the system.