Analyse de boulangerie.py
Le programme choisit 64 fois une recette dans sa liste, effectue quelques transformations sur celle-ci et, à chaque fois, nous devons retrouver, grâce aux informations publiques, quelle recette a été choisie.
bake
Cette fonction pioche p,q,r trois entiers premiers. Elle renvoie :
$$ (m^e[rq], e, pq) $$
en sachant que m est l’entier associé à la recette chosit
ot
Soit x le paramètre que nous donnons à la fonction
$$ \begin{gathered} y_1^2 \equiv x[p] \\ y_2^2 \equiv x[q] \end{gathered} $$
Ensuite on utilise le théorème des restes chinois pour calculer
$$ \begin{gathered} \varepsilon_1,\varepsilon_2 \in {-1,1} \\ \begin{cases} y \equiv\varepsilon_1y_1[p] \\ y \equiv\varepsilon_2y_2[q] \end{cases} \end{gathered} $$
On remarque que cette fonction nous sert à calculer la racine carré de x modulo pq :
$$ \begin{gathered} y \equiv y_1[p] \Longleftrightarrow y^2 \equiv y_1^2 \equiv x [p] \\ \text{et} \\ y \equiv y_2[q] \Longleftrightarrow y^2 \equiv y_2^2 \equiv x [q] \\ \text{Et comme } p\land q = 1\\ y^2 \equiv x[pq] \end{gathered} $$
Nouvelle tentative ?
Maintenant que vous savez ce que font ces fonctions, vous pouvez réessayer le challenge, sinon regardez la suite…
Solution
Un des gros piège était d’essayer d’utiliser la fonction ot !
Seul les informations de la fonction bake étaient utiles. La solution se résume par un simple calcul de pgcd :
$$ \begin{gathered} \text{Soit } a \text{ la recette testé et } m \text{ la recette tirée}\\ \text{Si } a \text{ est la bonne recette, alors :}\\ m^e \equiv a^e[pq] \Longrightarrow q | (m^e - a^e)\\ \text{Et donc, si a est la bonne recette :}\\ pgcd(pq, m^e[pq] - a^e[pq]) \geq q \end{gathered} $$
Code de la solution
from pwn import *
from math import gcd
from ast import literal_eval
HOST = "localhost"
PORT = 4000
recette = ["pain", "ananas", "croissant", "pain au chocolat"]
io = remote(HOST, PORT)
for i in range(64):
io.recvuntil(b"?")
print(f"Tour {i+1}/64")
io.recvuntil(b"Et voila : ")
line = io.recvline()
c, e, n = literal_eval(line.decode())
rep = None
for a in recette:
m = int.from_bytes(a.encode(), "big")
g = gcd(n, c - pow(m, e,n))
if 1 < g < n:
rep = a
break
if rep is None:
print("Impossible de trouver la recette !")
io.close()
exit(1)
x = "1"
io.sendlineafter(b"Alors ?", x.encode())
print("Envoi recette :", rep)
io.sendlineafter(b"Alors alors ??? ", rep.encode())
print(io.recvall())
io.close()