import random #sage: prover(flag) r = [141, 56, 14, 221, 102, 34, 216, 33, 204, 223, 194, 174, 179, 67, 226, 101, 79, 236, 214, 198, 129, 11, 52, 148, 180, 49] y = [138, 229, 245, 162, 184, 116, 195, 143, 68, 1, 94, 35, 73, 202, 113, 235, 46, 97, 100, 148, 191, 102, 60, 118, 230, 256, 9, 175, 203, 136, 232, 82, 242, 236, 37, 201, 37, 116, 149, 90, 240, 200, 100, 179, 154, 69, 243, 43, 186, 167, 94, 99, 158, 149, 218, 137, 87, 178, 187, 195, 59, 191, 194, 198, 247, 230, 110, 222, 117, 164, 218, 228, 242, 182, 165, 174, 149, 150, 120, 202, 94, 148, 206, 69, 12, 178, 239, 160, 7, 235, 153, 187, 251, 83, 213, 179, 242, 215, 83, 88, 1, 108, 32, 138, 180, 102, 34] p = 257 k = 25 + 1 F = GF(p) FF. = GF(p)[] FQ = FF.quotient_ring(x^k + 1) def prover(secret, beta=107, alpha=42): r = FF.random_element(k - 1) masked = (r * secret).mod(x^k + 1) y = [ masked(i) if randint(0, beta) >= alpha else masked(i) + F.random_element() for i in range(0, beta) ] return r.coefficients(sparse=False), y rpoly = FQ(r) rpoly_inv = rpoly^(-1) # check if inverse exists in FQ assert rpoly_inv in FQ assert rpoly_inv * rpoly == 1 points = list(enumerate(y)) i=0 while 1: s = random.sample(points, 26) masked = FQ(FF.lagrange_polynomial(s)) secret = (rpoly_inv * masked).lift() # change ring to FF or might get 0 if min(secret) >= 0x20 and max(secret) <= 0x7F: print repr("".join(map(chr,secret))) exit() if i%1000 == 0: print str(i/1000) + 'k' i+=1