We all know that quantum computing is the future, so in order to practice my quantum computing skills, I have built my own encoding scheme, then I used it to hide the flag, can you recover it!

This challenge was in the misc category of the first GDG Algiers CTF due to involving quantum computing. In my opinion, a well founded knowledge of cryptography is useful in this challenge as shown later.

In essence, it envolved the decryption of a 3-stage encryption algorithm, which operated on some state vectors generated by each step. The first stage was a simple NOT, the second stage was a controlled NOT, and the third stage was a controlled CNOT.

Thanks to the basics track of the Qalypso Summer School I was able to fully understand the challenge and solve it using the intended method.

kvant.py

The first function in kvant.py is basically the application of the ket notation on a binary number.

def get_state(x):
    l = [0] * 2**len(x)
    l[int(x, 2)] = 1
    return l

In computer science terms, it maps a binary number string $b$ of length $n$ (corresponding to a decimal number $x$) to an array of size $2^n$ whose entries are all $0$ except for the $x^ \text{th}$ one, which is $1$. An example:

The next two functions should be self explanatory:

def str2bin(s):
    return ''.join(bin(ord(i))[2:].zfill(8) for i in s)

def bin2str(a):
    return ''.join(chr(int(a[i:i+8], 2)) for i in range(0, len(a), 8))

Encoding functions

encode_1()

Now comes the interesting part. The following function expects an initial state vector and creates a single qubit quantum circuit. Thus the initial state must be an array of size $2^1$.

def encode_1(initial_state):
    qc = QuantumCircuit(1)
    qc.initialize(initial_state)
    qc.x(0)
    qc.save_statevector()
    qobj = assemble(qc)
    state = sim.run(qobj).result()
    return list(state.get_statevector().real.astype(int))

It is to be noted that the above circuit performs the Qiskit .x() gate ( NOT ) on the $0^\text{th}$ qubit of the circuit, returning the resultant state vector. Given our definitions of $\ket{0}$ and $\ket{1}$, the possible results can be as follows:

encode_2()

The second encoding function happens to be a 2-qubit circuit, hence expecting a state vector of size $2^2$ as an input.

def encode_2(initial_state):
    qc = QuantumCircuit(2)
    qc.initialize(initial_state)
    qc.cx(0, 1)
    qc.save_statevector()
    qobj = assemble(qc)
    state = sim.run(qobj).result()
    return list(state.get_statevector().real.astype(int))

This time however, a .cx() gate ( CNOT ) is being applied to the 2 qubits – the $0^\text{th}$ and $1^\text{st}$ bit being the target and control bits respectively (damn qiskit for inverting their order). The CNOT gate simply flips the target bit, only if the control bit is set to 1 and does nothing otherwise. Fortunately, mathematics comes to the rescue with a handy matrix definition for the CNOT gate:

Its effect on a 2-qubit state vector $M$ is replicable by swapping the $1^\text{st}$ and $3^\text{rd}$ entries of $M$ (starting from 0), i.e.

An example with a prepared state $\ket{11}$:

encode_3()

The third encoding function is a 3-qubit circuit, hence expecting a state vector of size $2^3$ as an input.

def encode_3(initial_state):
    qc = QuantumCircuit(3)
    qc.initialize(initial_state)
    qc.ccx(0, 1, 2)
    qc.save_statevector()
    qobj = assemble(qc)
    state = sim.run(qobj).result()
    return list(state.get_statevector().real.astype(int))

The last encoding function is a .ccx() gate ( CCNOT ), also known as the Toffoli gate, which acts on 3 qubits. The CCNOT gate is a controlled version of the CNOT gate, i.e. it flips the target bit only if both control bits are set to 1 and does nothing otherwise. The CCNOT gate is defined as follows:

Again, it can be seen as swapping the $6^\text{th}$ and $7^{th}$ entries (starting from 0) of a 3-qubit state vector $M$ like so:

Encrypting functions

encrypt_1/2/3()

