RSA Algorithm: Encryption and Decryption
What you'll learn: How RSA uses modular exponentiation to transform plaintext into ciphertext with a public key, and back again with a private key.
The Core Mechanism
Now that you've seen how RSA keys are generated, let's see how they actually protect messages. RSA encryption and decryption both rely on modular exponentiation—raising a number to a power and taking the remainder when divided by the modulus n.
Encryption with the Public Key
To encrypt a message M (represented as a number less than n), the sender uses the recipient's public key (e, n):
Ciphertext C = M^e mod n
The exponent e and modulus n are public knowledge, but recovering M from C is computationally infeasible without the private key.
Decryption with the Private Key
The recipient uses their private key (d, n) to decrypt:
Plaintext M = C^d mod n
This works because of the mathematical relationship between e and d established during key generation. They are modular multiplicative inverses, ensuring that (M^e)^d ≡ M (mod n).
Why This Works
Think of it like a special lock: the public key (e) locks the box in a way that scrambles the contents mathematically. Only the private key (d) has the precise "shape" to unscramble it back to the original. The trapdoor function property means computing C from M is easy, but reversing it without d requires factoring n—an intractable problem for large numbers.
Key Takeaway: RSA encryption raises the message to the public exponent e modulo n, while decryption raises the ciphertext to the private exponent d modulo n, leveraging the mathematical relationship between the keys to securely recover the original message.