Hacktm Ddlp
DDLP (Upsolve)
Discussion at y011d4.
Source of this problem: HackTM Finals
Challenge Source
import os
import signal
from random import SystemRandom
random = SystemRandom()
flag = os.getenv("FLAG", "FAKEFLAG{THIS_IS_FAKE}")
if __name__ == "__main__":
signal.alarm(60)
try:
# parameter setup
p = int(input("p = "))
assert p.bit_length() >= 256
assert is_prime(p)
a = int(input("a = "))
b = int(input("b = "))
E = EllipticCurve(GF(p), [a, b])
assert not E.is_singular()
assert 0 < a < p
assert 0 < b < p
# DLP in GF(p)
g = GF(p)(input("g = "))
x = random.randint(0, p - 1)
h = g**x
print(f"{h = }")
x_ = int(input("x = "))
# DLP in E
Gx = int(input("Gx = "))
Gy = int(input("Gy = "))
G = E(Gx, Gy)
y = random.randint(0, p - 2 * int(sqrt(p))) # order should be > p - 2 * sqrt(p)
H = y * G
print(f"{H = }")
y_ = int(input("y = "))
if x == x_ and y == y_:
print(flag)
else:
print(f"{x = }, {y = }")
except Exception:
print("Something wrong...")
In short, we have to provide parameters \((p, a, b)\) such that both the DLP problem on \(\mathbb{F}_p\) and the ECDLP problem on \(E / \mathbb{F}_p : y^2 = x^3 + ax + b\) are feasible.
Background
There is a result from basic CM theory that is very easy to apply. For any negative integer \(D \equiv 0, 1 \pmod{4}\), there exists an integer polynomial \(H_D(X) \in \mathbb{Z}[X]\). Furthermore, if we find one of its roots over \(\mathbb{F}_p\) for prime \(p\), say \(j_0\), then any elliptic curve with \(j\)-invariant \(j_0\) over \(\mathbb{F}_p\) will have Frobenius trace \(t = p + 1 - |E / \mathbb{F}_p|\) satisfying \(4p = t^2 - Dy^2\). Moreover, \(H_d\) can be computed efficiently when \(D\) is small. This will be used below to construct a curve with a given trace.
Solution
The most common attacks on ECDLP are Smart’s attack on anomalous curves and the MOV attack on supersingular / curves with low embedding degree. I chose to go with the first since it is nicer. For Smart’s attack to work, we need an elliptic curve such that \(|E / \mathbb{F}_p| = p\). We also need \(p - 1\) to be smooth in order for DLP to work.
To do this, first note that an anomalous curve satisfies \(t = 1\). This means that we want to find \(p\) and some \(D\) such that \(4p = 1 - Dy^2\) and \(D\) is small. Furthermore, remember that we want \(p - 1\) to be smooth enough so that DLP works. We can incorporate this information by writing \(p = kX + 1\), where \(X\) is a large smooth integre. Substituting into the equation, we get that \(4(kX + 1) = 1 - Dy^2\), if we reduce the equation modulo \(4X\), we get that \(4 \equiv -Dy^2 \pmod{4X}\), which means that \(-3D^{-1}\) is a quadratic residue modulo \(4X\). With this, we can then solve for \(y\) to get a congruence \(y \equiv \sqrt{-3D^{-1}} \pmod{4X}\). Therefore, our plan is quite clear:
- Generate a large smooth \(X\)
- Iterate through small \(D\)s
- For each \(D\), check if \(-3D^{-1}\) is a quadratic residue modulo \(4X\). If not, restart
- If so, we generate a random \(y\) such that \(y \equiv \sqrt{-3D^{-1}} \pmod{4X}\)
- We then solve for \(k\) and check whether \(p = kX + 1\) is prime. If not, restart
- If so, we compute the Hilbert class polynomial \(H_{-D}(X)\) and find its roots over \(p\)
- Finally, curves with those \(j\)-invariants will have trace \(\pm 1\). If the curve has trace \(-1\), then we can take its quadratic twist for a curve with trace \(1\).
The only steps that require further explanation are steps 6 and 7. In step 6, we can compute the Hilbert class polynomial in Sage using the function hilbert_class_polynomial
. For step 7, we have to generate a curve with a given \(j\)-invariant. This can be done explicitly, but Sage provides an elliptic curve constructor EllipticCurve(GF(p), j=j0)
.
import time
import itertools
start_time = time.process_time()
Ds = []
primes = prime_range(2^15, 2^16)
while len(Ds) == 0:
X = product(sample(primes, 8))
Ds = [D for D in range(-7, -1000, -4) if D % 4 and is_square(Zmod(4 * X)(-3 / D))]
rs = [ZZ(Zmod(4 * X)(-3 / D).sqrt()) for D in Ds]
for D, r in itertools.cycle(zip(Ds, rs)):
y = randrange(2^16) * (4 * X) + r
p = ZZ((1 - D * y^2) / 4)
mx = max([p for p, _ in factor(p - 1)])
# Modify 48 to higher numbers if your computer is strong
if p.nbits() > 256 and is_prime(p) and mx.nbits() <= 48:
break
# Verification
assert is_prime(p)
print(f"{p = } ({p.nbits()} bits)")
print(f"largest prime factor: {mx} ({mx.nbits()} bits)")
print(f"Time taken: {time.process_time() - start_time:.3f} seconds")
# Curve
start_time = time.process_time()
j0 = hilbert_class_polynomial(D).change_ring(GF(p)).roots(multiplicities=False)[0]
E = EllipticCurve(GF(p), j=j0)
P = E.random_point()
if p * P != E(0):
E = E.quadratic_twist()
P = E.random_point()
assert p * P == E(0)
print("Is the curve anomalous?", E.order() == p)
print(f"Time taken: {time.process_time() - start_time:.3f} seconds")
# DLP
start_time = time.process_time()
g = GF(p).multiplicative_generator()
r = randrange(p - 1)
a = g^r
assert a.log(g) == r
print("DLP passed")
print(f"Time taken: {time.process_time() - start_time:.3f} seconds")
# ECDLP
start_time = time.process_time()
G = E.random_point()
r = randrange(G.order())
P = r * G
assert G.discrete_log(P) == r
print("ECDLP passed")
print(f"Time taken: {time.process_time() - start_time:.3f} seconds")
Example output:
p = 112724698004539627624570484385750988204241234813855755125331421145620885542006974769 (276 bits)
largest prime factor: 360332723321 (39 bits)
Time taken: 4.261 seconds
Is the curve anomalous? True
Time taken: 4.903 seconds
DLP passed
Time taken: 0.523 seconds
ECDLP passed
Time taken: 0.076 seconds
Running Time
(This is just an excuse for me to share my knowledge in analytic number theory) Let’s say our computer is a potato and can only perform discrete logarithm when the largest prime factor of \(p - 1\) is less than \(2^{32}\). What is the probability that a random integer less than \(X\) is \(2^{32}\)-smooth? As it turns out, this prolbem has been studied by Karl Dickman Apparently he was an actuary and only published one math paper , and the answer can be expressed in terms of the Dickman function \(\rho\). He proved that asymptotically, the proportion of numbers below \(X\) that are \(B\)-smooth tends to \(\rho\left(\frac{\log X}{\log B}\right)\), where \(\rho\) satisfies the delayed differential equation \(u\rho’(u) + \rho(u - 1) = 0\), with initial conditions \(\rho(u) = 1\) for \(0 \leq u \leq 1\). With this, we can recursively compute analytic functions \(\rho_n\) that matches with \(\rho\) on the interval \([n - 1, n]\). In our scenario, we want to compute the probability that an integer below \((p - 1) / X \sim 2^{276 - 120}\) is \(2^{32}\)-smooth. It can be approximated by \(\rho\left(\frac{156}{32}\right) \approx \frac{1}{2400}\). We can then use the Prime Number Theorem to approximate the probability that \((p - 1) / X\) is a prime, etc.
Thank you y011d4 for the discussion and nice challenge!
Update a year later
(29 Jan 2024) Surprising update! Me and Giacomo (jack) implemented a EllipticCurve_with_order
function into Sage. Once the PR is merged, it should also include a function EllipticCurve_with_trace
which will solve this problem easily.