我们已经准备好了,你呢?

2020我们与您携手共赢,为您的企业形象保驾护航!

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.解密

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) 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))
我们凭借多年的网站建设经验,坚持以“帮助中小企业实现网络营销化”为宗旨,累计为1000多家客户提供品质建站服务,得到了客户的一致好评。如果您有网站建设网站改版百度优化、名注册、主机空间、手机网站建设公众号开发小程序制作、网站备案等方面的需求...
请立即点击咨询我们或拨打咨询热线: 13820372851,我们会详细为你一一解答你心中的疑难。项目经理在线

我们已经准备好了,你呢?

2020我们与您携手共赢,为您的企业形象保驾护航!

在线客服
联系方式

热线电话

13820372851

上班时间

周一到周五

公司电话

022-26262675

二维码
线
在线留言