This challenge was unexpectedly hard.

We are given a remote server to connect to. Let’s see what it’s got for us.

[!] The ancient texts are being prepared...

You have entered the Grand Archives of Eldoria! The scholars shall test your wisdom. Answer their questions to prove your worth and claim the hidden knowledge.
You are given the sacred prime: p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061

[1] How many bits is the prime p? > 

Okay, so the first part is just asking us the bit length of this prime. This part is easy, we can construct a simple pwntools script to solve this.

from pwn import *

context.log_level = 'debug'

HOST = "94.237.58.253"
PORT = 35225

server = remote(HOST, PORT)

# This part is just taking the value of p sent to us
server.recvuntil(b'You are given the sacred prime: p = ')
p_line = server.recvline().strip().decode()

p = int(p_line) 

# <int>.bit_length() can give us the bit length. We just need to send this
bit = p.bit_length()

server.recvuntil(b'[1] How many bits is the prime p? > ')
server.sendline(str(bit).encode())

Okay, so that wasn’t that bad. Note that this question was always the same prime $p$. The next question asks a slightly more complex but still not too hard question.

[2] Enter the full factorization of the order of the multiplicative group in the finite field F_p in ascending order of factors (format: p0,e0_p1,e1_ ..., where pi are the distinct factors and ei the multiplicities of each factor) >

A little background information

• A finite field $\mathbb{F}_{p^n}$ where $p$ is prime is (very very simply) a field where all regular axioms of arithmetic apply, and has a finite amount of elements. This is because calculations are taken mod some number $p$.
• A multiplicative group is the set of all nonzero elements in the field $\mathbb{F}_p$. The order refers to the number of elements in this set. For example, if I had the finite field $\mathbb{F}_5 = [ 0,1,2,3,4 ] $, the multiplicative group is $[ 1,2,3,4 ]$, and the order is $4$.
• For most multiplicative groups over $\mathbb{F}_p$, the order is $p-1$.

In this case, the prime they gave us is very large, but we can find factors $p-1$ on FactorDB.

2121433434...60<116> = 2^2 · 5 · 635599 · 2533393 · 4122411947<10> · 175521834973<12> · 206740999513<12> · 1994957217983<13> · 215264178543783483824207<24> · 10254137552818335844980930258636403<35>

The question asks for them in a specific format, so let’s align it like that and then send it to the server.

# ... lines before ...

server.recvuntil(b'[2] Enter the full factorization of the order of the multiplicative group in the finite field F_p in ascending order of factors (format: p0,e0_p1,e1_ ..., where pi are the distinct factors and ei the multiplicities of each factor) > ')
answer = b'2,2_5,1_635599,1_2533393,1_4122411947,1_175521834973,1_206740999513,1_1994957217983,1_215264178543783483824207,1_10254137552818335844980930258636403,1'

server.sendline(answer)

Now onto question 3. Question 3 gives us a number of random numbers, and asks if the element is a generator of $\mathbb{F}_p$.

[3] For this question, you will have to send 1 if the element is a generator of the finite field F_p, otherwise 0.

Background information

• A generator of a field $\mathbb{F}_p$ is a number $g$ such that any number in the field $\mathbb{F}_p$ can be generated by raising $g$ to the power of some other number.
• You can check if an element is a generator by checking the order of the element $g$, which is defined as the smallest integer $k$ such that \[ g^k \equiv 1 \pmod{p} \]
• This can be thought of as “How many points can $g$ generate when it is raised to some power?”
• In this case, the order of the element $g$ should equal the order of the field $\mathbb{F}_p$, which we have found. SageMath has some tools built in for this, let’s use that.

# tests.py
from sage.all import *

p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061
test_g = 20631491223838476789119932403317136634575330973372563721464512446554469551621060375105239548965734742969957472879257

F = GF(p)
g = F(test_g)

ans = 0
if g.multiplicative_order() == p-1
    ans = 1

