python实现elgamal加解密

ElGamal加密算法是一种非对称加密算法，下面是Python实现的示例代码：

import random
import math

# 生成大质数
def generate_prime_number(length):
    while True:
        p = random.getrandbits(length)
        if is_prime(p):
            return p

# 判断是否为质数
def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# 求解最大公约数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

# 求解模逆
def inverse(a, p):
    for i in range(1, p):
        if (a * i) % p == 1:
            return i
    raise ValueError("Modular inverse does not exist")

# 加密
def encrypt(plaintext, p, g, y):
    k = random.randint(1, p - 2)
    c1 = pow(g, k, p)
    s = pow(y, k, p)
    c2 = (plaintext * s) % p
    return (c1, c2)

# 解密
def decrypt(ciphertext, p, x):
    c1, c2 = ciphertext
    s = pow(c1, x, p)
    plaintext = (c2 * inverse(s, p)) % p
    return plaintext

# 主函数
if __name__ == "__main__":
    # 生成大质数
    p = generate_prime_number(256)

    # 选择生成元
    g = random.randint(2, p - 1)

    # 选择私钥
    x = random.randint(1, p - 2)

    # 计算公钥
    y = pow(g, x, p)

    # 明文
    plaintext = 123456789

    # 加密
    ciphertext = encrypt(plaintext, p, g, y)
    print("Ciphertext: ", ciphertext)

    # 解密
    decryptedtext = decrypt(ciphertext, p, x)
    print("Decryptedtext: ", decryptedtext)

以上代码实现了ElGamal加密算法的加解密过程。需要注意的是，加密过程中需要生成随机数k，解密过程中需要求解模逆。这里使用了Python的内置函数pow()来进行快速幂运算，避免了使用循环的低效实现。