Shamir 的秘密共享（Python） - 当 len > 10 时无法取回原始秘密

Question

每当我尝试取回原始值时，我都会得到“Hello World►/”、“Hello Worlc”、“Hello World►/”、“Hello Worle♦S”或其他一些变体。我按照这个网站进行拆分和重构的实现：https://www.geeksforgeeks.org/implementing-shamirs-secret-sharing-scheme-in-python/。这是我的代码：

import random
from math import ceil
from decimal import Decimal

FIELD_SIZE = 10**5

def reconstruct_secret(shares):
    sums = Decimal(0)
    for j, share_j in enumerate(shares):
        xj, yj = share_j
        prod = Decimal(1)
        for i, share_i in enumerate(shares):
            xi, _ = share_i
            if i != j:
                # Check if xi is equal to xj
                if xi == xj:
                    continue
                prod *= Decimal(xi) / (Decimal(xi) - Decimal(xj))

        prod *= Decimal(yj)
        sums += prod

    return int(round(sums))


def polynom(x, coefficients):
    point = 0
    for coefficient_index, coefficient_value in enumerate(coefficients[::-1]):
        point += x ** coefficient_index * coefficient_value
    return point


def coeff(t, secret):
    coeff = [random.randrange(0, FIELD_SIZE) for _ in range(t - 1)]
    coeff.append(secret)
    return coeff


def generate_shares(n, m, secret):
    coefficients = coeff(m, secret)
    shares = []

    for i in range(1, n+1):
        x = random.randrange(1, FIELD_SIZE)
        shares.append((x, polynom(x, coefficients)))

    return shares

if __name__ == '__main__':

    # (3,5) sharing scheme
    t, n = 3, 5

    tt = "Hello World!!!"
    secret = int.from_bytes(tt.encode(), byteorder='big')
    # Phase I: Generation of shares
    shares = generate_shares(n, t, secret)

    # Phase II: Secret Reconstruction
    pool = random.sample(shares, t)
    # Reconstruct the secret
    r_secret_int = reconstruct_secret(pool)
    r_secret_string = r_secret_int.to_bytes(
        (r_secret_int.bit_length() + 7) // 8, byteorder='big').decode('utf-8', 'ignore')
    print("Reconstructed secret:", r_secret_string)

我咨询了chatgpt，它建议更改reconstruct_secret(shares)的算法或增加FIELD_SIZE，但它给出的代码，秘密要么返回空白，要么返回一些乱码。

Answer 1

欢迎来到 StackOverflow！

这个问题比 Python 更倾向于密码学，但我很乐意提供帮助。

TL；DR：

reconstruct_secret

有问题。它在某些情况下不起作用。它适用于

secret

较小的近似值，但如果

secret

很大，则很难从

shares

重建值。我会在这里解释为什么。

---

让我们回顾一下 SSS 的实现是如何工作的。假设有一个以下形式的多项式：

P(x, n-1) = S + a*x + b*x^2 + ... c*x^(n-1)

然后，如果

a, b, ..., c

和

P

的值恰好位于曲线上的

x

位置，则可以找到系数

n

。这就是拉格朗日插值定理。您可以在维基百科页面上查看更多相关信息：https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing

代码味道是四舍五入+小数的使用：

def reconstruct_secret(shares):
    sums = Decimal(0)
    for j, share_j in enumerate(shares):
        xj, yj = share_j
        prod = Decimal(1)
        for i, share_i in enumerate(shares):
            xi, _ = share_i
            if i != j:
                # Check if xi is equal to xj
                if xi == xj:
                    continue
                prod *= Decimal(xi) / (Decimal(xi) - Decimal(xj))

        prod *= Decimal(yj)
        sums += prod

    return int(round(sums))

当我们生成份额时，我们通过选择一个随机多项式来实现。我们通过随机选取

0

和

FIELD_SIZE

之间的系数来做到这一点。这里的划分并不是100%准确：

                prod *= Decimal(xi) / (Decimal(xi) - Decimal(xj))

为什么这不起作用？

像像素化一样思考这个问题

如果

FIELD_SIZE << secret

，则系数“无关紧要”。这样想吧：

P(x, 2) = 1000000000000000 + 2x + 3x^2

这个多项式完全由秘密

1000000000000000

支配。很难找到曲线的确切形状，因为它在

x = 0

附近“基本平坦”。我们使用

x = 0

值来找到秘密。您可以看到如下：

P(x, n)

的导数远小于

P(0, n)

处的值。你基本上是根据部分信息重建一些东西。它基本上太“像素化”而无法工作。

舍入误差

当您重建秘密时，您使用的算法存在舍入误差。那是因为当你这样做

a/b

时，你不会得到确切的答案。您会得到一个“大约”正确的答案。自己尝试一下：

>>> 1/3
0.3333333333333333

那些 3 实际上会永远持续下去。查看对应于基础多项式的这一位：

prod *= Decimal(xi) / (Decimal(xi) - Decimal(xj))

为了准确地做到这一点，

(xi - xj)

不应该“太大”。如果它比

xi

大得多，我们将超出表示小数的精度。所以，如果你有

P(x) = 1000000000000000 + 2x + 3x^2

，这些系数变化

很多

，因此，除法的舍入误差主导你的结果，并破坏秘密。 这个问题本质上是

灾难性取消

。 修复

最简单的解决方法是使用不同的算法方法。问题的关键在于，对于较大的

reconstruct_secret

值，

secret

很容易出错。共享很好，但该函数无法准确地重建秘密。请参阅此处的替代方法：

https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing#Python_code