But there’s a problem. These questions are timed, maybe giving us only half a second at most to answer, and this is slow for large fields. We need a more efficient method. Since $p$ is the same every time, we can leverage this and precompute data. Turning to PARI/GP, we get all the unique divisors (not just the prime divisors) of $p-1$. This is because, there is another way to test if an element $g$ is a generator, by testing for all unique divisors $d$ that none of them satisfy this congruence: \[ g^d \equiv 1 \pmod{p} \] If any divisor $d$ satisfies this congruence (excluding $d = 1$ or $d = p-1$ for Fermat’s little theorem), then $g$ is not a generator. PARI/GP spewed out 90 kilobytes of divisors, which is a lot, but still faster than the sagemath method. So let’s construct the script for this part.

# The factors are too much to put in here. I import them from factors.py
from factors import Dlist

# Check for all g^d mod p that it does not equal 1
def check_g(g):
    ans = b"1"
    for i in Dlist:
        if pow(e, i, p) == 1:
            ans = b"0"
    return ans

# Question 3 asks for several unique points, so loop to capture all.
for i in range(17):
    e_line = server.recvuntil(b'? > ').strip().decode()[:-3]
    e = int(e_line)

    ans = check_g(e)
    server.sendline(ans)

That’s question 3 down. The next question asks about an elliptic curve defined with the given parameters:

The scholars present a sacred mathematical construct, a curve used to protect the most guarded secrets of the realm. Only those who understand its nature may proceed.
a = 408179155510362278173926919850986501979230710105776636663982077437889191180248733396157541580929479690947601351140
b = 8133402404274856939573884604662224089841681915139687661374894548183248327840533912259514444213329514848143976390134

[4] What is the order of the curve defined over F_p? >

Thankfully, this question also uses the same parameters $a$ and $b$ each time. So we can precompute this using sage.

# tests.py
from sage.all import *

p = 21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061

a = 408179155510362278173926919850986501979230710105776636663982077437889191180248733396157541580929479690947601351140
b = 8133402404274856939573884604662224089841681915139687661374894548183248327840533912259514444213329514848143976390134

F = GF(p)
C = EllipticCurve(F, [a,b])

print(C.cardinality()) # cardinality also refers to order

Interestingly, we see that the cardinality of this is equal to $p$ itself. We’ll come back to this little fact later. Let’s send this to the server.

ec_order = b"21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061"

server.recvuntil(b"[4] What is the order of the curve defined over F_p? > ")
server.sendline(ec_order)

Question 5 now asks about the order of the elliptic curve over the field extension $\mathbb{F}_{p^3}$, which is a finite field with $p^3$ elements.

[5] Enter the full factorization of the order of the elliptic curve defined over the finite field F_{p^3}. Follow the same format as in question 2 >

Background information

• There is a relationship between the order over the finite fields defined by $p$ and $p^3$.
• The order/cardinality over $\mathbb{F}_p$ is related to a special value known as the trace of Frobenius of the curve, via the equation: \[ O_C = p + 1 - t \]
• where $t$ is the trace, and $O_C$ is the order/cardinality of the curve.

So, for the curve over $\mathbb{F}_{p^3}$, the order can be found via the equation: \[ O_3 = p^3 + 1 - t_3 \] Note that $t_3 \neq t$ but it is related to it. That relationship is defined by this equation:

\[ t_3 = t(t^2 - 3p) \]

So from that, we can find the order of the curve over $\mathbb{F}_{p^3}$. Using FactorDB again, we can factorise it into its prime factors and send it to the server.

F_p3_order = b"2,2_7,2_21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061,1_2296163171090566549378609985715193912396821929882292947886890025295122370435191839352044293887595879123562797851002485690372901374381417938210071827839043175382685244226599901222328480132064138736290361668527861560801378793266019,1"
server.recvuntil(b'[5] Enter the full factorization of the order of the elliptic curve defined over the finite field F_{p^3}. Follow the same format as in question 2 > ')
server.sendline(F_p3_order)

