RSA 基本思路如下（ Linux 实现自动登陆远程机器）

RSA 基本思路如下（ Linux 实现自动登陆远程机器） 1.公钥与私钥的生成：(1) 随机挑选两个大质数 p 和 q，构造n = p*q;(2)计算欧拉函数φ(n) = (p-1) * (q-1);(3)随机挑选e，使得gcd(e, φ(n)) = 1，即 e 与 φ(n) 互素,gcd指的是求最大公约数;(4)计算d，使得 e*d ≡ 1 (mod φ(n))，即d 是e 的乘法逆元。2.加密过程：

(1)待加密信息（明文）为 m，m < n；（因为要做模运算，若m大于n，则后面的运算不会成立，因此当信息比n要大时，应该分块加密）;

(2))密文 c 的生成是 $$ c = m^e mod (n) $$

3.解密

$$c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ;$$

3.解密$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$为什么能解密？

要用到欧拉定理（其实是费马小定理的推广）

a^φ(n) ≡ 1 (mod n)，

再推广：a^(φ(n)k) ≡ 1 (mod n)，

得到 a^(φ(n)k+1) ≡ a (mod n)

注意到 ed ≡ 1 mod φ(N)，即：ed = 1 + k*φ(N)。因此，$$M^(de) mod N = M^1 + kφ(N) mod N = M$$

4.代码如下 实例 #coding=utf-8#__author__ = 'ralph'import random def extendedGCD(a, b): #a*xi + b*yi = ri if b == 0: return (1, 0, a) #a*x1 + b*y1 = a x1 = 1 y1 = 0 #a*x2 + b*y2 = b x2 = 0 y2 = 1 while b != 0: q = a / b #ri = r(i-2) % r(i-1) r = a % b a = b b = r #xi = x(i-2) - q*x(i-1) x = x1 - q*x2 x1 = x2 x2 = x #yi = y(i-2) - q*y(i-1) y = y1 - q*y2 y1 = y2 y2 = y return(x1, y1, a) def computeD(fn, e): (x, y, r) = extendedGCD(fn, e) #y maybe < 0, so convert it if y < 0: return fn + y return y def keyGeneration(p,q,e): #generate public key and private key n = p * q fn = (p-1) * (q-1) d = computeD(fn, e) return (d,n) p_v = int(raw_input('请输入p的值(10进制)\n'))q_v = int(raw_input('请输入q的值(10进制)\n'))e_v = int(raw_input('请输入e的值(10进制)\n'))c_v = int(raw_input('请输入密文c的值(10进制)\n')) (d,n) = keyGeneration(p_v,q_v,e_v) #生成 d和n m = pow(c_v,d,n)print ("得到的明文m是: "+str(m))当输入p值：18443，q值：49891，e值19，密文c值：70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148得到的结果就会显示

得到的明文m是: 88455713