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

实验环境：

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

实现目标：

实现基于中国剩余定理的$（t, n）$门限秘密共享算法并完成对测试数据的测试与分析。

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

背景：

1983年，ASMUTH和BLOOM提出基于中国剩余定理的$(t,n)$门限秘密共享方案，该方案可将一个秘密拆分为n个子秘密，满足特定恢复条件即可恢复秘密，广泛应用于信息安全领域的秘密分发与保护场景。

原理：

（t,n）门限密码共享方案：
将秘密k分成n个子秘密$k₁, k₂, …, kₙ$，满足下面两个条件：
(1) 如果已知任意t个$kᵢ$值，易于恢复出k；
(2) 如果已知任意t-1个或更少个$kᵢ$值，不能恢复出$k$。

公式：

秘密分割：

$（t,n）$门限，选择n个整数$d₁, d₂,⋯, dₙ$，满足：
(1) $d₁M$。

对于某个秘密k，要求$N>k>M$，计算：

则子秘密为$（dᵢ, kᵢ）$。

秘密恢复：

n个子秘密$（dᵢ, kᵢ）$中任意选择t个：$（dᵢ₁, kᵢ₁）,（dᵢ₂, kᵢ₂）,⋯,（dᵢₜ, kᵢₜ）$

基于中国剩余定理计算下列一次同余方程组：

恢复出秘密$x≡k\pmod{N₁}，N₁=dᵢ₁dᵢ₂⋯dᵢₜ$。

算法步骤：

  1. 读入文件中500位左右的大整数，作为秘密k；
  2. 输入t和n的值；
  3. 随机生成5个互素的d值；
  4. 计算N、M值并完成条件验证；
  5. 输出中间数据的值；
  6. 计算子秘密的值；
  7. 任选2组子秘密，利用中国剩余定理进行恢复；
  8. 将原秘密与恢复得到的相比，分析是否恢复正确。

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

算法流程图：

主要函数的介绍：

（1）read_secret()

  • 功能：读取500位大整数秘密文件（secret1.txt）；
  • 输入：文件路径；
  • 输出：字符串格式的原始秘密k（转为Python大整数类型用于计算）。

（2）generate_d(t,n)

  • 功能：生成n个互质的大整数$d₁~dₙ$，范围$10¹⁶⁷到10¹⁶⁸$；
  • 输入：t和n的值；
  • 输出：排序后的d列表（$d₁<d₂<…<dₙ$）。

（3）check_d_conditions(d_list,k,t,n)

  • 功能：验证d列表是否满足N>M且N>k>M；
  • 输入：d列表、原始秘密k、t、n；
  • 输出：布尔值（满足条件返回True，否则返回False）。

（4）split_secret(k,d_list,t,n)

  • 功能：拆分秘密为n个子秘密；
  • 输入：原始秘密k、d列表、t、n；
  • 输出：子秘密列表（每个元素为（d_i,k_i）元组）。

（5）chinese_remainder_theorem(remainders,moduli)

  • 功能：求解同余方程组x≡remainders[i] (mod moduli[i])；
  • 输入：余数列表（k_i）、模数列表（d_i）；
  • 输出：方程组的解x（大整数）。

（6）recover_secret(secret_parts,k_original,t)

  • 功能：根据输入的子秘密恢复原始秘密并验证；
  • 输入：子秘密集合、原始秘密k、t；
  • 输出：恢复结果、是否匹配的标记。

算法实现的主要代码：

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
149
150
151
152
153
import random
import math

def read_secret(file_path):
    """读取原始秘密文件"""
    with open(file_path, 'r', encoding='utf-8') as f:
        secret_str = f.read().strip()
    return int(secret_str)

def is_coprime(a, b):
    """判断两个数是否互质"""
    return math.gcd(a, b) == 1

def generate_d(t, n):
    """生成n个互质的大整数，范围10^167到10^168"""
    d_list = []
    min_d = 10**167
    max_d = 10**168 - 1
    while len(d_list) < n:
        # 生成随机大整数
        d_candidate = random.randint(min_d, max_d)
        # 确保与已生成的d都互质
        if all(is_coprime(d_candidate, d) for d in d_list):
            d_list.append(d_candidate)
    # 排序使d1 < d2 < ... < dn
    d_list.sort()
    return d_list

def calculate_N_M(d_list, t, n):
    """计算N和M的值"""
    # N = d1*d2*...*dt
    N = 1
    for d in d_list[:t]:
        N *= d
    m_start_idx = n - t + 1  # 索引从0开始，n-t+2对应索引n-t+1
    M = 1
    for d in d_list[m_start_idx:]:
        M *= d
    return N, M

def check_conditions(N, M, k):
    """验证N>M且N>k>M"""
    return N > M and N > k and k > M

def split_secret(k, d_list):
    """拆分秘密为子秘密"""
    secret_parts = []
    for d in d_list:
        k_i = k % d
        secret_parts.append((d, k_i))
    return secret_parts