Now for question 6, the hardest question. It gives us two $x$ coordinates corresponding to the famous $P = kG$ on the elliptic curve, and asks for the value of $k$. This may seem trivial, but scalar multiplication works differently on an elliptic curve and finding $k$ is very very hard.

But first, since we’re only given $x$, let’s find the actual points $P$ and $G$ instead of just their $x$. Elliptic curves must satisfy the congruence: \[ y^2 \equiv x^3 + ax + b \pmod{p} \]

So we can just solve for this congruence. Note that there will be 2 $y$ coordinates for most $x$ coordinates, however both will work.

# tests.py
from sage.all import *

def get_Y_affine(x):
    y_squared = (x**3 + a*x + b) % p
    R = Integers(p)
    return R(y_squared).sqrt(all=True) # We have to take the modular square root

testY = get_Y_affine(g_x)
pos_g = []

for i in testY:
    pos_g.append(C(g_x, i))

The given $g$ is always the same in this question. So we can precompute this no problem.

Finding k and anomalous elliptic curves

Remember that we saw the order of the curve over $\mathbb{F}_p$ was equal to $p$? That fact comes into play here. It turns out that this is a weakness in elliptic curves, and these types of curves are known as anomalous elliptic curves. I stumbled across this paper describing an attack called “Smart’s Attack” that specifically targets anomalous elliptic curves. Along with it is the included sage code for implementing it.

def HenselLift(P,p,prec):
    E = P.curve()
    Eq = E.change_ring(QQ)
    Ep = Eq.change_ring(Qp(p,prec))
    x_P,y_P = P.xy()

    x_lift = ZZ(x_P)
    y_lift = ZZ(y_P)

    x, y, a4, a6 = var('x,y,a4,a6')

    f(a4,a6,x,y) = y^2 - x^3 - a4*x - a6
    g(y) = f(ZZ(Eq.a4()),ZZ(Eq.a6()),ZZ(x_P),y)

    gDiff = g.diff()

    for i in range(1,prec):
        uInv = ZZ(gDiff(y=y_lift))
        u = uInv.inverse_mod(p^i)
        y_lift = y_lift - u*g(y_lift)
        y_lift = ZZ(Mod(y_lift,p^(i+1)))

    y_lift = y_lift+O(p^prec)
    return Ep([x_lift,y_lift])

def SmartAttack(P,Q,p,prec):
    E = P.curve()
    Eqq = E.change_ring(QQ)

    P_Qp = HenselLift(P,p,prec)
    Q_Qp = HenselLift(Q,p,prec)

    p_times_P = p*P_Qp
    p_times_Q=p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    k = Mod(k,p)
    return k

Let’s test this method on sage.

$ sage ecdlp.sage
# order of the EC
21214334341047589034959795830530169972304000967355896041112297190770972306665257150126981587914335537556050020788061

# ... our value of k?!
10581123324646794895523392501394046260808875735968273340546838386704131024005640419746651345597313555539325773053867

And this method, is actually very fast when you pass a small prec parameter (3, in this case). Fast enough to solve the challenge with the correct value of $k$. Sage converts all its code into python code, so we can very easily include this. We will want to prime the initialisation of the finite field and the elliptic curve before the main part of the script starts as they can be slow to initialise in sage for large $p$, but after that, finding $k$ for this curve is easy.

px = server.recvuntil(b'[6] What is the value of d? > ').strip().decode()
tL = px.split("\n")
px_i = int(tL[2][42:])
px_y = get_Y_affine(px_i)[0]

ans = SmartAttack(G, C(px_i, px_y), p, 3)

server.sendline(str(ans).encode())
server.interactive()

Flag: HTB{Welcome_to_CA_2k25!Here_is_your_anomalous_flag_for_this_challenge_and_good_luck_with_the_rest:)_1ee268743cea1302fa252f1d11fa331e}