实验目的（包括实验环境、实现目标等等）

实验环境：

  • Window11
  • Visual Studio Code v1.105.0
  • python v3.12.0a7

实现目标：

实现ElGamal公钥密码算法并完成对实验数据的测试与分析。

方案设计（包括背景、原理、必要的公式、图表、算法步骤等等）

背景

ElGamal公钥加密算法，是基于Diffie-Hellman密钥协商算法的公钥加密算法。GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法。1985年由塔希尔·盖莫尔（Taher Elgamal)提出。塔希尔·盖莫尔（Taher Elgamal)1955年生于埃及开罗，密码学家。他是SSL的最初设计者，被称为SSL之父。

原理

离散对数困难问题：
设g是模p的一个原根，任一整数h，
(1) 给定整数$x$，计算元素$g^x \equiv h \pmod{p}$很容易；
(2) 给定整数$h$，计算整数x,$0≤x≤p-2$，使得$g^x \equiv h \pmod{p}$非常困难。

算法步骤

密钥产生过程：

(1) 随机产生一个大素数$p$及模$p$的一个原根$g$；
(2) 随机选取整数$a$，计算$g^a \pmod{p}$。

Alice的公钥是$(P,g,g^a)$，私钥是$a$。

加密过程：Bob将明文消息m加密成密文

(1) 随机选取一个整数$k$,$1≤k≤p-2$;
(2) 计算$C_1 \equiv g^k \pmod{p}$，$C_2 \equiv m \cdot (g^a)^k \pmod{p}$；
(3) 将密文$(C_1,C_2)$发送给Alice。

解密过程：Alice将密文$(C_1,C_2)$恢复为明文m

(1) 计算$V \equiv C_1^a \pmod{p}$；
(2) 计算$m \equiv C_2 V^{-1} \pmod{p}$。

方案实现（包括算法流程图、主要函数的介绍、算法实现的主要代码等等）

算法流程图

主要函数的介绍

is_prime(n, k=5)

  • 功能：使用米勒-拉宾素性检测算法判断一个数是否为素数
  • 参数：
    • n: 待检测的整数
    • k: 测试轮数
  • 返回值：布尔值，True表示可能是素数，False表示肯定不是素数

generate_strong_prime(bit_length=256, min_value=1)

  • 功能：生成强素数p=2q+1形式的素数对
  • 参数：
    • bit_length: 素数的比特长度
    • min_value: 生成素数的最小值
  • 返回值：元组(p,q)，其中p=2q+1，p和q都是素数

find_primitive_root(p, q)

  • 功能：寻找模p的原根
  • 参数：
    • p: 素数
    • q: 满足p=2q+1的素数
  • 返回值：模p的原根g

mod_inverse(a, p)

  • 功能：使用扩展欧几里得算法计算模逆元
  • 参数：
    • a: 待求逆元的数
    • p: 模数
  • 返回值：a模p的逆元，即满足$(a*x)≡1(mod p)$的x

elgamal_key_gen(p, g)

  • 功能：生成ElGamal密钥对
  • 参数：
    • p: 大素数
    • g: 模p的原根
  • 返回值：元组(a,y)，其中a是私钥，$y=g^a mod p$是公钥组件

elgamal_encrypt(m, p, g, y)

  • 功能：使用ElGamal算法加密明文
  • 参数：
    • m: 明文
    • p: 大素数
    • g: 模p的原根
    • y: 公钥组件
  • 返回值：元组(C1,C2, k)，其中(C1,C2)是密文，k是随机数

elgamal_decrypt(C1, C2, p, a)

  • 功能：使用ElGamal算法解密密文
  • 参数：
    • C1, C2: 密文对
    • p: 大素数
    • a: 私钥
  • 返回值：解密后的明文m

主要代码

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import random
import math

def is_prime(n, k=5):
    """米勒-拉宾素数检测（增强稳定性，k=10提高检测准确率）"""
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(10):
        a = random.randint(2, n - 2)
        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

def generate_strong_prime(bit_length=256, min_value=1):
    """生成强素数p=2q+1"""
    while True:
        q = random.getrandbits(bit_length - 1)
        if q % 2 == 0:
            q += 1
        # 确保q是素数且p=2q+1>min_value
        if is_prime(q):
            p = 2 * q + 1
            if is_prime(p) and p > min_value:
                return p, q

def find_primitive_root(p, q):
    """寻找模p的原根"""
    if p == 2:
        return 1
    # p-1=2q，q为素数，原根需满足g^1≠1 mod p、g^2≠1 mod p、g^q≠1 mod p
    while True:
        g = random.randint(2, p - 2)
        # 双重验证：避免g=1或g=p-1（此时g^2≡1 mod p）
        if pow(g, 1, p) == 1 or pow(g, 2, p) == 1:
            continue
        if pow(g, q, p) != 1:
            return g

def mod_inverse(a, p):
    """扩展欧几里得算法求模逆"""
    m0 = p
    y = 0
    x = 1
    if p == 1:
        return 0
    a_original = a
    while a > 1:
        if p == 0:
            raise Exception(f"模逆不存在：gcd({a_original}, {m0})={a_original}≠1")
        q = a // p
        t = p
        p = a % p
        a = t
        t = y
        y = x - q * y
        x = t
    if x < 0:
        x += m0
    # 验证逆元正确性：(a_original * x) mod m0 == 1
    if (a_original * x) % m0 != 1:
        raise Exception(f"模逆计算错误：{a_original} * {x} mod {m0} = {(a_original * x) % m0} ≠ 1")
    return x

