用python代码实现elgamal数字签名

ElGamal是一种非对称加密算法，它不仅用于数据加密，还包含了数字签名的功能。以下是使用Python实现ElGamal数字签名的基本步骤：

首先，你需要了解几个基本概念：
1. **公钥** 和 **私钥**：每个用户都有两个密钥对，公钥公开给所有人，私钥保密。
2. **加密**：使用接收者的公钥对信息进行加密。
3. **解密**：只有拥有对应私钥的人才能解密。
4. **签名**：使用发送者的私钥生成消息的签名，验证者使用发送者的公钥来验证。

以下是一个简单的示例，假设Alice有私钥 `a` 和公钥 `(g^a mod p, g)`，Bob想要向Alice发送一条消息 `m` 并验证其真实性：

import secrets
from math import pow

# 定义常量
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def inverse_modulo(a, m):
    g, _, _ = egcd(a, m)
    assert g == 1, "Modular inverse does not exist"
    return pow(a, m - 2, m)

def generate_keys(p=2**512 + 19):  # 选择足够大的素数
    g = 2  # ElGamal通常选择2作为生成元
    while True:
        a = secrets.randbelow(p - 2) + 2  # 私钥范围
        if gcd(a, p - 1) == 1:  # 检查是否互质
            break
    public_key = (g**a % p, g)
    private_key = a
    return public_key, private_key

def encrypt(message, recipient_public_key):
    pub_g, pub_y = recipient_public_key
    r = secrets.randbelow(p - 1) + 1
    c1 = pow(pub_g, r, p)
    c2 = (message * pow(pub_y, r, p)) % p
    return c1, c2

def sign(message, sender_private_key):
    k = secrets.randbelow(p - 1) + 1
    s = (k * inverse_modulo(message, sender_private_key)) % (p - 1)
    signature = (pow(g, s, p), message * pow(sender_private_key, s, p))
    return signature

def verify(signature, message, signer_public_key):
    pub_g, pub_y = signer_public_key
    r, s = signature
    u1 = inverse_modulo(s, p - 1)
    u2 = inverse_modulo(r, p - 1)
    v = (u1 * message + u2 * pub_y) % (p - 1)
    return pow(g, v, p) == pow(pub_g, r, p) * pow(sender_private_key, s, p)

# 示例
sender_public_key, sender_private_key = generate_keys()
recipient_public_key = (6, 7)  # 假设这是Alice的公钥
message = 12345

signature = sign(message, sender_private_key)
encrypted_message = encrypt(message, recipient_public_key)

print("Signature:", signature)
print("Encrypted message:", encrypted_message)
print("Verification result:", verify(signature, message, recipient_public_key))