题目描述
【实验目的】
- 通过基于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
}