<aside> š
Attachment:
</aside>
<aside> š”
This challenge was finished a long time ago (just a few days after QnQSecCTF 2025) and was originally intended for HITszCTF 2026. Until the recent infobahnCTF, where @Aeren released Madoka RSA challenge, I realized that if I didnāt release this one soon, it would become outdatedš
</aside>
The challenge generates primes with a certain special structure, then uses them in RSA. You are also given an oracle that allows you to query square roots of some numbers modulo n. The core idea is actually quite simpleāit is essentially a special case of ECM. But before talking about ECM, letās briefly review what factorization algorithms like Pollard p-1, Williams p+1, BachāShallit, etc. are really doing.
Abstractly and somewhat informally, all these algorithms exploit certain special structures of primes to construct a group. Then, starting from a known element in the group, we perform some operations to obtain a result that we can control. Using this result, we can often construct a number that shares a non-trivial common factor with n, thereby factoring n.
For example, Pollard p-1 constructs the multiplicative group modulo p and computes $gcd(a^{p-1} - 1, n)$.
Back to this challenge. If you try it out first, you will find that the oracle only returns a value when the input is 96. Without exploiting the structure of the primes, an oracle with only a single valid output is almost useless.
However, if you are sensitive to algebraic number theory (or if you are clever enough to prompt an LLM properly), you will notice that: $4p = 4pp^2 + 12pp + 12 = (2pp + 3)^2 + 3 = (2pp + 3 + \sqrt{-3})(2pp + 3 - \sqrt{-3})$
$q = p + 2pp + 3$
Primes of this form allow us to construct elliptic curves with complex multiplication (CM). We know that for an elliptic curve with CM, its order satisfies $E_p = p + 1 \pm t$, where $t$ is the Frobenius trace.
Moreover, for a CM elliptic curve $E_p$, the Frobenius trace satisfies $4p = t^2 + D y^2$. In this challenge, this corresponds to $t = 2pp + 3, D = 3, y = 1$.
By consulting references (or asking an AI), we know that CM with $D = 3$ corresponds to curves of the form $y^2 = x^3 + b$, which have sextic twists.
Since in this challenge $p \equiv 1 \pmod{3}$ , the sextic twists correspond to six curves, i.e., six different values of $b$ . In theory, we would need to know a primitive root $g$ modulo p, and then take $g \in \{1, b, b^2, \ldots, b^5\}$ to obtain these six curves and find the one with the desired order. However, in this challenge, from the fact that āonly oracle(96) returns a valueā, you can guess that the smallest primitive root modulo p is not large, and thus simply enumerate all possible values of $b$ .
On the other hand, you can also directly construct $y^2 = x^3 + 96$, and then brute-force the x-coordinates to try to obtain the corresponding curve and point.
In summary, the curve needed for this challenge is $E: y^2 = x^3 + 32$ , and the point returned by oracle(96) is (4, ā¦), which we denote as $P$ .
Placing E modulo p, we have $Q := E.order \cdot P = O \Rightarrow Q.x \equiv 0 \pmod{p}$ . Thus, over $\mathbb{Z}$ , we have $Q.x = k \cdot p$ .
Furthermore, with high probability we have $k < q$ , so the relation $Q.x = k \cdot p$ also holds in $\mathbb{Z} / n\mathbb{Z}$ . At this point, we can simply compute $gcd(Q.x, n)$ to recover p.
<aside> š”
In fact, if you try ECM factorization by randomly selecting $b$ and points, there is already a fairly high probability of factoring N.
</aside>