Task: 构造shamir算法的secret

trick

零点也可以用于在shamir secret sharing中重构多项式

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
import hashlib, json
from pwn import *

def hash(msg):
    return hashlib.sha256(msg.encode()).hexdigest()

target = int(hash("gimme flag"), 16)
r = remote('ADDRESS', PORT)

r.recvuntil(b':\n')
dat = r.recvline().strip(b'\n').replace(b"'",b'"').replace(b'(',b'[').replace(b')',b']').decode()
print(dat)
share = json.loads(dat)
p = share["p"]
shares = share["shares"]
F = GF(p)
P = PolynomialRing(F, 'x')

points = []
for p in shares:
    points.append((F(p[0]),F(p[1])))
print(points)
poly = P.lagrange_polynomial(points + [(F(0),F(target))])

print(poly)
coord_x = randint(1, 2^54)

ret = (coord_x,poly(coord_x))

# check
poly1 = P.lagrange_polynomial(points + [ret])
assert poly1(0) == target

payload = dict()
payload["xs"] = int(ret[0]) # default __Integer_gmp__, json won't accept
payload["ys"] = int(ret[1]) # convert to python int

r.sendlineafter(b': ',json.dumps(payload).replace("'",'"').encode())
r.interactive()

# Securinets{1nv4l1d_sh4r3_w4_s0nz41_suru!}