elgamal签名算法代码

以下是 Python 3 实现的 ElGamal 签名算法代码：

import random
from Crypto.Util.number import inverse

def generate_keys(p, g, x):
    # 生成公钥和私钥
    y = pow(g, x, p)
    return (y, x)

def sign(m, p, g, x):
    # 签名
    k = random.randint(1, p-2)
    r = pow(g, k, p)
    s = (inverse(k, p-1) * (int.from_bytes(m, 'big') - x*r)) % (p-1)
    return (r, s)

def verify(m, p, g, y, r, s):
    # 验证签名
    if not (0 < r < p and 0 < s < p-1):
        return False
    v1 = pow(g, int.from_bytes(m, 'big'), p)
    v2 = (pow(y, r, p) * pow(r, s, p)) % p
    return v1 == v2

# 示例
p = 2147483647
g = 2
x = 1234567890
message = b"Hello, world!"
y, x = generate_keys(p, g, x)
r, s = sign(message, p, g, x)
print("Signature: (r={}, s={})".format(r, s))
if verify(message, p, g, y, r, s):
    print("Signature is valid.")
else:
    print("Signature is invalid.")

其中，`generate_keys` 函数用于生成公钥和私钥，`sign` 函数用于对消息进行签名，`verify` 函数用于验证签名。在示例中，我们使用了一个 31 位质数 `p`，基于 `g=2` 的 ElGamal 签名算法进行了签名，并验证了签名的有效性。