Shipwrecked Lattices Solve Script

README.md

From classical theory, we know that the class group of $\mathcal{O} = \mathbb{Z}[\sqrt(-d)]$ acts on the isogeny graph of a curve $E$ with $\mathbb{F}_p$-endomorphism ring $\mathcal{O}$.

In theory, we can just "transfer" such an isogeny from $E_0 \stackrel{\varphi}{\to} E_a$ to $E_b \stackrel{\varphi}{\to} E_{ab}$ (in fact, that's how you prove correctness). However, to do this we need an effective(?) endomorphism ring. After all, we can't just apply an isogeny $\varphi: E_0 \to E_a$ to $E_b$.

But guess what? In this challenge we're given it, since it's precisely $\mathcal{B}(-1, -p)$. Furthermore, we are given an embedding $\omega$. More specifically, it's the embedding $\iota: \mathbb{Z}[\sqrt{-d}] \hookrightarrow \mathcal{B}(-1, -p)$, given by $\iota(\sqrt{-d}) = \omega$. (This is suggested by $\omega^2 + d = 0$.) So, the solution is to simply perform the following steps. Below I write $\mathcal{O}_*$, but if you are unfamiliar with quaternion orders, you can treat them as just elliptic curves.

0. Normalise the oriented orders so that $\sqrt{-d}$ embeds to the same element $\omega$
1. Find a connecting (quaternion) ideal $J$ from $\mathcal{O}_0$ to (an order isomorphic to) $\mathcal{O}_a$. More specifically, find ideal $J \subseteq \mathcal{O}_0$ such that $\mathcal{O}_R(J) \cong \mathcal{O}_a$.
2. "Pull" that $J$ back to $\mathbb{Z}[\sqrt{-d}]$, by intersecting it with the ideal space $\mathrm{span}_{\mathbb{Z}}{1, \omega}$. In other words, take the elements in $J$ that is a linear combination of $1$ and $\omega$. This is an ideal in $\mathbb{Z}[\sqrt{-d}]$, e.g. since it represents some $E_0 \to E_a$. More specifically, it will equal to $\prod_i [\mathfrak{l}_i]^{e_i}$, where $e$ is the secret vector and $\mathfrak{l} = \langle l, \sqrt{l} + \sqrt{d} \rangle$ are the generators used in GroupAction. Again, think about CSIDH.
3. "Push" the $J$ into $\mathcal{O}_b$ using the embedding given ($\omega$).
4. Finally, $\mathcal{O}_{ab}$ is the "codomain" of the action of the pushed $J$, i.e. $\mathcal{O}_{ab} = \mathcal{O}_R(J)$.

solve.sage

# `findIsom` imported from https://github.com/Jonathke/Computing-Optimal-Embeddings/blob/main/helpers.py#L260
# (It is simply linear algebra)

sage: # Step 1: Prepare data and match omega's "direction"
....: for line in open("output.txt", "r").readlines()[:4]:
....:     exec(preparse(line.strip()))
....: 
....: OA_ = B.quaternion_order(O_A)
....: alpha = findIsom(O0, omega_a, omega)
....: assert alpha * omega_a * alpha^-1 == omega
....: OA = B.quaternion_order([alpha * b * alpha^-1 for b in OA_.basis()])
....: 
....: OB_ = B.quaternion_order(O_B)
....: alpha = findIsom(O0, omega_b, omega)
....: assert alpha * omega_b * alpha^-1 == omega
....: OB = B.quaternion_order([alpha * b * alpha^-1 for b in OB_.basis()])

sage: # Step 2: Find I \cap <1, omega> as a imaginary quadratic order
....: M_omega = Matrix([list(omega), list(B(1))])
....: I = connectingIdeal(START, OA)
....: FM = ZZ^4
....: I_module = I.free_module()
....: K_module = FM.submodule(M_omega)
....: cap = I_module.intersection(K_module)
....: _gens = M_omega.solve_left(cap.basis_matrix())
....: 
....: K.<d2> = QuadraticField(-d)
....: J = K.ideal([d2 * x + y for x, y in _gens])

sage: J
Fractional ideal (20816482029993582812165860491549622288014907504125869469007643433498749268844207526, d2 + 10226743542002992718495793683695575619047811524242918527038846504225868369852897985)
sage: # Step 3: Transfer this to OB
....: g0 = 20816482029993582812165860491549622288014907504125869469007643433498749268844207526
....: g1 = 10226743542002992718495793683695575619047811524242918527038846504225868369852897985
....: frak = OB * g0 + OB * (omega + g1) # you can treat this as ideal intersection
....: OAB = frak.right_order()

sage: # Step 4: Flag
....: shared_secret = invariant(OAB)
....: key = SHA256.new(data=str(shared_secret).encode()).digest()[:128]
....: iv = bytes.fromhex("...")
....: ct = bytes.fromhex("...")
....: AES.new(key, AES.MODE_CBC, iv).decrypt(ct)

b'kalmar{1s_th1s_l4tt1c3_b4s3d_crypt0?_meme.jpg}\x02\x02'

crazy