Elgamal

发表于2025-05-12

一、概述

ElGamal 加密算法是一种公钥加密算法，由Taher Elgamal 在1985年提出，基于离散对数问题的计算困难性（即：在某些群中，计算离散对数非常困难）。它是 非对称加密 的一种典型实现，与 RSA 加密算法类似，具有加密和解密需要不同密钥的特性。ElGamal 加密算法广泛用于数字签名（例如 DSA），也可以作为其他加密方案（如 PGP）的一部分。

二、算法框架

三、主要部分分析

密钥生成

ElGamal 使用一对密钥：公钥和私钥。

公钥 (p, g, y)：p：一个大素数（用于构建群体，通常是 128 位或更大）。g：一个原根（生成素数群的生成元）。y：y = g^x mod p，其中 x 是私钥，y 是公钥的组成部分。

私钥 x：x 是一个随机生成的秘密数（1 < x < p-1），用于解密。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# Miller-Rabin 素性测试
def is_prime(n, k=5):
    if n <= 1 or n % 2 == 0:
        return False
    if n == 2 or n == 3:
        return True
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
# 自动生成大素数
def generate_large_prime(bits=128):
    while True:
        p = random.getrandbits(bits)
        p |= (1 << bits - 1) | 1  # 确保最高位和最低位为1
        if is_prime(p):
            return p
# 快速幂取模
def mod_exp(base, exponent, mod):
    result = 1
    base %= mod
    while exponent > 0:
        if exponent % 2:
            result = (result * base) % mod
        exponent //= 2
        base = (base * base) % mod
    return result
# 快速找原根（适合大素数）
def find_primitive_root(p):
    if p == 2:
        return 1
    phi = p - 1
    factors = set()
    n = phi
    i = 2
    while i * i <= n:
        if n % i == 0:
            factors.add(i)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        factors.add(n)
    for g in range(2, p):
        if all(pow(g, phi // f, p) != 1 for f in factors):
            return g
    return None
# 密钥生成
def generate_keys(p):
    g = find_primitive_root(p)
    x = random.randint(2, p - 2)
    y = mod_exp(g, x, p)
    return (p, g, y), x

加密

对消息 m（需满足 0≤m<p ，十进制数）的加密步骤如下：

  1. 选择随机数 k
    • k 需满足 1<k<p−1，且 与 p−1 互质。
    • 注意：若 g 的阶为 q（如 p=2q+1 且 q 为素数），则 k应满足 1≤k≤q−1，无需强制互质。
  2. 计算中间值 a和密文 b
    • a=g^k mod p,b=m⋅y^k mod p
    • 输出密文：(a,b)。

解密过程

使用私钥 x 解密密文 (a,b)：

  1. 计算共享密钥 s

s=a^x mod p=(g^k)^x mod p=g^(xk) mod p

  1. 计算 s **的模逆元 s_inv
    • s_inv≡s^(−1) mod p
    • 通过扩展欧几里得算法或费马小定理（若 p 为素数）计算。
  2. 还原消息 m

image

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
import random

# Miller-Rabin 素性测试
def is_prime(n, k=5):
    if n <= 1 or n % 2 == 0:
        return False
    if n == 2 or n == 3:
        return True
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
    
# 自动生成大素数
def generate_large_prime(bits=128):
    while True:
        p = random.getrandbits(bits)
        p |= (1 << bits - 1) | 1  # 确保最高位和最低位为1
        if is_prime(p):
            return p
            
# 快速幂取模
def mod_exp(base, exponent, mod):
    result = 1
    base %= mod
    while exponent > 0:
        if exponent % 2:
            result = (result * base) % mod
        exponent //= 2
        base = (base * base) % mod
    return result
    
# 快速找原根（适合大素数）
def find_primitive_root(p):
    if p == 2:
        return 1
    phi = p - 1
    factors = set()
    n = phi
    i = 2
    while i * i <= n:
        if n % i == 0:
            factors.add(i)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        factors.add(n)
    for g in range(2, p):
        if all(pow(g, phi // f, p) != 1 for f in factors):
            return g
    return None
    
# 密钥生成
def generate_keys(p):
    g = find_primitive_root(p)
    x = random.randint(2, p - 2)
    y = mod_exp(g, x, p)
    return (p, g, y), x
    
# 加密
def encrypt(p, g, y, m):
    k = random.randint(2, p - 2)
    a = mod_exp(g, k, p)
    b = (m * mod_exp(y, k, p)) % p
    return a, b, k
    
# 解密
def decrypt(p, x, a, b):
    s = mod_exp(a, x, p)
    s_inv = pow(s, -1, p)
    m = (b * s_inv) % p
    return m, s, s_inv
    
# 主程序（只显示核心加解密过程）
if __name__ == "__main__":
    # 获取用户输入的 p 位数
    try:
        bits = int(input("请输入要生成素数的位数："))
        if bits < 8:
            raise ValueError("位数应当大于等于 8 位")
    except ValueError as e:
           print(f"输入无效: {e}")
        exit(1)

    print(f"正在生成 {bits} 位素数用于 ElGamal 密钥，请稍等...")
    p = generate_large_prime(bits)
    public_key, private_key = generate_keys(p)
    g, y = public_key[1], public_key[2]
    x = private_key

    print("\n密钥生成完毕：")
    print(f"私钥 x: {x}")
    print(f"公钥 (g={g}, y={y})")

    message = int(input("\n请输入要加密的整数消息（必须小于 p）: "))
    if message >= p:
        raise ValueError("消息必须小于 p")
        
    a, b, k = encrypt(p, g, y, message)
    print("\n 加密过程：")
    print(f"随机 k: {k}")
    print(f"计算 a = g^k mod p = {a}")
    print(f"计算 b = m * y^k mod p = {b}")

    m_decrypted, s, s_inv = decrypt(p, x, a, b)
    print("\n解密过程：")
    print(f"计算共享密钥 s = a^x mod p = {s}")
    print(f"计算 s 的逆 s^(-1) mod p = {s_inv}")
    print(f"解密后消息 m = b * s^(-1) mod p = {m_decrypted}")

    print("\n解密是否成功？", "是" if m_decrypted == message else "否")

elgamal.py