RSA Algorithm

Cryptography · Axiom Academy

Understanding the revolutionary public-key cryptography system that transformed secure communication 1. The Big Idea: Public-Key Cryptography Before RSA, all encryption required both parties to share a secret key. This created the "key distribution problem"—how do you securely share the key in the first place? RSA's revolutionary insight: Use two different keys! Public Key: Anyone can use this to encrypt messages for you Private Key: Only you have this, and it's the only way to decrypt those messages The security comes from the computational difficulty of factoring large composite numbers . If n = p × q where p and q are large primes, finding p and q from n alone is practically impossible with current technology. The RSA key generation process creates your public and private key pair through these steps: Choose two large prime numbers: p and q (typically hundreds of digits long) Compute the modulus: n = p × q (this will be public) Compute Euler's totient: φ(n) = (p - 1)(q - 1) (this must stay secret!) Choose public exponent e: A number where 1 < e < φ(n) and gcd(e, φ(n)) = 1 Compute private exponent d: The modular multiplicative inverse where e × d ≡ 1 (mod φ(n)) 3. Phase 2 & 3: Encryption and Decryption Once keys are generated, sending secure messages is straightforward: Encryption (anyone with your public key can do this): To encrypt a message m (represented as a number less than n), compute: Decryption (only you with your private key can do this):

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