目录

RSA算法原理

1. 密钥生成

步骤：

2. 加密

3. 解密

RSA算法示例

示例步骤

加密示例

解密示例

---

RSA算法是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出。RSA算法的安全性基于大整数因子分解的难度，是一种广泛应用于数据加密和数字签名的算法。

RSA算法原理

1. 密钥生成

RSA算法的第一步是生成一对密钥：公钥和私钥。

步骤：

1. 选择两个大素数 p 和 q。
2. 计算模数 n=p×q。
3. 计算欧拉函数 ϕ(n)=(p−1)(q−1)。
4. 选择公钥指数 e，使得 1<e<ϕ(n) 且 e 与 ϕ(n) 互质。
5. 计算私钥指数 d，使得 d×e mod  ϕ(n)≡1。

公钥是 (e,n)，私钥是 (d,n)。

2. 加密

使用公钥 (e,n) 对明文 M 进行加密，生成密文 C。

3. 解密

使用私钥 (d,n)对密文 C 进行解密，恢复明文 M。

RSA算法示例

示例步骤

1. 选择两个素数 pp 和 qq：

   • p=11
   • q=13

2. 计算模数 n： n=p×q=11×13=143

3. 计算欧拉函数 ϕ(n)： ϕ(n)=(p−1)(q−1)=10×12=120

4. 选择公钥指数 e：

   • 选择 e=7，因为 1<7<120 且 7 与 120 互质。

5. 计算私钥指数 d：

   • 需要找到 d 使得 d×e≡1mod  ϕ(n)。
   • 使用扩展欧几里得算法，可以找到 d=103，因为 7 * 103( mod 120)=1。

公钥是 (7,143)，私钥是 (103,143)。

加密示例

假设明文 M=9。

        加密：

 

解密示例

        解密：

 

通过以上步骤，我们成功地完成了RSA算法的加密和解密过程。