#!/usr/bin/sage
import sys
print("I caught an anglerfish in the sea! ")
sys.stdout.flush()
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast
n = 100
m = 100
q = 5
FF.<x> = GF(q)
def apply(F, v):
out = []
for i in range(m):
out.append((v.T * F[i] * v)[0, 0])
return matrix(FF, m, 1, out)
def apply_verif_info(F, a, b):
out = []
for i in range(m):
out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
return matrix(FF, m, 1, out)
def create_pok(v, s, F):
proofs = []
for i in range(64):
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F, t)
verif = apply_verif_info(F, t, s)
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
proofs.append((com, t - a * s, verif))
return proofs
def verif_pok(v, F, pis):
coms = []
for pi in pis:
com = pi[0]
assert com not in coms
coms.append(com)
resp = pi[1]
verif = pi[2]
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
out1 = apply(F, resp)
out2 = com + (a * a) * v - a * verif
assert out1 == out2
rng = SystemRandom()
gen_seed = []
for i in range(64):
gen_seed.append(rng.randint(0, 255))
init_seed = gen_seed
gen_seed = bytes(gen_seed)
F = []
for i in range(m):
cur = []
for j in range(n):
cur.append([])
for k in range(n):
cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
gen_seed = sha256(gen_seed).digest()
F.append(matrix(FF, n, n, cur))
s = random_matrix(FF, n, 1)
v = apply(F, s)
pok = create_pok(v, s, F)
verif_pok(v, F, pok)
for pi in pok:
print("m0 =", [list(FF).index(i[0]) for i in list(pi[0])])
print("m1 =", [list(FF).index(i[0]) for i in list(pi[1])])
print("m2 =", [list(FF).index(i[0]) for i in list(pi[2])])
print("Can you catch an anglerfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])
pis = []
for x in range(64):
m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]
for pi in pok:
assert(m0 != [list(FF).index(i[0]) for i in list(pi[0])])
assert(m1 != [list(FF).index(i[0]) for i in list(pi[1])])
assert(m2 != [list(FF).index(i[0]) for i in list(pi[2])])
m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])
assert m0 not in [pi[0] for pi in pok]
assert m1 not in [pi[1] for pi in pok]
assert m2 not in [pi[2] for pi in pok]
pi = (m0, m1, m2)
pis.append(pi)
verif_pok(v, F, pis)
This time we have to pass the server check 64 times and we can't reuse the same value.
First, we see the how the parameters are being generated
The intention of the question was to ensure that the user had the value of s, such that the second input(m1) would be t - a * s and would cancel v^2*a in out2. However, since we can't find the value of s, we have to plan around v. We do this by setting the value of a to be 0. The value of a ranges from 0 to 4 according to
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
We do this by choosing random terms for resp and verif and set com to be apply(F,resp) until the value of a becomes 0.
def find():
a=1
while a:
resp,verif = matrix(FF, n, 1, [FF.random_element() for i in range(n)]),matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F,resp)
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
return com,resp,verif
We do this 64 times and get the flag.
for i in range(64):
pok = find()
r.recv()
r.sendline(f'{pok[0].list()}')
r.recv()
r.sendline(f'{pok[1].list()}')
r.recv()
r.sendline(f'{pok[2].list()}')
print(r.recvline())
b'corctf{extra_equations_means_extra_information_isnt_zk}'