RSA生成公私鑰及簽名算法

Miller_Rabin素數檢測算法

multimod 快速幂取模算法

公私鑰生成算法

from random import randint

from algorithm.g_prime import Miller_Rabin
from algorithm.g_prime import multimod

#     求最大公約數
def gy(m,n):
    if m < n:  # 如果m比n小，互換m和n的位置
      m, n = n, m
    r = m % n  # 求出m除n的餘數
    while r:  # 如果餘數不為0，進行循環
        m = n  # 把n指派給m
        n = r  # 把r指派給n
        r = m % n  # 求餘數
    return n

# 擴充歐幾裡得求逆元
def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

# 擴充歐幾裡得求逆元
def ModReverse(a,p):
    x, y, q = exgcd(a,p)
    if q != 1:
        raise Exception("No solution.")
    else:
        return (x + p) % p #防止負數

# 生産大素數
def g_p():
    p = randint(2 ** 64, 2 ** 65)
    while Miller_Rabin(p,8)!=True:
        if(p%2)==1:
            p+=2
        else:
            p=p+1
   # p,'出錯機率為',1/(4**4))
    return p

# 生産公私鑰對
def g_keypairs():
    # 生成兩個大素數
    p=g_p()
    q=g_p()
    # print("p",p,'\n',"q",q)
    # n與phi（n）
    N=q*p

    r=(p-1)*(q-1)
    # print("r", r);
    # 随機數e與r互質
    e=randint(2**10,2**16)
    while(gy(e,r)!=1):
        e-=1
    d=ModReverse(e,r)
    # print("逆元",e*d)
    # print("逆元",e*d%r)

    # print(pub_key,pri_key)
    return [e,N,d]


"""
用來加解密測試公私鑰對的正确性
"""
if __name__=="__main__":
    print(ModReverse(100,1093))
    # a=g_keypairs()
    #
    # m=1000
    # c=multimod(m,a[0][1],a[0][0])
    # print(c)
    # n=multimod(c,a[1][1],a[0][0])
    # print("m",n)
           

簽名算法

這裡的簽名隻對64位16進制有效

from algorithm.g_prime import multimod

# 需要簽名的都是 64位16進制的 hash值
def sign(server,text):
    a,b,c,d=int(text[0:16],16),int(text[16:32],16),int(text[32:48],16),int(text[48:64],16)
    result=[]
    for i in a,b,c,d:
        signed=multimod(i,server.keypairs[2],server.keypairs[1])
        result.append(signed)
    return result

def design(server,signed):
    m=""
    for i in signed:
        r=multimod(i,server.keypairs[0],server.keypairs[1])
        temp=str(hex(r))
        if 16-len(temp[2:])!=0:
            m+='0'*(16-len(temp))+temp
    return m