Maojui

0CTF 2019 Final - Quantum Measure (Crypto, 428)

2019-06-09

Challenge

The unzip password is sha256 of flag in Quantum game.

File : Quantum Measure.zip (without password)

This challenge has two programs sharing 8 qubits (as q0 ~ q7).

The flag is 4 bytes long (8 hex), each hex can be expressed as the probability of qubit’s outcome.

e.g. the flag is “01234567” :

  • $q_0 = \frac{0}{16}|1\rangle + \frac{16}{16}|0\rangle$

  • $q_1 = \frac{1}{16}|1\rangle + \frac{15}{16}|0\rangle$

  • $q_2 = \frac{2}{16}|1\rangle + \frac{14}{16}|0\rangle$

  • $q_3 = \frac{3}{16}|1\rangle + \frac{13}{16}|0\rangle$

  • $q_4 = \frac{4}{16}|1\rangle + \frac{12}{16}|0\rangle$

  • $q_5 = \frac{5}{16}|1\rangle + \frac{11}{16}|0\rangle$

  • $q_6 = \frac{6}{16}|1\rangle + \frac{10}{16}|0\rangle$

  • $q_7 = \frac{7}{16}|1\rangle + \frac{9}{16}|0\rangle$

program1 :
  • measure q4 ~ q7 as input.
  • Some gates (Swap,Cnot,X gate) will act on q0 ~ q3 (depends on result of q4 ~ q7 measurement).
  • the output will be the first four bits in result.
program2 :
  • measure q0 ~ q3 as input.
  • Some gates (Swap,Cnot,X gate) will act on q4 ~ q7 (depends on result of q0 ~ q3 measurement).
  • the output will be the last four bits in result.

Solution

1. Consider the qubits (q4~`q7`), there are only 16 conditions. Parse the program to 16 subprograms.

Origin Program (here is program1) :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
I 4
MEASURE 4 reg[4]
@IF reg[4]
    SWAP 0 2
@ELSE
    CNOT 3 1

I 5
MEASURE 5 reg[5]
@IF3 reg[5]
    CNOT 0 2
@ELSE3
    SWAP 3 0
    X 0

...

convert into :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if |0000> :
    CNOT 3 1
    SWAP 3 0
    X 0
    SWAP 2 1
    SWAP 0 1
    X 0
if |0001> :
    ...
if |0010> :
    ...
    ...
if |1111> :
    ...

2. Consider the qubits (q0~`q3`), there are also only 16 conditions.

Match those inputs and corresponding outputs

1
2
3
4
5
6
7
|0000> -> |1000>
|0001> -> |1001>
|0010> -> |0100>
|0011> -> |0101>
|0100> -> |1010>
|0101> -> |1011>
...

3. Convert to formula.

Assume the probabilty of q0 ~ q7 outcome $1$ is, a,b,c,d,e,f,g,h

If the measurment of q4 ~ q7 is $|0000\rangle$ (this probability is $(1-e)(1-f)(1-g)(1-h)$ ),

and the probability of first four bits in result become $|1000\rangle$ will equal to the probability of q0 ~ q3 getting $|0000\rangle$ (Here, the probability is $(1-a)(1-b)(1-c)(1-d)$),

$\Rightarrow$ The probability of output $|1000\rangle$ will be $(1-e)(1-f)(1-g)(1-h) * (1-a)(1-b)(1-c)(1-d)$

Consider all possible in q4 ~ q7 …

The probability of output $p0 : |0000\rangle$ will be the sum of below :

  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|0000\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|0001\rangle$
  • The probability of q0~`q3= $|0000\rangle$ withq4~q7` = $|0010\rangle$
  • The probability of q0~`q3= $|0000\rangle$ withq4~q7` = $|0011\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|0100\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|0101\rangle$
  • The probability of q0~`q3= $|0000\rangle$ withq4~q7` = $|0110\rangle$
  • The probability of q0~`q3= $|0000\rangle$ withq4~q7` = $|0111\rangle$
  • The probability of q0~`q3= $|1100\rangle$ withq4~q7` = $|1000\rangle$
  • The probability of q0~`q3= $|1100\rangle$ withq4~q7` = $|1001\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|1010\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|1011\rangle$
  • The probability of q0~`q3= $|1100\rangle$ withq4~q7` = $|1100\rangle$
  • The probability of q0~`q3= $|1100\rangle$ withq4~q7` = $|1101\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|1110\rangle$
  • The probability of q0~`q3= $|1000\rangle$ withq4~q7` = $|1111\rangle$

