网络信息安全上机作业罢了,人已经麻了
假设有秘密S要保护,任意取t-1个随机数,构造如下多项式: ,其中, ,所有运算均在有有限域中进行。
从任意t个服务器上取得数据,假设取得 ,带入并求解多项式系数;
用矩阵乘法表示为:
在求得 之后便可以构造出多项式
将 带入到多项式中,可以求的原秘密
from math import ceil
from decimal import Decimal
import random
##测试数据
max = 1000000
t = 5
n = 8
secret = 31298123678
print('before:',secret)
print('ENCRYPTING.......')
##构造多项式f(x)
fx = [random.randrange(0,max) for _ in range(t-1)]
fx.append(secret)
##任取n个x,分别带入多项式,产生对应的(x,y)
share = []
for i in range(n):
x = random.randrange(1,max)
y = 0
for idx, value in enumerate(fx[::-1]):
y += value * x**idx
share.append((x,y)) ##每人分到的(x,y)序列
print('share:(',x,',',y,')')
print('DECRYPTING......')
##任取t个(x,y)序列,并解密
key = random.sample(share,t)
sum =0
for i, key_i in enumerate(key):
x_i,y_i = key_i
print('key:(',x_i,',',y_i,')')
temp = Decimal(1)
for j, key_j in enumerate(key):
x_j,y_j = key_j
if i != j:
temp *= Decimal(Decimal(x_j)/Decimal(x_j-x_i))
temp *= y_i
sum += Decimal(temp)
sum = int(round(Decimal(sum),0))
print('after:',sum)
┌─[loorain@ubuntu] - [~/crypto/shamir] - [2304]shamir
└─[$] python3 shamir.py [20:33:27]
before: 31298123678
ENCRYPTING.......
share:( 385490 , 19613871609040056923504678528 )
share:( 208439 , 1676593182288704748621405212 )
share:( 111980 , 139661059121519203627546778 )
share:( 287787 , 6092505271995476798344376612 )
share:( 57978 , 10036212148635231635583656 )
share:( 8027 , 3687858811716396682052 )
share:( 640969 , 149919642500298401999699916572 )
share:( 444105 , 34550423234050839227167648028 )
DECRYPTING......
key:( 444105 , 34550423234050839227167648028 )
key:( 111980 , 139661059121519203627546778 )
key:( 208439 , 1676593182288704748621405212 )
key:( 287787 , 6092505271995476798344376612 )
key:( 385490 , 19613871609040056923504678528 )
after: 31298123800
这里用0-255的矩阵模拟灰度图像
随机生成 O 和 S,并计算 d 和 si
S_img = rd.randint(0,256,(10,10))
O_img = rd.randint(0,256,(20,20))
Q_img = rd.randint(0,1,(20,20))
m = number.getPrime(4) #随机生成一个素数m
d = O_img % m
S_i = S_img % m
生成Q
for i in range(20):
for j in range (20):
Q_img[i,j] = math.floor(O_img[i,j] / m) * m
生成y = f(x),求得y与Q相加的到n个Oi
O_i = []
##生成y = f(x),求得y与Q相加的到n个Oi
for n in range(400):
key = random.randrange(1,max)
y = 0
for i in range(10):
for j in range(10):
y += S_i[i,j]* (key ** (i*10+j))
y += d[n] * (key ** (i*10+j))
O_i.append((Q_img + y))
for i in range(101):
Q_img.append((O_i[i, 0] // m) * m)
so1.append(d[i] - (O_i[i, 0] // m) * m)
for i in range(101):
d.append(Q_img[i])
sol = []
for i in range(101):
d1 = np(0,m,(10, 10))
for j in range(10):
for k in range(10):
d1[j, k] = S_img[i, j]**k
sol.append(d1.solve_right(O_img[i])[0])
for i in range(101):
assert sol[i]>m
solve = []
for i in range(101):
solve.append(so1[i]+Q_img[i])
print(solve == d)