ElGamal 加密算法 / ElGamal Public-key Cryptosystem

import secrets

print("************程序功能************")
print("ElGamal加密算法")
print("********************************")
print("Reference books: 《现代密码学（第二版）》")
print("Reference books: https://blog.csdn.net/qq_41491942/article/details/103200388")
print("Reference books: https://www.cnblogs.com/mx-lqk/p/10315789.html")
print("Completion time：2021-6-5")
print("Last modification time ：2021-6-5",'\n')
print("--------------------------------------------------------")

#高幂模
def gaomimo(a,b,P):
    c = 1
    if (b == 0):
        return (c)
    while(1):
        if (b%2 != 0):
            b = b-1
            c = (c*a) % P
            if (b == 0):
                return (c)
        else:
            b = b//2
            a = (a*a) % P
    

#米勒-拉宾素性检验
def judge_sushu(P):
    if (P==2 or P==3):
        return (1)

    s = 1
    while(1):
        if((P-1)%(2**s) == 0):
            s = s+1
        else:
            s = s-1
            break
    m = (P-1)//(2**s)

    judge = 0
    for b in range(1,(P-1),int((P-1)/10)):
        r = 0
        z = gaomimo(b,m,P)
        if(z == 1 or z == P-1):
            judge = judge + 1
            continue
        else:
            while(1):
                if (r == s-1):
                    return(0)
                else:
                    r = r+1
                    z = gaomimo(z,2,P)
                    if(z == P-1):
                        continue
    return(1)

#生成大素数p
q = secrets.randbelow(2**256)
if (q%2 == 0):
        q = q+1
while(judge_sushu(q) == 0):
                q = q+2
p = 2*q+1

print("生成大素数p中......")
while(judge_sushu(p) == 0):
        q = q+2
        while(judge_sushu(q) == 0):
                q = q+2
        p = 2*q+1

#p = 2579

#生成本原元g
print("\n","生成本原元g中......")
oula = p-1
g = 0
for i in range(secrets.randbelow(2**64),p):
        g = i
        if (gaomimo(g,1,p) == 1):
                continue
        else:
                if (gaomimo(g,2,p) == 1):
                        continue
                else:
                        if (gaomimo(g,q,p) == 1):
                                continue
                        else:
                                if (gaomimo(g,oula,p) == 1):
                                        break

#g = 2

#生成公钥y及私钥x
print("\n","生成公钥y及私钥x中......")
x = secrets.randbelow(2**256)
while (not( 1<x and x<(p-2) )):
        x = secrets.randbelow(2**256)
y = gaomimo(g,x,p)

#x = 765
#y = 949

#加密密文
print("\n","加密中......")
M = 1299  #明文M

k = secrets.randbelow(2**256)
while (not( 1<k and k<(p-2) ) or k==2 or k==q):
        k = secrets.randbelow(2**256)

#k = 853
y1 = gaomimo(g,k,p)
U = gaomimo(y,k,p)
y2 = gaomimo(U*M,1,p)
print("密文:(",y1,",",y2,")")

#解密
print("\n","解密中......")
V =  gaomimo(y1,x,p)

while(y2%V != 0):    #用于修正参数，防止无法正确得到明文
        y2 = y2 + p
M = gaomimo(y2//V,1,p)
print("明文为:",M)

print("\n","私钥x为:",x)
print("\n","公钥:")
print("p:",p)
print("\n","g:",g)
print("\n","y:",y)