from machinerie import Circuit, draw404
draw404()
Challenge 3 : Algorithme de Grover cassé (2/2)
Notre ingénieur s’est trompé lorsqu’il a programmé l’algorithme, il a oublié des \(H\)… Comment faire pour récupérer le drapeau ?
Soit un drapeau “00101011”, le circuit complet s’écrit :
from machinerie import create_grover
flag = [0, 0, 1, 1, 0, 1, 1]
n = len(flag)
grover = create_grover(flag, range(n), range(n))
grover.draw_circuit()
full_circuit = Circuit(n)
full_circuit.h(range(n))
full_circuit.compose(grover, inplace=True)
full_circuit.compose(grover, inplace=True)
full_circuit.compose(grover, inplace=True)
full_circuit.compose(grover, inplace=True)
results = full_circuit.get_measure()
drapeau = sorted(results, key=lambda x: x[1], reverse=True)[0]
print(f"""
Drapeau : {drapeau}
Probabilité : {results[drapeau]}
""")
Drapeau : 1101100
Probabilité : 0.52734375
À une inversion près, on retrouve notre drapeau en 4 coups, … quand le circuit est bien implémenté. Ce n’est malheureusement pas le cas pour le circuit sur nos serveurs, il manque au moins 2 \(H\) par colonne…
Par exemple :
grover = create_grover(flag, range(n - 2), range(n - 2))
grover.draw_circuit()
Pour couronner le tout, il n’y a qu’une passe qui a été implémentée.
Votre mission : récupérer le drapeau.
Vous avez accès à 3 paramètres : - l’entrée - les positions des \(H\) entre \(Z_f\) et \(Z_\text{OR}\) - vous avez le droit d’en poser \(\leq n-2\) - les positions des \(H\) après \(Z_\text{OR}\) - vous avez le droit d’en poser \(\leq n-2\)
à travers la fonction test_flag_grover (j’utilise exactement la même fonction côté API).
Pour éviter le brute force sur le CTFd directement, vous devrez reproduire la procédure deux fois, pour récupérer deux drapeaux de 12 bits chacuns, le drapeau final sera 404CTF{premier_flag+deuxième_flag}, par exemple : 404CTF{0101010101010101010101010}
Pour éviter l’explosion de votre ordinateur lors de l’appel à get_flat_unitary, vous utiliserez des angles pour m’envoyer votre entrée. À partir d’une liste de \(n*3\) flottants, je construis n’importe quel état d’entré avec des portes \(U\). Les angles sont ceux de la sphère de Bloch. Vous avez l’implémentation dans Circuit : Circuit.from_angles().
Par exemple deux Hadamards :
from math import pi
# theta_0, phi_0, lambda_0, theta_1, ...
angles = [0, 0, 0] # [pi / 2, 0, pi, pi, 0, 0]
qc = Circuit.from_angles(angles)
qc.draw_qubits()\[ |0\rangle\]
En appelant l’API, vous obtiendrez une mesure. Pour éviter la surcharge, je mesure à chaque fois sur 1000 essais. Le brute force de l’API est évidemment toujours interdit, vous êtes sensé pouvoir trouver le drapeau avec moins de \(30\) essais (\(5\) si vous n’êtes pas trop malchanceux).
Solution
Même si l’algorithme de Grover ne pouvait pas être reproduit avec \(n-2\) portes, il était possible de récupérer de l’information sur le drapeau en complexité linéaire. Par exemple, pour connaître les deux dernier bits, il était possible d’essayer la combinaison suivante :
qc = Circuit(7)
qc.h([0, 1, 2, 3, 4])
qc.x(5)
grover = create_grover(flag, range(n - 2), [])
qc.compose(grover, inplace=True)
qc.draw_circuit()
Si le drapeau ne fini pas part 10, alors aucune des combinaison en entrée n’est égale au drapeau et \(Z_f\) n’a aucun effet. Arrivé à la troisième couche, tous les \(H\) sont annulés (\(HH=I\)), donc on se retrouve avec un état unique. \(Z_\text{OR}\), n’a qu’un effect sur la polarisation, cela n’affectera pas la mesure. La sortie est donc 0000010 avec une probabilité de 1.
Si le drapeau fini par 10, alors le drapeau fait parti des combinaisons en entrée et \(Z_f\) aura un effet sur le bon drapeau. Sans dérouler les opérations, on peut voir que \(H Z_f H\) n’est plus égal à l’identité, et qu’il y a donc des superpositions qui restent. La sortie sera donc une superposition de plusieurs possibilités.
La résolution est alors la suivante : tester les qubits 2 par 2 (00, 01, 10, 11), si la mesure donne une superposition, alors c’est que les deux qubits sont bons.
from math import pi
h = [pi / 2, 0, pi]
x = [pi, 0, 0]
zero = [0, 0, 0]
z = 10 * himport requests
from machinerie import q
import json
from math import pi
z = 10 * h + x + x + 0 * h
data = {
"input_qubits": z,
"hadamard_middle": [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] + [],
"hadamard_end": [],
}
headers = {"Content-Type": "application/json", "Accept": "application/json"}
url = "https://causapscal-des-profondeurs.404ctf.fr/grover/2"
response = requests.post(url, json=data, headers=headers)
print(json.loads(response.content)){'message': "{'000000001100': 0.0009765625, '000101110000': 0.001953125, '101010011111': 0.0009765625, '001000000100': 0.001953125, '010111011000': 0.0009765625, '010011110011': 0.0009765625, '011111000111': 0.0009765625, '111110000101': 0.0009765625, '101111000011': 0.0009765625, '110010111001': 0.0009765625, '111100111101': 0.001953125, '101001001100': 0.0009765625, '011100001010': 0.0009765625, '001001011100': 0.0009765625, '001100010010': 0.0009765625, '100011100101': 0.0009765625, '001100001010': 0.0009765625, '110000001111': 0.0009765625, '001011111010': 0.001953125, '000000010110': 0.0009765625, '101001010111': 0.0009765625, '110010101110': 0.001953125, '101100001101': 0.0009765625, '000111010001': 0.0009765625, '001000110011': 0.0009765625, '100011001110': 0.001953125, '110101111110': 0.0009765625, '100100011110': 0.001953125, '010001000110': 0.0009765625, '110101000110': 0.0009765625, '001010110000': 0.0009765625, '100100001111': 0.0009765625, '011110100010': 0.0009765625, '101011010010': 0.0009765625, '000110011000': 0.0009765625, '010101100000': 0.0009765625, '111000001111': 0.0009765625, '111100011101': 0.0009765625, '010111011001': 0.0009765625, '010000000010': 0.0009765625, '010010111010': 0.0009765625, '011011010010': 0.0009765625, '000000011101': 0.0009765625, '000111011100': 0.001953125, '100011110010': 0.0009765625, '101001010000': 0.001953125, '111000101110': 0.001953125, '001111000001': 0.0009765625, '010110110110': 0.0009765625, '010101000000': 0.001953125, '100110100001': 0.0009765625, '101111011011': 0.0029296875, '010011000111': 0.0009765625, '011000100010': 0.0009765625, '011110101010': 0.0009765625, '000111000010': 0.0009765625, '100001111001': 0.0009765625, '010111110101': 0.0009765625, '100110110101': 0.001953125, '101101110001': 0.0009765625, '010100001101': 0.0009765625, '010111010000': 0.0009765625, '011001110100': 0.0009765625, '000010100011': 0.0009765625, '111101110000': 0.0009765625, '110000111101': 0.0009765625, '001101111010': 0.0009765625, '001111000101': 0.0009765625, '110011110111': 0.0009765625, '111001101110': 0.0009765625, '001011111101': 0.0009765625, '011000111111': 0.001953125, '100100000110': 0.0009765625, '100000111110': 0.0009765625, '010100000101': 0.0009765625, '001100011000': 0.001953125, '001011010110': 0.0009765625, '111001001111': 0.0009765625, '000000100000': 0.0009765625, '010011101111': 0.0009765625, '001001100110': 0.0009765625, '101001110111': 0.0009765625, '110111010100': 0.0009765625, '110000001000': 0.001953125, '110000111011': 0.0009765625, '100001101100': 0.0009765625, '011100110100': 0.0009765625, '011011011110': 0.0009765625, '011111111001': 0.001953125, '100010010110': 0.0009765625, '100001011101': 0.001953125, '010111010100': 0.0009765625, '011101001101': 0.001953125, '110110001101': 0.001953125, '100100101110': 0.0009765625, '111011010001': 0.0009765625, '110110110100': 0.001953125, '110001011010': 0.0009765625, '101100100001': 0.0009765625, '101111100001': 0.0009765625, '101101011010': 0.0009765625, '010011101101': 0.001953125, '100101111011': 0.0009765625, '110110010011': 0.0009765625, '100001110100': 0.0029296875, '101000110101': 0.0009765625, '010111101101': 0.0009765625, '101101011000': 0.0009765625, '110100111001': 0.0009765625, '100111110001': 0.0009765625, '001000100110': 0.0009765625, '100011011110': 0.0009765625, '100100111110': 0.0009765625, '001010110011': 0.001953125, '010111100110': 0.0009765625, '100000100100': 0.001953125, '010001011000': 0.0009765625, '001100111011': 0.0009765625, '001101101100': 0.0009765625, '011101110001': 0.001953125, '101100011011': 0.0009765625, '010101011010': 0.0009765625, '110001000111': 0.0009765625, '000101011100': 0.001953125, '111001011101': 0.0009765625, '011110010001': 0.0009765625, '011010000000': 0.0009765625, '011000010111': 0.0009765625, '100101101110': 0.0009765625, '001011111001': 0.001953125, '011110111101': 0.0009765625, '011001000001': 0.0009765625, '010111111100': 0.0009765625, '001001100010': 0.001953125, '010001101010': 0.0009765625, '111101001000': 0.0009765625, '101100110100': 0.0009765625, '111011011010': 0.0009765625, '101000001100': 0.0009765625, '100001011110': 0.0009765625, '110100101111': 0.0009765625, '011111101100': 0.001953125, '111101100010': 0.0009765625, '011000110001': 0.0009765625, '111111110001': 0.0009765625, '100000001010': 0.0009765625, '110111111111': 0.0009765625, '001110000101': 0.0009765625, '000000100110': 0.0009765625, '010000110011': 0.001953125, '101000011000': 0.0009765625, '000110011100': 0.0009765625, '011110001100': 0.0009765625, '100101000100': 0.0009765625, '001110110111': 0.0009765625, '101110101011': 0.0009765625, '010101000111': 0.0009765625, '110100110111': 0.0009765625, '000110010101': 0.0009765625, '111100100010': 0.0009765625, '000000111100': 0.0009765625, '010010101100': 0.0009765625, '010111000101': 0.0009765625, '001110011100': 0.0009765625, '011110110110': 0.0009765625, '100100001100': 0.0009765625, '001001110111': 0.0009765625, '001101011011': 0.001953125, '000101101011': 0.0009765625, '100101000011': 0.001953125, '000100010101': 0.001953125, '100101011110': 0.0009765625, '010001011111': 0.0009765625, '111111111000': 0.0009765625, '000100110011': 0.0009765625, '001100010101': 0.0009765625, '100111100011': 0.0009765625, '010110000000': 0.0009765625, '011101010100': 0.001953125, '010011101000': 0.0009765625, '000100011110': 0.0009765625, '001100100001': 0.0009765625, '101100101000': 0.0009765625, '010100001001': 0.0009765625, '011111101000': 0.0009765625, '011100011110': 0.001953125, '110000101110': 0.0009765625, '110100001101': 0.0009765625, '011101101010': 0.0009765625, '011110110011': 0.0009765625, '101110110010': 0.0009765625, '111111000001': 0.0029296875, '110110110010': 0.0009765625, '110110000010': 0.0009765625, '100101001001': 0.0009765625, '010001111101': 0.0009765625, '100000111101': 0.0009765625, '100001011100': 0.0009765625, '101111111100': 0.0009765625, '010011101011': 0.0009765625, '010000111101': 0.001953125, '110111100111': 0.0009765625, '100001001100': 0.0009765625, '111111111101': 0.0009765625, '111010010011': 0.0009765625, '110101011110': 0.0009765625, '101010011000': 0.0009765625, '001011100110': 0.0009765625, '100111110111': 0.0009765625, '101011110000': 0.0009765625, '111001011010': 0.001953125, '000110000000': 0.0009765625, '100101111010': 0.001953125, '001011000110': 0.0009765625, '000100100000': 0.0009765625, '001011100010': 0.0009765625, '101001110011': 0.0009765625, '001100011110': 0.0009765625, '000110001000': 0.001953125, '011011101110': 0.0009765625, '110000011000': 0.001953125, '111011010100': 0.0009765625, '111101100111': 0.0009765625, '000100000010': 0.0009765625, '100010001011': 0.0009765625, '110100010011': 0.001953125, '000101100001': 0.0009765625, '010001111010': 0.0009765625, '101010011100': 0.0009765625, '011001011110': 0.0009765625, '001111111000': 0.0009765625, '001101011101': 0.0009765625, '001111001100': 0.0009765625, '100111000010': 0.0009765625, '100101111110': 0.001953125, '010001101111': 0.0009765625, '111000110101': 0.0009765625, '001111101110': 0.0009765625, '100111000101': 0.0009765625, '101001111110': 0.0009765625, '101000111100': 0.0029296875, '011111111101': 0.0009765625, '110100001001': 0.0009765625, '011100001011': 0.0009765625, '000100010010': 0.0009765625, '011111011101': 0.0009765625, '101001110001': 0.001953125, '110110110101': 0.0009765625, '101001101001': 0.0009765625, '111011111111': 0.0009765625, '100010100000': 0.0009765625, '110000100010': 0.0009765625, '010000101111': 0.0009765625, '110100000001': 0.0009765625, '011000111110': 0.0009765625, '111010101101': 0.0009765625, '110101111000': 0.0009765625, '110001001001': 0.001953125, '110011101111': 0.0009765625, '101101111101': 0.0009765625, '000111110100': 0.0009765625, '101100011110': 0.0009765625, '100111001011': 0.0009765625, '000010100110': 0.0009765625, '011011001000': 0.0009765625, '001101010001': 0.0009765625, '111010001111': 0.0009765625, '101111101000': 0.0009765625, '010000000100': 0.0009765625, '011100001110': 0.0009765625, '010011101010': 0.0009765625, '110000010001': 0.001953125, '010000111110': 0.0009765625, '101110111111': 0.0009765625, '100000110100': 0.0009765625, '100100110001': 0.0009765625, '110011011001': 0.0009765625, '011110001011': 0.0009765625, '100010010111': 0.0009765625, '011000100101': 0.0009765625, '010100010111': 0.0009765625, '011101000011': 0.0009765625, '010101111010': 0.001953125, '101110100010': 0.0009765625, '101010000010': 0.0009765625, '101101101100': 0.0009765625, '011001000101': 0.0009765625, '010000010000': 0.0009765625, '100100000011': 0.0009765625, '100001111111': 0.0009765625, '000011011100': 0.0009765625, '001001001110': 0.0009765625, '110100001010': 0.0009765625, '000010010000': 0.0009765625, '010111100101': 0.0009765625, '001110010000': 0.0009765625, '100110110100': 0.0009765625, '000100001001': 0.0009765625, '110101010111': 0.001953125, '000100100010': 0.0009765625, '110110100001': 0.0009765625, '101001010010': 0.0009765625, '011000110100': 0.0009765625, '010101101101': 0.0009765625, '110111111100': 0.0009765625, '101101010100': 0.0009765625, '001001111111': 0.0009765625, '101011011111': 0.001953125, '011000101111': 0.0009765625, '001011101000': 0.0009765625, '000011000100': 0.0009765625, '010111110110': 0.0009765625, '111000000101': 0.0009765625, '100001000000': 0.0009765625, '111100111010': 0.0009765625, '010110011010': 0.0009765625, '011100110010': 0.0009765625, '101001111101': 0.0009765625, '101100011111': 0.0009765625, '101000110111': 0.001953125, '010111001010': 0.0009765625, '001100000110': 0.0009765625, '101111010010': 0.0009765625, '101100000011': 0.0009765625, '100100001110': 0.0009765625, '111010111101': 0.001953125, '110101100000': 0.0009765625, '111110111011': 0.0009765625, '001011000001': 0.0009765625, '100100111010': 0.001953125, '101010001001': 0.0009765625, '101011010110': 0.0009765625, '001111100100': 0.0009765625, '000111100001': 0.0009765625, '011010100011': 0.0009765625, '011010111011': 0.0009765625, '000011001101': 0.0009765625, '010110001001': 0.001953125, '001001010000': 0.0009765625, '000110111010': 0.001953125, '000011011000': 0.0009765625, '101111110111': 0.0009765625, '111010000000': 0.0009765625, '001100101110': 0.0009765625, '101010010110': 0.0009765625, '110110111111': 0.0009765625, '101011001100': 0.0009765625, '001110011011': 0.001953125, '101111110010': 0.001953125, '001110010001': 0.0009765625, '011110010000': 0.0009765625, '110000100111': 0.0009765625, '100101110001': 0.0009765625, '000100111111': 0.0009765625, '011010100110': 0.001953125, '111001101000': 0.0009765625, '101100010011': 0.0009765625, '011010100101': 0.0009765625, '110101001000': 0.0009765625, '100011100011': 0.001953125, '110111000100': 0.0009765625, '111100100000': 0.0009765625, '101101011001': 0.0009765625, '011100011011': 0.001953125, '101011101111': 0.0009765625, '101011000011': 0.001953125, '011101011010': 0.0009765625, '110000010010': 0.001953125, '011101101100': 0.0009765625, '010010111001': 0.0009765625, '011001100000': 0.0009765625, '011000101001': 0.0009765625, '111110011111': 0.0009765625, '010100000000': 0.0009765625, '110111100001': 0.0009765625, '011111010001': 0.0009765625, '001010011110': 0.0009765625, '001111111110': 0.0009765625, '110111011101': 0.0009765625, '111011110100': 0.0009765625, '000101000101': 0.0009765625, '011110111100': 0.001953125, '011011001011': 0.001953125, '001000001010': 0.0009765625, '110001110101': 0.0009765625, '000001000001': 0.0009765625, '011010011011': 0.0009765625, '011110100000': 0.0009765625, '000010000111': 0.0009765625, '001000011110': 0.0009765625, '011100011111': 0.001953125, '111101101000': 0.0009765625, '001010000001': 0.0009765625, '101100011101': 0.0009765625, '001011101001': 0.0009765625, '100010010010': 0.0009765625, '011010110010': 0.0029296875, '011111000100': 0.0009765625, '010000100010': 0.0009765625, '111111001111': 0.0009765625, '100000101100': 0.0009765625, '101011001000': 0.0009765625, '001000010110': 0.0009765625, '000111100111': 0.0009765625, '100000000011': 0.0009765625, '100110000011': 0.0009765625, '001101101110': 0.001953125, '000001011101': 0.0009765625, '011001001010': 0.0009765625, '110000101101': 0.0009765625, '000101101110': 0.0009765625, '110001000010': 0.001953125, '001100100011': 0.0009765625, '100110001001': 0.0009765625, '100100001011': 0.0009765625, '001101111001': 0.0009765625, '111010101111': 0.0009765625, '011011101011': 0.0009765625, '000101111111': 0.001953125, '011110111010': 0.0009765625, '000011011001': 0.0009765625, '010011000101': 0.0009765625, '101010001010': 0.0029296875, '111000100001': 0.0009765625, '100110111000': 0.0009765625, '010011011101': 0.0009765625, '100010011110': 0.0009765625, '100000011100': 0.001953125, '111001000010': 0.0009765625, '101000000000': 0.0009765625, '001111111011': 0.0009765625, '110101001010': 0.0009765625, '010000001110': 0.0009765625, '000010010001': 0.0009765625, '101111101100': 0.0009765625, '101101111011': 0.0009765625, '001011001100': 0.0009765625, '110010001101': 0.0009765625, '101110001110': 0.001953125, '110011011110': 0.001953125, '001101000000': 0.0009765625, '000111110000': 0.0009765625, '100111001110': 0.0009765625, '000011000000': 0.001953125, '110010010111': 0.001953125, '011101111011': 0.0009765625, '110110111001': 0.0009765625, '011111100111': 0.0009765625, '000111101011': 0.0009765625, '100010000001': 0.0009765625, '000001101001': 0.0009765625, '110011010110': 0.001953125, '101000111111': 0.0009765625, '001010001111': 0.0009765625, '011101110011': 0.0009765625, '111110010011': 0.0009765625, '101000111010': 0.0009765625, '100010011011': 0.0009765625, '000011110110': 0.0009765625, '000000010001': 0.0009765625, '100110010001': 0.0009765625, '001000001011': 0.0009765625, '001011010001': 0.0009765625, '111111001011': 0.0009765625, '100010101101': 0.0009765625, '111110001110': 0.0009765625, '110001001011': 0.0009765625, '111111100010': 0.0009765625, '101000000101': 0.0009765625, '101000100111': 0.0009765625, '101110111010': 0.0009765625, '101000111110': 0.0009765625, '110011101011': 0.0009765625, '110000111100': 0.0009765625, '111101110110': 0.0009765625, '101101111001': 0.0009765625, '111111111110': 0.0009765625, '000100011111': 0.001953125, '111000101001': 0.0009765625, '101010100100': 0.0009765625, '111110110111': 0.0009765625, '000101101100': 0.0009765625, '101101011111': 0.0009765625, '010010111100': 0.0009765625, '110110010100': 0.0009765625, '110111100010': 0.0009765625, '110011110000': 0.0009765625, '000001010100': 0.0009765625, '000000101001': 0.0009765625, '000000011111': 0.0009765625, '110100000010': 0.0009765625, '100111101001': 0.0009765625, '111101010111': 0.0009765625, '101011101101': 0.0009765625, '010101110101': 0.0009765625, '011010110011': 0.0009765625, '101001010001': 0.0009765625, '100001100110': 0.0009765625, '011000111001': 0.0009765625, '101111000111': 0.0009765625, '010001101100': 0.0009765625, '100010111111': 0.0009765625, '011000001100': 0.0009765625, '011000001001': 0.0009765625, '100000110101': 0.0009765625, '011000100110': 0.0009765625, '110011001111': 0.0009765625, '001001110011': 0.0009765625, '110011011100': 0.0009765625, '100010100101': 0.0009765625, '111110100111': 0.0009765625, '110000110000': 0.001953125, '110011010111': 0.0009765625, '111000010101': 0.001953125, '011011000000': 0.0009765625, '011101101011': 0.0009765625, '011101011110': 0.0009765625, '100111101101': 0.0009765625, '100000110010': 0.0009765625, '000011100101': 0.0009765625, '010000100110': 0.0009765625, '110101100010': 0.0009765625, '101011101110': 0.0009765625, '110100100101': 0.0009765625, '010001000001': 0.0009765625, '110110100000': 0.0009765625, '111000011110': 0.0009765625, '010010110110': 0.0009765625, '100101000010': 0.0009765625, '110111111110': 0.0009765625, '000001010011': 0.0009765625, '001101101101': 0.0009765625, '011011000011': 0.0009765625, '000110010100': 0.0009765625, '100000101001': 0.001953125, '101101110111': 0.0009765625, '000101100010': 0.0009765625, '011111010101': 0.0009765625, '001111100011': 0.0009765625, '101111010000': 0.0009765625, '111011101001': 0.0009765625, '010100100100': 0.0009765625, '001011101111': 0.0009765625, '000010101101': 0.0009765625, '110110111000': 0.0009765625, '110000100011': 0.0009765625, '001011000000': 0.0009765625, '001011011101': 0.001953125, '101010000011': 0.001953125, '110000100110': 0.0009765625, '010011000000': 0.0009765625, '010001010101': 0.0009765625, '001001011001': 0.0009765625, '010011000100': 0.0009765625, '000000001111': 0.0009765625, '111110001101': 0.0009765625, '000111001110': 0.001953125, '110010011000': 0.0009765625, '100011100100': 0.0009765625, '011001011111': 0.0009765625, '000100101111': 0.0009765625, '110000001010': 0.0009765625, '001010001110': 0.0009765625, '101000101111': 0.0009765625, '001100000000': 0.0009765625, '111011100011': 0.0009765625, '010110000011': 0.001953125, '100101111101': 0.0009765625, '111100100100': 0.0009765625, '111111010100': 0.0009765625, '110100010010': 0.0009765625, '101000001001': 0.0009765625, '000000000100': 0.0009765625, '011101111100': 0.0009765625, '101111111011': 0.0009765625, '010011110000': 0.0009765625, '100110100010': 0.001953125, '000110110101': 0.0009765625, '110001010000': 0.0009765625, '010010101101': 0.0009765625, '101011100011': 0.0009765625, '010100111100': 0.0009765625, '101111000100': 0.0009765625, '010100111010': 0.0009765625, '011010111001': 0.0009765625, '001001101000': 0.001953125, '101010100000': 0.0009765625, '100101100111': 0.0009765625, '110000001011': 0.0009765625, '101011011101': 0.0009765625, '010001100011': 0.0009765625, '010001001000': 0.0009765625, '100110011000': 0.0009765625, '001010010001': 0.0009765625, '011010010101': 0.0009765625, '001000010011': 0.0009765625, '011100100100': 0.0009765625, '001110000111': 0.0009765625, '011011000001': 0.0009765625, '110001101100': 0.0009765625, '100111011111': 0.0009765625, '101000101001': 0.0009765625, '101111011001': 0.0009765625, '001010000100': 0.0009765625, '011001001001': 0.0009765625, '110111000001': 0.0009765625, '000100011101': 0.0009765625, '010111101011': 0.0009765625, '001110001011': 0.0009765625, '001100110000': 0.0009765625, '010000011011': 0.0009765625, '111111010111': 0.0009765625, '101000111000': 0.0009765625, '010010110010': 0.0009765625, '011101101111': 0.0009765625, '111110100011': 0.0009765625, '011111110011': 0.0009765625, '111111001010': 0.001953125, '001100000111': 0.0009765625, '110110110011': 0.0009765625, '011011001001': 0.0009765625, '011101010011': 0.001953125, '001001000111': 0.001953125, '010111001001': 0.0009765625, '000001100101': 0.0009765625, '010111110111': 0.0009765625, '000110010110': 0.0009765625, '000101101010': 0.0009765625, '111000111111': 0.0009765625, '011110001110': 0.0009765625, '111010100000': 0.0009765625, '111001110010': 0.0009765625, '110111011011': 0.0009765625, '010001110000': 0.0009765625, '011100111111': 0.0009765625, '000011010101': 0.0009765625, '001101110100': 0.0009765625, '111011011101': 0.0009765625, '110101010100': 0.0009765625, '010110011001': 0.0009765625, '110010100001': 0.0009765625, '011100111110': 0.001953125, '011010101000': 0.0009765625, '001101101001': 0.0009765625, '111010010001': 0.0009765625, '000101001011': 0.0009765625, '111010000010': 0.0009765625, '000110011101': 0.0009765625, '011110100001': 0.0009765625, '111011000111': 0.0009765625, '100011011001': 0.0009765625, '110010110000': 0.0009765625, '010000101101': 0.0009765625, '011100101010': 0.0009765625, '000000101011': 0.0009765625, '111010010110': 0.0009765625, '001000101011': 0.0009765625, '101111101110': 0.0009765625, '110001110110': 0.0009765625, '000000000001': 0.0009765625, '011000001110': 0.0009765625, '000100111010': 0.0009765625, '010001111011': 0.0009765625, '110111001101': 0.0009765625, '110100000101': 0.0009765625, '101011110101': 0.0009765625, '110100100000': 0.0009765625, '110110001111': 0.0009765625, '001111111101': 0.0009765625, '100100000010': 0.0009765625, '000111111100': 0.0009765625, '111001101101': 0.0009765625, '110011100011': 0.0009765625, '000100011010': 0.0009765625, '100101011011': 0.0009765625, '001011100000': 0.0009765625, '000001010000': 0.001953125, '100101111000': 0.0009765625, '111101011011': 0.0009765625, '000011000010': 0.0009765625, '111100111100': 0.0009765625, '010101010101': 0.0009765625, '001000011000': 0.001953125, '100000100101': 0.0009765625, '110011111101': 0.0009765625, '110110101011': 0.0009765625, '010010010011': 0.0009765625, '101011000111': 0.0009765625, '101011000100': 0.0009765625, '111111001100': 0.0009765625, '101111001011': 0.0009765625, '110010111110': 0.001953125, '000011100110': 0.001953125, '100011010000': 0.0009765625, '001101111011': 0.0009765625, '010100100010': 0.0009765625, '111111100101': 0.0009765625, '101010100110': 0.0009765625, '110101101010': 0.0009765625, '100000011010': 0.0009765625, '110100111010': 0.0009765625, '010100101110': 0.0009765625, '111101010110': 0.0009765625, '001000001101': 0.0009765625, '010001111110': 0.0009765625, '010111000000': 0.0009765625, '101110000010': 0.0009765625, '000100111011': 0.0009765625, '110100110000': 0.001953125, '010110111001': 0.0009765625, '001101011100': 0.0009765625, '111111111010': 0.0009765625, '001001110110': 0.0009765625, '001000001111': 0.0009765625, '010000101010': 0.001953125, '100111111011': 0.0009765625, '110110111101': 0.0009765625, '111110101001': 0.0009765625, '100001011000': 0.0009765625, '011011111000': 0.0009765625, '011101100011': 0.0009765625, '001010001010': 0.0009765625, '101100111111': 0.0009765625, '000111101110': 0.0009765625, '000100110000': 0.0009765625, '011111100100': 0.001953125, '011011100111': 0.0009765625, '101011100110': 0.0009765625, '000101111101': 0.0009765625, '001101010101': 0.0009765625, '011000000111': 0.001953125, '011101111101': 0.0009765625, '101101100000': 0.0009765625, '111110001010': 0.0009765625, '000100001011': 0.0009765625, '110110011001': 0.0009765625, '111111100110': 0.0009765625, '110100000000': 0.0009765625, '101010100101': 0.0009765625, '101001010101': 0.001953125, '001011110011': 0.0009765625, '101100000110': 0.0009765625, '001011011000': 0.0009765625, '100010110000': 0.0009765625, '101110011101': 0.0009765625, '110111110110': 0.0009765625, '000111011110': 0.0009765625, '110010111000': 0.0009765625, '000000001011': 0.0009765625, '000001010111': 0.0009765625, '100111101000': 0.0009765625, '111010001000': 0.0009765625, '110010110010': 0.0009765625, '111010111110': 0.0009765625, '010000100011': 0.0009765625, '011011011100': 0.0009765625, '100100101000': 0.0009765625, '000110010111': 0.0009765625, '000110111001': 0.0009765625, '000101010011': 0.0009765625, '011101001011': 0.0009765625, '000010010010': 0.0009765625, '111010010010': 0.0009765625, '101010011101': 0.0009765625, '000101100111': 0.0009765625, '110101110011': 0.0009765625, '010100001010': 0.0009765625, '010001001011': 0.0009765625, '011001001101': 0.001953125, '111111000000': 0.0009765625, '000110110010': 0.0009765625, '111010110010': 0.0009765625, '100110011010': 0.0009765625, '000110010010': 0.0009765625, '101101011101': 0.0009765625, '111011110011': 0.0009765625, '000101010101': 0.001953125, '100001111010': 0.0009765625, '111111011001': 0.0009765625, '101010100111': 0.0009765625, '110000111010': 0.0009765625, '101001001011': 0.0009765625, '110001100010': 0.0009765625, '010001001010': 0.0009765625, '110100010000': 0.0009765625, '100010110111': 0.0009765625, '100100101010': 0.0009765625, '110100000011': 0.0009765625, '001111001010': 0.0009765625, '101000000100': 0.0009765625, '101010111100': 0.0009765625, '010111100011': 0.0009765625, '100001101001': 0.001953125, '111000011111': 0.0009765625, '010110110000': 0.0009765625, '111001011111': 0.0009765625, '100000001111': 0.0009765625, '010111111000': 0.001953125, '010011010011': 0.0009765625, '011001000111': 0.0009765625, '100011110101': 0.0009765625, '000110100110': 0.0009765625, '010111100111': 0.0009765625, '110100011011': 0.0009765625, '000110110011': 0.0009765625, '010010010100': 0.0009765625, '100110101101': 0.0009765625, '111110001011': 0.0009765625, '000001100011': 0.0009765625, '010100001110': 0.0009765625, '001111101000': 0.0009765625, '000000100100': 0.0009765625, '101000111101': 0.0009765625, '101010100010': 0.0009765625, '010101100111': 0.0009765625, '000100100011': 0.0009765625, '000000011011': 0.0009765625, '000011111000': 0.0009765625, '111011011100': 0.0009765625, '101010001101': 0.0009765625, '011001111111': 0.0009765625, '110101000001': 0.0009765625, '011100100001': 0.0009765625, '100111010001': 0.001953125, '010010110100': 0.0009765625, '011101011100': 0.0009765625, '001101010110': 0.0009765625, '000111111011': 0.0009765625, '001111100101': 0.0009765625, '111010011000': 0.0009765625, '111100000011': 0.0009765625, '010101110001': 0.0009765625, '010001001100': 0.0009765625, '000111100110': 0.0009765625, '110111100101': 0.0009765625, '111010000101': 0.0009765625, '111011000001': 0.0009765625, '001111111010': 0.0009765625, '100010100111': 0.0009765625, '111101111010': 0.0009765625, '101100010010': 0.0009765625, '011111100110': 0.0009765625, '111111110111': 0.0009765625, '011111010111': 0.0009765625, '101011000001': 0.0009765625, '011100001100': 0.0009765625, '000010101001': 0.0009765625, '001000001000': 0.0009765625, '101100111000': 0.0009765625, '001000101001': 0.0009765625, '101001001101': 0.0009765625, '010101111100': 0.0009765625, '100100111011': 0.0009765625, '001100100010': 0.0009765625, '011100000001': 0.0009765625, '010010000001': 0.0009765625, '001100011001': 0.0009765625, '111011110000': 0.0009765625, '100100000101': 0.0009765625, '101000001011': 0.0009765625, '100111011100': 0.0009765625, '011011110001': 0.0009765625, '110011000010': 0.0009765625, '011010001000': 0.0009765625, '001110100000': 0.0009765625, '110011010101': 0.0009765625, '100010110010': 0.0009765625, '001001101111': 0.0009765625, '100010111001': 0.0009765625, '111111101001': 0.0009765625, '000011011111': 0.0009765625, '110011110110': 0.0009765625, '010010011010': 0.0009765625, '110010010110': 0.0009765625, '100110010111': 0.0009765625, '111100111110': 0.0009765625, '100000100111': 0.0009765625, '011110110001': 0.0009765625, '000001110101': 0.0009765625, '010110100001': 0.0009765625, '111110011010': 0.0009765625, '000011100011': 0.0009765625, '100011010110': 0.0009765625, '001111011101': 0.0009765625, '110000010000': 0.0009765625, '011010111000': 0.0009765625, '011001011101': 0.0009765625, '011011010100': 0.0009765625, '111101101011': 0.0009765625, '010111011101': 0.0009765625, '011100010101': 0.0009765625, '100000010110': 0.0009765625, '111100110010': 0.0009765625, '101001000110': 0.0009765625, '010011111010': 0.0009765625, '010100000011': 0.0009765625, '001100111111': 0.0009765625, '010111100001': 0.0009765625, '011001011001': 0.0009765625, '000010100010': 0.0009765625, '101110111011': 0.0009765625, '111001000001': 0.0009765625, '100001011011': 0.0009765625, '000101001000': 0.0009765625, '010100011001': 0.0009765625, '101100110000': 0.0009765625, '001111110101': 0.0009765625, '000111110010': 0.0009765625, '000110100001': 0.0009765625, '001011011111': 0.0009765625, '100101100010': 0.0009765625, '000010000001': 0.0009765625, '101001000100': 0.0009765625}"}