公钥密码体制
根据加密密钥能否公开，将密码体制划分为两类，一类是对称密码体制，另一类是公钥密码体制。对称密码加密和解密使用相同的密钥，公钥密码体制（又称非对称密码体制）加密和解密使用不同的密钥。
公钥密码满足的要求
- 用户产生一对密钥 $\mathrm{(K_e，K_d)}$ 在计算上是容易的。
- 已知公钥和明文M，发送方产生密文$\space \mathrm{C=E(M,K_e)}$ 在计算上是容易的。
- 接受方使用其私钥对接受的密文$\space \mathrm{C}$ 进行解密，在计算上是容易的。
- 已知公钥$\space \mathrm{K_e}$，攻击者确定私钥$\space \mathrm{K_d}$ 在计算上不可行。
- 加密和解密的顺序可以互换。即$\space \mathrm{D(E(M,K_e),K_d)=E(D(M,K_d),K_e)=M}$
RSA 公钥密码体制
- RSA 算法的可靠性基于大数的因子分解问题。
- RSA 算法的安全性基于数论中大素数分解的困难性。
- RSA 算法密码用于加密，数字签名。RSA算法是目前应用最广泛的公钥密码。
💡 公钥和密钥是成对出现的，使用公钥加密数据，使用私钥解密数据。目前只有短的RSA 密钥才可能被穷举方式破解。只要密钥的长度足够长，用RSA加密的信息实际上是不能被破解的。
RSA 算法流程
- 选定两个质数p和q
- 计算出 n=p*q
- 通过欧拉函数计算$\space \mathrm {\phi(n)=(p-1)(q-1)}$ 。$\mathrm{\phi(n)}$表示 1~n 之间质数的个数。
- 选定一个质数 e （1 < e < $\mathrm{\phi(n)}$）。（e, n）为公钥。
- 计算d, d满足$\space \mathrm{e*d \space mod \space \phi(n)}$=1。(d, n)为私钥。
RSA 算法加密解密流程
使用公钥加密数据，私钥解密数据。
- 计算密文：$\mathrm{C={M^e \space mod \space n}}$
- 解密密文：$\mathrm{M={C^d \space mod \space n}}$
举例
例:已知密文C=10，用户公钥（e, n）其中 e=5，n=35，求明文？
解:
将n分解成两个质数相乘，得到 35=5*7
计算 $\mathrm {\phi(n)=(5-1)(7-1)}=24$
使 e*d%$\mathrm{\phi(n)}$=1 条件满足
即 5*d%24=1
得 d=5
得到私钥为（5, 35）
解密明文=$\mathrm {10^5 \space mod \space 35}=10$