生成密钥

1. 选择两个大的质数 $p$ 和 $q$。
2. 计算 $n=p\cdot{}q$
3. 计算欧拉函数 $\phi(n)=(p-1)\cdot(q-1)$
4. 选择一个整数 $e$。$e$ 需要小于 $\phi(n)$ 且跟 $\phi(n)$ 互质。不需要很大。一般选 65537 即可（因为 65537 本身是质数，所以其实只需要满足 $\phi(n)$ 不是 65537 的倍数即可）。
5. 计算 $d$。$d$ 是 $e$ 模 $\phi(n)$ 的乘法逆元，也就是说 $d\cdot e \equiv1\mod\phi(n)$。可以用扩展欧几里得法求得。
6. 生成密钥对：
   • 公钥： $(e, n)$
   • 私钥： $(d, n)$

数据加解密

给定一个数据 $M$（$M$ 需要满足 $0\le M<n$）。

1. 使用公钥 $(e, n)$ 加密过程：

   $C = M^e\mod n$

   得到密文 $C$。

2. 使用私钥 $(d, n)$解密过程：

   $M=C^d\mod n$

   得到明文 $M$。

观察加密解密的过程可以发现：

• 加密和解密的过程本质上是一样的，都是乘方后取模。所以公钥和私钥是可以互换的（只是数学上可以互换，你要是真的把 ssh 公钥当私钥用，别人很容易破解公钥的那个 $e$ 吧，毕竟 $e$ 很小）。
• 解密最终需要 $\mod n$，因此如果数据 $M \ge n$，最终取模后会无法获得原始数据，只能得到 $M\mod n$，解密失败。因此加密时可能需要分块加密。
  • 不过，现在的 ssh 都是用 非对称加密算法 协商密钥，然后用对称加密算法来加密后续的通信数据的。所以 RSA 需要加密的数据可能也不会很大。
• 如果明文是 $0$ 或 $1$，那加密后的密文也是 $0$ 或 $1$。因为这两个数字的任意次方都是自身。所以要避免这两个数字的明文。

为什么是安全的

对外暴露的信息三个：$e$， $n$ 和密文 $C$。没有暴露的信息是 $p$， $q$， $\phi(n)$， $d$ 和明文 $M$。

解密需要拿到 $d$ → 需要 $\phi(n)$ → 需要 $p$ 和 $q$。

恰好，对于大整数的质因数分解是个非常困难的问题，目前几乎不可能破解（据说将来量子计算机可以破解）。所以 RSA 目前是非常安全的。

注意，此处拿到 $n$ 并不能直接推出 $\phi(n)$，基本上还是需要先拿到 $p$ 和 $q$ 才能计算 $\phi(n)$。