最近打的幾個比賽沒意思，不是不會就是不會。不過比賽完后看到別人的WP，感覺受益匪淺。

先看一個多項式：

當輸入Xi時會得到一個Si,要求輸入一定數量的xi 來求[c]?

當可以輸入的x個數與c的個數相同時，可以用矩陣直接求解。（這塊比較簡單，就是個矩陣的除法略）

當x個數小于c時，理論上不可能得到全部的解，但可以得到一部分。

第1種情況是求c0 這個比較簡單，輸入0時0^0=1，其它冪為0所以可以直接得到c0

后邊是求某個值的兩個題。

import random, osp = 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] = secretreturn polydef poly_eval(f, x):return sum(c * pow(x, i, p) for i, c in enumerate(f)) % pif __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)) % pt = 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 randomp = 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] + gdef evaluate_poly(f, x):return sum(c * pow(x, i, p) for i, c in enumerate(f)) % pfor _ 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 - 19shares = [(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))