python实现Elgamal加密算法

Elgamal加密算法是一种非对称加密算法，它由Diffie和Hellman在1976年提出。下面是Python实现Elgamal加密算法的示例代码：

import random

# 生成大素数p和原根g
def gen_key():
    p = 23
    g = random.randint(2, p-2)
    while pow(g, (p-1)//2, p) == 1:
        g = random.randint(2, p-2)
    return p, g

# 生成密钥
def gen_keypair(p, g):
    x = random.randint(1, p-2)
    y = pow(g, x, p)
    return x, y

# 加密
def encrypt(p, g, y, m):
    k = random.randint(1, p-2)
    a = pow(g, k, p)
    b = (m * pow(y, k, p)) % p
    return a, b

# 解密
def decrypt(p, x, a, b):
    m = (b * pow(a, p-1-x, p)) % p
    return m

# 测试
if __name__ == '__main__':
    p, g = gen_key()
    x, y = gen_keypair(p, g)
    m = 10
    a, b = encrypt(p, g, y, m)
    m_decrypted = decrypt(p, x, a, b)
    print(f"Original message: {m}")
    print(f"Encrypted message: ({a}, {b})")
    print(f"Decrypted message: {m_decrypted}")

在这个实现中，我们首先生成一个大素数p和原根g。然后，我们使用生成的p和g生成一个密钥对(x, y)。接下来，我们使用公钥(g, y)和明文m加密消息，并得到密文(a, b)。最后，我们使用私钥x解密密文并恢复原始消息。

请注意，这个实现是为演示目的而提供的，因此使用了硬编码的参数和随机数生成器。在实际应用中，应该使用更安全的参数和更可靠的随机数生成器。