Rating:
# X-Mas CTF 2019
## Quantum
The quantum challenges were a lot of fun for me since i knew almost nothing about quantum computing and the challenges helped me
a lot with getting started and then keeping up my interest when it got to the more complicated parts.
1. [Q-Trivia](#q-trivia)
2. [Datalines](#datalines)
3. [Quantum Secret](#quantum-secret)
### Q-Trivia
This task was a quiz about all things quantum computing related. It helped a lot with getting to know the basics of quantum computing. It was basically a lot of reading through wikipedia pages.
Task:
```
Before we dive deeper into the Quantum Computing category, here are some basic trivia questions for warmup
Remote server: nc challs.xmas.htsp.ro 13003
*Author: Reda*
Hint! For superposition #1, you will find a very simple notation (made out of 3 characters) to show the 2 states after being superposed with an H gate.
```
When connecting to the server with netcat, we get the following introduction:
```
Welcome to Quantum Trivia! You will be presented with 4 categories with 5 questions each.
If you answer them correctly, I will reward you with a flag! Hooray!
NOTE: ONLY USE ASCII when answering questions. That means no foreign characters.
Good luck!
```
It then proceeds with the first question category
##### General Knowledge
```
Question: How are the special bits called in quantum computing
Your answer: qubits
```
This one i already knew the answer to, so there is not much to be said here.
Pretty much all of the other questions in this category could be solved by reading the wikipedia page about [qubits](https://en.wikipedia.org/wiki/Qubit)
```
Question: What is the name of the graphical representation of the qubit?
Your answer: bloch sphere
Question: In what state is a qubit which is neither 1 or 0
Your answer: superposition
Question: What do you call 2 qubits which have interacted and are now in a wierd state in which they are correlated?
Your answer: entangled
Question: What do you call the notation used in Quantum Computing where qubits are represented like this: |0> or |1>?
Your answer: dirac
```
##### Quantum Gates
Most of the answers in this category could be found on the the wikipedia page about [quantum logic gates](https://en.wikipedia.org/wiki/Quantum_logic_gate)
```
Question: What gate would you use to put a qubit in a superposition
Your answer: CNOT
Question: What gate would you use to "flip" a qubit's phase in a superposition?
Your answer: Z
Question: What's the full name of the physicist who invented the X, Y and Z gates?
Your answer: wolfgang pauli
```
This actually required a seperate lookup since the gate-page only gave you the last name. If you were more well versed in physics than i was, you could've probably know the first name without having to look it up.
```
Question: What are quantum gates represented by (in dirac notation)
Your answer: matrix
```
##### Superposition
```
Question: How do you represent a qubit |1> put in a superposition?
Your answer: |->
```
This was a tough question because the answer was really well hidden. I only found it after taking a closer look at the hint and actually looking up the wikipedia page for the [hadamard-transformation](https://en.wikipedia.org/wiki/Hadamard_transform#Quantum_computing_applications) since the chapter on the quantum gates page didn't go enough into detail to mention it.
The next two questions are just yes-no answers so you could theoretically just try out which answer is correct but i knew the first and the second could be looked up on the wikipedia page for [quantum logic gates](https://en.wikipedia.org/wiki/Quantum_logic_gate)
```
Question: Will a superposition break if measured
Your answer: yes
Question: Can you take a qubit out of a superposition with a Hadamard gate
Your answer: yes
Question: If you measure a qubit in a superposition, what's the average chance of measuring |0>?
Your answer: 50
Question: What's the name of the famous paradox which demonstrates the problem of decoherence?
Your answer: schrodinger's cat
```
This last answer was a little bit problematic for me since i am German and i looked up the correct english name which is
"Schrödinger's cat" and i didn't remember that the ö is sometimes replaced with o because it's not usually used in english so i looked around for other paradoxes such as the EPR-paradox until i tried the correct answer on a whim.
##### Entanglement
```
Question: Will particles always maeasure the same when entangled
Your answer: No
Question: Will entangled qubits violate Bell's Inequality?
Your answer: Yes
```
The answer to this question was mostly a guess on my part because i had read about bell states before so i assumed that qubits that were not in those states would violate the inequality.
```
Question: Does the following state present 2 entangled qubits? 1/sqrt(2)*(|10> + |11>)
Your answer: No
Question: Does the following state present 2 entangled qubits? 1/sqrt(2)*(|10> + |01>)
Your answer: Yes
```
Honestly i thought they were both entangled when answering the question during the CTF but looking back at it now, i can see
that the first qubit in the first question will always read to 1 and thus is not entangled.
```
Question: Can 2 entangled qubits ever get untangled?
Your answer: yes
```
With this last question completed, you will receive a message with the flag:
```
Congratz! You made it! ;)
Here's your flag: X-MAS{Qu4ntwm_Tantrum_M1llionar3}
```
### Datalines
In this challenge, you needed to apply quantum cryptography to decipher a message.
Task:
```
Alice and Bob managed to get their hands on quantum technology! They now use it to do evil stuff, like factoring numbers :O
They want to send data between their computers, but the problem is, only Bob has a quantum computer, Alice has a classic one!
They cannot transmit qubits between their computers, so Alice thought it would be smart to use a technique she already knows, but only send instructions to Bob's Quantum computer in order to transmit data.
Can you figure out what Alice told Bob?
Files: transmission.txt
Author: Reda
```
The file provided contained the following text:
```
Initial State: 1/sqrt(2)*(|00> + |11>)
The first one is mine.
Instructions:
X X Z ZX I ZX X X Z Z Z I X Z ZX X I Z Z I I ZX Z X I ZX X X ZX Z Z X X Z Z I I ZX X Z X Z Z I X ZX I ZX I ZX X X ZX ZX ZX ZX ZX ZX X I Z Z ZX Z ZX ZX X Z I ZX Z X I Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I X Z Z X X ZX I Z X ZX ZX I I ZX X I Z Z ZX Z ZX Z X ZX X Z X ZX I Z Z I X Z ZX ZX Z Z Z I I Z ZX I X ZX ZX I I Z ZX Z ZX ZX ZX X X ZX ZX I I ZX X X ZX Z ZX ZX Z ZX ZX I X Z Z I X ZX Z ZX Z ZX X I Z ZX ZX X X ZX I ZX I ZX X X ZX ZX ZX Z ZX Z Z I X ZX I ZX I Z ZX ZX ZX Z Z I X ZX Z X X Z Z I X Z ZX X I Z Z I I ZX Z X I ZX X X ZX Z Z X X Z Z I I ZX X Z X Z Z I X ZX Z ZX Z ZX X I Z ZX X Z I ZX X Z I Z Z I I ZX X X ZX ZX I ZX I ZX Z ZX Z ZX Z X I Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I X Z ZX I X Z ZX Z ZX ZX X I Z Z Z X X ZX X I Z ZX Z ZX Z ZX X I Z ZX X ZX I Z Z I X Z Z X X ZX X I ZX Z Z I X Z Z X X Z ZX Z ZX ZX Z X I ZX X X ZX Z ZX ZX Z ZX X Z I ZX I ZX I Z Z X I Z Z I X Z Z X X Z Z Z Z ZX X I ZX Z Z I X ZX Z ZX Z ZX X ZX X ZX Z X I Z ZX ZX Z Z ZX ZX Z ZX I ZX I ZX Z ZX Z ZX Z X I ZX X ZX I Z Z I X ZX Z Z ZX ZX I ZX I Z Z X X Z ZX ZX ZX Z Z I X ZX X I Z ZX ZX ZX Z Z Z I X ZX I ZX I ZX X X ZX ZX ZX ZX ZX ZX X I Z Z ZX Z ZX ZX X Z I ZX Z X I Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I I Z I Z X ZX I ZX X Z X X ZX ZX ZX I X Z X X Z Z X ZX I Z Z I X ZX ZX I I ZX I ZX I Z Z X X ZX I Z X ZX ZX I I Z ZX Z Z Z Z I I ZX ZX I I ZX ZX I I Z X ZX I Z Z I I ZX ZX I I ZX ZX X X Z X ZX I Z Z I I ZX ZX X X ZX ZX I I Z Z I X ZX X I Z Z ZX Z Z Z Z I I ZX ZX X X ZX ZX X X Z I ZX X Z Z I X ZX ZX ZX ZX Z ZX Z ZX ZX X I Z ZX X Z X Z Z I X ZX Z X X Z Z I X Z ZX ZX Z ZX ZX I I ZX X X ZX ZX ZX X X ZX ZX I I Z ZX Z Z Z Z I I Z I Z X ZX X I Z ZX ZX ZX ZX Z Z X X ZX ZX I I ZX X X Z Z Z I X ZX Z ZX Z ZX Z X I ZX X ZX X ZX X ZX X ZX ZX I I ZX ZX X I Z Z I X X I X I ZX X ZX X ZX I ZX I ZX Z ZX Z ZX ZX I X Z I ZX X Z Z I X Z Z X X ZX X I ZX Z Z I X ZX Z X X Z Z I X Z ZX Z ZX ZX ZX I I ZX Z ZX Z ZX ZX I I ZX I ZX I Z Z ZX ZX ZX ZX I I Z ZX Z Z Z Z I I Z I Z X ZX X I Z ZX ZX ZX ZX Z Z X X ZX ZX I I ZX X X Z Z Z I X ZX Z ZX Z ZX Z X I ZX X ZX X ZX X ZX X ZX ZX I I ZX ZX X I Z Z I X X I Z ZX ZX X I Z ZX Z Z Z Z I ZX X Z X ZX I Z Z I X ZX Z Z ZX Z X ZX X Z Z I X Z ZX ZX Z ZX ZX I I ZX X X ZX ZX ZX X X ZX I ZX I ZX X X ZX ZX ZX Z ZX Z Z I X ZX X I Z ZX X X ZX ZX X ZX X Z X ZX X Z Z I X ZX X I Z ZX X X ZX ZX ZX I X Z Z I X Z ZX X I Z Z I I ZX Z Z ZX ZX I ZX I Z Z X I Z Z I X ZX ZX ZX ZX Z ZX Z ZX ZX X I Z ZX X Z X Z Z I X X I X I ZX X ZX X ZX I ZX I ZX Z ZX Z ZX ZX I X Z Z I X Z Z X X ZX X I ZX Z Z I X X I Z ZX ZX X I Z ZX Z Z Z Z X ZX I Z Z I X Z Z I I ZX X X ZX ZX ZX X X ZX ZX I I Z ZX Z Z Z Z I X Z Z X X ZX I Z X ZX ZX I X Z Z I X ZX Z X I Z ZX ZX Z Z ZX ZX Z Z Z I I ZX X Z I Z ZX I X Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I X ZX X I Z ZX ZX ZX Z Z Z I X X I X I ZX X ZX X ZX I ZX I ZX Z ZX Z ZX ZX I X Z Z I X ZX Z X I ZX X X ZX ZX ZX X I Z Z I X X I Z ZX ZX X I Z ZX Z Z Z Z Z I X Z ZX I X Z ZX Z ZX ZX ZX I X Z X Z I Z ZX ZX Z ZX I Z X ZX Z X I Z ZX Z ZX ZX I ZX I ZX X X ZX ZX ZX Z ZX Z Z I X ZX Z X I ZX X X Z Z Z I X ZX ZX I I ZX X X ZX Z Z X X ZX Z X I ZX X X ZX ZX ZX Z Z ZX X ZX X ZX ZX I I ZX ZX X I Z Z I X Z ZX ZX Z Z Z X X ZX Z X I Z Z X X ZX ZX I X Z X X Z Z Z I X I ZX Z I Z X Z I X ZX Z I X I X I I X ZX Z Z X X ZX ZX ZX ZX Z Z X Z X Z Z X X Z ZX Z ZX ZX Z X I I Z I Z X X X X X X I I ZX X X ZX I X ZX ZX ZX ZX ZX Z I Z I Z X I ZX ZX ZX ZX I X ZX ZX X I ZX ZX X I ZX X X ZX ZX ZX Z Z I Z I Z X X Z Z X I X I X ZX X ZX X X Z Z Z I Z
~Alice
```
Right of the bat one notices that the instructions are made up only from three different letters: I,X and Z.
From my research in the trivia task, i knew that Z and X were both quantum logic gates and since gates are represented by matrices, i assumed that I was the identity-matrix. Alice also gives us an initial state of two entangled qubits in superposition. My first guess was to apply those gates on the qubits, however i didn't know how to do that for two-qubit-states since they are represented by a vector of size 4 whereas gates are just 2x2 matrices so a dot-product won't work. After taking another look at the wikipedia page for quantum logic gates i found out that in order to apply the gate to one of the qubits, you need to form the kronecker-product of the gate with the identity matrix and then form the dot-product with the two-qubit state.
However i made the mistake of thinking that ZX means the kronecker-product between the Z and X matrices.
After some initial attempts just applying the gates on the initial state and collecting four strings, each string representing the state of each of the 4 numbers in the initial state throughout the process, and then converting each string into ascii, i didn't get a readable message out of it. So i decided to look into quantum cryptography and there, i found the solution: [Superdense Coding] (https://en.wikipedia.org/wiki/Superdense_coding)
One of my errors that this corrected was that ZX is actually the dot product of Z and X.
The other one was, that after the application of the respective gate from the instructions, i had to first apply a CNOT-Gate and the kronecker-product of an H-Gate and an idenitiy-matrix on the result to figure out what Alice wanted to encode in that step, since that is what Bob would have to do if they both had Quantum Computers.
Depending on resulting state, the corresponding encoded bits are:
* "00" if the state is |00>
* "01" if the state is |01>
* "10" if the state is |10>
* "11" if the state is |11>
Thus, my final python-script looked like this:
```python
import numpy
import binascii
message = "X X Z ZX I ZX X X Z Z Z I X Z ZX X I Z Z I I ZX Z X I ZX X X ZX Z Z X X Z Z I I ZX X Z X Z Z I X ZX I ZX I ZX" \
" X X ZX ZX ZX ZX ZX ZX X I Z Z ZX Z ZX ZX X Z I ZX Z X I Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I X Z Z X X " \
"ZX I Z X ZX ZX I I ZX X I Z Z ZX Z ZX Z X ZX X Z X ZX I Z Z I X Z ZX ZX Z Z Z I I Z ZX I X ZX ZX I I Z ZX Z " \
"ZX ZX ZX X X ZX ZX I I ZX X X ZX Z ZX ZX Z ZX ZX I X Z Z I X ZX Z ZX Z ZX X I Z ZX ZX X X ZX I ZX I ZX X X ZX" \
" ZX ZX Z ZX Z Z I X ZX I ZX I Z ZX ZX ZX Z Z I X ZX Z X X Z Z I X Z ZX X I Z Z I I ZX Z X I ZX X X ZX Z Z X" \
" X Z Z I I ZX X Z X Z Z I X ZX Z ZX Z ZX X I Z ZX X Z I ZX X Z I Z Z I I ZX X X ZX ZX I ZX I ZX Z ZX Z ZX Z " \
"X I Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I X Z ZX I X Z ZX Z ZX ZX X I Z Z Z X X ZX X I Z ZX Z ZX Z ZX X" \
" I Z ZX X ZX I Z Z I X Z Z X X ZX X I ZX Z Z I X Z Z X X Z ZX Z ZX ZX Z X I ZX X X ZX Z ZX ZX Z ZX X Z I ZX " \
"I ZX I Z Z X I Z Z I X Z Z X X Z Z Z Z ZX X I ZX Z Z I X ZX Z ZX Z ZX X ZX X ZX Z X I Z ZX ZX Z Z ZX ZX Z " \
"ZX I ZX I ZX Z ZX Z ZX Z X I ZX X ZX I Z Z I X ZX Z Z ZX ZX I ZX I Z Z X X Z ZX ZX ZX Z Z I X ZX X I Z ZX" \
" ZX ZX Z Z Z I X ZX I ZX I ZX X X ZX ZX ZX ZX ZX ZX X I Z Z ZX Z ZX ZX X Z I ZX Z X I Z Z X X ZX I ZX I ZX " \
"X I Z ZX X X Z Z Z I I Z I Z X ZX I ZX X Z X X ZX ZX ZX I X Z X X Z Z X ZX I Z Z I X ZX ZX I I ZX I ZX I Z" \
" Z X X ZX I Z X ZX ZX I I Z ZX Z Z Z Z I I ZX ZX I I ZX ZX I I Z X ZX I Z Z I I ZX ZX I I ZX ZX X X Z X ZX I" \
" Z Z I I ZX ZX X X ZX ZX I I Z Z I X ZX X I Z Z ZX Z Z Z Z I I ZX ZX X X ZX ZX X X Z I ZX X Z Z I X ZX ZX ZX" \
" ZX Z ZX Z ZX ZX X I Z ZX X Z X Z Z I X ZX Z X X Z Z I X Z ZX ZX Z ZX ZX I I ZX X X ZX ZX ZX X X ZX ZX I I Z" \
" ZX Z Z Z Z I I Z I Z X ZX X I Z ZX ZX ZX ZX Z Z X X ZX ZX I I ZX X X Z Z Z I X ZX Z ZX Z ZX Z X I ZX X ZX X" \
" ZX X ZX X ZX ZX I I ZX ZX X I Z Z I X X I X I ZX X ZX X ZX I ZX I ZX Z ZX Z ZX ZX I X Z I ZX X Z Z I X Z Z" \
" X X ZX X I ZX Z Z I X ZX Z X X Z Z I X Z ZX Z ZX ZX ZX I I ZX Z ZX Z ZX ZX I I ZX I ZX I Z Z ZX ZX ZX ZX I" \
" I Z ZX Z Z Z Z I I Z I Z X ZX X I Z ZX ZX ZX ZX Z Z X X ZX ZX I I ZX X X Z Z Z I X ZX Z ZX Z ZX Z X I ZX X" \
" ZX X ZX X ZX X ZX ZX I I ZX ZX X I Z Z I X X I Z ZX ZX X I Z ZX Z Z Z Z I ZX X Z X ZX I Z Z I X ZX Z Z ZX " \
"Z X ZX X Z Z I X Z ZX ZX Z ZX ZX I I ZX X X ZX ZX ZX X X ZX I ZX I ZX X X ZX ZX ZX Z ZX Z Z I X ZX X I Z ZX" \
" X X ZX ZX X ZX X Z X ZX X Z Z I X ZX X I Z ZX X X ZX ZX ZX I X Z Z I X Z ZX X I Z Z I I ZX Z Z ZX ZX I ZX " \
"I Z Z X I Z Z I X ZX ZX ZX ZX Z ZX Z ZX ZX X I Z ZX X Z X Z Z I X X I X I ZX X ZX X ZX I ZX I ZX Z ZX Z ZX " \
"ZX I X Z Z I X Z Z X X ZX X I ZX Z Z I X X I Z ZX ZX X I Z ZX Z Z Z Z X ZX I Z Z I X Z Z I I ZX X X ZX ZX " \
"ZX X X ZX ZX I I Z ZX Z Z Z Z I X Z Z X X ZX I Z X ZX ZX I X Z Z I X ZX Z X I Z ZX ZX Z Z ZX ZX Z Z Z I I " \
"ZX X Z I Z ZX I X Z Z X X ZX I ZX I ZX X I Z ZX X X Z Z Z I X ZX X I Z ZX ZX ZX Z Z Z I X X I X I ZX X ZX X " \
"ZX I ZX I ZX Z ZX Z ZX ZX I X Z Z I X ZX Z X I ZX X X ZX ZX ZX X I Z Z I X X I Z ZX ZX X I Z ZX Z Z Z Z Z I" \
" X Z ZX I X Z ZX Z ZX ZX ZX I X Z X Z I Z ZX ZX Z ZX I Z X ZX Z X I Z ZX Z ZX ZX I ZX I ZX X X ZX ZX ZX Z ZX" \
" Z Z I X ZX Z X I ZX X X Z Z Z I X ZX ZX I I ZX X X ZX Z Z X X ZX Z X I ZX X X ZX ZX ZX Z Z ZX X ZX X ZX ZX " \
"I I ZX ZX X I Z Z I X Z ZX ZX Z Z Z X X ZX Z X I Z Z X X ZX ZX I X Z X X Z Z Z I X I ZX Z I Z X Z I X ZX Z I " \
"X I X I I X ZX Z Z X X ZX ZX ZX ZX Z Z X Z X Z Z X X Z ZX Z ZX ZX Z X I I Z I Z X X X X X X I I ZX X X ZX I X" \
" ZX ZX ZX ZX ZX Z I Z I Z X I ZX ZX ZX ZX I X ZX ZX X I ZX ZX X I ZX X X ZX ZX ZX Z Z I Z I Z X X Z Z X I X I" \
" X ZX X ZX X X Z Z Z I Z"
messageDigest = message.split(" ")
X = numpy.array([[0, 1], [1, 0]])
I = numpy.array([[1, 0], [0, 1]])
Z = numpy.array([[1, 0], [0, -1]])
ZX = numpy.dot(Z, X)
H = numpy.array([[1, 1], [1, -1]])
CNOT = numpy.array([
[1, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 1],
[0, 0, 1, 0]
])
XI = numpy.kron(X, I)
II = numpy.kron(I, I)
ZI = numpy.kron(Z, I)
ZXI = numpy.kron(ZX, I)
HI = numpy.kron(H, I)
init1 = numpy.array([1, 0, 0, 0])
init2 = numpy.array([0, 0, 0, 1])
initial = (1 / 2 ** (1 / 2) * (init1 + init2))
digest = ""
for m in messageDigest:
if m == "I":
init1 = numpy.transpose(numpy.dot(init1,II))
init2 = numpy.transpose(numpy.dot(init2,II))
elif m == "X":
init1 = numpy.transpose(numpy.dot(init1,XI))
init2 = numpy.transpose(numpy.dot(init2,XI))
elif m == "Z":
init1 = numpy.transpose(numpy.dot(init1,ZI))
init2 = numpy.transpose(numpy.dot(init2,ZI))
elif m == "ZX":
init1 = numpy.transpose(numpy.dot(init1,ZXI))
init2 = numpy.transpose(numpy.dot(init2,ZXI))
else:
print("Unknown Op: {0}".format(m))
dig1 = numpy.transpose(numpy.dot( init1,CNOT))
dig2 = numpy.transpose(numpy.dot(init2, CNOT))
dig1 = numpy.transpose(numpy.dot(dig1,HI))
dig2 = numpy.transpose(numpy.dot(dig2,HI))
dig = dig1 + dig2
if dig[0] != 0:
digest += "00"
elif dig[1] != 0:
digest += "01"
elif dig[2] != 0:
digest += "10"
elif dig[3] != 0:
digest += "11"
n = int('0b'+digest,2)
print(n.to_bytes((n.bit_length() + 7)//8,'big').decode())
```
The decoded message includes the flag:
```
In quantum information theory, superdense coding is a quantum communication protocol to transmit two classical bits of information (i.e., either 00, 01, 10 or 11) from a sender (often called Alice) to a receiver (often called Bob), by sending only one qubit from Alice to Bob, under the assumption of Alice and Bob pre-sharing an entangled state. X-MAS{3xtra_DEnS3_C0d1ng_GANG}
```
### Quantum Secret
This challenge was about extracting a secret string from a blackbox function.
Task:
```
The server will generate a binary array of 5 random elements called s.
In this challenge, you are going to input an initial state for 5 qubits.
I am going to take your input qubits and apply a series of quantum gates to them,
so that |x>|y> -> |x>|y ⊕ f(x)> where |x> are the 5 input qubits, |y> is a temporary qubit and f(x) = (Σᵢ sᵢ*xᵢ) % 2.
I will return to you the state after the transformation (|x>)
Example: Input: |011> and (s (secret) = [0, 1, 0])
I will compute the temporary qubit y ⊕ f(x) = (0*0 + 1*1 + 1*0) % 2 = 1,
so therefore I will return |011>, because the initial state wasn't modified.
The goal is to query this secret function with any state of the qubits and find out the secret binary array s.
Oh, and one more thing: you can only query the function ONCE.
And to make it even harder, I will not even return the temporary qubit ;)
Good luck!
Remote Server: nc challs.xmas.htsp.ro 13004
Author: Reda
```
When you connect to the server you get this message:
```
You will have to complete the exercise 3 times iin a row
Initial State |00000>
Before sending the qubits, you can apply quantum gates to them
Please choose between the I, X, Y, Z, H gates, or input - to stop applying gates to the certain qubit
Enter gate for Qubit #1
```
We can now apply an arbitrary amount of gates on each qubit. Afterwards we receive the message:
```
You can now apply other quantum gates to the Qubits before measurment:
Please choose between the I, X, Y, Z, H gates, or input - to stop applying gates to the certain qubit
Enter gate for Qubit #1
```
Initially this didn't make much sense to me since what would be the difference between the first and the second time. Eventually i figured out though that the calculation
```
I am going to take your input qubits and apply a series of quantum gates to them,
so that |x>|y> -> |x>|y ⊕ f(x)> where |x> are the 5 input qubits, |y> is a temporary qubit and f(x) = (Σᵢ sᵢ*xᵢ) % 2.
I will return to you the state after the transformation (|x>)
```
was done between those two steps.
I honestly was about to move on to another task because i thought solving this would require some deeper knowledge of quantum computing and i had no idea how to get the secret, since all we see in the end are the bits we send ourselves. I figured that you had to use H-Gates at some point since only superposition would allow the value of our qubits to be variable.
Just on a whim i looked at the wikipedia page for quantum computing to find out other applications for it, when i noticed the chapter on [quantum search] (https://en.wikipedia.org/wiki/Quantum_computing#Quantum_search). There, it mentioned Grover's Algorithm and considering my lack of ideas, i opened its [wikipedia entry](https://en.wikipedia.org/wiki/Grover%27s_algorithm).
And there, in the setup chapter it defines a unitary operator U_ω which is defined like this:
```
U_ω |x>|y> -> |x>|y ⊕ f(x)>
```
Even though f(x) represents a different but similar function in the context of Grover's algorithm, i had found at least some connection to the problem in my task, since the server also applies such an operator on my input.
Unfortunately, Grover's algorithm won't work in this case since it requires multiple attempts and is ment for database search.
So, i figured maybe there is another quantum search algorithm that might help me out.
After some searching i found the paper [A Review on Quantum Search Algorithms](https://arxiv.org/abs/1602.02730) which listed a couple other algorithms, amongst them the one that would help me. This was the Bernstein-Vazirani algorithm, which shows exactly how to extract the secret from the function f(x) as it is used in the case of this task. The authors prove how applying H-Gates on each qubit, then applying the unitary operator |x>|y> -> |x>|y ⊕ f(x)> on the result and then applying H-Gates on each qubit again will result in |x> = |s> with s being the secret from f(x).
Since the unitary operator is applied by the server, all we have to do to get the secret is apply the H-Gates before and after sending on each qubit and the measured result will be the secret we need.
We do this 3 times and we receive the flag:
```
Good job! 3/3 done!
Nice! You got it! FLAG: X-MAS{Fl3X1n_0N_B3rnstein_V4z1r4ni}
```
