Last active
February 28, 2017 13:20
-
-
Save hellman/e50c9404992591c686feb18132aac94f to your computer and use it in GitHub Desktop.
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