def elgamal_key_gen(p, g):
    """生成私钥a和公钥y=g^a mod p"""
    # 私钥a选取范围：[3, p-3]，避免a=1或a=p-2等极端值
    a = random.randint(3, p - 3)
    y = pow(g, a, p)
    return a, y

def elgamal_encrypt(m, p, g, y):
    """加密：返回(C1, C2)"""
    # 校验1：明文m必须小于p，否则溢出
    if m >= p:
        raise ValueError(f"明文m={m} ≥ 强素数p={p}，请增大p的比特长度或减小明文")
    # 校验2：随机数k选取范围[3, p-3]，且与p-1互素
    while True:
        k = random.randint(3, p - 3)
        # 确保gcd(k, p-1)=1，避免密文空间缩小
        if math.gcd(k, p - 1) == 1:
            break
    C1 = pow(g, k, p)
    yk = pow(y, k, p)
    C2 = (m % p) * (yk % p) % p
    return C1, C2, k

def elgamal_decrypt(C1, C2, p, a):
    """解密：返回明文m"""
    # 校验密文合法性：C1和C2必须在[1, p-1]之间
    if C1 < 1 or C1 >= p or C2 < 0 or C2 >= p:
        raise ValueError(f"密文非法：C1={C1}，C2={C2}（需满足1≤C1≤p-1，0≤C2≤p-1）")
    V = pow(C1, a, p)
    V_inv = mod_inverse(V, p)
    m = (C2 * V_inv) % p
    return m

def read_plaintext(file_path="secret1.txt"):
    """读取明文文件"""
    with open(file_path, "r") as f:
        content = f.read().strip()
    m = int(content)
    print(f"成功读取明文：m={m}")
    return m

if __name__ == "__main__":
    # 1. 读取明文（先获取明文，再生成足够大的p）
    m = read_plaintext()
    # 2. 生成强素数p（确保p > m，比特长度至少256位）
    bit_length = max(256, m.bit_length() + 10)  # p比m多10位，确保p > m
    p, q = generate_strong_prime(bit_length=bit_length, min_value=m + 1)
    # 3. 寻找模p的原根g
    g = find_primitive_root(p, q)
    # 4. 生成密钥对
    a, y = elgamal_key_gen(p, g)
    # 5. 加密
    C1, C2, k = elgamal_encrypt(m, p, g, y)
    # 6. 解密
    m_decrypted = elgamal_decrypt(C1, C2, p, a)
    # 7. 输出结果
    print("\n=== ElGamal算法测试结果===")
    print(f"强素数p（比特长度：{bit_length}）: {p}")
    print(f"素数q（满足p=2q+1）: {q}")
    print(f"模p的原根g: {g}")
    print(f"私钥a: {a}")
    print(f"公钥组件y=g^a mod p: {y}")
    print(f"随机整数k（与p-1互素）: {k}")
    print(f"密文C1=g^k mod p: {C1}")
    print(f"密文C2=m*y^k mod p: {C2}")
    print(f"原始明文m: {m}")
    print(f"解密明文m': {m_decrypted}")
    print(f"\n=== 验证结果 ===")
    print(f"明文一致性验证：{'✅ 一致' if m == m_decrypted else '❌ 不一致'}")

数据分析(包括算法测试数据的分析，运行结果截图等等)

测试数据分析

对secrect1.txt文件中的数据进行测试，明文

m=268934047525129207430358090155831774406988263017537886266459743124401877032780923870438637078936998897356703572131607069480172048042746

运行结果

思考与总结

  1. 请简述什么是本原根，给定素数P，如何求其本原根？

    答：设p是素数，若存在整数g满足：$g^0, g^1, g^2,⋯,g^{p-2},$在模p下遍历所有非零元素，则称g是模p的本原根。求本原根首先需要将p-1分解为互不相同的素因子乘积。从2开始，依次选取候选数g。对p-1的每个素因子$q_i$，计算$g^\frac{(p-1)}{q_i} \pmod{p}$。若所有结果都不等于1，则$g$是模$p$的本原根；否则换一个候选数继续验证。

  2. 如果𝑘与𝑝−1不互素，可能会发生什么情况？

    答：k与p-1不互素时，$g^k \pmod{p}$的可能取值数量减少，导致C1的取值范围变小，降低密文的不确定性。且可能存在多个明文对应同一密文，导致解密后无法唯一恢复原始明文。

  3. 实验过程中还遇到了什么问题，如何解决的？通过该实验有何收获？

    答：通过本次实验深入理解了ElGamal 算法的核心原理，掌握了离散对数困难问题在公钥密码中的应用。学会了强素数、本原根、模逆等密码学基础概念的工程实现方法。体会了公钥密码算法的安全性依赖于数学难题，以及参数选取（如k与p-1互素）对算法安全性的影响。提升了Python语言的工程实践能力，掌握了大整数运算、素数检测、模运算等密码学常用技术。