特点

RSA 之所以叫非对称算法，是因为加密和解密的密钥不一样。任何一个密钥都可以用来加密。

公钥和私钥

通过私钥可以轻松计算出公钥，反之不行。

1. 随机选择两个不相等的质数 $p$ 和 $q$，$p$ 不等于 $q$，计算 $N=pq$。
   这里选择 103 和 349。$N=pq$ = 35947。$N$ 的长度就是密钥长度。35947 对应的二进制是 ‭1000110001101011‬，一共有 16 位，所以这个密钥就是 16 位。实际应用中 RSA 密钥一般是1024位。
2. 计算 $N$ 的欧拉函数 $\phi (N)$。$r=\phi (35947)=\phi (103)\phi (349)=(102)(348)=35496$。
3. 选择一个小于 $r$ 的整数 $e$，使 $e$ 与 $r$ 互质，这里取 $e=773$。
4. 求 $e$ 关于 $r$ 的模反元素，命名为 $d$（求 $d$ 令 $ed\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}r)ed\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}r)$）。最终转为 773d-1=35496k 这个二元一次方程，求得一组解(d,k)=(45,1)。
5. 将 $(N,e)$ 封装成公钥， $(N,d)$ 封装成私钥。所以公钥就是 (35496 ,773)，私钥就是（35496 , 45）。

加密和解密

用公钥加密时，私钥可以解密。反之亦然，私钥加密后的信息用公钥可以解密。

签名和验签