elgamal加密算法代码

以下是ElGamal加密算法的Python代码实现：

import random

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def mod_inverse(a, m):
    if gcd(a, m) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

def generate_keys(p):
    g = random.randint(2, p - 1)
    x = random.randint(2, p - 2)
    h = pow(g, x, p)
    return (p, g, h, x)

def encrypt(p, g, h, m):
    y = random.randint(2, p - 2)
    c1 = pow(g, y, p)
    s = pow(h, y, p)
    c2 = (m * s) % p
    return (c1, c2)

def decrypt(p, x, c1, c2):
    s = pow(c1, x, p)
    m = (c2 * mod_inverse(s, p)) % p
    return m

# 示例
p = 65537
keys = generate_keys(p)
m = 12345
ciphertext = encrypt(*keys, m)
plaintext = decrypt(p, keys[3], *ciphertext)
print("明文：", m)
print("密文：", ciphertext)
print("解密后的明文：", plaintext)