秘密共享

Shamir门限机制

很简单,实际上就是求解线性方程组

假设有\(n\)个人,希望\(t,(t<n)\)个人提供信息的时候能得到秘密,那就构造一个有\(t\)个未知数的多项式, 然后给每个人一个多项式上的点,这样提供信息的人数大于t的时候,就可以求解出多项式,从而得到秘密.

\(K\)是秘密,\(t\)是门限,\(n\)是人数,那么选取 \(t-1\)个数\(a_1,a_2,\cdots,a_{t-1}\),构造多项式

\[f(x)=K+a_1x+a_2x^2+\cdots+a_{t-1}x^{t-1}\]

信息选取为\((x_i,f(x_i))\mod p\),其中\(p\)是素数,\(x_i\)是随机数

(或者别的也行,1,2,3,选择随机数主要是为了让规律不那么明显,取模感觉是为了让数字小一点,不取也是可以的)

这样把\(n\)个不同的信息给到\(n\)个人,然后\(t\)个人提供信息的时候,就可以求解出多项式,从而得到秘密.

中国剩余定理

给一些定义:

• 整除: \(a|b\)表示\(a\)整除\(b\),即\(\exists k\in Z,s.t.\;b=ak\)

• 最大公约数: \(\gcd(a,b)\)表示\(a\)和\(b\)的最大公约数

• 同余: \(a\equiv b \mod p\)表示\(a\)和\(b\)除以\(p\)的余数相等

• 逆元: 若\(\exists b\in Z,s.t.\;a\cdot b\equiv 1 \mod p\),称\(a\)模\(p\)可逆,并称\(b\)是\(a\)模\(p\)的逆元,记为\(a^{-1}\)

  • \(a\)模\(p\)可逆的充要条件是\(gcd(a,p)=1\)

    • 充分性:由费马小定理\(a^{p-1}\equiv 1 \mod p\),故令\(b=a^{p-2}\)即可
    • 必要性: \(\exists b\in Z,s.t.\;a\cdot b\equiv 1 \mod p,\;i.e.\;\exists k\in Z,s.t.\;ab=kp+1\Rightarrow \frac{a}{p}=\frac{kp+1}{b}\) 若\(\gcd(a,p)=s>1\)那么\((sb-k)p=1\)矛盾

• 一次同余方程:\(ax\equiv b \mod p\)称为模p的一次同余方程

  • 方程有解的充要条件是:\(\gcd(a,p)|b\)
  • 当\(\gcd(a,p)=1\),方程的解是\(a^{-1}b\),且小于\(p\)的非负整数解是唯一的

中国剩余定理

• 一次同余方程组 \(x\equiv a_j\mod p_j,1\leq j\leq k\)小于\(p\)的解是唯一的:

\[ x = N_1N_1^{-1}a_1+\cdots+N_kN_k^{-1}a_k \]

• 其中 \(p = p_1p_2\cdots p_k,N_j = \frac{p}{p_j},N_j^{-1}\)是\(N_j\)模\(p_j\)的逆

• \(\forall l\in Z,x+lp\)也是方程的解

Asmuth-Bloom门限机制

参考这个论文

太复杂了,对着看吧

RESOURCES