- RSA relies on the hardness of factoring the product of two large prime numbers.
- Public key $(e, n)$ encrypts: $C = M^e \pmod n$.
- Private key $(d, n)$ decrypts: $M = C^d \pmod n$.
### Mathematics of RSA
RSA uses asymmetric key pairs derived from two large secret primes $p$ and $q$:
1. Compute modulus $n = p \times q$.
2. Compute Euler totient $\phi(n) = (p-1)(q-1)$.
3. Select public exponent $e$ coprime to $\phi(n)$.
4. Compute private exponent $d \equiv e^{-1} \pmod{\phi(n)}$.
#### Encryption & Decryption
* **Encrypt**: $C = M^e \pmod n$
* **Decrypt**: $M = C^d \pmod n$