Shamir秘密共享协议
简述
Shamir密钥分享算法最早在1970年基于Lagrange插值和矢量方法提出的，基本思想是分发着通过秘密多项式，将秘密s分解为n个秘密，分发给持有者，其中任意不少于t个秘密均能恢复密文，而任意少于t个秘密均无法得到密文的任何信息。
算法思路
实现代码：
加密：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| a = getPrime(256)
b = getPrime(256)
c = getPrime(256)
d = bytes_to_long(flag)
n = getStrongPrime(2048)
def poly(x):
return (a * x ** 3 + b * x ** 2 + c * x + d) % n
for _ in range(4):
x = getRandomNBitInteger(256)
print(f'({x}, {poly(x)})')
print(n)
|
解密：
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
| import gmpy2
import libnum
def GCRT(mi,ai):
assert(isinstance(mi,list) and isinstance(ai,list))
curm,cura = mi[0],ai[0]
for(m,a) in zip(mi[1:],ai[1:]):
d = gmpy2.gcd(curm,m)
c = a - cura
assert(c % d == 0)
K = c // d * gmpy2.invert(curm // d,m // d)
cura += curm * K
curm = curm * m // d
cura %= curm
retrun (cura % curm,curm)
a1 =
d1 =
a2 =
d2 =
.....
at =
dt =
aa = [a1,a2,a3.....at]
dd = [d1,d2,d3.....dt]
p =
s,aa = GCRT(aa,dd)
s %= p
print(libnum.n2s(int(s)))
|
