编程实现Elgamal

Elgamal是一种公钥密码学算法，它包含密钥生成、加密和解密三个部分。以下是一个用Python实现Elgamal加密和解密的示例代码：

import random

# 选择一个素数p和一个原根g
def choose_p_g():
    while True:
        p = random.randint(100, 500)
        if is_prime(p):
            break
            
    while True:
        g = random.randint(2, p-1)
        if pow(g, (p-1)//2, p) != 1 and pow(g, p-1, p) == 1:
            break
            
    return p, g

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

# 生成公私钥
def generate_key():
    p, g = choose_p_g()
    x = random.randint(2, p-1)
    y = pow(g, x, p)
    return (p, g, y), x

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

# 解密信息
def decrypt(pk, sk, ciphertext):
    p, g, y = pk
    a, b = ciphertext
    message = (b * pow(a, p-1-sk, p)) % p
    return message

# 测试
pk, sk = generate_key()
print("公钥：", pk)
print("私钥：", sk)

message = 123
print("原始信息：", message)

ciphertext = encrypt(pk, message)
print("加密后信息：", ciphertext)

decrypted_message = decrypt(pk, sk, ciphertext)
print("解密后信息：", decrypted_message)

这样，我们就实现了一个简单的Elgamal算法加密和解密的过程。