RSA
Public-key encryption and signatures built on the difficulty of factoring a product of two large primes.
RSA
RSA — named for Rivest, Shamir, and Adleman, who published it in 1977 — was the first practical scheme to deliver the full promise of Public-Key Cryptography: a public key anyone can use to encrypt to you, and a private key only you can use to decrypt. Its security rests on a single asymmetry of Modular Arithmetic: multiplying two large primes is easy, but factoring their product back apart is, as far as anyone knows, impossibly slow.
Building the keys
- Pick two large primes p and q and multiply them: n = p q. This n is public; its factors are not.
- Compute \varphi(n) = (p-1)(q-1) — secret.
- Choose a public exponent e coprime to \varphi(n) (commonly 65537).
- Find the private exponent d as the modular inverse of e: \;ed \equiv 1 \pmod{\varphi(n)}.
Your public key is the pair (n, e); your private key is d. Encryption and decryption are each one modular exponentiation:
The reason decryption undoes encryption is Fermat/Euler's theorem: m^{ed} = m^{1 + k\varphi(n)} \equiv m \pmod{n}.
A tiny worked example
Real RSA uses primes hundreds of digits long. To see the gears turn, take absurdly small ones.
The catch for an attacker: to find d they need \varphi(n) = (p-1)(q-1), which means knowing p and q — i.e. factoring n. For n = 33 that is trivial. For a 2048-bit n it is the wall.
Why factoring is the whole game
Multiplying is a near-instant operation even on huge numbers; factoring the result is believed to take time that explodes with the size of n. The chart sketches that gulf in difficulty.
Because the public and private exponents are interchangeable, running the private key first and the public key to check produces not secrecy but a Digital Signature — proof that only the key's owner could have created the value.