关于RSA算法原理

1. 欧拉函数φ(n)
   φ(n) = 小于等于n的正整数中，有多少与n互质的数（互质，即两个数除了1，没有其他公因数）；
   当n为质数时，φ(n) = n-1;
   如：φ(7) = 6 （1，2，3，4，5，6）；
   当n为2个质数乘积时，φ(ab) = φ(a) φ(b)
   如： φ(49) = φ(7)φ(7) = 36；
   2.欧拉定理
   当m和n互质时，（m^(φ(n)) ）% n == 1；
   若n为质数，（m^(n-1) ）% n == 1；
   同理 m^ (kφ(n)) % n == 1；（m^ (kφ(n)+1) ）% n == m；
   若有e，d，ed %x = 1,则e和x互质，此时d为e对于x的模反元素，ed = kx +1;
   若x = φ(n)，m^(ed) %n = m;此时，当m，n不为互质且m<n时，该等式也成立；
   由上可得 m^e %n = c; c^d %n = m；此时加密解密完成
   3 总结
   e和n为公钥，d和n为私钥，ed = kφ(n)+1；
   此时，要求的变量为 e，d，n，φ(n)；
   最简单的φ(n) 为n 为2质数乘积，
   φ(n) = (p1 - 1)(p2 - 1)，n = p1p2；ed = kφ(n) +1；e和φ(n)互质，ed %φ(n) = 1；
   所以要求的变量只有 e，d，n，φ(n)，p1，p2；
   4 安全
   由于在 e，d，n，φ(n)，p1，p2中，只有e和n公开，如果想得到d，ed = kφ(n)+1，则要知道φ(n)，要知道φ(n)就要知道p1，p2，而n = p1*p2；

注：φ(希腊文-键盘上的f)