[Crypto学习笔记] shamir共享密钥协议
发布时间：
目录
前置概念
拉格朗日插值法
对于拉格朗日插值法, 其实更广为人知(特别可能是公务员)的应该是以下题目:
试着找出?所代表的数:
1,3,5,7,?
大概学数学的看不惯这种没头没尾的逻辑题, 于是有人使用拉格朗日插值法做了个表情包1, 以下是实现逻辑:
- 假设存在函数f(x)可以始得存在点(1, 1), (2, 3), (3, 5), (4, 7), (5, 114514)
- 我们可以简单构造一个带有五个变量的多项式以满足函数f(x)的需求(这个原理很容易推导出, 我打算把它留给读者, 不过实际上已经有一个可视化视频已经很好地阐述了2.)
- 可以使用拉格朗日插值法进行插值, 硬性凑出五个变量
某种意义上拉格朗日插值法原理与泰勒级数有一定的关联性, 我们先列出公式:
\[\begin{matrix} f(1) = 1 \\ f(2) = 3 \\ f(3) = 5 \\ f(4) = 7 \\ f(5) = 114514 \\ f(x) = a \times x^4 + b \times x^3 + c \times x^2 + d \times x + e \end{matrix}\]当然我们还无法直接求出a,b,c,d,e, 还需要依靠拉格朗日插值法进行计算, 公式如下表达1:
\[\begin{matrix} f(x) = \sum f(x_i) \times f_i(x) \\ f_i(x) = \prod_{j \neq i} \frac{(x-x_j)}{(x_i-x_j)} \end{matrix}\]将5个点带入函数, 有:
\[f(x) = 1 \times \frac{(x-2)(x-3)(x-4)(x-5)}{(1-2)(1-3)(1-4)(1-5)} + 3 \times \frac{(x-1)(x-3)(x-4)(x-5)}{(2-1)(2-3)(2-4)(2-5)} + 5 \times \frac{(x-1)(x-2)(x-4)(x-5)}{(3-1)(3-2)(3-4)(3-5)} + 7 \times \frac{(x-1)(x-2)(x-3)(x-5)}{(4-1)(4-2)(4-3)(4-5)} + 114514 \times \frac{(x-1)(x-2)(x-3)(x-4)}{(5-1)(5-2)(5-3)(5-4)}\]可以计算出结果如下:
\[4771.041666666666*x^4 - 47710.41666666666*x^3 + 166986.4583333333*x^2 - 238550.0833333333*x + 114503.99999999999\]以上结果由sage得出, 我们同样可以使用sage进行验证:
from sage.all import *
x = var('x')
f = 1*(x-2)*(x-3)*(x-4)*(x-5)*((1-2)*(1-3)*(1-4)*(1-5))**(-1) + \
3*(x-1)*(x-3)*(x-4)*(x-5)*((2-1)*(2-3)*(2-4)*(2-5))**(-1) + \
5*(x-1)*(x-2)*(x-4)*(x-5)*((3-1)*(3-2)*(3-4)*(3-5))**(-1) + \
7*(x-1)*(x-2)*(x-3)*(x-5)*((4-1)*(4-2)*(4-3)*(4-5))**(-1) + \
114514*(x-1)*(x-2)*(x-3)*(x-4)*((5-1)*(5-2)*(5-3)*(5-4))**(-1)
print(f.expand())
print(f(x=5))
# 4771.041666666666*x^4 - 47710.41666666666*x^3 + 166986.4583333333*x^2 - 238550.0833333333*x + 114503.99999999999
# 114513.99999999999
符合结论. 在拉格朗日插值法中, \(f_i(x)\)作为开启f(x)传入数值$x_i$的门, 当传入的x为对应数值, 明显有\(f_i(x)=1\), 否则\(f_i(x)=0\), 当然如果从函数上看我们可以有一个更为美妙的过程, 不过这里不是动画, 暂且省略不表.
拉格朗日插值法可以以矩阵形式进行表述:
\[\begin{bmatrix} 1 & x_1 & x_1^2 & ... & x_1^4 \\ 1 & x_2 & x_2^2 & ... & x_2^4 \\ 1 & x_3 & x_3^2 & ... & x_3^4 \\ 1 & x_4 & x_4^2 & ... & x_4^4 \\ 1 & x_5 & x_5^2 & ... & x_5^4 \end{bmatrix} \times \begin{bmatrix} a \\ b \\ c \\ d \\ e \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 5 \\ 7 \\ 114514 \end{bmatrix}\]数值参考以上题目, 对应有:
\[x_i=i\]我们在采用拉格朗日插值法计算时可以通过矩阵与结果反求出向量:
\[\begin{bmatrix} a & b & c & d & e \end{bmatrix} ^T\]shamir原理
想象一下未来某一天要将自己的传家bitcoin交给子孙们, 但是担心传到某一代的时候有人突然决裂, 这时候其他人需要在少人的情况也能获取到bitcoin与其对抗, 但是决裂的人却无法获取bitcoin, shamir共享密钥协议解决了以上问题:
当一段密文需要多位成员保存, 且不确定保存的成员是否包含不可信任的人时, 能保证n位成员保存密钥, 通过n-x位成员也可以还原密文, 其中x < n.
现假设密文为m, 有公式如下3所示:
\[\begin{bmatrix} 1 & x_1 & ... & x_1^{i-1} \\ 1 & x_2 & ... & x_2^{i-1}\\ 1 & x_3 & ... & x_3^{i-1}\\ ... & ... & ... & ...\\ 1 & x_j & ... & x_j^{i-1} \end{bmatrix} \times \begin{bmatrix} m \\ a_1 \\ a_2 \\ ... \\ a_i \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ ... \\ y_i \end{bmatrix} (i<j)\]其中n位成员分别获取私钥为:
\[x_1, x_2, ..., x_j\]如果能凑满所有成员的私钥, 我们可以按代数思维直接通过矩阵求逆获取m:
\[{\begin{bmatrix} 1 & x_1 & ... & x_1^{i-1} \\ 1 & x_2 & ... & x_2^{i-1}\\ 1 & x_3 & ... & x_3^{i-1}\\ ... & ... & ... & ...\\ 1 & x_j & ... & x_j^{i-1} \end{bmatrix}}^{-1} \times \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ ... \\ y_i \end{bmatrix} = \begin{bmatrix} m \\ a_1 \\ a_2 \\ ... \\ a_i \end{bmatrix}\]如果参与获取信息的成员n有: \(i \leq n < j\) 时, 我们可以利用拉格朗日插值法将已知私钥作为函数上的点, 求取:
\[{\begin{bmatrix} m & a_1, a_2 & ... & a_i \end{bmatrix}}^T\]但是当成员n有 n < i 时, 因为缺少信息无法求出.
秩
在代数中描述矩阵常常用到行列式与秩两个概念, 如果行列式可以用来描述矩阵在变换中对空间的伸缩状态, 那么秩可以用来形容矩阵的最小表现维度(在代数证明中很经常能看见秩的存在).
\[A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 3 & 6 & 9 \end{bmatrix}\]我们假设存在以上矩阵A, 稍微对代数有了解可以知道这是一个拥有3个向量的3维矩阵:
\[\begin{matrix} a = \begin{bmatrix}1 & 2 & 3 \end{bmatrix} \\ b = \begin{bmatrix}2 & 4 & 6 \end{bmatrix} \\ c = \begin{bmatrix}3 & 6 & 9 \end{bmatrix} \end{matrix}\]现在我们将三个向量分别表示出来, 可以发现向量之间存在共线关系, 即:
\[\begin{matrix} 2a = b \\ 3a = c \end{matrix}\]实际上在3维空间中我们只需要a向量就可以表示出空间中的所有可达点, 故我们可以说在3维空间中有:
\[rank(A) = rank({\begin{bmatrix} 1 & 2 & 3 \end{bmatrix}}^T) = 1\]即在3维空间中只需要1个向量就可以表示(注: 这是很不严谨的表达手法, 主要是更容易让大家快速理解). 当存在不共线的向量时, 例如如下情况:
\[B = \begin{bmatrix} 1 & 2 & 7 \\ 2 & 4 & 4 \\ 3 & 6 & 5 \end{bmatrix}\]同样可以分解为3个向量进行分析:
\[\begin{matrix} a = \begin{bmatrix}1 & 2 & 3 \end{bmatrix} \\ b = \begin{bmatrix}2 & 4 & 6 \end{bmatrix} \\ c = \begin{bmatrix}3 & 6 & 9 \end{bmatrix} \end{matrix}\]可以发现这次矩阵B中的c向量与其他两个向量线性无关, 所以这次有rank(B) = 2, 可以使用代码进行检验:
from sage.all import *
A = matrix([[1,2,3],[2,4,6],[3,6,9]])
B = matrix([[1,2,7],[2,4,4],[3,6,5]])
print(rank(A))
print(rank(B))
# 1
# 2
对于初学者来说直接使用向量表达是一种很不负责任的描述方式, 那么矩阵表示什么? 向量表示什么? 最终还是要回到空间的变换以更好地回答这些问题. 对于我们常用的空间坐标其实可以表示为一组基向量.
\[O_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]通过分解出的向量x,y,z可以表示出3维空间的任意一点:
\[n = ax + by + cz (a, b, c \in R)\]对于矩阵A则可以表示为\(O_3\)经过变换得到的新空间, 经过变换后x,y,z可以更新为矩阵A上的三个向量, 但是因为A上的x,y,z共线, 有:
\[\begin{matrix} 2x = y \\ 3x = z \end{matrix}\]所以实际上在空间上能够表达的点有:
\[\begin{matrix} n = ax + by + cz \rightarrow n = da \\ d = a + 2b + 3c \\ (a, b, c, d \in R) \end{matrix}\]故空间上的点只需要一个变量就可以表示, 我们可以对比一下一维空间\(O_1\):
\[\begin{matrix} O_1 = [1] \\ n = ax \end{matrix}\]A与\(O_1\)上的点表述方式实际上是相同的, 我们可以将A看作一个新的1维空间, 故A的秩为1.
满秩
当我们把矩阵看作标准空间变换后的结果后, 满秩就很好理解了, 以A为例, 变换前的空间为3维, 但是变换后空间为1维, 故维度实际收缩了, 这是一种不可逆变换, 我们可以说A不是满秩的, 现在假设有一个方阵(可以是矩阵, 这里只是为了凑以下定理)在变换后的维度等于变换前的维度, 则秩为满秩, 这时候矩阵是可逆的, 我们可以发现行列式不为零, 实际上我们有以下定理:
方阵可逆
方阵的行列式不为零
方阵满秩
以上三个命题是等价的. 4
网鼎杯初赛
Crypto1
题目
# SageMath version 10.0, Release Date: 2023-05-20
from sage.all import *
from Crypto.Util.number import *
from secret import flag
flag = flag.lstrip(b"wdflag{").rstrip(b"}")
class ShamirSS:
def __init__(self, coefs, value):
self.coefs = coefs
self.value = value
class ShamirProtocol:
def __init__(self, n_players, threshold, modulus):
self.n_players = n_players
self.threshold = threshold
assert isPrime(modulus), "Modulus must be a prime number"
self.modulus = modulus
def input_share(self, values):
coefs = [
[getRandomRange(1, self.modulus) for _ in range(self.threshold)]
for _ in range(self.n_players)
]
randoms = values + [getRandomRange(1, self.modulus) for _ in range(self.threshold - len(values))]
values = [
sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
for coef in coefs
]
shares = [ShamirSS(coef, value) for coef, value in zip(coefs, values)]
return shares
protocol = ShamirProtocol(len(flag), len(flag) * 2, 257)
values = list(flag)
import os
os.mkdir("shares")
for i in range(10000):
shares = protocol.input_share(values)
save(shares, f"shares/share_{i}.sobj")
分析
本题相比标准的shamir密钥交换稍微做了调整, 通过审计源码可以得知信息如下:
\[[FLAG|A] \times [B] = [C] \mod{257}\]| 其中[ FLAG | A ]分块矩阵中矩阵FLAG由分解为32个数ord()后写入数组构建为方阵, 类似如下: |
| [ FLAG | A ]分块矩阵中的矩阵A则是随机数构成的32x32矩阵, 向量C已知 |
EXP
from Crypto.Util.number import *
from tqdm import *
class ShamirSS:
def __init__(self, coefs, value):
self.coefs = coefs
self.value = value
shares = []
for i in trange(10000):
files = "share_" + str(i) + ".sobj"
sharesi = load(files)
shares.append(sharesi)
def convert_2_Matrix(single_share):
L = []
R = []
for i in single_share:
L.append(i.coefs)
R.append(i.value)
L = Matrix(Zmod(257), L)
R = vector(Zmod(257), R)
A = L[:, :36]
B = L[:, 36:]
if(B.rank() != 36):
v = B.left_kernel().basis()[0]
return (v*A, v*R)
L = Matrix(Zmod(257), 0, 36)
R = []
for i in tqdm(shares):
res = convert_2_Matrix(i)
if(res != None):
l, r = res
L = L.stack(l)
R.append(r)
R = vector(Zmod(257), R)
flag = L.solve_right(R)
print("".join(list(map(chr, flag))))
参考文献
olderciyuan.拉格朗日插值学习笔记[EB/OL]博客园.https://www.cnblogs.com/olderciyuan/p/15578688.html.2021-11-19. ↩ ↩2
3blue1brown.【官方双语】微积分的本质-10-泰勒级数.https://www.bilibili.com/video/BV1Gx411Y7cz/.2017-06-11 ↩
红烧喵.Shamir秘密共享协议[EB/OL]知乎.https://zhuanlan.zhihu.com/p/440667227.2021-12-03 ↩
Shamir秘密共享协议[EB/OL]知乎.https://zhuanlan.zhihu.com/p/440667227.2021-12-03 ↩