Python實現Shamir密鑰分享算法中的解密過程

發表於 | 分類於

Shamir的$(k,n)$密鑰分享算法將祕密分為$n$個子祕密，任意$k$個子祕密都可以恢復出$s$，而任意$k-1$個子祕密無法恢復出$s$。

Shamir密鑰分享算法（TSSS）最早由Shamir和Blackly在1970年基於Lagrange插值法提出。下文先簡要介紹Shamir密鑰分享算法加密的原理，再介紹如何使用Python進行解密。

TSSS算法的加密

Shamir的$(k,n)$密鑰分享算法將祕密分為$n$個子祕密，任意$k$個子祕密都可以恢復密文$s$，而任意小於$k$個子祕密無法得到$s$的任何訊息。

構造多項式

第一步：對於密文$s$，設其滿足$s\in\mathbb Z_p$，其中$p>k$。（確保所有的運算都在有限域$\mathbb Z_p$中進行）

第二步：令$a_0=s$，並任取$k-1$個整數$a_1,a_2,…,a_{k-1}\in\mathbb Z_p$。

第三步：定義多項式$f(x)=\sum\limits^{k-1}_{i=0} {a_ix^i}({\rm mod}\ p)$。

分發密鑰

第一步：任取$n$個數$x_1,x_2,…,x_n$，分別計算$f(x_1),f(x_2),…,f(x_n)$。（一般可取$x_i=i$）

第二步：對於$n$個對象$P_1,P_2,…,P_n$。$\forall 1\leqslant i\leqslant n$，將$(x_i,f(x_i))$發送給$P_i$。

TSSS算法的解密

首先，我們需要了解Lagrange插值法。

Lagrange插值法

對於$n+1$個數值對$(x_0,y_0),(x_1,y_1),…,(x_n,y_n)$（其中$x_i$互不相同），有且僅有一個次數不超過$n$的多項式$L(x)$對$\forall 0\leqslant i\leqslant n$，$L(x_i)=y_i$，此多項式即為Lagrange插值多項式，其表達式為：

$L(x)=\sum\limits^n_{j=0} {y_jl_j(x)}$

其中$l_j(x)$為Lagrange基本多項式，其表達式為：

$l_j(x)=\prod\limits^n_{i\not =j} {\frac {x-x_i} {x_j-x_i} }\ (0\leqslant j\leqslant n)$

可以注意到，$l_j(x_i)=\begin{cases} 1\ (i=j)\\0\ (i\not=j) \end{cases}\ (0\leqslant i\leqslant n)$。

解密

設現已有$k$個對象$P_{i_1},P_{i_2},…,P_{i_k}$的數據$(x_{i_1},f(x_{i_1})),(x_{i_2},f(x_{i_2})),…,(x_{i_k},f(x_{i_k}))$。

由於多項式$f(x)$的次數不超過$k-1$，又有對應的$k$個數值對，因此$f(x)$為Lagrange插值多項式。

$f(x)=\sum\limits^k_{j=1} {(f(x_{i_j})\prod\limits^k_{m\not =j} {\frac {x-x_{i_m}} {x_{i_j}-x_{i_m}} )} }$

（注意：Lagrange基本多項式的除法是在$\mathbb Z_p$中的，即等價於乘以除數的逆）

代碼如下（其中的EEA已在Python實現RSA算法中的解密過程中提及，不再贅述）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def eea(a,b):
    if b==0:
        return a,1,0
    r,x,y=eea(b,a%b)
    # ax+by=r
    # return r,x,y successively
    return r,y,x-a//b*y
def tsss(s_dict,n,k,p):
    # s_dict is 
    s=0
    for i in range(n): 
        up=1
        down=1
        for j in range(n): 
            if i!=j: 
                up*=-s_dict[j][0]
                down*=s_dict[i][0]-s_dict[j][0]
        delta=(up*eea(down,p)[1])%p
        s+=delta*s_dict[i][1]
    return s%p
# There is a testcase below
print(tsss([(1,8),(3,10),(5,11)],3,5,17)) # It prints 13

例題

解密由Shamir的$(5,9)$密鑰分享算法加密的密文$s\in\mathbb Z_{1125899906900597}$。所有子密碼擁有者的數據如下：

$i$ $s_i$
1 75044643784737
2 940519894412855
3 941263003333598
4 736739711411826
5 254180887785524
6 940382343666996
7 132205297839880
8 63775631863924
9 1111084448671404

使用代碼

1
2
3
s_dict=[(1,75044643784737),(2,940519894412855),(3,941263003333598),(4,736739711411826),(5,254180887785524),(6,940382343666996),(7,132205297839880),(8,63775631863924),(9,1111084448671404)]
p=1125899906900597
print(tsss(s_dict,5,9,p))

可得

1
s=330836359559300
0%