RSA Key Generation

Cryptography · Axiom Academy

Learn the step-by-step process of generating secure RSA public and private key pairs 1. Choose Two Large Distinct Primes p and q The foundation of RSA key generation begins with selecting two large prime numbers, p and q . These primes must be: Large : Typically 1024-2048 bits each for security Distinct : p ≠ q to ensure proper factorization difficulty Random : Chosen using cryptographically secure random generation 2. Compute n = pq (The Modulus) Multiply the two primes together to get n , which serves as the modulus for both the public and private keys. The size of n (in bits) determines the key length. Breaking RSA requires factoring n back into p and q. For large primes, this is computationally infeasible with current technology. Calculate Euler's totient function φ(n) , which counts the number of integers less than n that are coprime to n. For n = pq where p and q are prime: 4. Choose e Such That 1 < e < φ(n) and gcd(e, φ(n)) = 1 Select the public exponent e that is coprime to φ(n). This means gcd(e, φ(n)) = 1, ensuring that e has a multiplicative inverse modulo φ(n). Common choice: e = 65537 = 2¹⁶ + 1 5. Compute d ≡ e⁻¹ (mod φ(n)) Using Extended Euclidean Algorithm Calculate the private exponent d , which is the modular multiplicative inverse of e modulo φ(n). This satisfies: 6. Public Key: (n, e) | Private Key: (n, d) The RSA key generation is complete! You now have: Public Key: (n, e) - shared openly for encryption Private Key: (n, d) - kept secret for decryption

This is the written version of the interactive lesson above. See the full Cryptography course.