用python编程实现 ElGamal

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

from random import randint

# 生成大素数
def generate_prime_number(n):
    while True:
        p = randint(2**(n-1), 2**n-1)
        if is_prime(p):
            return p

# 判断是否为素数
def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5)+1, 2):
        if n % i == 0:
            return False
    return True

# 求模反元素
def mod_inverse(a, m):
    for i in range(1, m):
        if (a*i) % m == 1:
            return i
    return None

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

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

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

# 测试
if __name__ == '__main__':
    # 生成大素数p和原根g
    p = generate_prime_number(16)
    g = 2
    while pow(g, (p-1)//2, p) == 1:
        g = randint(2, p-1)
    
    # 生成公私钥
    x = randint(1, p-2)
    y, _ = generate_keys(p, g, x)
    print('公钥：', (p, g, y))
    print('私钥：', x)

    # 加密
    m = 123456789
    a, b = encrypt(p, g, y, m)
    print('密文：', (a, b))

    # 解密
    m_decrypt = decrypt(p, x, a, b)
    print('明文：', m_decrypt)

这个代码实现了 ElGamal 的加密、解密过程，可以通过测试进行验证。需要注意的是，这里的安全性参数比较低，只是为了演示方便。在实际应用中，需要选择更高的安全性参数。