Shamir秘密共享

作者：hxd

日期：2025年3月28日

1. 秘密共享

秘密 $s$ （通过某种方案）被分为 $n$ 个部分,每个部分称为份额(share),由一个参与者持有，使得

  • 由 $k$ 个或多于 $k$ 个参与者所持有的部分信息可重构 $s$
  • 由少于 $k$ 个参与者所持有的部分信息则无法重构 $s$

称该方案为 $(k,n)$ 门限秘密共享方案，$k$ 称为门限值。

2. Shamir秘密共享（Shamir Secret Sharing SSS）

Shamir秘密共享（Shamir’s Secret Sharing, SSS） 是一种密码学协议，由 Adi Shamir 在 1979 年提出。它的核心思想是将一个秘密（如密钥或敏感数据）分成多个部分（称为“份额”或“shares”），并将这些份额分发给多个参与者。只有达到一定数量的份额（称为“阈(yu)值”）才能恢复出原始秘密，而少于阈值的份额无法提供任何关于秘密的信息。

SSS 是一种门限秘密共享方案，广泛应用于分布式系统、密码学、数据备份和安全多方计算等领域。

前言

多项式上的 $k$ 个点能够唯一确定小于或等于 $k−1$ 次的多项式一般地，设${(x_1,y_1),…,(x_k,y_k)}$是平面上$k$个不同的点构成的点集，那么在平面上存在唯一的$k-1$次多项式$f(x)=a_0+a_1x+\cdots +a_{k-1}x^{k-1}$通过这$k$个点，其中$a_0,a_1,…a_k-1$是随机数。

确定好门限值$k$和总值$n$，若把秘密 $s$取做$f(0)$ ，为每个参与者生成一个份额$(x_i, y_i)$，其中$y_i = f(x_i)$。$x_i(i=1\cdots n)$作为参与方id，$n$个份额取做$(x_i,f(x_i))(i=1,…n)$，那么利用其中任意$k$个份额可以重构$f(x)$，从而可以得到秘密$s$。

构造

  • 设$GF(q)$为大素数$q$生成的有限域，其中$q\ge n+1$.

  • 秘密$s$是$GF(q)/{0}$上均匀选区的随机数，即$s\in GF(q)/{0}$.

  • 在$GF(q)$上构造一个$k-1$次多项式$f(x)=a_0+a_1x+\cdots +a_{k-1}x^{k-1}$，其中：$a_0=s，a_i\in GF(q)/{0}(i\ne 0)$

  • $n$个参与者$P_1,P_2…,P_n$，其中$P_i$的份额为$f(i)$。任意$k$个参与者想要得到秘密$s$，可使用

例如：假定一个秘密值$s=45$，要求将其分给10个参与方，至少 3 方参与计算才能够恢复出原始秘密，即 $n=10,k=3$。构造对应的多项式 $f(x)=45+19x+13x^2$。在此多项式上选取连续的整数点作为各个子秘密：

秘密重建

对于 $y_i$ 值的任意 $k$ 个子集，我们可以通过插值找到 $f(x)$ 的多项式系数，然后计算 $s=f(0)$。另一方面，仅知道子集中的 $k−1$ 个并不足以计算出 $s$。

在生成秘密份额的时候，已经确定需要$k$ 个秘密份额来恢复原始秘密。即根据$(x_1,y_1),(x_2,y_2),…,(x_k,y_k)$ 等一系列点构造出原始的多项式 $f(x)$，进而求解得到秘密值 $s=f(0)=a_0$。

