网络信息安全上机作业罢了，人已经麻了

shamir秘密共享协议

加密过程

假设有秘密S要保护，任意取t-1个随机数，构造如下多项式： [公式] ，其中， [公式] ，所有运算均在有有限域中进行。

  • 取任意n个数， [公式] 分别带入多项式，得到 [公式] 。
  • 将 [公式] 分发给n个服务器上。

解密过程

从任意t个服务器上取得数据，假设取得 [公式] ，带入并求解多项式系数；
[公式]
用矩阵乘法表示为：
img
在求得 [公式] 之后便可以构造出多项式 [公式]

将 [公式] 带入到多项式中，可以求的原秘密 [公式]

算法实现

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
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)

运行示范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
┌─[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

1
2
3
4
5
6
7
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

1
2
3
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

1
2
3
4
5
6
7
8
9
10
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))

解密过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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)