RSA非对称加密
欧拉函数
φ(n)= n - 1(n为质数的时候)
(例如:φ(7)=6;φ(4)=2)
φ(n)= φ(m) * φ(h)
例如 φ(56) = φ(7) * φ(8);
如果m,和h 都是质数的时候,φ(n)= (m-1)*(h-1);
欧拉定理
m^φ(n) % n ===1 (其中m,n为互质)
什么叫互质?互质就是m,n公因数只有1。
有了上面的欧拉定理也就是有以后的“迪菲赫尔曼秘钥交换法”
m^e*d % n = m (m < n)
其中e,d也就是以后rsa中常用到的公钥和私钥,到这里,技术在当时就止步了,这个公式并不能拆分
rsa算法
有了迪菲赫尔曼秘钥交换法,我们现在将上面公式拆分也就得到了rsa加密和解密公式:
m^e % n = c;加密
c^d % n = m;解密
m 为源数据
e和n 就是公钥
d和n 就是私钥
e必须与φ(n)互质
e*d = φ(n) * k + 1;
实际操作一下
假如
m = 3;
n = 15;
那么 φ(15)= 8;
假设e = 3(需要跟φ(15)互质)
就可以得到:
3^3%15 = c = 12;
加密过后数据为12;
选择需要解密的秘钥d;
3*d = 8k + 1 (k为正整数);
由于d也为正整数,所以符合等式成立时候;
k = 1; d = 3;
k = 7; d = 19;
k = 4; d = 11;
..... ......
所以d的取值只要符合以上,就可以作为私钥,解密后结果:
12^3 % 15 = 3;
12^11 % 15 = 3;
12^19 % 15 = 3;
解密出来值完全等于m,也就是3;
所以暴露出来的就是公钥e和n,就可以解密了,这个就是rsa算法;