计算机安全学第四次实践作业

作业内容一：

用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