Toshi's Treasure (toshitreasure)

cryptohack

Task: a 5-of-6 Shamir Secret Sharing combiner over GF(2^521-1) that reveals the reconstructed private key after you submit your share. Solution: Lagrange interpolation is LINEAR in our submitted y6, so secret(y6) = sec0 + L6·y6 with L6=5 the Lagrange coefficient at x=0 for x=6 (x in {2,3,4,5,6}). Submit y6=0 to learn sec0, then craft y6=(target-sec0)·L6^{-1} to make the combiner output any chosen value (the cheat); finally submit the REAL secret sec0 + 5·(our genuine share y) as the privkey to unlock and get the flag. Lesson: use verifiable secret sharing.