中国剩余定理的 (k, n) 门限方案

秘密分发

秘密 D 输入,k,n的输入和 p 的获取和上面一样,这里不多说,获取完后,要生成一个集合 D,其中有 n 个 di,且满足条件

  1. p > D
  2. d1<d2<...<dn
  3. p 与任意 di 互素
  4. di 之间两两互素
  5. 最小的 k 个 di 的乘积 > p 与 最大的 k-1 个 di 的乘积

这里采取的方法是

  1. 还是用 getPrime 函数,参数字节数为 max(D字节数,n字节数) + 2,并在后面判断若p<D或n,重新取值,保证 p > D,n
  2. getPrime 函数取 n 个素数,然后进行 sort() 排列,素数间一定两两互素,解决条件3,4
  3. 判断 ‘最小的 k 个 di 的乘积 > p 与 最大的 k-1 个 di 的乘积’ 是否成立,若不成立,重新取值

生成 di

1
2
3
4
5
6
7
8
9
10
11
def make_d(bit, n): # 生成d序列
d = []
for i in range(n):
tmp = getPrime(int(bit) + 3)
if tmp not in d:
d.append(tmp)
else:
i -= 1
d.sort()

return d

生成完之后进行检查:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def check(d, p, k, n): # 检查是否符合条件
mm = p # p与最大的k-1个di的乘积
m = getM(d, k)
for i in range(n-k+1, n):
mm *= d[i]
if(m > mm):
return True
else:
return False


def getM(d, k): # k个最小di的乘积
m = 1
for i in range(k):
m *= d[i]
return m


d = make_d(bit, n)
while (not check(d, p, k, n)):
d = make_d(bit, n)
print(d)

[0,(m/p)-1] 的范围内随机取一个 r,计算 D' = D + rp,最后计算出 n 个 $Di$ 块

1
2
3
4
5
6
7
m = getM(d, k)
rand = random.randint(0, m//p-1)
print("r:", rand)

_D = D + rand*p
for i in range(n):
print((_D % d[i], d[i]))

只要知道上述 Di 块中的任意 k 个,就可以应用中国剩余定理求出 D’。

公开 p 和 r,并分发每一份数据给每个秘密共享者。

效果图:

image-20200922095121102

秘密恢复

输入 k,p 和每一份 Di,计算出 m = d1d2..dk ,为了应用中国剩余定理,首先求出 inv(m/di, di),即 m/didi 的逆元,然后计算出 ($\sum_{m=0}^k \frac{m}{di}yiDi$) mod m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def recover():
k = int(input("k: "))
rand = int(input("r: "))
p = int(input("Prime: "))
m1 = 1
recoverD = []
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))
for i in recoverD:
m1 *= i[1]
result = 0
for i in recoverD:
y = gmpy2.invert(m1//i[1], i[1])
result += m1//i[1]*y*i[0]

DD = result % m1
print("===============Result===============")
print(libnum.n2s(DD-rand*p))

利用上面的数据进行计算:

image-20200922095249345


中国剩余定理的 (k, n) 门限方案
https://52hertz.tech/2020/09/21/crt/
作者
Ustin1an
发布于
2020年9月21日
许可协议