---
tag: 0HM584C465
kind: example
name: RSA cryptosystem
aliases: [rivest-shamir-adleman]
msc: [94A60]
instance_of: [01E9MNJYEX]
uses: [0VC4DVE7DQ, 0VV04M41AN, 00GXTQMY8Z, 04DR5PM25N]
sources:
  - url: https://en.wikipedia.org/wiki/RSA_cryptosystem
    locator: Key generation
  - url: https://en.wikipedia.org/wiki/RSA_cryptosystem
    locator: Proof using Euler's theorem
same_as:
  wikidata: Q181551
  wikipedia: RSA cryptosystem
---

## Example

The RSA cryptosystem is an example of [[public-key cryptography|01E9MNJYEX]].
To make the keys, choose two distinct primes $p$ and $q$, and put $n = pq$ and $\varphi(n) = (p - 1)(q - 1)$, the value of [[Euler's totient function|0VV04M41AN]].
Choose an integer $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$. Let $d$ be the [[inverse|00GXTQMY8Z]] of $e$ modulo $\varphi(n)$.
The public key is $(n, e)$, and the private key is $d$.
To encrypt a message $m$ with $0 \le m < n$, compute $c = m^e \bmod n$. To decrypt, compute $c^d \bmod n$, which is equal to $m$.
A small case: $p = 5$, $q = 11$, $n = 55$, $\varphi(n) = 40$, $e = 3$ and $d = 27$, since $3 \cdot 27 = 81 \equiv 1 \pmod{40}$.
The message $m = 2$ gives $c = 2^3 = 8$, and $8^{27} \equiv 2 \pmod{55}$.

## Remarks

Decryption works by [[Euler's theorem|0VC4DVE7DQ]]: $ed = 1 + k \varphi(n)$, so $m^{ed} \equiv m \pmod n$ when $\gcd(m, n) = 1$. The general case follows from the [[Chinese remainder theorem|0FNN9B4W64]].
The security rests on the belief that it is hard to factor $n$ when $p$ and $q$ are large.
Ron Rivest, Adi Shamir and Leonard Adleman described the system publicly in 1977.

## Explanations

### L1 human

Anyone can raise a message to the power $e$ modulo $n$. To undo this, you need $d$, and to find $d$ you need the factors of $n$.
Multiplying two large primes is easy, but recovering them from the product is believed to be very hard.