01 秘密共享¶
约 2475 个字 预计阅读时间 12 分钟
数学建模的第一个例子¶
Question
11名科学家正在进行一个秘密项目。他们希望把文件锁在一个柜子里，只有当6名或更多的科学家在场时，柜子才能被打开。问：需要的最小锁数是多少？每个科学家必须携带的最小钥匙数量是多少？
秘密共享-组合数学¶
首先，你想到了高中学过的组合数学！你决定先从基数比较少的情况入手，即只有5名科学家的情况。
特殊情况¶
问题背景
5人在保险柜内存放秘密文件，只有3人及以上在场才能打开，至少几把锁？每个人至少要带多少钥匙？
分析
- 两个人过来的时候，必然至少有一把锁不能被打开。
- 因为我们此时考虑最少锁的情况，所以取任意二人组合不能打开锁的数量为 \(1\)。
- 所以每把锁与一对（没有钥匙的）两人组合对应，要有\(C_{5}^{2}=10\)把锁
- 为什么不能是两对？
- ——因为两对都不能打开同一把锁的情况下，三个人过来的时候，就不能打开保险柜了。
-
三个人过来的时候，必然能打开其中的一把锁。
- 所以每人拥有他不在的两人组合对应的锁的钥匙，每人有\(C_4^2=6\)把钥匙
-
记录如下：
| A | B | C | D | E | 谁没有钥匙？ | |
|---|---|---|---|---|---|---|
| 1 | √ | √ | √ | AB | ||
| 2 | √ | √ | √ | AC | ||
| 3 | √ | √ | √ | AD | ||
| 4 | √ | √ | √ | AE | ||
| 5 | √ | √ | √ | BC | ||
| 6 | √ | √ | √ | BD | ||
| 7 | √ | √ | √ | BE | ||
| 8 | √ | √ | √ | CD | ||
| 9 | √ | √ | √ | CE | ||
| 10 | √ | √ | √ | DE |
\(\therefore\) 至少要有\(10\)把锁，每人有\(6\)把钥匙。
然后我们来考虑一般情况，即有\(2n+1\)名科学家的情况。
一般情况¶
设相关人共有\(2n+1\)人，其中\(n\)人组成的“少数”团体不能打开安全门，任意\(n+1\)人组成的“多数”团体可以打开安全门。
少数与多数
- 两个不同的“少数”团体联合可成为多数团体
- 任一“少数”团体和不属该团体的任一人联合可成为多数团体
需要几把锁？需要多少钥匙？
每把锁与一个“少数”团体对应，至少要有\(C_{2n+1}^n\)把锁。
每人拥有他不在的“少数”团体对应的锁的钥匙，每人有\(C_{2n}^n\)把钥匙。
秘密共享-密码学¶
在密码学里，有专业术语来表示这种情况，叫做门限机制\((t,n)\): 在\(n\)人之间共享秘密，其中任意 \(t\) 人可以重构出秘密，而任意 \(t-1\) 人都不能重构出秘密。
Shamir 门限机制 \((t,n)\)¶
基本思想
通过秘密多项式，将秘密\(s\)分解为\(n\)个秘密，分发给持有者，其中任意不少于\(t\)个秘密均能恢复密文，而任意少于\(t\)个秘密均无法得到密文的任何信息。
分发方法
假设有秘密 \(K\) 要保护，任意取\(t-1\)个随机整数\(\{x_1,\cdots,x_{t-1}\}\)，构造如下多项式：
其中，\(K \in \mathbb{Z}\)，就是我们的秘密。
取\(n\)个不同的整数\(\{c_1,\cdots,c_n\}\)，取公开大素数\(p>n+1,K\)。计算\(b_j\equiv f(c_j)(\mod p)\)，将\((c_j,b_j)\)发送给第\(j\)个持有者。
证明可行性
就是判断任意\(t\)个方程是否有唯一解，任意\(t-1\)个方程是否有无穷多解。
任意\(t\)个方程是否有唯一解
取\(t\)个方程，则有解对应的行列式：
由于\(c_i\)互不相同，所以行列式不为零，有唯一解。
任意\(t-1\)个方程是否有无穷多解
对于任意\(t-1\)个方程，由于我们有\(t\)个未知数，所以有无穷多解。
恢复秘密
任意\(t\)个持有者联合，可以构造\(t\)个方程，从而可以恢复出秘密。
例子：Secret:\(123\); Shamir\((3,5)\)
分配步骤
- 首先确定 \(t\) 和 \(n\)，这里 \(t=3,n=5\)。
- 确定秘密 \(K=123\)，取模数 \(p=127\)，
-
秘密选择 \(t-1=2\) 个随机数 \(x_1=2,x_2=3\)，构造多项式：
\[ f(c)=123+2c+3c^2 \] -
选择 \(n=5\) 个不同的整数 \(c_1=1,c_2=2,c_3=3,c_4=4,c_5=5\)，计算 \(b_j\equiv f(c_j)(\mod p)\)，然后将 \((c_j,b_j)\) 发送给第 \(j\) 个持有者：
\(c_j\) \(f(c_j)\) \(b_j\) 1 128 1 2 139 12 3 156 29 4 179 52 5 208 81
恢复秘密
-
集齐任意\(t\)个钥匙，例如第一个人的\((c_1,b_1)\)，第二个人的\((c_2,b_2)\)，第五个人的\((c_5,b_5)\)，则可以构造如下方程组：
\[ \begin{cases} K+1\cdot x_1+1^2\cdot x_2\equiv 1(\mod 127) \\ K+2\cdot x_1+2^2\cdot x_2\equiv 12(\mod 127) \\ K+5\cdot x_1+5^2\cdot x_2\equiv 81(\mod 127) \\ \end{cases} \]
解得
所以密码\(K=123\)。
秘密共享-数论¶
线性同余方程
线性同余方程是指形如 \(ax\equiv b(\mod m)\) 的方程，其中 \(a,b,m\) 为整数，\(m>0\)。
- 当且仅当 \(gcd(a,m)|b\) 时，线性同余方程有解。
- 当 \(gcd(a,m)=1\) 时，方程的解为 \(a^{-1}b\)，且小于 \(m\)的非负整数解唯一。
- \(gcd(a,m)\neq 1\)的情况，例如\(6\cdot x \equiv 3(\mod 8)\)，解为 \(x=3\) 和 \(x=7\)。
- \(a^{-1}\) 是 \(a\) 在模 \(m\) 意义下的逆元。
什么是逆？
设 \(a,b\) 为整数，\(m\) 为正整数，若 \(ab\equiv 1(\mod m)\)，则称 \(a\) 模 \(m\) 可逆，且 \(b\) 是 \(a\) 在模 \(m\) 意义下的逆元，记为 \(a^{-1}\)。
如何求逆？
大衍求一术
求\(27^{-1}(\mod 64)\)
其中,\(64=2\cdot 27+10\)，所以
其中,\(27=2\cdot 10+7\)，所以
其中,\(10=1\cdot 7+3\)，所以
其中,\(7=2\cdot 3+1\)，所以
所以 \(27^{-1}\equiv 19(\mod 64)\)。
扩展欧几里得算法
用欧拉公式列出一系列等式，直到出现末尾的1。然后从最后一个等式开始，依次代入前面的等式，直到把\(gcd(a, b)\)写成\(sa + tm\)。其中，\(a\)的系数就是\(a^{-1}\)。
例如，求\(27^{-1}(\mod 64)\)：
所以
所以 \(27^{-1}\equiv 19(\mod 64)\)。
中国剩余定理
设 \(m_1,m_2,\cdots,m_k\) 为两两互质的正整数，\(a_1,a_2,\cdots,a_k\) 为任意整数，记\(M = m_1m_2\cdots m_k\)，则同余方程组
有小于 \(M\) 的唯一正整数解\(x=M_1M_1^{-1}a_1+M_2M_2^{-1}a_2+\cdots+M_kM_k^{-1}a_k(\mod M)\)，其中\(M_i=M/m_i\)，\(M_i^{-1}\)是\(M_i\)在模\(m_i\)意义下的逆元。
如何求解？
- 计算 \(M=m_1m_2\cdots m_k\)。
- 计算 \(M_i=M/m_i\)。
- 计算 \(M_i^{-1}\)。
- 解为 \(x=M_1M_1^{-1}a_1+M_2M_2^{-1}a_2+\cdots+M_kM_k^{-1}a_k(\mod M)\)。
例如，求解 \(x\equiv 2(\mod 3),x\equiv 3(\mod 5),x\equiv 2(\mod 7)\)：
Asmuth-Bloom 门限机制¶
参数选取
记秘密为\(K\)，\(n\)个人，\(t\)个人可以恢复秘密。
选取两两互素的整数\(p\)和\(m_1,m_2,\cdots,m_n\)，满足\(p>K\)以及\(m_1<m_2<\cdots<m_n\)，且
也就是说任意\(t\)个整数的乘积都大于\(p\)乘以任意\(t-1\)个整数的乘积。
秘密分割
为了选出一个能代表\(K\)的数\(K'<m_1\cdots m_t\)，我们选取一个随机数\(r\in \mathbb{N}\)，满足\(0\leq r \leq \frac{m_1\cdots m_t}{p}-1\)。记\(K'=K+rp\)。
\(K'=K+rp\leq K+(\frac{m_1\cdots m_t}{p}-1)p=K+m_1\cdots m_t-p\leq m_1\cdots m_t\)。
令\(k_j \equiv K'(\mod m_j),1\leq j\leq n\)，将秘密份额\((k_j,m_j)\)分发给第\(j\)个持有者。
秘密恢复
当\(t\)个持有者联合时，由\((k_j,m_j)\)，可构建方程组
\(k_j \equiv K'(\mod m_j)\)也就意味着\(K'\equiv k_j(\mod m_j)\)
然后可由中国剩余定理求解\(x\)，
证明可行性
判断任意\(t\)个方程可行，任意\(t-1\)个方程不可行。
为什么任意\(t\)个方程可行？
由于中国剩余定理，所以任意\(t\)个方程都有小于\(m_{k_1}m_{k_2}\cdots m_{k_t}\)的唯一解\(x\)。
当我们限制了\(K'<m_1\cdots m_t\)
那么\(n\)个方程解出来有唯一解\(K'<m_1\cdots m_t \leq m_{k_1}m_{k_2}\cdots m_{k_t}\)
而对任意\(t\)个方程能解出唯一解\(x \leq m_{k_1}m_{k_2}\cdots m_{k_t}\)，由于区间的限制以及解的唯一性，所以\(x=K'\)。
如果\(x\neq K'\)，则\(t\)个方程的解不唯一，与中国剩余定理矛盾。
为什么任意\(t-1\)个方程不可行？
因为对任意\(t-1\)个方程，我们解出的那个唯一解\(x<m_{k_1}m_{k_2}\cdots m_{k_{t-1}}\)的。
而\(m_{k_1}m_{k_2}\cdots m_{k_{t-1}}<q*m_{k_1}m_{k_2}\cdots m_{k_t}\)。
所以在\(m_{k_1}m_{k_2}\cdots m_{k_{t-1}}\)和\(q*m_{k_1}m_{k_2}\cdots m_{k_t}\)之间，仍有数解，所以不可行。