Shamir门限分割方案

Shamir门限分割方案是一种基于数学方法的密钥分割技术，它允许将一个密钥分割成多个部分，其中任意集合中的k个部分可以重新组合成原始密钥。这种方案可以用于实现分布式密钥管理和安全多方计算。

generate_shares_shamir函数接受三个参数：

  • secret：要分享的秘密值。
  • n：总共要生成的分享数量。
  • k：恢复秘密所需的最小分享数量。
  • prime：用于生成多项式的素数（如果未提供，则随机生成）。

函数的主要逻辑是生成一个包含n个分享的列表shares。在每次循环中，首先生成一个随机系数列表coefficients，然后使用这些系数计算分享的值。最后，返回生成的分享列表和素数。

在程序的最后部分，使用示例中的secret_shamir、n_shamir和k_shamir参数调用generate_shares_shamir函数，并将生成的分享列表打印出来。然后，使用recover_secret_shamir函数从部分分享中恢复秘密，并将恢复的秘密值打印出来。

Shamir门限分割方案的安全性取决于秘密和分享数量的选择，以及分享的随机性。在实际应用中，需要确保秘密和分享数量的选择是足够大的值，以防止攻击者破解生成的分享。

代码部分：

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
from sympy import randprime, mod_inverse
import random

def generate_shares_shamir(secret, n, k, prime=None):
    """
    生成秘密分享的函数（Shamir's 秘密共享方案）
    :param secret: 要分享的秘密值
    :param n: 总共要生成的分享数量
    :param k: 恢复秘密所需的最小分享数量
    :param prime: 用于生成多项式的素数（如果未提供，则随机生成）
    :return: 生成的分享列表
    """
    if prime is None:
        prime = randprime(2**127, 2**128)  # 随机选择一个素数
    coefficients = [secret] + [random.randint(1, prime - 1) for _ in range(k - 1)]  # 生成 k 个随机系数
    shares = []
    for i in range(1, n + 1):
        share = sum((coefficients[j] * i**j) % prime for j in range(k)) % prime
        shares.append((i, share))
    return shares, prime

def recover_secret_shamir(shares, prime):
    """
    恢复秘密的函数（Shamir's 秘密共享方案）
    :param shares: 分享列表
    :param prime: 用于生成多项式的素数
    :return: 恢复的秘密值
    """
    x = [share[0] for share in shares]
    y = [share[1] for share in shares]
    secret = 0
    for i in range(len(x)):
        numerator, denominator = 1, 1
        for j in range(len(x)):
            if i != j:
                numerator = (numerator * -x[j]) % prime
                denominator = (denominator * (x[i] - x[j])) % prime
        lagrange = (y[i] * mod_inverse(denominator, prime) * numerator) % prime
        secret = (secret + lagrange) % prime
    return secret

# 输入
secret_shamir = "123abc"  # 要分享的秘密值
n_shamir = 5  # 总共要生成的分享数量
k_shamir = 3  # 恢复秘密所需的最小分享数量

# 生成分享
shares_shamir, prime_shamir = generate_shares_shamir(int.from_bytes(secret_shamir.encode(), 'big'), n_shamir, k_shamir)
print("Generated shares (Shamir's):", shares_shamir)  # 打印生成的分享

# 恢复秘密
recovered_secret_shamir = recover_secret_shamir(shares_shamir[:k_shamir], prime_shamir)  # 从部分分享中恢复秘密
print("Recovered secret (Shamir's):", bytes.fromhex(hex(recovered_secret_shamir)[2:]).decode('utf-8'))  # 打印恢复的秘密值

实验结果

1
2
3
4
Generated shares (Shamir's): [(1, 251016269231287306291163047880048203059), (2, 189757478496317825575377239648440243192), (3, 75642021324164959982155086402090127867), (4, 168088291243902111641009045146231718533), (5, 207677894726455878422426658875631153741)]
Recovered secret (Shamir's): 123abc

Process finished with exit code 0