开发过程中, 常常会涉及到加密算法的应用, 因不知其所以然, 导致忘性依旧, 整理成册, 温故而知新
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 (D为 E 相对于 φ(N)的模反元素)
exp: 3 * D % 4 = 1 D = 3 | 7 | 11 | 15 | …. | D(3) + 4n
6.重点: 因为 E 与 φ(N) 互质, 且 E * D % φ(N) = 1, 可以反推 D 和 φ(N) 也互质
使用下述公式可完成密文的加密解密
即: 加密可以用: C ＝ M^E mod N (C：密文 M：明文)
即:解密可以用: M ＝C^D mod N (C：密文 M：明文 )
即: 公钥为: (E, N) 私钥为: (D, N)
(注意是 mod N 而不是 mod φ(N))
加密过程只可以加密小于 N 的数, 实际操作是分割报文, 或者使用对称加密算法加密报文, 在使用 RSA 加密 DES 的秘钥
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)