Elgamal 加密算法代码

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

import random

# 求模幂运算
def pow_mod(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent // 2
        base = (base * base) % modulus
    return result

# 求模反元素
def mod_inverse(a, modulus):
    # 判断是否互质
    x, y, r = 0, 1, modulus
    u, v, r = 1, 0, a
    while r != 0:
        quotient = r // u
        x, y, r = y, x - quotient * y, u - quotient * r
        u, v, r = v, u, r
    if x < 0:
        x += modulus
    return x

# 生成大素数
def generate_prime(n):
    while True:
        prime = random.randrange(2**(n-1), 2**n)
        if is_prime(prime):
            return prime

# 判断素数
def is_prime(n, k=10):
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    r, s = 0, n-1
    while s % 2 == 0:
        r += 1
        s //= 2
    for i in range(k):
        a = random.randrange(2, n-1)
        x = pow_mod(a, s, n)
        if x == 1 or x == n-1:
            continue
        for j in range(r-1):
            x = pow_mod(x, 2, n)
            if x == n-1:
                break
        else:
            return False
    return True

# 生成 Elgamal 密钥对
def generate_keypair(n):
    p = generate_prime(n)
    g = random.randint(2, p-2)
    x = random.randint(1, p-2)
    y = pow_mod(g, x, p)
    return ((p, g, y), x)

# 加密消息
def encrypt(message, public_key):
    p, g, y = public_key
    k = random.randint(1, p-2)
    a = pow_mod(g, k, p)
    b = (message * pow_mod(y, k, p)) % p
    return (a, b)

# 解密消息
def decrypt(ciphertext, private_key):
    p, x = private_key
    a, b = ciphertext
    message = (b * mod_inverse(pow_mod(a, x, p), p)) % p
    return message

使用示例：

# 生成密钥对
public_key, private_key = generate_keypair(1024)

# 加密消息
message = 12345
ciphertext = encrypt(message, public_key)

# 解密消息
decrypted_message = decrypt(ciphertext, private_key)

print(f"原始消息：{message}")
print(f"加密后：{ciphertext}")
print(f"解密后：{decrypted_message}")

注意，这里使用的是 1024 位的密钥，可以根据需要调整密钥长度。另外，由于 Elgamal 加密算法是基于离散对数问题的，因此在实际应用中需要确保素数的安全性，并且加密和解密过程中需要处理可能出现的异常情况。