最近打的几个比赛没意思，不是不会就是不会。不过比赛完后看到别人的WP，感觉受益匪浅。
先看一个多项式：
当输入Xi时会得到一个Si,要求输入一定数量的xi 来求[c]
当可以输入的x个数与c的个数相同时，可以用矩阵直接求解。（这块比较简单，就是个矩阵的除法略）
当x个数小于c时，理论上不可能得到全部的解，但可以得到一部分。
第1种情况是求c0 这个比较简单，输入0时0^0=1，其它幂为0所以可以直接得到c0
后边是求某个值的两个题。
import random, os
p = 2 ** 256 - 189
FLAG = os.getenv("FLAG", "SEKAI{}")
def challenge(secret):
t = int(input())
assert 20 <= t <= 50, "Number of parties not in range"
f = gen(t, secret)
for i in range(t):
x = int(input())
assert 0 < x < p, "Bad input"
print(poly_eval(f, x))
if int(input()) == secret:
print(FLAG)
exit(0)
else:
print(":<")
def gen(degree, secret):
poly = [random.randrange(0, p) for _ in range(degree + 1)]
index = random.randint(0, degree)
poly[index] = secret
return poly
def poly_eval(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
if __name__ == "__main__":
secret = random.randrange(0, p)
for _ in range(2):
challenge(secret)
这个题输入的次数自定，p已知，只要求出大部分值，并且两次中找到相同值即可。这里边用到一个degree次根g
先找一个比较大的幂k使得g^k = 1 mod p这样求出g，这题可以发现50以内最大的是29
g = pow(2,(p-1)//k,p) (这里(p-1)%29==0)
其实这样的g有k个分别是g^1==1,g^2==1,g^3==1...
当把这个g代入到式子中，由于g^29==g^0,g^30==g^1...得到
s = (c0+c29)*g^0 +c1*g^1 + c2*g^2+...
这样可输入的g的个数与系数的个数相同就能直接得到c（不过这里的第1个是c0+c29所以第1个和最后一个c是未知的）这种情况下大概率两次的index都命中从而找到对应的secret值。
p = 2 ** 256 - 189
poly = [random.randrange(0, p) for _ in range(degree + 1)]
def poly_eval(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
t = 29 #(p-1)%29==0
g = pow(2, (p-1)//t, p)
#assert pow(g, t, p) == 1
xs = [pow(g, i, p) for i in range(t)]
shares = [(x, poly_eval(poly, x)) for x in xs]
R.<x0> = GF(p)[]
list(R.lagrange_polynomial(shares))这里有多少个根不只看(p-1)%k==0，也就是8不一定有8个根可能只有4个或者3个，需要用g^i验证一下。
然后周末遇到另外一个题：
#!/usr/local/bin/python3
import random
p = 2**255 - 19
k = 15
SECRET = random.randrange(0, p)
print("welcome to ssss")
# Step 1: Generate a random, degree-(k−3) polynomial g(x)
g = [random.randrange(p) for _ in range(k - 2)]
# Step 2: Select a random c in Fp
c = random.randrange(0, p)
# Step 3: Set f(x)=g(x)x^2+Sx+c
f = [c] + [SECRET] + g
def evaluate_poly(f, x):
return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
for _ in range(k - 1):
x = int(input())
assert 0 < x < p, "no cheating!"
print(evaluate_poly(f, x))
if int(input("secret? ")) == SECRET:
FLAG = open("flag.txt").read()
print(FLAG)
这题的p = 2^255-19,可以输入14个数，这里的最大根的个数是12，对于15个数来说0，1，2会和最后3个重叠，12次只能求出3-11的值，而这题的secret是第2个，剩下两次也求不出第2个来。看了WP感觉走错方向了。
这时候想下数学，每轮两次输入x和-x则有
s1 = c0*x^0 + c1*x^1 +...
s2 = c0*x^0 - c1*x^1 +...
两式相减
s = s1-s2 = c1*2*x^1 + c3*2*x^3 + ...
这样7组14次输入会得到7个式子，回到第1种情况可以求到c1,c3,...
这里对s要乘2x的逆，并用 x^2作为输入值
这题和用根来折叠没有关系
p = 2**255 - 19
shares = [(i^2, (evaluate_poly(f,i)-evaluate_poly(f,-i))*inverse_mod(2*i,p)%p) for i in range(1,8)]
R.<x0> = GF(p)[]
v = list(R.lagrange_polynomial(shares))