The encrypt_1/2/3() functions are the ones that actually perform the ‘encryption’. The first one iterates over every bit, applying the encode_1() to it and concatenating all the entries of the resulting state vectors. The second and third functions do the same, but with the encode_2() and encode_3() functions over every pairs and triples of bits respectively.

Note: After every encrypting function, the length of the encrypted message doubles!

Dry run using 'a'

Consider the encryption with the following string – 'a'

'a' = 97

↓ str2bin()

01100001

↓ encode_1()

not |0> not |1> not |1> not |0> not |0> not |0> not |0> not |1>

↓ computing!

|1> |0> |0> |1> |1> |1> |1> |0>

↓ expanding the states!

01 10 10 01 01 01 01 10

↓ encode_2() remember, first bit is target and second bit is control

cnot |01> cnot |10> cnot |10> ...

↓ computing!

|11> |10> |10> ...

↓ expanding the states!

0001 0010 0010 0001 0001 0001 0001 0010

↓ group every 3 bits (last one is wrong due to the short length of the message — length of message should be a multiple of 3)

000 100 100 010 000 100 010 001 000 100 10

↓ encode_3()

ccnot |000> ccnot |100> ccnot |100> ...

↓ computing!

|000> |100> |100> ...

↓ expanding the states!

10000000 00001000 0000100 ...

</br>

Now that we’ve understood how the encrpytion occurs, it’s just a matter of reversing each function, by doing the right swaps and collapsing the array to the previous, shorter, bit string.

My Solution

Download solve_kvant.py

def str2bin(s):
    return ''.join(bin(ord(i))[2:].zfill(8) for i in s)

def bin2str(a):
    return ''.join(chr(int(a[i:i+8], 2)) for i in range(0, len(a), 8))

def decrypt_1(enc_1):
    dec_bin = ''
    for i in range(0, len(enc_1), 2):
        state = [int(x) for x in enc_1[i:i+2]]
        dec_bin += str(bin(state.index(0))[2:]) # swap 0 and 1
    return dec_bin

def decrypt_2(enc_2):
    enc_1 = ''
    for i in range(0, len(enc_2), 4):
        state = [int(x) for x in enc_2[i:i+4]]
        state[1], state[3] = state[3], state[1] # CNOT swap
        enc_1 += str(bin(state.index(1))[2:].zfill(2))
    return enc_1

def decrypt_3(enc_3):
    enc_2 = ''
    for i in range(0, len(enc_3), 8):
        state = [int(x) for x in enc_3[i:i+8]]
        state[3], state[7] = state[7], state[3] # CCNOT swap
        enc_2 += str(bin(state.index(1))[2:].zfill(3))
    return enc_2

with open('enc.txt', 'r') as f:
    enc = str2bin(f.read()) # read file and convert to binary

flag = bin2str(decrypt_1(decrypt_2(decrypt_3(enc)))) # full decrypt and convert to string

print(flag)

Flag = CyberErudites{W3lc0m3_7o_th3_w0rld_0f_Qu4ntum_C0mput1ng!}

An uninteded solution

The beasts at SekaiCTF (winners) bruteforced the decryption process. It turns out that the search space for the decryption is very small, and the decryption can be done on a classical computer in a matter of seconds using the following script:

with open("enc.txt","r") as f:
    enc_3 = str2bin(f.read())
enc_3_map = {}
for w in ["000", "001", "010","011", "100", "101", "110", "111"]:
    enc_3_map[encrypt_3(w)] = w

enc_2 = ""
for _ in range(0,len(enc_3),8):
    enc_2 += enc_3_map[enc_3[_:_+8]]

enc_2_map = {}
for w in ["00", "01", "10","11"]:
    enc_2_map[encrypt_2(w)] = w

enc_1 = ""
for _ in range(0,len(enc_2),4):
    enc_1 += enc_2_map[enc_2[_:_+4]]

enc_1_map = {}
for w in ["0", "1"]:
    enc_1_map[encrypt_1(w)] = w

flag = ""
for _ in range(0,len(enc_1), 2):
    flag += enc_1_map[enc_1[_:_+2]]
print(bin2str(flag))

Credits: sahuang#6271