A form of asymmetric cryptography.

Full name is the Rivest, Shamir, Adelson Algorithm

It relies on modular arithmetic which, unfortunately, is really slow :((. Encryption/decryption are computation-heavy. Ok for occasional communication but too slow for extensive data transfer. It’s good for establishing initial secure connection. Hard to crack because to determine $d$ from $(n,e)$ requires computing factors of $n$ which is a hard problem

Steps:

- Choose two large primes $p$ and $q$ (1024-bits each)
- Compute $n=pq,z=(p−1)(q−1)$
- Choose $e<n$ that has no common factors with $z$ (commonly 3)
- Choose $d<n$ such that $edmodz=1$
- Public key: $K_{B}=(n,e)$
- Private key: $K_{B}=(n,d)$
- Encrypting is then $encrypt(m)=m_{e}modn$
- Decrypting is then $decrypt(c)=c_{d}modn$

Key exchange can also be performed using RSA

- If Alice and Bob both know the other’s public key, how can they agree on a shared “session” key?
- Alice chooses key $K_{S}$ and encrypts it with Bob’s public key and Alice’s private key $K_{A}(K_{B}(K_{S}))$
- Bob decrypt’s the message using his private key and Alice’s public key $K_{B}(K_{A}(K_{A}(K_{B}(K_{S}))))=K_{S}$

See also: elliptic curve cryptography