Question

1976 年，美国的 Diffie 和 Hallman 提出了一种新的加密体制－公开密钥加密体制。

1、基本思想：设计一种新的加密算法，该算法拥有一对不同的加密密钥 E 和解密密钥 D 。使得 E 和 D 之间具有如下性质：

• D（E（M））＝M，即对数据 M 用 E 加密后再用 D 解密，应当可以还原为 M；
• E 和 D 都是易于计算的；
• 从 E 难以推导出 D 的结构。

2、工作原理

由于这种体制的加密密钥可以公开，因此被称为公开密钥加密体制。

1	每个用户可以选择一对 E 和 D，并将 E 公开（称为公开密钥），存入其他用户都可访问的公共存储区，将 D（称为秘密密钥）严格保密。
2	如果 A 用户希望向 B 用户发送数据（M），A 首先从公共存储区中取得 B 的加密密钥 Eb，并用 Eb 对数据进行加密，产生 Eb（M）传输给 B
3	根据性质(1)，B 可对接收的密文用 Db 进行解密获得明文数据 M。根据性质(3)，B 以外的所有用户都不掌握 Db，并且无法从公开的 Eb 中推导出 Db，所以即使攻击者获得了密文，也无法解出相应的明文

3、RSA 算法

RSA 算法是公开密钥加密体制的典型算法。该算法由美国的 Rivest、Shamir、Adleman 三人于 1978 年提出。

RSA 算法的设计依据：可以较容易地获得两个大的质数，而将它们的乘积分解并还原则极为困难，对于 RSA 算法的密钥选取以及加密和解密的实现描述如下：

	步骤说明
1	随机地选择两个不同的大质数 P 和 Q，计算其合数 R＝P×Q，要求保密
2	计算 R 的欧拉φ函数，φ(R)=(P-1)×(Q-1)，要求保密
3	选择某个与φ(R) 互质的量 K（即 K 和φ(R) 的最大公因子 gcd(K,φ(R))=1），K 可以被确定为秘密密钥 Ps，或者确定为公开密钥 Pk
4	使用欧几里德算法，计算满足同余方程 K×T＝1 (mod φ(R)) 的解 T，并将 T 作为公开密钥 Pk，或者作为秘密密钥 Ps，这依赖于 3) 的选择
5	将被传输的明文 X 进行分块，使得每一子块 x 对应的数值 m 小于等于 R-1（即 m∈(1,2,...R-1)），并针对每一明文块 x，独立进行加密和解密
6	加密：明文块 x 自乘 Pk 次，并取模 R，得到密文块 y；所有密文块 y 的串接形成整个密文 Y
7	解密：密文块 y 自乘 Ps 次，并取模 R，可得到明文块 x；所有明文块 x 的串接形成整个明文 X

4、RSA 算法的评价

	说明
优点	RSA 算法使用方便，尤其是公开密钥的特征使得用户在数据传输之前无需交换密钥，即使和多个用户进行秘密通信，也无需记忆太多的密钥；原理上，N 个用户进行通信，需要 N 对密钥，但每个用户只需记忆自己的秘密密钥，并去公共存储区中获取其他用户的公开密钥。
不足之处	算法的实现依赖于计算机的速度和容量，效率较低。统计表明，对于相同体积的数据块进行加密，DES 算法的加密效率比 RSA 算法的加密效率高上数十倍
结论	因此，RSA 算法仅用于较少数据的加密，常用于数字签名等。