def extended_gcd(a, b):
    """扩展欧几里得算法，用于中国剩余定理"""
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return gcd, y - (b // a) * x, x

def chinese_remainder_theorem(remainders, moduli):
    """中国剩余定理求解同余方程组"""
    x = 0
    M_total = 1
    # 计算所有模数的乘积
    for m in moduli:
        M_total *= m
    # 逐个合并同余方程
    for m, r in zip(moduli, remainders):
        M_i = M_total // m
        # 求M_i在模m下的逆元
        gcd, inv, _ = extended_gcd(M_i, m)
        if gcd != 1:
            raise Exception("模数不互质，无法求解")
        x += r * M_i * inv
    return x % M_total

def recover_secret(secret_parts, k_original, t):
    """恢复秘密并验证"""
    num_parts = len(secret_parts)
    moduli = [d for d, k_i in secret_parts]
    remainders = [k_i for d, k_i in secret_parts]
    
    if num_parts >= t:
        try:
            recovered_k = chinese_remainder_theorem(remainders, moduli)
            is_match = recovered_k == k_original
            return recovered_k, is_match
        except Exception as e:
            return None, False
    else:
        try:
            fake_k = chinese_remainder_theorem(remainders, moduli)
            is_match = fake_k == k_original
            return fake_k, is_match
        except Exception as e:
            return None, False

def main():
    # 1. 读取原始秘密
    secret_file = "secret1.txt"
    k_original = read_secret(secret_file)
    print("原始秘密k（前20位）：", str(k_original)[:20], "...")
    
    # 2. 输入t和n
    t = int(input("请输入t的值："))
    n = int(input("请输入n的值："))
    
    # 3. 生成d列表并验证条件
    print("正在生成d1-d{}...".format(n))
    d_list = generate_d(t, n)
    N, M = calculate_N_M(d_list, t, n)
    while not check_conditions(N, M, k_original):
        print("d列表不满足条件，重新生成...")
        d_list = generate_d(t, n)
        N, M = calculate_N_M(d_list, t, n)
    
    # 4. 输出中间数据
    print("\n===== 中间数据 =====")
    for i in range(n):
        print("d{}: {}".format(i+1, d_list[i]))
    print("N = d1*d2*...*dt: {}".format(N))
    print("M = d_{}*...*dn: {}".format(n-t+2, M))
    
    # 5. 拆分秘密
    secret_parts = split_secret(k_original, d_list)
    print("\n===== 子秘密 =====")
    for i, (d, k_i) in enumerate(secret_parts):
        print("子秘密{}：（d={}, k_i={}）".format(i+1, d, k_i))
    
    # 6. 恢复秘密测试
    print("\n===== 秘密恢复测试 =====")
    num_recover = int(input("请输入用于恢复的子秘密数量："))
    selected_parts = []
    for i in range(num_recover):
        idx = int(input("请输入第{}个子秘密的序号（1-{}）：".format(i+1, n))) - 1
        selected_parts.append(secret_parts[idx])
    
    recovered_k, is_match = recover_secret(selected_parts, k_original, t)
    
    # 7. 输出恢复结果
    print("\n===== 恢复结果 =====")
    if recovered_k is not None:
        print("恢复的秘密（前20位）：", str(recovered_k)[:20], "...")
        print("原始秘密（前20位）：", str(k_original)[:20], "...")
        print("恢复结果是否与原始秘密一致：", is_match)
        if num_recover <= t-1:
            print("提示：使用少于t个子秘密，无法正确恢复原始秘密")
    else:
        print("恢复失败")

if __name__ == "__main__":
    main()

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

测试数据分析：

选取secret1进行测试，测试参数：t=3，n=5，原始秘密k为500位大整数

53823875121815031555991041726961963027167497087379606444752695810921446308620440784282908764903404381700859802589128088582231023318257395900650579969430836361568310072045989148202938122332018094970612150023975385103662839669401286231859032076966069321281804566076496995671875391401767723508755290586711966288915719170263680685765819809015089246767200303041035239107653221933068989117389227123695590846277200135849802429057524011609755858115850472691720432153190744237874436679626434222385571795646340

运行结果：

思考与总结

  1. 在基于中国剩余定理的(t, n)秘密共享方案中，少于t个子秘密，是否能够正确恢复出秘密？请简述原因。

    答：不能正确恢复出密码，当使用$s（s≤t-1）$个子秘密恢复时，对应的模数乘积$Nₛ=dᵢ₁×…×dᵢₛ$，因$s<t$，$Nₛ≤dₙ₋ₜ₊₁×…×dₙ≤M<k$，即$Nₛ<k$不满足限制条件。

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

    答：通过实验实现了基于中国剩余定理的（t,n）门限秘密共享方案，不仅深化了对该方案“秘密分割-恢复”流程、中国剩余定理作用及“t个子秘密可恢复、t-1个及以下不可恢复”核心逻辑的理解，巩固了互质、模运算等密码学基础。