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
-
(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
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
实例
#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
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))
#__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
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))
得到的明文m是: 88455713
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
评论(0)