ElGamal数字签名算法python实现，包括大素数判断

和求原根的过程。

为了实现ElGamal数字签名算法，我们需要进行以下几个步骤：

1. 生成两个随机数p和g，其中p是大素数，g是模p意义下的原根。

2. 选择一个私钥d，使得1 < d < p - 1。

3. 计算公钥y = g**d mod p。

4. 对原始数据进行哈希处理，得到哈希值h。

5. 选择一个随机数k，使得1 < k < p - 1，且k与p - 1互质。

6. 计算r = g**k mod p，s = (h - d * r) * k**-1 mod (p - 1)。

7. 返回数字签名（r, s）。

以下是ElGamal数字签名算法的Python实现：

import random

# 判断一个数是否为素数
def is_prime(n):
    if n <= 1:
        return False
    
    # 小于1000的素数表
    primes_under_1000 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

    # 判断是否在素数表内
    if n in primes_under_1000:
        return True
    
    # 排除一些低效的情况
    if n % 2 == 0 or n % 3 == 0:
        return False
    
    # Miller-Rabin素性测试
    s = 0
    d = n - 1
    
    while d % 2 == 0:
        s += 1
        d //= 2
    
    for _ in range(30):
        a = random.randint(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    
    return True

# 求模p意义下的原根
def primitive_root(p):
    factors = [p - 1]
    phi = p - 1
    
    # 分解phi
    for i in range(2, int(phi ** 0.5) + 1):
        if phi % i == 0:
            factors.append(i)
            factors.append(phi // i)
    
    # 尝试每一个数
    for g in range(2, p):
        flag = True
        for factor in factors:
            if pow(g, phi // factor, p) == 1:
                flag = False
                break
        if flag:
            return g
    return None

# ElGamal数字签名算法
def elgamal_sign(msg, p, g, d):
    h = hash(msg)
    while True:
        k = random.randint(1, p - 2)
        if math.gcd(k, p - 1) == 1:
            break
    r = pow(g, k, p)
    s = (h - d * r) * pow(k, -1, p - 1) % (p - 1)
    return r, s

# 例子
if __name__ == '__main__':
    p = 11
    g = primitive_root(p)
    d = 7
    msg = 'Hello, World!'
    signature = elgamal_sign(msg, p, g, d)
    print(f'Signature: {signature}')

在上述代码中，我们使用了Miller-Rabin素性测试来判断一个数是否是素数，在求模p意义下的原根时，我们使用了试除法和欧拉定理。

当我们运行这段代码时，它会输出签名的r和s值。需要注意的是，在实际应用中，我们需要将消息和签名一起发送给验证者，验证者会根据公钥重新计算哈希值，然后使用公钥、消息和签名进行验证。