秘密共享

发表于 | 更新于: | 分类于

拉格朗日插值法

对某个多项式函数，已知有给定的k + 1个取值点：(x0,y0)...(xk,yk)
假设任意两个不同的xj都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：

1
2
3
l0 = (((x-x1)(x-x2)...(x-xk))/((x0-x1)(x0-x2)...(x0-xk)))*y0
    ...
lk = ...

f(x) = l0+l1...+lk即可求出多项式

example

1
2
3
4
5
6
7
已知3个点(4,10)(5,5.25)(6,1)

l0 = (((x-5)(x-6))/((4-5)(4-6))) * 10
l1 = (((x-4)(x-6))/((5-4)(5-6))) * 5.25
l2 = (((x-4)(x-5))/((6-4)(6-5))) * 1

f(x) = l0+l1+l2 = 1/4(x^2-28x+136)

Shamir 秘密共享

生成

  • 设需要生成w个密钥，至少需要t个密钥才能算出真实密钥
  • 选择一个数P，之后所有数都需要进行模运算
  • 设置真实密钥K
  • 随机选择t-1个不大于P的数 a0,a1...at-1
  • 得到多项式 f(x)=K+a0x+a1x^2...+at-1x^t
  • 将x=1.x=2...x=w带入多项式即可获得多个密钥(1,k1)(2,k2)...(w,kw)

解密

  • 利用拉格朗日插值法即可算出多项式
  • 需要带上模计算多项式，如果计算多项式时有除法需要进行计算模乘逆元
  • 因为只需要K所以计算的时候可以直接x=0

eg1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
w=4,t=3,K=2,p=23，选择随机数 a0=3, a1=2

加密

得到多项式 f(x) = (2 + 3x + 2x^2) mod 23
f(1) = 2, f(2) = 16, f(3) = 6, f(4) = 0
获得4个密钥(1,2)(2,16)(3,6)(4,0)

解密

选择其中三个进行解密，(1,7)(3,6)(4,0)

l0 = (((x-3)(x-4))/((1-3)(1-4)))*7
l1 = (((x-1)(x-4))/((3-1)(3-4)))*6
l2 = (((x-1)(x-3))/((4-1)(4-3)))*0

将x=0带入可得

l0 = 14
l1 = -12
l2 = 0

可得k = (l0+l1+l2) mod 23
     = 2 mod 23
     = 2

eg2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
w=5,t=3,k=13,p=17,选择随机数a0=10,a1=2

加密

得到多项式 f(x) = (13 + 10x + 2x^2) mod 17
f(1) = 8, f(2) = 7, f(3) = 10, f(4) = 0, f(5) = 11
获得5个密钥(1,8)(2,7)(3,10)(4,0)(5,11)

解密

选择其中三个进行解密，(1,8)(2,7)(5,11)

l0 = 11 * ( ((x-1)(x-2)) / ((5-1)(5-2)) )
l1 = 7  * ( ((x-1)(x-5)) / ((2-1)(2-5)) )
l2 = 8  * ( ((x-2)(x-5)) / ((1-2)(1-5)) )

将 x=0 带入

l0 = 22/12
l1 = -140/12
l2 = 240/12

K = (l0+l1+l2) mod 17
  = (61/6) mod 17
  = (61 * 6^-1) mod 17 // 6^-1为6关于17的模乘逆元为3
  = (61 * 3) mod 17 
  = 13

中国剩余定理

example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
w=5,t=3,K=117

选择w个d,要求单调递增并两两互素,t个最小的d相乘大于K,K大于t-1个最大d相乘
d1=4,d2=5,d3=7,d4=9,d5=11

计算 ki=Key mod di // = -> \equal

k1 = 117 mod 4 = 1
k2 = 117 mod 5 = 2
k3 = 117 mod 7 = 5
k4 = 117 mod 9 = 0
k5 = 117 mod 11 = 7

即五个密钥(1,4),(2,5),(3,7),(0,9),(7,11)

解密
选其中三个密钥(1,4)(2,5)(3,7)
可得

k mod 4 = 1
k mod 5 = 2
k mod 11 = 7

分解为
k1 mod 4 = 1, k1 mod 5 = 0, k1 mod 11 = 0
  -> 5 * 11 * x1 mod 4 = 1
  -> x1 = 3
  -> k1 = 55 * 3 = 165

k2 mod 4 = 0, k2 mod 5 = 2, k2 mod 11 = 0
  -> 4 * 11 * x2 mod 5 = 2
  -> 44 * x2 * 2^-1 mod 5 = 1 // 2^-1 为2关于5的模乘逆元
  -> 44 * x2 * 3 mod 5 = 1
  -> 132 * x2 mod 5 = 1 // 相当于算132关于5的模乘逆元
  -> x2 = 3
  -> k2 = 44 * 3 = 132

k3 mod 4 = 0, k3 mod 5 = 0, k3 mod 11 = 7
  -> 4 * 5 * x3 mod 11 = 7
  -> 20 * x3 * 7^-1 mod 11 = 1 // 7^-1 为7关于11的模乘逆元
  -> 20 * x3 * 8 mod 11 = 1
  -> 160 * x3 mod 11 = 1 // 相当于算160关于11的模乘逆元
  -> x3 = 2
  -> k3 = 40

K = (k1 + k2 + k3) mod 4*5*11
  = (165+132+40) mod 220
  = 337 mod 220
  = 117

另一种：
k1 mod 4 = 1, k1 mod 5 = 0, k1 mod 11 = 0
  -> 1 * (k1 mod 4 = 1, k1 mod 5 = 0, k1 mod 11 = 0) 
  -> 5 * 11 * x1 mod 4 = 1
  -> x1 = 3
  -> k1 = 1 * 55 * 3 = 165

k2 mod 4 = 0, k2 mod 5 = 2, k2 mod 11 = 0
  -> 2 * (k2 mod 4 = 0, k2 mod 5 = 1, k2 mod 11 = 0)
  -> 4 * 11 * x2 mod 5 = 1
  -> x2 = 4
  -> k2 2 * 44 * 4 = 352

k3 mod 4 = 0, k3 mod 5 = 0, k3 mod 11 = 7
  -> 7 * (k3 mod 4 = 0, k3 mod 5 = 0, k3 mod 11 = 1)
  -> 4 * 5 * x3 mod 11 = 1
  -> x3 = 5
  -> k3 = 7 * 20 * 5 = 700

K = (k1 + k2 + k3) mod (4*5*11)
  = (165 + 352 + 700) mod 220
  = 1217 mod 220
  = 117