In the same way, we can write down all outputs’ probability to formula.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p0 =  -q0*q3*q4*q6*q7*(q1 - 16)*(q2 - 16)*(q5 - 16) - q0*q4*q5*q6*q7*(q1 - 16)*(q2 - 16)*(q3 - 16) - q1*q2*q3*q6*q7*(q0 - 16)*(q4 - 16)*(q5 - 16) + q1*q3*q4*q7*(q0 - 16)*(q2 - 16)*(q5 - 16)*(q6 - 16) - q1*q3*q6*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) + q1*q3*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q1*q4*q5*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q6 - 16) - q1*q5*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) + q2*q5*q6*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16) - q3*q4*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q5 - 16)*(q7 - 16) + q3*q4*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q3*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) - q4*q5*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q7 - 16) + q4*q5*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) + q5*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) - q5*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16)
p1 =  q3*(q0*q1*q2*q6*q7*(q4 - 16)*(q5 - 16) + q0*q1*q6*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) - q0*q1*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*q4*q6*q7*(q1 - 16)*(q5 - 16) + q0*q4*q5*q6*q7*(q1 - 16)*(q2 - 16) - q0*q7*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) - q1*q2*q4*q7*(q0 - 16)*(q5 - 16)*(q6 - 16) + q1*q2*q5*q6*q7*(q0 - 16)*(q4 - 16) - q1*q4*q5*q7*(q0 - 16)*(q2 - 16)*(q6 - 16) + q1*q5*q6*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q7 - 16) - q1*q5*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q2*q4*q6*(q0 - 16)*(q1 - 16)*(q5 - 16)*(q7 - 16) - q2*q4*(q0 - 16)*(q1 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q4*q5*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q7 - 16) - q4*q5*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q6 - 16)*(q7 - 16) - q5*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q6 - 16))
p2 =  q0*q1*q2*q3*q4*q7*(q5 - 16)*(q6 - 16) + q0*q1*q2*q3*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q1*q3*q4*q5*q7*(q2 - 16)*(q6 - 16) + q0*q1*q3*q4*q6*q7*(q2 - 16)*(q5 - 16) + q0*q1*q4*q5*q6*q7*(q2 - 16)*(q3 - 16) + q0*q2*q3*q4*(q1 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*q3*q7*(q1 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q0*q3*q4*q5*(q1 - 16)*(q2 - 16)*(q6 - 16)*(q7 - 16) + q1*q2*q3*q5*(q0 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) - q1*q2*q5*q6*q7*(q0 - 16)*(q3 - 16)*(q4 - 16) + q1*q3*q4*q6*(q0 - 16)*(q2 - 16)*(q5 - 16)*(q7 - 16) + q1*q4*q5*q6*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q7 - 16) - q1*q5*q6*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) + q2*q3*q5*q7*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q6 - 16) + q2*q3*q6*q7*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q5 - 16) + q3*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16)
p3 =  -q0*q1*q2*q3*q4*q6*q7*(q5 - 16) - q0*q1*q3*q4*q5*q6*q7*(q2 - 16) - q0*q1*q3*q4*q7*(q2 - 16)*(q5 - 16)*(q6 - 16) - q0*q1*q4*q5*q7*(q2 - 16)*(q3 - 16)*(q6 - 16) - q0*q2*q3*q6*q7*(q1 - 16)*(q4 - 16)*(q5 - 16) - q0*q3*q4*(q1 - 16)*(q2 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q0*q3*q6*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) - q0*q4*q5*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) - q1*q2*q3*q4*q6*(q0 - 16)*(q5 - 16)*(q7 - 16) - q1*q2*q3*(q0 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q1*q2*q5*q7*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) - q1*q3*q4*q5*q6*(q0 - 16)*(q2 - 16)*(q7 - 16) - q2*q3*q5*q6*q7*(q0 - 16)*(q1 - 16)*(q4 - 16) - q2*q3*q7*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q2*q5*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) - q3*q5*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q7 - 16)
p4 =  -q0*q1*q2*q3*q6*(q4 - 16)*(q5 - 16)*(q7 - 16) + q0*q1*q2*q4*q5*q7*(q3 - 16)*(q6 - 16) - q0*q1*q2*q5*q7*(q3 - 16)*(q4 - 16)*(q6 - 16) - q0*q2*q3*q4*q6*(q1 - 16)*(q5 - 16)*(q7 - 16) - q0*q3*q4*q5*q6*(q1 - 16)*(q2 - 16)*(q7 - 16) + q0*q3*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q4*q6*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16) + q0*q5*q6*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16) + q1*q2*q3*q4*(q0 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q1*q2*q3*q5*q6*(q0 - 16)*(q4 - 16)*(q7 - 16) + q1*q3*q4*q5*(q0 - 16)*(q2 - 16)*(q6 - 16)*(q7 - 16) - q1*q4*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) + q1*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) - q2*q4*q5*q6*q7*(q0 - 16)*(q1 - 16)*(q3 - 16) - q2*q6*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) + q3*q5*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16)
p5 =  -q0*q1*q2*q3*q4*q5*q7*(q6 - 16) + q0*q1*q3*q5*q6*q7*(q2 - 16)*(q4 - 16) - q0*q1*q7*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) - q0*q2*q3*q5*q7*(q1 - 16)*(q4 - 16)*(q6 - 16) - q0*q2*q4*q6*q7*(q1 - 16)*(q3 - 16)*(q5 - 16) + q0*q2*q6*q7*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) + q0*q3*q4*q6*(q1 - 16)*(q2 - 16)*(q5 - 16)*(q7 - 16) + q0*q4*q5*q6*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q7 - 16) + q1*q2*q3*q6*(q0 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) + q1*q2*q4*q7*(q0 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) - q1*q3*q4*(q0 - 16)*(q2 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q1*q4*q5*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) + q1*q5*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q2*q3*q4*q5*q6*q7*(q0 - 16)*(q1 - 16) - q2*q5*q6*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) - q3*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16)
p6 =  q0*q1*q2*q3*q4*q6*(q5 - 16)*(q7 - 16) - q0*q1*q2*q4*q7*(q3 - 16)*(q5 - 16)*(q6 - 16) + q0*q1*q2*q7*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q0*q1*q3*q4*q5*q6*(q2 - 16)*(q7 - 16) + q0*q1*q3*q4*(q2 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q1*q4*q5*(q2 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) - q0*q1*q4*q6*q7*(q2 - 16)*(q3 - 16)*(q5 - 16) - q0*q1*q5*q6*q7*(q2 - 16)*(q3 - 16)*(q4 - 16) + q0*q2*q3*q6*(q1 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) + q0*q3*q5*q7*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q6 - 16) + q1*q2*q3*q4*q5*q7*(q0 - 16)*(q6 - 16) + q1*q2*q4*q5*q6*q7*(q0 - 16)*(q3 - 16) - q1*q2*q5*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q1*q2*q6*q7*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) + q2*q3*q5*q6*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q7 - 16) + q2*q3*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16)
p7 =  -q0*q1*q2*q3*q4*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q1*q2*q4*q6*q7*(q3 - 16)*(q5 - 16) - q0*q1*q2*q6*q7*(q3 - 16)*(q4 - 16)*(q5 - 16) - q0*q1*q3*q4*q5*(q2 - 16)*(q6 - 16)*(q7 - 16) - q0*q1*q3*q4*q6*(q2 - 16)*(q5 - 16)*(q7 - 16) - q0*q1*q4*q5*q6*(q2 - 16)*(q3 - 16)*(q7 - 16) + q0*q1*q4*q7*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) + q0*q1*q5*q7*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) - q0*q2*q3*(q1 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q0*q3*q5*q6*q7*(q1 - 16)*(q2 - 16)*(q4 - 16) - q1*q2*q3*q4*q5*q6*q7*(q0 - 16) - q1*q2*q4*q5*q7*(q0 - 16)*(q3 - 16)*(q6 - 16) + q1*q2*q5*q6*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) - q1*q2*q7*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) - q2*q3*q5*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) - q2*q3*q6*(q0 - 16)*(q1 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16)
p8 =  -q0*q2*q4*q5*q6*(q1 - 16)*(q3 - 16)*(q7 - 16) + q0*q2*q4*q5*(q1 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*q5*q6*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) - q0*q2*q5*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q1*q3*q6*q7*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16) - q1*q3*q7*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q3*q4*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q5 - 16) - q3*q4*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q5 - 16)*(q6 - 16) + q4*q5*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16) - q4*q5*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q6 - 16) + q4*q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) - q4*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q5*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16) + q5*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) - q6*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) + (q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16)
p9 =  q0*q1*q2*q3*q5*q6*(q4 - 16)*(q7 - 16) - q0*q1*q2*q3*q5*(q4 - 16)*(q6 - 16)*(q7 - 16) - q0*q1*q3*q6*q7*(q2 - 16)*(q4 - 16)*(q5 - 16) + q0*q1*q3*q7*(q2 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q0*q2*q3*q4*q5*q6*(q1 - 16)*(q7 - 16) - q0*q2*q3*q4*q5*(q1 - 16)*(q6 - 16)*(q7 - 16) + q0*q6*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) - q0*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q1*q3*q5*q6*q7*(q0 - 16)*(q2 - 16)*(q4 - 16) + q1*q3*q5*q7*(q0 - 16)*(q2 - 16)*(q4 - 16)*(q6 - 16) - q2*q3*q4*q6*q7*(q0 - 16)*(q1 - 16)*(q5 - 16) + q2*q3*q4*q7*(q0 - 16)*(q1 - 16)*(q5 - 16)*(q6 - 16) - q2*q4*q6*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) + q2*q4*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q3*q4*q5*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16) + q3*q4*q5*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q6 - 16)
p10 = -q0*q1*q2*q3*q7*(q4 - 16)*(q5 - 16)*(q6 - 16) + q0*q1*q2*q4*q5*q6*(q3 - 16)*(q7 - 16) - q0*q1*q2*q5*q6*(q3 - 16)*(q4 - 16)*(q7 - 16) + q0*q1*q3*q5*(q2 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) - q0*q2*q3*q4*q7*(q1 - 16)*(q5 - 16)*(q6 - 16) - q0*q2*q4*(q1 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q0*q3*q4*q5*q7*(q1 - 16)*(q2 - 16)*(q6 - 16) - q1*q2*q3*q5*q7*(q0 - 16)*(q4 - 16)*(q6 - 16) - q1*q3*q4*q6*q7*(q0 - 16)*(q2 - 16)*(q5 - 16) - q1*q4*q5*q6*q7*(q0 - 16)*(q2 - 16)*(q3 - 16) - q1*q4*q6*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) + q1*q5*q6*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16) + q1*q6*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) + q2*q3*q4*q5*(q0 - 16)*(q1 - 16)*(q6 - 16)*(q7 - 16) - q3*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16)
p11 = -q0*q1*q2*q3*q4*q5*q6*(q7 - 16) - q0*q1*q6*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) - q0*q2*q3*q5*q6*(q1 - 16)*(q4 - 16)*(q7 - 16) + q0*q3*q4*q7*(q1 - 16)*(q2 - 16)*(q5 - 16)*(q6 - 16) + q0*q3*q6*q7*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q5 - 16) + q0*q4*q5*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q6 - 16) + q0*q4*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q5*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q1*q2*q3*q4*q6*q7*(q0 - 16)*(q5 - 16) + q1*q2*q3*q7*(q0 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q1*q2*q4*q6*(q0 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) + q1*q3*q4*q5*q6*q7*(q0 - 16)*(q2 - 16) - q2*q4*q5*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) - q2*q5*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) - q2*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q3*q5*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q4 - 16)
p12 = q0*q1*q2*q3*q4*q5*(q6 - 16)*(q7 - 16) - q0*q1*q3*q5*q6*(q2 - 16)*(q4 - 16)*(q7 - 16) + q0*q1*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*q3*q5*(q1 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*q4*q5*q6*q7*(q1 - 16)*(q3 - 16) - q0*q2*q4*q5*q7*(q1 - 16)*(q3 - 16)*(q6 - 16) + q0*q2*q4*q6*(q1 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) - q0*q2*q5*q6*q7*(q1 - 16)*(q3 - 16)*(q4 - 16) + q0*q2*q5*q7*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) - q0*q2*q6*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) - q1*q2*q4*(q0 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q2*q3*q4*q5*q6*(q0 - 16)*(q1 - 16)*(q7 - 16) - q4*q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16) + q4*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) + q6*q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) - q7*(q0 - 16)*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)
p13 = -q0*q1*q2*q3*q5*q6*q7*(q4 - 16) + q0*q1*q2*q3*q5*q7*(q4 - 16)*(q6 - 16) - q0*q1*q2*q4*q5*(q3 - 16)*(q6 - 16)*(q7 - 16) + q0*q1*q2*q5*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) - q0*q2*q3*q4*q5*q6*q7*(q1 - 16) + q0*q2*q3*q4*q5*q7*(q1 - 16)*(q6 - 16) - q0*q4*q6*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) - q0*q5*q6*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) - q0*q6*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) + q0*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q1*q4*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q1*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q2*q4*q5*q6*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q7 - 16) + q2*q4*q6*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q5 - 16) - q2*q4*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) + q2*q6*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16)
p14 = -q0*q1*q2*q4*q5*q6*q7*(q3 - 16) - q0*q1*q2*q4*q6*(q3 - 16)*(q5 - 16)*(q7 - 16) + q0*q1*q2*q5*q6*q7*(q3 - 16)*(q4 - 16) + q0*q1*q2*q6*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) - q0*q1*q3*q5*q7*(q2 - 16)*(q4 - 16)*(q6 - 16) - q0*q1*q4*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q0*q1*q5*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) + q0*q2*q4*q7*(q1 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) - q0*q2*q7*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16) + q0*q3*q5*q6*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q7 - 16) + q1*q2*q3*q4*q5*q6*(q0 - 16)*(q7 - 16) + q1*q2*q4*q5*(q0 - 16)*(q3 - 16)*(q6 - 16)*(q7 - 16) + q1*q2*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q1*q4*q6*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16) - q1*q6*q7*(q0 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) - q2*q3*q4*q5*q7*(q0 - 16)*(q1 - 16)*(q6 - 16)
p15 = q0*q1*q2*q3*q4*q5*q6*q7 + q0*q1*q2*q4*(q3 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) - q0*q1*q2*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)*(q7 - 16) + q0*q1*q4*q6*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q7 - 16) + q0*q1*q5*q6*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q7 - 16) + q0*q1*q6*q7*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16) + q0*q2*q3*q5*q6*q7*(q1 - 16)*(q4 - 16) - q0*q3*q5*(q1 - 16)*(q2 - 16)*(q4 - 16)*(q6 - 16)*(q7 - 16) - q0*q4*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q5 - 16)*(q6 - 16) - q0*q5*q7*(q1 - 16)*(q2 - 16)*(q3 - 16)*(q4 - 16)*(q6 - 16) - q1*q2*q3*q4*q5*(q0 - 16)*(q6 - 16)*(q7 - 16) - q1*q2*q4*q5*q6*(q0 - 16)*(q3 - 16)*(q7 - 16) - q1*q2*q4*q6*q7*(q0 - 16)*(q3 - 16)*(q5 - 16) - q1*q2*q6*(q0 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q7 - 16) + q2*q4*q5*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q6 - 16) + q2*q7*(q0 - 16)*(q1 - 16)*(q3 - 16)*(q4 - 16)*(q5 - 16)*(q6 - 16)

4. Brute force to get flag.

1
2
3
4
5
6
7
8
9
10
11
for (int q0 = 0; q0 < 16; q0++)
for (int q1 = 0; q1 < 16; q1++)
for (int q2 = 0; q2 < 16; q2++)
for (int q3 = 0; q3 < 16; q3++)
for (int q4 = 0; q4 < 16; q4++)
for (int q5 = 0; q5 < 16; q5++)
for (int q6 = 0; q6 < 16; q6++)
for (int q7 = 0; q7 < 16; q7++){
    ...
    long long int diff = p1+p2+p3+ ... +p15;
}

the smallest diff with the file result will be the flag.

flag{95066ebd}

solve.py
brute.cpp

Tags: Brute-force Quantum
← 0CTF 2019 Final - Quantum Game (Crypto, 214) GoogleCTF 2019 - Quantum Key Distribution (Crypto, 90) →