Before 1977, if you wanted to send a secret message to someone, you had to meet them first to agree on a code (Key Exchange Problem). RSA changed history. It allowed two strangers who have never met to communicate securely immediately. It relies on the fact that Multiplying two large prime numbers is easy, but factoring the result back is impossible.
The Simplified Algorithm
- Choose two large primes: p and q.
- Calculate
n = p * q. (n is the Modulus). - Calculate specific values for e (Public Exponent) and d (Private Exponent).
- Public Key: (n, e).
- Private Key: (n, d).
The security relies on n. If an attacker can factor n back into p and q, they can calculate d and break the code.
But n is 2048 bits long. Factoring it would take billions of years.
1. Encryption (The Math)
To encrypt a message m (converted to a number):
c = m^e mod n
This is modular exponentiation. We raise the message to the power of the public key, then take the remainder when divided by n.
2. Decryption
To decrypt the ciphertext c:
m = c^d mod n
Mathematically, (m^e)^d mod n = m. The math loops back to the original number.
Only the person with d can do this.
3. Digital Signatures
RSA also works in reverse for signing!
If I encrypt a hash with my Private Key, absolutely anyone can decrypt it with my **Public Key**.
Why would I do that?
Because if it decrypts successfully, it PROVES that only I could have created it. This is the basis of Digital Signatures and Identity.