Boston Key Party CTF 2016 - Supercomputer
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from sage.all import * | |
import re | |
active_bits = [ | |
0, 3, 4, 7, 8, 9, 10, 11, 14, 20, 21, 24, 25, 26, | |
35, 40, 41, 43, 45, 46, 47, | |
] | |
code = """ | |
cnot(40, 34) | |
cnot(45, 0) | |
cnot(32, 20) | |
cnot(44, 47) | |
cnot(45, 10) | |
cnot(45, 24) | |
cnot(5, 28) | |
cnot(41, 15) | |
cnot(25, 12) | |
cnot(43, 25) | |
cnot(24, 9) | |
cnot(10, 37) | |
cnot(26, 37) | |
cnot(35, 11) | |
cnot(12, 19) | |
cnot(24, 5) | |
cnot(24, 9) | |
cnot(0, 43) | |
cnot(45, 33) | |
cnot(11, 42) | |
cnot(34, 35) | |
cnot(3, 44) | |
cnot(25, 21) | |
cnot(4, 18) | |
cnot(10, 43) | |
cnot(21, 39) | |
cnot(39, 20) | |
cnot(24, 45) | |
cnot(46, 0) | |
cnot(47, 16) | |
cnot(35, 24) | |
cnot(19, 14) | |
cnot(38, 17) | |
cnot(13, 38) | |
cnot(5, 24) | |
cnot(19, 10) | |
cnot(6, 41) | |
cnot(3, 26) | |
cnot(43, 37) | |
cnot(45, 46) | |
cnot(40, 6) | |
cnot(10, 27) | |
cnot(37, 1) | |
cnot(18, 42) | |
cnot(37, 25) | |
cnot(20, 32) | |
cnot(37, 3) | |
cnot(34, 40) | |
cnot(13, 35) | |
cnot(7, 6) | |
cnot(28, 16) | |
cnot(40, 35) | |
cnot(35, 5) | |
cnot(14, 42) | |
cnot(46, 34) | |
cnot(7, 43) | |
cnot(38, 42) | |
cnot(32, 30) | |
cnot(27, 16) | |
cnot(1, 21) | |
cnot(35, 13) | |
cnot(33, 34) | |
cnot(10, 28) | |
cnot(23, 45) | |
cnot(8, 13) | |
cnot(21, 31) | |
cnot(16, 40) | |
cnot(37, 20) | |
cnot(3, 32) | |
cnot(28, 29) | |
cnot(15, 10) | |
cnot(19, 47) | |
cnot(6, 36) | |
cnot(4, 34) | |
cnot(23, 19) | |
cnot(19, 12) | |
cnot(40, 18) | |
cnot(38, 19) | |
cnot(16, 3) | |
cnot(22, 26) | |
cnot(11, 44) | |
cnot(6, 16) | |
cnot(1, 0) | |
cnot(0, 10) | |
cnot(42, 9) | |
cnot(21, 6) | |
cnot(42, 31) | |
cnot(32, 6) | |
cnot(11, 22) | |
cnot(36, 44) | |
cnot(9, 8) | |
cnot(45, 1) | |
cnot(26, 27) | |
cnot(16, 13) | |
cnot(36, 33) | |
cnot(42, 26) | |
cnot(28, 18) | |
cnot(27, 21) | |
cnot(16, 31) | |
cnot(1, 41) | |
cnot(19, 46) | |
cnot(34, 16) | |
cnot(11, 47) | |
cnot(9, 47) | |
cnot(42, 12) | |
cnot(46, 13) | |
cnot(3, 45) | |
cnot(3, 36) | |
cnot(25, 37) | |
cnot(0, 3) | |
cnot(0, 36) | |
cnot(22, 27) | |
cnot(46, 0) | |
cnot(32, 46) | |
cnot(36, 17) | |
cnot(20, 39) | |
cnot(34, 17) | |
cnot(2, 35) | |
cnot(23, 42) | |
cnot(29, 35) | |
cnot(34, 29) | |
cnot(41, 33) | |
cnot(33, 22) | |
cnot(15, 34) | |
cnot(34, 25) | |
cnot(20, 28) | |
cnot(39, 38) | |
cnot(10, 23) | |
cnot(35, 31) | |
cnot(41, 28) | |
cnot(32, 0) | |
cnot(47, 30) | |
cnot(33, 12) | |
cnot(2, 22) | |
cnot(26, 24) | |
cnot(44, 21) | |
cnot(38, 43) | |
cnot(46, 30) | |
cnot(26, 29) | |
cnot(19, 36) | |
cnot(14, 42) | |
cnot(41, 0) | |
cnot(16, 31) | |
cnot(27, 22) | |
cnot(30, 26) | |
cnot(11, 4) | |
cnot(13, 31) | |
cnot(16, 10) | |
cnot(3, 11) | |
cnot(20, 33) | |
cnot(23, 14) | |
cnot(30, 21) | |
cnot(41, 29) | |
cnot(43, 37) | |
cnot(7, 24) | |
cnot(13, 12) | |
cnot(19, 42) | |
cnot(34, 9) | |
cnot(34, 8) | |
cnot(40, 23) | |
cnot(23, 36) | |
cnot(6, 45) | |
cnot(19, 26) | |
cnot(13, 28) | |
cnot(35, 36) | |
cnot(19, 2) | |
cnot(10, 36) | |
cnot(3, 15) | |
cnot(0, 20) | |
cnot(32, 20) | |
cnot(10, 41) | |
cnot(6, 11) | |
cnot(43, 26) | |
cnot(23, 5) | |
cnot(28, 17) | |
cnot(4, 15) | |
cnot(37, 43) | |
cnot(37, 22) | |
cnot(46, 21) | |
cnot(47, 33) | |
cnot(24, 15) | |
cnot(27, 35) | |
cnot(2, 1) | |
cnot(39, 0) | |
cnot(36, 13) | |
cnot(0, 1) | |
cnot(18, 25) | |
cnot(11, 47) | |
cnot(10, 25) | |
cnot(13, 21) | |
cnot(8, 33) | |
cnot(30, 21) | |
cnot(22, 29) | |
cnot(35, 24) | |
cnot(18, 38) | |
cnot(6, 25) | |
cnot(40, 37) | |
cnot(10, 32) | |
cnot(20, 23) | |
cnot(4, 33) | |
cnot(14, 31) | |
cnot(3, 22) | |
cnot(17, 21) | |
cnot(4, 13) | |
cnot(36, 14) | |
cnot(45, 8) | |
cnot(47, 43) | |
cnot(14, 40) | |
cnot(4, 46) | |
cnot(47, 13) | |
cnot(5, 47) | |
cnot(39, 20) | |
cnot(45, 39) | |
cnot(31, 7) | |
cnot(16, 40) | |
cnot(3, 43) | |
cnot(20, 43) | |
cnot(24, 2) | |
cnot(3, 35) | |
cnot(21, 46) | |
cnot(20, 24) | |
cnot(24, 22) | |
cnot(15, 34) | |
cnot(26, 11) | |
cnot(31, 30) | |
cnot(2, 14) | |
cnot(39, 34) | |
cnot(35, 43) | |
cnot(4, 18) | |
cnot(15, 20) | |
cnot(36, 17) | |
cnot(16, 5) | |
cnot(46, 45) | |
cnot(5, 6) | |
cnot(41, 17) | |
cnot(20, 19) | |
cnot(16, 12) | |
cnot(30, 9) | |
cnot(45, 4) | |
cnot(22, 37) | |
cnot(33, 30) | |
cnot(12, 23) | |
cnot(23, 32) | |
cnot(32, 37) | |
cnot(39, 28) | |
cnot(3, 23) | |
cnot(41, 43) | |
cnot(15, 33) | |
cnot(26, 1) | |
cnot(19, 26) | |
cnot(36, 7) | |
cnot(31, 18) | |
cnot(17, 23) | |
cnot(26, 34) | |
cnot(18, 39) | |
cnot(35, 12) | |
cnot(28, 1) | |
cnot(10, 20) | |
cnot(8, 44) | |
cnot(19, 5) | |
cnot(44, 13) | |
cnot(4, 19) | |
cnot(10, 40) | |
cnot(22, 34) | |
cnot(31, 16) | |
cnot(13, 19) | |
cnot(25, 19) | |
cnot(12, 10) | |
cnot(27, 37) | |
cnot(44, 21) | |
cnot(47, 23) | |
cnot(9, 25) | |
cnot(27, 15) | |
cnot(9, 12) | |
cnot(41, 43) | |
cnot(21, 4) | |
cnot(20, 5) | |
cnot(15, 41) | |
cnot(31, 32) | |
cnot(35, 34) | |
cnot(1, 38) | |
cnot(16, 20) | |
cnot(43, 23) | |
cnot(27, 25) | |
cnot(29, 17) | |
cnot(8, 9) | |
cnot(13, 0) | |
cnot(16, 7) | |
cnot(43, 45) | |
cnot(6, 10) | |
cnot(43, 22) | |
cnot(1, 8) | |
cnot(18, 36) | |
cnot(30, 5) | |
cnot(32, 26) | |
cnot(34, 20) | |
cnot(28, 47) | |
cnot(46, 8) | |
cnot(22, 20) | |
cnot(16, 1) | |
cnot(38, 47) | |
cnot(5, 6) | |
cnot(45, 22) | |
cnot(40, 8) | |
cnot(2, 36) | |
cnot(27, 16) | |
cnot(7, 2) | |
cnot(46, 0) | |
cnot(37, 6) | |
cnot(36, 4) | |
cnot(27, 17) | |
cnot(19, 37) | |
cnot(1, 31) | |
cnot(4, 43) | |
cnot(30, 43)""".strip() | |
def comp(bits): | |
bits = list(bits) | |
for line in code.splitlines(): | |
if "cnot" in line: | |
src, dst = map(int, re.findall(r"\d+", line)) | |
bits[dst] ^= bits[src] | |
return bits | |
def tobin(x, n): | |
return tuple(map(int, bin(x).lstrip("0b").rjust(n, "0"))) | |
def frombin(v): | |
return int("".join(map(str, v)), 2 ) | |
m = matrix(GF(2), 48, 48) | |
vals = [] | |
for x in xrange(48): | |
v = [0] * 48 | |
if x in active_bits: | |
v[x] = 1 | |
v = comp(v) | |
vals.append(frombin(v)) | |
m.set_column(x, v) | |
if 0: # 2^21 exhaustion | |
mx = 0 | |
for vs in Combinations(vals): | |
res = 0 | |
for v in vs: | |
res ^= v | |
mx = max(mx, res) | |
print mx | |
else: # linear algebra solution | |
prefix = [] | |
for bit in xrange(48): | |
mat = m[:bit+1] | |
vec = vector(GF(2), prefix + [1]) | |
try: | |
mat.solve_right(vec) | |
except Exception as err: | |
prefix.append(0) | |
else: | |
prefix.append(1) | |
print frombin(prefix) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment