avatar

Catalog
Shamir (k, n)门限秘密分发

秘密分发我分为了两个模块,一个是分发,一个是恢复。

秘密分发

1
环境:Windows 10,Python 3.7.1

因为k,n都是整数,因此输入的时候进行一下强制类型转换,对于需要分发的秘密,示例是整数,但有可能是字符串,因此利用 libnum.s2n 将字符串转换成整数,再进行运算。

1
2
3
D = input("Input your secret: ")
n = int(input("How many parts do you want to devide: "))
k = int(input("Subset: "))

对于素数 p 的获取,我使用了 Crypto.Util.number 模块中 getPrime 函数,它的参数取决于 D 和 n 的字节长度,在p不会太过大的情况同时,保证 D、n<p,并在后面判断若p<D或n,重新取值,然后用随机数生成对多项式的系数进行赋值,放进一个列表里,然后公开 p 和 k。

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
def printnum(num): # 打印多项式,便于自己查看
print(str(num[0]), end='')
for i in range(1, len(num)):
if(i == 1):
print('+' + str(num[i]) + "x", end='')
else:
print('+' + str(num[i]) + "x^" + str(i), end='')
print()


D = libnum.s2n(D)
bit_D = math.log(D, 2)
bit_n = math.log(n, 2)
bit = max(bit_D, bit_n)
p = getPrime(int(bit) + 2)
while p < D or p < n:
p = getPrime(int(bit) + 2)

num = [D]
for i in range(k-1):
num.append(random.randint(1, p))

printnum(num)
print("Your Prime:", p)
print("Subset:", k)

然后求出所有的 Di,将它的 iDi(x, y) 的形式打包存储进一个列表中。

1
2
3
4
5
6
7
8
9
10
11
12
def f(num, x, p): # 计算每个i多项式方程的值
result = 0
for i in range(len(num)):
result += num[i]*(x**i)
return (x, result % p)


_D = []
for i in range(1, n+1):
tmp = f(num, i, p)
_D.append(tmp)
print("D" + str(i) + ':' + str(tmp))

将每一个 Di 输出,由秘密输入者进行分发 n 个部分。

运行效果:

(k, n) = (3, 6)

image-20200921203437444

秘密恢复

首先输入 k,然后输入素数 p,接着将 Di 的值输入进去,以 (x, y) 的形式打包存储进一个列表中。

1
2
3
4
5
6
7
8
recoverD = []
print("Now to recover your secret")
k = int(input("Subset: "))
p = int(input("Prime: "))
print("Now to input your point like x,y")
for i in range(k):
x, y = map(int, input("Input point " + str(i+1) + ": ").split(','))
recoverD.append((x, y))

数据获取完毕后,利用拉格朗日插值法进行计算,将 i 值和 Di 的值分开各位一个列表,然后每一次计算每一个小块的 q(x)。对于多项式的计算,形如 (x-1)(x-2),这里为了偷懒我利用了 numpy 里的 array,并利用它的性质计算多项式。

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
def l(D): # 拉格朗日插值法
x_s, y_s = zip(*D)
lst = []
for i in range(len(x_s)):
others = list(x_s)
cur = others.pop(i)
dxs = cal(cur, others)
fm = fm_cal(cur, others)

lst.append((dxs, fm))

return lst


def cal(x, others): # 计算多项式,即分子
re = np.array([1])
for i in others:
p = np.array([1, -i])
re = np.convolve(re, p)

return re


def fm_cal(x, others): # 计算分母
re = 1
for i in others:
re *= (x-i)

return re

待计算好返回每一个 Di 的分子和分母后,即可以计算 ip 的逆元,利用 gmpy2.invert 来计算,求出后将各项相加,即是多项式方程,其中常数项位秘密,可利用 libnum.n2s() 恢复成字符串。

1
2
3
4
5
6
7
8
9
10
def recover_secret(k, p, D):
re = l(D)
cnt = 0
fz, fm = zip(*re)
for i in range(k):
inv = gmpy2.invert(fm[i], p)
cnt += D[i][-1] * inv * fz[i][-1]
cnt %= p

return libnum.n2s(cnt)

利用上面的秘密分发的数据进行恢复:

1
2
3
4
5
6
如:
Prime: 167569419418447
Subset: 3
D2:(2, 59529348878006)
D4:(4, 21970926061031)
D5:(5, 35309714193955)

效果图如下:

image-20200921211306075

Author: 52HeRtz
Link: https://www.52hertz.tech/2020/09/21/Shamir/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • Wechat
    Wechat
  • Alipay
    Alipay

Comment