题目描述
【实验目的】
- 通过基于Shamir门限方案的密钥分割及恢复的演示，理解密钥分割的重要性，理解密钥分割的基本原理和作用，掌握基于Shamir门限方案的密钥分割软件的使用
【实验原理】
秘密共享体制为将秘密分给多人掌管提供了可能。例如重要场所的通行、遗嘱的生效等都必须由两人或多人同时参与才能生效，这时都需要将秘密分给多人掌管并同时参与才能恢复。在实际应用中，秘密共享的要求多种多样、形形色色，每一种解决问题的方案都可成为一种体制。1979年，Shamir在提出秘密分享思想的同时，利用拉格朗日插值多项式理论设计出了一个具体的（t,n）秘密分享方案。1979年以后，人们通过对秘密共享问题的分析研究，构建出了许多类型的秘密共享体制。具有代表性和一般性的除了有Shamir提出的(t,n)门限体制，还有Blakley提出的矢量体制，Asmuth和Bloom提出的同余类体制，Karnin提出的矩阵法体制等。
一般地，一个由秘密分发者D和参与者P1，P2，…，Pn构成的（t,n）秘密分享体制包含下面两个协议：
（1） 秘密分发协议：在这个协议中，秘密分发者D在n个参与者中分享秘密s，每个参与者Pi获得一个碎片si，i=1,2，…，n。
（2） 秘密重构协议：在这个协议中，任意不少于t个参与者一起合作，以自己的碎片为输入，重构原秘密s。
一个安全的（t,n）秘密分享体制必须同时提供两个性质：一方面，任意t个参与者通过提供自己的碎片能够协作地恢复出原秘密s；另一方面，任意少于t个参与者即便拥有自己的碎片也无法计算关于原秘密s的任何信息。一般称这里的t为门限值。
Shamir提出的基于LaGrange插值公式的密钥分存思想是,利用有限域GF(p)上的t-1次多项式
h(x)= at- 1xt- 1+ … + a1x+ a0 mod p (1)
构造秘密共享的（t,n）门限体制。其中，所选的随机素数p要大于最大可能的秘密数S和参与者总数n，并且公开；S=h(0)=a0，而at-1，at-2，… ，a1为选用的随机系数，这些都需要保密，在生成n个秘密份额之后即可销毁。通过计算多项式h(x)对n个不同xi的取值就给出每个人的秘密份额:
Si= h(xi)mod p，i= 1,2,3,… ,n (2)
每一(xi,Si)对就是曲线h上的一个点，可看作是用户的标识符。由于任意t个点都可唯一地确定相应的t- 1次多项式，所以，秘密S可以从t个秘密份额重构。给定任意t个秘密份额Si1，Si2，… ，Sit，由LaGrange插值公式重构的多项式为
具体步骤如下。如图所示
需要使用到逆元计算；
关于逆元，可以参看csdn一篇文章
其中有些例子不够完善，请谨慎选取，小心验证。
具体例子：
n=5, t=3, p=17; 随机选取K=13,a1=10,a2=2;
于是有
解密的时候选取 （1 8）（2 7） （5 11）来解密
上面的例子每个倒数都计算了一次逆元，大家可以想想有没有什么简化的方法。
输入
大素数p
子秘钥总数n
门限值t
输出
设置的密钥与恢复的密钥的差值
样例
输入：
1006000813
10
3
输出：
0
解题
其实你可以先不看问题描述的，我先大白话解释一下。
Shamir算法解决的问题是，将一个数字密钥key分解成n个碎片交给每一个人，当有至少t个人聚在一起的时候，就可以解出密码key。
然后可以看回上面的问题描述了。
主要分为两大模块：
- 分发
- 重构
分发
从具体例子入手，在描述中，
n=5, t=3, p=17; 随机选取 K=13,
=10,
=2;
这里的K就是密钥key，随机选取，在问题中，我们定死它为13
t是还原出密钥的最少碎片数，同时意味着最高次项为t-1=2，即平方
每个碎片i的形式都是
那很方便写出，产生第i个碎片的函数(i<=n)：
func makeKey(i, t, p, K int) int {
ans := K
for time := 1; time < t; time++ {
ans += CONST_A[time] * pow(i, time)
}
return ans % p
}
其中
CONST_A = []int{0, 10, 2, 3, 8, 7, 5, 4, 3}
由我随机生成，注意数组索引为1和2的两个元素，为题意给的10、2
其实问题描述没有给出这个序列的话，意味着测试用例t不会超过3
重构
本题的难点就是重构，这里需要一点先决知识
- 数论逆元 参考 OI Wiki-乘法逆元
欢迎回来，通过上面链接，我获得了求逆元的一个函数
func qpow(a, b int) int {
ans := 1
p := b+2
a = (a%p + p) % p
for ; b != 0; b >>= 1 {
if b&1 != 0 {
ans = (a * ans) % p
}
a = a * a % p
}
return ans
}
用的是快速幂那个，几乎原封不动的搬了
然后就是解密，或者说重构了，因为任意t个可以揭秘，不妨取前t个
下面的arr为通过makeKey获得的碎片的序列，p是输入里面的大素数
func deKey(arr []int, t int, p int) int {
ans := 0
for i := 0; i < t; i++ {
tmp := i
Vi := arr[i]
for j := (i + 1) % t; j != tmp; j %= t {
Vi *= (0 - j -1)
Vi *= qpow(i-j, p-2)
Vi %= p
j++
}
ans += Vi
}
return ans % p
}
内部的for循环写得有点抽象，但意思是要:
当i=0时，j遍历的数组元素为1,2
当i=1时，j遍历的数组元素为2,0
当i=2时，j遍历的数组元素为0,1
其实你也可以写成从0开始，让j!=i，且j最多为t-1
我这种写法类似于循环的队列，这一步卡我挺久，嘿嘿
毕竟有时候，顺序就有价值
于是加上输入输出，可以得到我们的完成程序：
package main
import (
"bufio"
"fmt"
"io"
"os"
)
var CONST_A []int
// 生成第i个碎片
func makeKey(i, t, p, K int) int {
ans := K
for time := 1; time < t; time++ {
ans += CONST_A[time] * pow(i, time)
}
return ans % p
}
// 重构，获得密钥
func deKey(arr []int, t int, p int) int {
ans := 0
for i := 0; i < t; i++ {
tmp := i
Vi := arr[i]
for j := (i + 1) % t; j != tmp; j %= t {
Vi *= (0 - j -1)
Vi *= qpow(i-j, p-2)
Vi%=p
j++
}
ans += Vi
}
return ans % p
}
// 求a对b+2的逆元
func qpow(a, b int) int {
ans := 1
p := b+2
a = (a%p + p) % p
for ; b != 0; b >>= 1 {
if b&1 != 0 {
ans = (a * ans) % p
}
a = a * a % p
}
return ans
}
func id_195(_r io.Reader, _w io.Writer) {
in := bufio.NewReader(_r)
out := bufio.NewWriter(_w)
defer out.Flush()
var t, n, p int
K := 13
fmt.Fscan(in, &p, &n, &t)
y_seq := []int{} // 子密钥的序列
for i := 1; i <= n; i++ {
y_seq = append(y_seq, makeKey(i, t, p, K))
}
DE_K := deKey(y_seq, t, p)
fmt.Println(K-DE_K)
}
func main() {
CONST_A = []int{0, 10, 2, 3, 8, 7, 5, 4, 3}
id_195(os.Stdin, os.Stdout)
}
func pow(x int, n int) int {
result := 1
for i := 0; i < n; i++ {
result *= x
}
return result
}
