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 randomdef extendedGCD(a, b):#a*xi + b*yi = riif b == 0:return (1, 0, a)#a*x1 + b*y1 = ax1 = 1y1 = 0#a*x2 + b*y2 = bx2 = 0y2 = 1while b != 0:q = a / b#ri = r(i-2) % r(i-1)r = a % ba = bb = r#xi = x(i-2) - q*x(i-1)x = x1 - q*x2x1 = x2x2 = x#yi = y(i-2) - q*y(i-1)y = y1 - q*y2y1 = y2y2 = yreturn(x1, y1, a)def computeD(fn, e):(x, y, r) = extendedGCD(fn, e)#y maybe < 0, so convert itif y < 0:return fn + yreturn ydef keyGeneration(p,q,e):#generate public key and private keyn = p * qfn = (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和nm = pow(c_v,d,n)print ("得到的明文m是: "+str(m))当输入p值:18443 q值:49891 e值19
密文c值:
70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148
得到的结果就会显示
得到的明文m是: 88455713
实例
#coding=utf-8#__author__ = 'ralph'import randomdef extendedGCD(a, b):#a*xi + b*yi = riif b == 0:return (1, 0, a)#a*x1 + b*y1 = ax1 = 1y1 = 0#a*x2 + b*y2 = bx2 = 0y2 = 1while b != 0:q = a / b#ri = r(i-2) % r(i-1)r = a % ba = bb = r#xi = x(i-2) - q*x(i-1)x = x1 - q*x2x1 = x2x2 = x#yi = y(i-2) - q*y(i-1)y = y1 - q*y2y1 = y2y2 = yreturn(x1, y1, a)def computeD(fn, e):(x, y, r) = extendedGCD(fn, e)#y maybe < 0, so convert itif y < 0:return fn + yreturn ydef keyGeneration(p,q,e):#generate public key and private keyn = p * qfn = (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和nm = pow(c_v,d,n)print ("得到的明文m是: "+str(m))
得到的明文m是: 88455713
尊贵的董事大人
英文标题不为空时 视为本栏投稿
需要关键字 描述 英文标题