由Lagrange插值公式得：给定$n+1$个数据点$(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$，其中所有的$x_i$互不相同，拉格朗日插值多项式$f(x)$可以表示为：

其中，$\ell_i(x)$是拉格朗日基多项式（也称为插值基函数），定义为：

基多项式的性质

  • 每个基多项式$\ell_i(x)$满足：

  • 因此，$P(x_i) = y_i$对所有$i$成立，确保多项式通过所有给定点。

  1. 当$j = i$时（即$x=x_{i}$） 基多项式$\ell_i(x)$的定义为：$\ell_i(x) = \prod_{\substack{0 \leq j \leq n \ j \neq i}} \frac{x-x_{j}}{x_{i}-x_{j}}$。将$x=x_{i}$代入：

    • 分子部分：$x_i - x_j$（与分母相同）。
    • 分母部分：$x_i - x_j$（与分子相同）。

    因此，每一项的值为$\frac{x_i - x_j}{x_i - x_j} = 1$，连乘后得到：

    $\ell_i(x_i)=\prod_{j\neq i}1=1.$

2.当$j \neq i$时（即$x = x_k$且$k \neq i$）

观察$\ell_i(x)$的连乘积形式：

$\ell_i(x)=\frac{(x-x_0)}{(x_i-x_0)}\cdot\frac{(x-x_1)}{(x_i-x_1)}\cdots\frac{(x-x_{i-1})}{(x_i-x_{i-1})}\cdot\frac{(x-x_{i+1})}{(x_i-x_{i+1})}\cdots\frac{(x-x_n)}{(x_i-x_n)}$

当$x = x_k$（$k \neq i$）时，连乘积中必定存在一项分子为$x_k - x_k = 0$（即第$k$项）。因此：

$\ell_i(x_k) = \text{（其他项）} \cdot \frac{x_k - x_k}{x_i - x_k} \cdot \text{（其他项）} = 0.$

直观理解

  • $\ell_i(x)$是一个“开关函数”：它在$x_i$处取值为 1，在其他数据点$x_j$（$j \neq i$）处强制为 0。
  • 插值多项式的构造：通过将每个$y_i$与对应的$\ell_i(x)$相乘后相加（$P(x) = \sum y_i \ell_i(x)$），可以确保：
    • 在$x = x_i$时，只有$\ell_i(x_i) = 1$，其他基函数均为 0，因此$P(x_i) = y_i$。
    • 在其他点$x_j$（$j \neq i$），$\ell_i(x_j) = 0$的机制避免了不同$y_j$之间的干扰。

例子验证

假设有 3 个点$(x_0, x_1, x_2)$，基函数$\ell_1(x)$为：

  • 在$x = x_1$时：
  • 在$x = x_0$或$x = x_2$时：

为了重建秘密，任意选取3个参与方的秘密份额作为输入。这里选择 id 为 2，3，6的参与方进行秘密重建。

$(x_0，y_0)=(2,135);（x_1，y_1)=(3,219);（x_2，y_2)=(6,627);$

或者可以看出其实秘密

所以秘密就是$s=a_0=45$。

代码实现：

Python代码实现如下：

import random
from math import ceil #ceil 是 math 模块中的一个函数，用于返回大于或等于给定数字的最小整数。例如，ceil(4.2)返回5
from decimal import Decimal#Decimal 是 decimal 模块中的一个类，用于进行精确的十进制浮点运算，适用于需要高精度的金融计算等场景
FIELD_SIZE=10*5

def reconstruct_secret(shares):#shares代表份额
    #使用拉格朗日插值法重构秘密
    sums=0
    prod_arr=[]

    for j,share_j in enumerate(shares):#enumerate表示同时获取索引值和元素值
        xj,yj=share_j;
        prod=Decimal(1)#prod等于高精度的1
        for i,share_i in enumerate(shares):
            xi,_=share_i
            if i!=j:#当i不等于j时
                prod*=Decimal(Decimal(xi)/(xj-xi))
        prod*=yj
        sums+=Decimal(prod)
    return int(round(Decimal(sums), 0))
        #sums 转换为 Decimal 类型，并四舍五入到最接近的整数(0表示四舍五入到小数点后0位)，然后将结果转换为 int 类型并返回


def polynom(x,coefficients):    #coefficients是多项式列表
    #多项式计算的值
    point=0
    for coefficient_index,coefficients_value in enumerate(coefficients[::-1]):
        #反向遍历coefficients列表，从列表最后一个元素开始，依次向前遍历每个元素
        point+=x**coefficient_index*coefficients_value
    #print(point)
    return point    #返回计算的值

def coeff(k,secret):
    #随机构造多项式，k-1次的，常数是秘密
    coeff=[random.randrange(0,FIELD_SIZE) for i in range(k-1)]
    #生成包含k-1个随机值a_i的列表
    coeff.append(secret) #append()秘密到列表后面了
    return coeff#返回多项式列表

def generate_shares(n,k,secret):
    #n代表秘密总数，k代表阀值
    #secret代表秘密
    coefficients=coeff(k,secret)#构造多项式，coefficients是多项式列表
    shares=[];

    for i in range(1,n+1):
        x=random.randrange(1,FIELD_SIZE)
        shares.append((x,polynom(x,coefficients)))#返回的是份额(x_i,y_i)的列表
    #print(shares)
    return shares

if __name__ == '__main__':
    n=int(input("请输入秘密s被分为几个部分n:"))
    k=int(input("请输入阀值k:"))
    secret=int(input("请输入秘密s:"))
    print(f"秘密s:{secret}")
    #第一步:生成每个人的份额
    shares=generate_shares(n,k,secret)#生成每个人的份额
    print(f'每个人的份额是:{", ".join(str(share) for share in shares)}')
    #第二部:重构秘密
    pool=random.sample(shares,k)#随机从shares列表中随机选择n个不重复的元素
    print(f'结合份额:{",".join(str(share) for share in pool)}')
    print(f"秘密重构:{reconstruct_secret(pool)}")