开发过程中, 常常会涉及到加密算法的应用, 因不知其所以然, 导致忘性依旧, 整理成册, 温故而知新

1.找两个质数 P Q : ( 除了1和本身之外, 没有别的因数 )

2.计算公共模数: N = P * Q ( 因为P和Q都是质数, 所以N的产生只能通过P * Q , 不存在其他的方式 )

3.计算欧拉函数: φ(N) = (P-1)(Q-1)

解释一下欧拉函数: 如果N为正整数, 那么φ(N)代表与N互质 ( 公约数只有1的两个数称之互质 ) 的数字的个数

exp: φ(8) = 4
与8互质的数有: 1 3 5 7

4.计算公钥 E : 1 < E < φ(N) && E 与 φ(N) 必须互质

exp: 1 < E < φ(8)
则 E可以取 3, 因为φ(N)=4

5.计算私钥 D : E * D % φ(N) = 1

exp: 3 * D % 4 = 1
D = 3 | 7 | 11 | 15 | …. | D(3) + 4n

6.重点: 因为 E 与 φ(N) 互质, 且 E * D % φ(N) = 1, 可以反推 D 和 φ(N) 也互质

因为 E 与 D 互质, 且 N 为质数, 可以得到下面的公式

即: 加密可以用:
C = M^E mod N 注释: C:密文 M:明文

即:解密可以用:
M =C^D mod N 注释: C:密文 M:明文
即: 公钥为: (E, N) 私钥为: (D, N)

(注意是 mod N 而不是 mod φ(N))

7.重点: 如果想通过公钥得到私钥: 则必须知道: φ(N)

而φ(N) = (P-1)(Q-1)
则必须知道P和Q
而P和Q必须通过分解N来得到

目前已知最大可分解的公约数大概7百位

所以破解RSA加密算法非常困难

RSA模值一般都会取1024bits以上 2048bits以下

换算成10进制是 2^1023 + 1 ~ 2^2047 + 1

EXP:

1、找出质数 P 、Q

P = 3
Q = 11

2、计算公共模数

N = P * Q = 3 * 11 = 33
N = 33

3、 欧拉函数

φ(N) = (P-1)(Q-1) = 2 * 10 = 20
φ(N) = 20

4、计算公钥E

1 < E < φ(N)
1 <E < 20
E 的取值范围 {3, 7, 9, 11, 13, 17, 19}
E的取值必须是整数 E 和 φ(N) 必须是互质数
为了测试,取最小的值 E =3
3 和 φ(N) =20 互为质数,满足条件

5、计算私钥D

E * D % φ(N) = 1
3 * D % 20 = 1
根据上面可计算出 D = 7 | 27 | D(7) + 20n

6、公钥加密

为了演示,就加密一个比较小的数字 M = 2
公式:C = M^E mod N
其中: M = 2; E = 3; N = 33
代入公式: C = 2^3 % 33 = 8
明文 “2” 经过 RSA 加密后变成了密文 “8”

7、私钥解密

M =CD mod N
其中: C = 8; D = 7; N = 33
代入公式: M = 8^7 % 33 = 2 8 * 8 * 8 * 8 * 8 * 8 * 8=2097152
8 * 8 * 8 * 8 * 8 * 8 * 8 % 33 = 2
密文 “8” 经过 RSA 解密后变成了明文 2

侧面解读

公钥私钥的生成和一开始选的质数没关系, 只与φ(N)有关系, 因为秘钥对里, 存储的是 N, N = P*Q, 但是 PQ 分解不出来, 所以就不能得到φ(N)



相关文章:
⤧  上一篇 Oracle数据导入导出(expdp impdp) ⤧  下一篇 Java常量池以及intern方法详解