Blog by grhkm

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:

  1. Generate a large smooth \(X\)
  2. Iterate through small \(D\)s
  3. For each \(D\), check if \(-3D^{-1}\) is a quadratic residue modulo \(4X\). If not, restart
  4. If so, we generate a random \(y\) such that \(y \equiv \sqrt{-3D^{-1}} \pmod{4X}\)
  5. We then solve for \(k\) and check whether \(p = kX + 1\) is prime. If not, restart
  6. If so, we compute the Hilbert class polynomial \(H_{-D}(X)\) and find its roots over \(p\)
  7. 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.