庆的密码学课程实验罢了:(

import random


def ni_yuan(x, p):
    returning = 0
    while True:
        returning += 1
        if x * returning % p == 1:
            return returning


p = 1553  # 素数
g = 3  # 模p本元
m = 541  # 明文
x = 423  # 私钥
# h, a, k = [random.randint(1, p - 1) for i in range(3)]
h = 121  # 随机数h
k = 133  # 随机数k
a = 599  # 随机数a
print(f"随机数h={h} a={a} k={k}")

y = (g ** x) % p  # 公钥
print("公钥y=", y)
B = (g ** h) % p  # 第一步，Alice将密文发送给Bob，B是密文
r1 = (B ** k) % p  # 第二步，Bob将计算的r‘发送回给Alice，r1是r’
r = (r1 ** a) % p  # 第三步-
m1 = (m * r1 * ni_yuan(r, p - 1)) % (p - 1)  # -Alice将计算的m‘发送给Bob，m1是m’
s1 = (ni_yuan(k, p - 1) * (m1 * x - r1)) % (p - 1)  # 第四步
s = (ni_yuan(a, p - 1) * ni_yuan(h, p - 1) * r * ni_yuan(r1, p - 1) * s1) % (p - 1)  # 第五步
print("B=", B, " r1=", r1, " r=", r, " m1=", m1, " s1=", s1, " s=", s)
print("sig(r,s)=", (r, s))
if (y ** m) % p == ((r ** s) * (g ** r)) % p:
    print("签名有效。")
else:
    print("签名无效")