RSA
实例步骤
- 选质数
- 计算模数
- 欧拉函数
-
计算公钥E
\[1 <E< \phi(N)=r=20 \\Let\ \ E=3 \] -
计算私钥D
\[ (3 \times D) \%\ r== 1 \\ So \ D=7 \] -
封装公钥
\[ Public\ key(33,7) \] -
封装私钥
\[ Private \ key (33,3) \] -
给出明文
\[ 3 \ \ 1 \ \ 15 \] -
加密过程
求幂
\[3^{7} \ \ 1^{7} \ \ 15^{7}\ \]求余
\[3^{7} \%33 =9 \\ 1^{7} \%33 =1 \\ 15^{7}\% 33=27 \] -
得到密文
\[ 9 \ \ 1 \ \ 27 \] -
解密过程
求幂
\[9^{3} \ \ 1^{3} \ \ 27^{3} \\ \\ \]求余
\[9^{3} \%33 =3 \\ 1^{3} \%33 =1 \\ 27^{3} \%33 =15 \\ \] -
得到明文
\[ 3 \ \ 1 \ \ 15 \]
理论步骤
| 步骤 | 公式或描述 | 备注 |
|---|---|---|
| 找出质数 | P、Q | (随机但 P ≠ Q) |
| 计算公共模数 | N = P × Q | |
| 欧拉函数 | r = φ(N) = (P - 1)(Q - 1) | |
| 计算公钥 | 1 < E < φ(N) = r | E 、r互质 |
| 计算私钥 | (E × D) % r == 1 | |
| 封装公钥 | (N, E) | |
| 封装私钥 | (N, D) | |
| 加密 | C = M^E mod N | C 密文 |
| 解密 | M = C^D mod N | M 明文 |
练习题
练习1
给定 P = 5 、 Q = 7 ，以及 E = 5，计算私钥 D 、公钥和私钥。
解题步骤：
-
计算公共模数 ( N )：
\[( N = P \times Q = 5 \times 7 = 35 ) \] -
计算欧拉函数 ( r )：
\[ r = \phi(N) = (P - 1)(Q - 1) = (5 - 1)(7 - 1) = 4 \times 6 = 24 \] -
选择公钥 ( E )：
已知 ( E = 5 )，满足 ( 1 < E < r ) 且与 ( r ) 互质，条件满足。 -
计算私钥 ( D )：
\[私钥 D 需要满足 \ (E \times D) \% r = 1 ，即： \\ (5 \times D) \% 24 == 1 \\ 我们需要找到 D 使得这个等式成立。通过逐一尝试可以得到：\\ 5 \times 5 = 25 ，25 \% 24 == 1 \\ 因此，D = 5 。 \]
封装公钥和私钥：
- 公钥：( (N, E) = (35, 5) )
- 私钥：( (N, D) = (35, 5) )
答案：
- 公钥：( (35, 5) )
- 私钥：( (35, 5) )
在这种情况下，公钥和私钥的值都是一样的。这种情况虽然在理论上是可以的，但在实际应用中，通常会选择更复杂的质数，以避免这样的情况发生。
练习2
假设质数 P = 5，Q = 11，试求出公共模数 N，欧拉函数 r，公钥 E，私钥 D，使用消息 M = 9 进行加密和解密。
解题步骤：
-
找出质数：
给定 P = 5，Q = 11。 -
计算公共模数：
\[N = P \times Q = 5 \times 11 = 55 \] -
计算欧拉函数：
\[r = \phi(N) = (P - 1)(Q - 1) = (5 - 1)(11 - 1) = 4 \times 10 = 40 \] -
选择公钥 E：
公钥 E 需要满足 ( 1 < E < r ) 且与 r 互质。
选择 E = 3，因为 3 与 40 互质。 -
计算私钥 D：
\[(E \times D) \% r == 1 \]
私钥 D 满足我们需要找到 D，使得
\[(3 \times D) \% 40 == 1) \]通过计算，D = 27
-
封装公钥和私钥：
公钥：(N, E) = (55, 3)
私钥： (N, D) = (55, 27) -
加密消息 M：
\[C = M^E \% N = 9^3 \% 55 \\ 9^3 = 729 ，729 \% 55 = 14 \]因此，加密后的密文 C = 14。
-
解密消息 C：
\[M = C^D \% N = 14^{27} \% 55 \]计算结果为 M = 9。
答案：
- 公钥： (55, 3)
- 私钥：(55, 27)
- 加密后的密文：C = 14
- 解密后的原文：M = 9