Our spies intercepted communications and a file between 5 of the top 10 robo-generals and their nuclear bomb server. We must recover the final launch code from the 5 robo-general’s secret codes, so we can stop the detonation!
Summary: Shamir’s Secret Sharing
Here we have a pcap file where 5 communications take place. Each looks like
> *** Welcome to Remote Nuclear Bomb Launch System *** > # Enter the launch code: < (4, 944438008684116...6L) > !!! Success !!! Bomb has been launched! |
It seems that 5 secret codes together allow to launch the bomb. Such things can be done with some secret sharing scheme. Google for some and Shamir’s Secret Sharing is the easiest to find. In wiki’s example only 3 keys are needed, so we need to extend it to 5.
$$a_0=y_0 * {(-x_1*x_2*x_3*x_4) \over (x_0-x_1)*(x_0-x_2)*(x_0-x_3)*(x_0-x_4)}$$
$$…$$
$$a_4=y_4 * {(-x_0*x_1*x_2*x_3) \over (x_4-x_0)*(x_4-x_1)*(x_4-x_2)*(x_4-x_3)}$$
$$secret=\sum_{i=0}^4 a_i$$
Here’s the code:
from libnum import * pairs = [] pairs += [(4, 9444...806)] pairs += [(2, 8577...243)] pairs += [(1, 3320...109)] pairs += [(5, 6259...452)] pairs += [(3, 6454...858)] p = int(open("p.txt").read()) res = 0 for i, pair in enumerate(pairs): x, y = pair top = 1 bottom = 1 for j, pair in enumerate(pairs): if j == i: continue xj, yj = pair top = (top * (-xj)) % p bottom = (bottom * (x - xj)) % p res += (y * top * invmod(bottom, p)) % p res %= p print res print n2s(res) |
$ py shamir.py 723126740974638694358413759917266643240116870314821228110113 s3cr3t_5h4r1n9_i5_H4RD_!! |
The flag: s3cr3t_5h4r1n9_i5_H4RD_!!
1 ping
[…] http://leetmore.ctf.su/wp/plaidctf-2012-…-guessing/ […]