RSA算法

---

1. 历史

1977年，三位数学家RonRivest、Adi Shamir 和 Leonard Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。

2. 密钥生成

1. 随机选择两个不相等的质数和
2. 计算
3. 选择一个整数,满足
4. 计算的模反元素，满足
5. 公钥为，密钥为

3. 加密和解密

1. 加密明文,

2. 解密密文,

4. 举例

1. 爱丽丝选择了, 计算

2. 爱丽丝选择，解同余方程

使用扩展欧几里得算法解方程

得到
3. 公钥为, 密钥为
4. 鲍勃使用公钥加密明文'A'=65

5. 爱丽丝用私钥解密

5. 证明

根据加密规则可以写成
下面证明下面的公式成立

将C代入要我们要证明的那个解密规则：

它等同于求证

由于

所以

将ed代入得到：

接下来，分成两种情况证明上面这个式子。

5.1 与互质

根据欧拉定理，此时

得到

原式得到证明。

5.2 与不是互质关系

此时，由于等于质数和的乘积，所以必然等于或。
以为例，考虑到这时与必然互质，则根据欧拉定理，下面的式子成立：

进一步得到

即

将它改写成下面的等式

这时必然能被整除，即

因为 ，所以

原式得到证明。

6. 密钥对的个数

对于选定的，能够产生的密钥对有多少个？

由于，所以，而且，所以的个数是和互质的数的个数，也就是有个
对于，由于，当确定时，方程在有且只有一个解，所以密钥对的个数为个

比如，那么,

所以一共有64对密钥

7. 交换律

当通信的双方使用模数相等的RSA算法时，RSA算法满足交换律，也就是说Alice使用的密钥为, Bob使用的密钥对为，满足

那么