作业内容一：
用Python或Sage实现RSA算法的加密、解密、签名/验证签名
from random import randint
#gcd函数求最大公因子
def gcd(a,b):
if a%b == 0:
return b
else :
return gcd(b,a%b)
def is_prime(a):
for i in range(2,a):
if (a % i) == 0:
return False
return True
#扩展欧几里得算法
def extendedGCD(a, b):
# a*xi + b*yi = ri
if b == 0:
return 1, 0, a
x, y, r = extendedGCD(b, a%b)
"""
gcd(a, b) = a*xi + b*yi
gcd(b, a % b) = b*xi+1 + (a - [a/b]*b)*yi+1
gcd(a, b) = gcd(b, a % b) => a*xi + b*yi = a*yi+1 + b*(xi+1 - [a/b]*yi+1)
xi = yi+1
yi = xi+1 - [a/b]*yi+1
"""
tmp = x
x = y
y = tmp - (a//b) * y
return x, y, r
#选择素数p，q
def select_prime(halflength):
while True:
n = randint(0, 1 << int(halflength))
if is_prime(n):
return n
#构造公钥和秘钥
def createkeys(length):
while True:
p=select_prime(length//2)
q=select_prime(length//2)
if p!=q:
break
print("p=",p,"q=",q)
n=p*q
Euler_n=(p-1)*(q-1)
while True:
e = randint(0, 1 << int(length//2))
x, y ,q = extendedGCD(e, Euler_n)
if q == 1:
break
x,y,r=extendedGCD(Euler_n, e)
if y < 0:
d=Euler_n+y
else:
d=y
return n,e,d
#明文加密
def encrypt(m,e,n):
C=powmod(m,e,n)
return C
#密文解密
def decrypt(c,d,n):
M=powmod(c,d,n)
return M
#幂模运算
def powmod(mn,ed,n):
ret = 1
mn = mn % n
while ed > 0:
if ed & 1:
ret = (ret * mn) % n
mn = (mn * mn) % n
ed >>= 1
return ret
#加解密
n,e,d=createkeys(1024) #16测试
M1=randint(0, 1 << 256) #8测试
C=encrypt(M1, e, n)
M2=decrypt(C, d, n)
print("e=",e,"d=",d,"n=",n)
print("原明文为：",M1)
print("加密后：",C)
print("解密后：",M2)
if M1==M2:
print("M1=M2,RSA加解密成功")
else:
print("RSA加解密不成功")
#签名和验证签名
sign=1 << 6
ensign=encrypt(sign, d, n)
verify=decrypt(ensign, e, n)
print("签名为：",sign)
print("签名加密：",ensign)
print("验证签名：",verify)
if sign==verify:
print("RSA签名和验证签名成功")
else:
print("RSA签名和验证签名不成功")
因为如果keys和明文太大的话我的系统很久都没跑出来，所以我把
n,e,d=createkeys(1024) #16测试
M1=randint(0, 1 << 256) #8测试
的1024和256分别改成16和8进行测试，以下是结果：
第四次实践作业1.PNG
作业内容二：
用Python或Sage实现DH秘钥交换协议
from random import randint
#随机产生一个素数
def prime():
while True:
q=randint(2,100)
for i in range(2,q):
if (q % i) == 0:
break
return q
#获得素数q的本原根a
def generator(q):
generator=[]
for a in range(2,q):
for power in range(1,q):
if (a ** power) % q == 1:
break
if power==q-1:
generator.append(a)
return generator
#计算Y
def getY(a,x,q):
Y=(a**x)%q
return Y
#计算K，获得密钥
def getK(Y,X,q):
K=(Y**X)%q
return K
#DH秘钥交换
q=prime()
generator=generator(q)
a=generator[-1]
print("q=",q,"a=",a)
XA=randint(1,q)
XB=randint(1,q)
print("XA=",XA,"XB=",XB)
YA=getY(a, XA, q)
YB=getY(a, XB, q)
print("YA=",YA,"YB=",YB)
KA=getK(YB, XA, q)
KB=getK(YA, XB, q)
print("KA=",KA,"KB=",KB)
if KA==KB:
print("AB交换密钥成功")
运行结果：
第四次实践作业2.PNG
