ECDSA Challenge Part 1 Writeup

Challenge Overview

• CTF: Pioneers25
• Challenge: PBTF 1
• Category: Cryptography
• Author: a_b
• Files: curves.py
• Connection info: nc 134.112.83.77 1003
• Description:

Introduction

This writeup details the solution to the first challenge in an elliptic-curve challenges series I solved during Pioneers25, which exploits weak curve parameters to forge an ECDSA signature for the message: LET ME IN !!!. In the first part, we demonstrate how a poorly chosen curve breaks the hardness assumption that ECDSA relies on, allowing full private key recovery from the public key alone. This writeup is beginner-friendly and explains everything in detail. We’ll start with how elliptic curves and ECDSA work, then walk through how I solved the challenge step by step.

Introduction to ECDSA

Before we can talk about what goes wrong, we need to understand how elliptic-curve signing is supposed to work.

What is an elliptic curve?

An elliptic curve is a set of points satisfying an equation of the form:

but we don’t work with real numbers. We work modulo a large prime \(p\) . This means every coordinate is an integer in the range \(\{0, 1, \ldots, p-1\}\) , and all arithmetic wraps around modulo \(p\) . For example, if \(p = 7\) , then \(6 + 3 = 2\) because \(9 \bmod 7 = 2\) . The resulting set of points, written \(E(\mathbb{F}_p)\) , forms a mathematical structure called a group: you can “add” any two points together and always get another point that also lies on the curve.

One special point acts like zero in this group. It’s called the point at infinity and written \(\mathcal{O}\) . Adding any point \(P\) to \(\mathcal{O}\) gives back \(P\) , just like adding zero to a number gives back that number.

What does “adding” two points mean?

Point addition on an elliptic curve is a geometric operation. To add two distinct points \(P\) and \(Q\) :

1. Draw the line through \(P\) and \(Q\) .
2. That line intersects the curve at exactly one more point.
3. Reflect that point across the x-axis.
4. The result is \(P + Q\) .

When you add a point \(P\) to itself (called point doubling), you use the tangent line at \(P\) instead. This might sound strange, but it has a clean algebraic formula that works entirely with modular arithmetic, so no actual geometry is needed in practice.

What is scalar multiplication?

If \(G\) is a point on the curve and \(d\) is a positive integer, then \(dG\) means “add \(G\) to itself \(d\) times”:

Doing this naively would be slow for large \(d\) , but an algorithm called double-and-add makes it fast. The idea is similar to fast exponentiation: instead of adding \(G\) one step at a time, you repeatedly double your current result and add \(G\) only when needed based on the binary representation of \(d\) . This means even if \(d\) is a 256-bit number, you only need around 256 doublings and additions, which is very fast.

Reversing scalar multiplication, however, is a completely different story. Given only \(G\) and \(Q = dG\) , figuring out \(d\) is believed to be computationally infeasible on a well-chosen curve. This one-way property is called the elliptic-curve discrete logarithm problem (ECDLP), and it is the security foundation of all elliptic-curve cryptography. The best known algorithms for solving it take around \(\sqrt{q}\) operations, where \(q\) is the number of points on the curve (we will define this precisely in a moment). For a 256-bit \(q\) that is roughly \(2^{128}\) steps, completely out of reach for any computer.

Key generation

A user picks:

• A curve \(E\) over \(\mathbb{F}_p\)
• A base point (generator) \(G\) with prime order \(q\) , meaning \(qG = \mathcal{O}\)
• A secret integer \(d\) drawn uniformly at random from \(\{1, \ldots, q-1\}\)

The private key is \(d\) . The public key is \(Q = dG\) . Because of the ECDLP, making \(Q\) public does not reveal \(d\) .

Signing a message

To sign a message \(m\) , the signer:

1. Computes a hash of the message: \(h = H(m)\) , treated as an integer. A hash function takes any input and produces a fixed-size output that looks random. Crucially, it is a one-way function: you cannot reverse it.
2. Picks a fresh random nonce \(k \in \{1, \ldots, q-1\}\) . This must be secret and never reused.
3. Computes \(R = kG\) and takes its x-coordinate: \(r = x(R) \bmod q\) .
4. Computes \(s = k^{-1}(h + dr) \bmod q\) .

The signature is the pair \((r, s)\) .

Verifying a signature

Given a message \(m\) , public key \(Q\) , and signature \((r, s)\) , anyone can verify:

1. Compute \(h = H(m)\) .
2. Compute \(u_1 = s^{-1} h \bmod q\) and \(u_2 = s^{-1} r \bmod q\) .
3. Compute \(P = u_1 G + u_2 Q\) .
4. Accept the signature if and only if \(x(P) \equiv r \pmod{q}\) .

This works because if \((r, s)\) was honestly generated, \(P\) will equal the original \(R = kG\) , so the x-coordinates match.

Why is \(k\) so important?

The nonce \(k\) must be:

• Truly random (not predictable)
• Never reused across two different signatures
• Never revealed

If an attacker learns \(k\) , they can immediately recover the private key from a single signature: \(d = r^{-1}(sk - h) \bmod q\) . If \(k\) is reused across two signatures on different messages, the same formula applies and the key leaks. This is the source of many real-world ECDSA breaks.

PS: this is not the vulnerability in this challenge.

What is the group order?

It is the number of points on the curve (including \(\mathcal{O}\) ) and it is written \(\#E(\mathbb{F}_p)\) . Intuitively, it tells you how “big” the group is. The order of the generator \(G\) is the smallest positive integer \(q\) such that \(qG = \mathcal{O}\) , i.e. the point that acts as zero. For the signature math to work correctly, \(q\) must be prime and large. Choosing a curve with the right order is a critical part of secure parameter generation, and as we are about to see, getting it wrong can be catastrophic.

Now that we have an idea of ECC and ECDSA, it is time to see what the challenge has for us.

Initial Analysis

curves.py

from fastecdsa.curve import Curve

h=0x1 #is'nt cofactor 1 vulnarable in the SafeCurve criteria ?
curves=[
    Curve(
    name='PBTF-256-1',
    p=0xc59769064089032aefe1d9b94a43964a34e5ed517cf3cafdbc0fecc47499c71d,
    a=0x23c8127aa083ad1faf1c4048b2784b88c7b6ba2919d3182f2d7db0af6a40e526,
    b=0x6adce1bc23bca037f4b8da91a4b90dabd1615e19781e629c559a8a01fa26e03c,
    gx=0x03a1084f405fc4da90f135131a4800eff322beddda8f0b464f0e38bf0296de3f,
    gy=0x092f8b74bf78af05e207c8e97e30a38ff960822776c0a189e0128f5d1eac7028,
    q=0xc59769064089032aefe1d9b94a43964a366b4bc207b059e6bb393611decba301

),

    Curve(
    name='PBTF-256-2',
    p=0xdde6820f1b72450f12028b08ec08f5e562347594eb6977fc9bda410a5c144277,
    a=0x1895567ca66d68190822a55af4fa309973b0248b7bc50b2bfe22a0e029a71b5f,
    b=0x496f5c40e438f96ed7bb042f2ddfc93a638713f0693551d97cd3dbf4b8a191ce,
    gx=0x123ef25e3587dd03263ebe242e7e9fb18117677177c098e0894747d763d7f2e5,
    gy=0xaca50518613ce3c3965282cabdae9124f77ca4fe03264ad85692f80a56b1f57c,
    q=0xdde6820f1b72450f12028b08ec08f5e496cf9700198a0cd1a16aa884951db29d
),

    Curve(
    name='PBTF-256-3',
    p= 0x86c8eb8c323ef2868e6c871ce5fd1dbbbc2d5e60f69bc119dae00c0cbb98a3a3,
    a= 0x3ec86a0ce99fa52c7c3e6861de2cd6b0226275df8cd415f69642a0df02c82ef6,
    b=0x39956bc1bac07a7f40dc7e2d965738cf3f816c83ec2cda7dbd53f93683198f50,
    gx=0x3889867e5f0e5115d3fa2560365a000a8da388d77423339f38b6918b1fa6042a,
    gy=0x1d7d575b94cb87bf093c960ae4b95ff35a74077655d99e917334cd6265277a77,
    q=0x86c8eb8c323ef2868e6c871ce5fd1dbbbc2d5e60f69bc119dae00c0cbb98a3a3
),
    Curve(
    name='PBTF-256-4',
    p=0xbe9f01af5bdd5c819ea66455194b6cd95279bd21c4114c4a4cb584a994a25ce3,
    a=0x91dd4d17195921550622b5b19ffbebb166b11bdb1b203f95af14e1d2ff0cfe08,
    b=0x51f3a44632e2c99499cbc131cc15cb09dc1deaadade9eb857c77faf2cf789fef,
    gx=0x5059b2f77e8f9d6ad91e1590d08f0b7cc3d6fa5c182935ca112016acc9548c94,
    gy=0xb877a60ca722b3fbccf7f89b513e638d073a0749c004da97fa9e24a2605cc2d0,
    q=0xbe9f01af5bdd5c819ea66455194b6cd95279bd21c4114c4a4cb584a994a25ce3
),
    Curve(
    name='PBTF-256-5',
    p=0x89445f52a5e032acb3eb9acce5502976e7d61632181ecdaf47b61d357b841e07,
    a=0x5b87a9cc9693290ea27c604b569e89468ab3a76edff8c47d8afd5653775a2574,
    b=0x26956ff572c7f56293a76fe4746b4a8f8b474e7ddc4e8380905212ed0f215e65,
    gx=0x1829e68c94865b3013a040574233acd2ecf1abdd9cfdc3dbfda0fad131df56af,
    gy=0x5377dfa1e78352d4191e8526bb3354747612e8a837c9d3a3230d3640421b69ed,
    q=0x89445f52a5e032acb3eb9acce5502976e7d61632181ecdaf47b61d357b841e07
)
]

The first thing we should check is curves.py. The important field there is q, the subgroup order:

Curve(
    name='PBTF-256-3',
    ...
    q=0x86c8eb8c323ef2868e6c871ce5fd1dbbbc2d5e60f69bc119dae00c0cbb98a3a3
),
Curve(
    name='PBTF-256-4',
    ...
    q=0xbe9f01af5bdd5c819ea66455194b6cd95279bd21c4114c4a4cb584a994a25ce3
),
Curve(
    name='PBTF-256-5',
    ...
    q=0x89445f52a5e032acb3eb9acce5502976e7d61632181ecdaf47b61d357b841e07
)

Comparing \(p\) and \(q\) for each curve gives:

• PBTF-256-1: \(q\) =/= \(p\)
• PBTF-256-2: \(q\) =/= \(p\)
• PBTF-256-3: \(q = p\)
• PBTF-256-4: \(q = p\)
• PBTF-256-5: \(q = p\)

That is the key observation: \(q = p\) . Curves 3, 4, and 5 are called anomalous curves, and this single property makes the ECDLP trivially solvable through an attack called Smart’s Attack.

Why are anomalous curves vulnerable?

An anomalous curve is a curve where \(\#E(\mathbb{F}_p) = p\) , meaning the number of points on the curve equals the prime \(p\) that defines the field. To understand why this is dangerous, recall that the security of ECDSA rests entirely on the ECDLP being hard. Smart’s attack exploits this special condition to reduce the ECDLP from a problem that would take \(2^{128}\) operations down to one that takes a fraction of a second.

The easiest way to think about it is to move from arithmetic modulo \(p\) to arithmetic modulo \(p^2\) . Over the original field \(\mathbb{F}_p\) , multiplying a point by the group order sends it to the point at infinity. So for an anomalous curve, we have:

But if we lift the same curve and the same point to \(\mathbb{Z}/p^2\mathbb{Z}\) , that cancellation is no longer exact. After lifting, \(p\tilde{G}\) is no longer the point at infinity. Instead, it lands very close to it, and that “small displacement” carries exactly the information we need.

The useful quantity here is the local parameter

evaluated modulo \(p^2\) . For the lifted points that appear in Smart’s attack, this value is always divisible by \(p\) , so it makes sense to divide by \(p\) and reduce modulo \(p\) :

This turns the elliptic-curve problem into a linear one. If \(Q = dG\) , then after lifting both points and multiplying by \(p\) , the corresponding values satisfy:

and that immediately gives:

So the discrete logarithm problem disappears and is replaced by one modular division. That is the whole reason anomalous curves are fatal.

For more details on Smart’s attack, check this paper

When connecting to the server, we get:

ncat $HOST $PORT
Identify yourself
> user
================================================================
    1-validate signature
    2-sign message
    3-curve info
    4-exit
================================================================

Choose an option:
>

Let’s try all 3 options and see what each does:

ncat $HOST $PORT
Identify yourself
> user
================================================================
    1-validate signature
    2-sign message
    3-curve info
    4-exit
================================================================

Choose an option:
> 1
r: 1
s: 1
Invalid signature!

Choose an option:
> 2
Provide the message to sign
> hello
Signature: (48121098683168411806888558148637554960283630459890929921946415149302409868807,30937089947738027606950137834210106716920386949931266477617445161555566212169)

Choose an option:
> 3
================================================================
Curve information:
- Name: PBTF-256-3
- Order: 60964916813188911719218621398134394471623745199485664185571910768334825104291
- Coefficients: 28397497958353750939575473210618173122376880519161075535184786725337131658998, 26045836291694244067112893411177059392294307128923990587509249096842340831056
- public key: 14185378144083796235680084563946135137280959929309143504625222096158084016635, 29313123839220856809039710511499747751570873447593360592831336223354639807138
================================================================


Choose an option:
>

So it is clear what each option does:

• 1 asks us to provide r and s, and it checks whether they sign the target message LET ME IN !!!
• 2 signs any message for us, except LET ME IN !!!
• 3 gives curve information, and we can notice that it uses one of the curves from curves.py each time we connect to the server

At this point the challenge flow became clear:

1. Connect and inspect the curve name.
2. Ignore non-anomalous sessions and keep trying until the connection uses an anomalous curve.
3. Recover the private key on anomalous sessions.
4. Forge a valid ECDSA signature.

Exploitation

Now that the weak point is identified, the rest is mostly about turning the math into a clean attack.

The nice thing about this challenge is that the server gives almost everything needed:

• the curve name
• the curve coefficients
• the group order
• the public key

So once the session uses an anomalous curve, the rest is just turning Smart’s attack into code and recovering the key.

Step 1: Wait for an anomalous curve

The first step is to keep connecting the server till we get an anomalous curve.

Since only curves 3, 4, and 5 satisfy \(q = p\) , only those sessions are useful. If the server happens to start on PBTF-256-1 or PBTF-256-2, there is nothing interesting to do there, so the right move is simply to reconnect until one of the anomalous curves appears.

Locally, it is convenient to keep a copy of the challenge parameters:

CURVES = {
    "PBTF-256-1": {...},
    "PBTF-256-2": {...},
    "PBTF-256-3": {...},
    "PBTF-256-4": {...},
    "PBTF-256-5": {...},
}

ANOMALOUS = {"PBTF-256-3", "PBTF-256-4", "PBTF-256-5"}

Then the current curve information can be requested from the service:

def get_curve_info(io):
    io.sendline(b"3")
    output = io.recvuntil((b"Choose an option",)).decode("utf-8", "replace")
    name = re.search(r"Name: ([^\n]+)", output).group(1).strip()
    public_x, public_y = map(int, re.search(r"public key: (\d+), (\d+)", output).groups())
    return name, public_x, public_y

If the current curve is not one of the vulnerable ones, there is no point continuing with that connection:

if curve_name not in ANOMALOUS:
    io.close()
    continue

Step 2: Rebuild the curve locally

Once a vulnerable curve appears, the next step is to reconstruct it locally in Sage:

field = GF(prime)
curve = EllipticCurve(field, [params["a"], params["b"]])
generator = curve((params["gx"], params["gy"]))
public_key = curve((public_x, public_y))

At this point:

• curve is the elliptic curve over \(\mathbb{F}_p\)
• generator is the base point \(G\)
• public_key is the server’s point \(Q = dG\)

So the target is now explicit: recover \(d\) from the relation

On a secure curve this would be infeasible. On an anomalous curve, however, the problem can be lifted to arithmetic modulo \(p^2\) and solved directly.

Step 3: Lift the curve and the points modulo \(p^2\)

The next step is to move from the original curve over \(\mathbb{F}_p\) to the same curve over \(\mathbb{Z}/p^2\mathbb{Z}\) :

modulus = prime * prime
curve_p2 = EllipticCurve(Integers(modulus), [params["a"], params["b"]])

The idea is simple: keep the same curve equation, but let the arithmetic happen modulo \(p^2\) instead of modulo \(p\) .

After that, the points themselves also need to be lifted:

So if the original point is \((x, y)\) modulo \(p\) , the lifted point has the form

for a carefully chosen correction term \(k\) .

def lift_y_square(x_value, y_value, a_value, b_value, prime):
    delta = ((x_value**3 + a_value * x_value + b_value - y_value**2) // prime) % prime
    correction = (delta * inverse_mod(2 * y_value, prime)) % prime
    return y_value + correction * prime

def lift_point_mod_p2(curve_p2, point, a_value, b_value, prime):
    x_value = ZZ(point[0])
    y_value = ZZ(point[1])
    lifted_y = lift_y_square(x_value, y_value, a_value, b_value, prime)
    return curve_p2(x_value, lifted_y)

Step 4: Apply Smart’s attack

Once both the generator and the public key are lifted modulo \(p^2\) , Smart’s attack becomes very short:

prime_generator = prime * generator_p2
prime_public = prime * public_p2
phi_generator = formal_log_mod_p(prime_generator, prime)
phi_public = formal_log_mod_p(prime_public, prime)
private_key = ZZ(mod(phi_public / phi_generator, prime))

This is essentially the whole attack, we could have used any exploits online but what is better than writing our own exploits.

The exploit matches the theory from the previous section:

1. Multiply the lifted points by \(p\) .
2. Compute the local parameter \(t(P) = -x(P)/y(P)\) modulo \(p^2\) .
3. Divide by \(p\) to obtain \(\phi(P)\) modulo \(p\) .
4. Solve for \(d\) using

Notice how there is no huge brute force and no expensive discrete-log attack. The problem collapses into a single modular division.

That is why anomalous curves are so dangerous: the whole hardness assumption collapses.

Step 5: Make sure the local model matches the server

Recovering a candidate private key is not enough by itself. The main subtle point here is the message hash. I got some errors at first but then I realised that only the first 8 bytes of SHA-256 are used. So I used this function to hash a message:

def hash_message(message):
    return ZZ(int.from_bytes(hashlib.sha256(message).digest()[:8], "big"))

To find out if 8 bytes is the correct one we can ask the oracle to sign a harmless message:

CHECK_MESSAGE = b"hello"

and then recover the nonce from the signature equation:

nonce = ((digest + private_key * r_value) * inverse_mod(s_value, order)) % order
return nonce != 0 and int((nonce * generator)[0]) % order == r_value

This is a very clean sanity check. If the recovered private key is correct and the hash convention matches the server, then recomputing kG from the derived nonce must give back the same r.

If this check fails, then something in the reconstruction is wrong and there is no reason to trust the forged signature yet.

Step 6: Forge the target signature

Once the private key is recovered and the model is validated, forging the final signature is just ordinary ECDSA:

def sign_message(message, private_key, generator, order):
    digest = hash_message(message)
    while True:
        nonce = ZZ(secrets.randbelow(order - 1) + 1)
        point = nonce * generator
        r_value = ZZ(point[0]) % order
        if r_value == 0:
            continue
        s_value = (inverse_mod(nonce, order) * (digest + private_key * r_value)) % order
        if s_value == 0:
            continue
        return int(r_value), int(s_value)

This is standard ECDSA signing. At this point the secret key is already known, so the target message can be signed like any legitimate signer would.

Step 7: Submit the signature

At that point, the last step is simply:

result = submit_signature(io, signature)

If everything lines up, the service accepts the forged signature and returns the flag.

Full Exploit Strategy

Putting everything together, the full strategy is:

1. Connect to the server.
2. Ask for the curve information and the public key.
3. If the curve is not anomalous, reconnect.
4. Reconstruct the curve locally in Sage.
5. Lift the curve and points modulo \(p^2\) .
6. Apply Smart’s attack to recover the private key.
7. Ask for a harmless signature to validate the recovered key and hash convention.
8. Forge a signature for LET ME IN !!!.
9. Verify it locally.
10. Submit it and recover the flag.

What makes this challenge satisfying is that once the anomalous curves are spotted, the rest is no longer guesswork. The weakness points directly to the right attack.

Full Solve Script

#!/usr/bin/env -S sage -python
import hashlib
import logging
import re
import secrets

from pwn import context, remote
from sage.all import EllipticCurve, GF, Integers, ZZ, inverse_mod, mod


HOST = "134.112.83.77"
PORT = 1003
TARGET = b"LET ME IN !!!"
CHECK_MESSAGE = b"hello"

context.log_level = "error"
logging.getLogger("pwnlib").setLevel(logging.ERROR)

CURVES = {
    "PBTF-256-1": {
        "p": 0xC59769064089032AEFE1D9B94A43964A34E5ED517CF3CAFDBC0FECC47499C71D,
        "a": 0x23C8127AA083AD1FAF1C4048B2784B88C7B6BA2919D3182F2D7DB0AF6A40E526,
        "b": 0x6ADCE1BC23BCA037F4B8DA91A4B90DABD1615E19781E629C559A8A01FA26E03C,
        "gx": 0x03A1084F405FC4DA90F135131A4800EFF322BEDDDA8F0B464F0E38BF0296DE3F,
        "gy": 0x092F8B74BF78AF05E207C8E97E30A38FF960822776C0A189E0128F5D1EAC7028,
        "q": 0xC59769064089032AEFE1D9B94A43964A366B4BC207B059E6BB393611DECBA301,
    },
    "PBTF-256-2": {
        "p": 0xDDE6820F1B72450F12028B08EC08F5E562347594EB6977FC9BDA410A5C144277,
        "a": 0x1895567CA66D68190822A55AF4FA309973B0248B7BC50B2BFE22A0E029A71B5F,
        "b": 0x496F5C40E438F96ED7BB042F2DDFC93A638713F0693551D97CD3DBF4B8A191CE,
        "gx": 0x123EF25E3587DD03263EBE242E7E9FB18117677177C098E0894747D763D7F2E5,
        "gy": 0xACA50518613CE3C3965282CABDAE9124F77CA4FE03264AD85692F80A56B1F57C,
        "q": 0xDDE6820F1B72450F12028B08EC08F5E496CF9700198A0CD1A16AA884951DB29D,
    },
    "PBTF-256-3": {
        "p": 0x86C8EB8C323EF2868E6C871CE5FD1DBBBC2D5E60F69BC119DAE00C0CBB98A3A3,
        "a": 0x3EC86A0CE99FA52C7C3E6861DE2CD6B0226275DF8CD415F69642A0DF02C82EF6,
        "b": 0x39956BC1BAC07A7F40DC7E2D965738CF3F816C83EC2CDA7DBD53F93683198F50,
        "gx": 0x3889867E5F0E5115D3FA2560365A000A8DA388D77423339F38B6918B1FA6042A,
        "gy": 0x1D7D575B94CB87BF093C960AE4B95FF35A74077655D99E917334CD6265277A77,
        "q": 0x86C8EB8C323EF2868E6C871CE5FD1DBBBC2D5E60F69BC119DAE00C0CBB98A3A3,
    },
    "PBTF-256-4": {
        "p": 0xBE9F01AF5BDD5C819EA66455194B6CD95279BD21C4114C4A4CB584A994A25CE3,
        "a": 0x91DD4D17195921550622B5B19FFBEBB166B11BDB1B203F95AF14E1D2FF0CFE08,
        "b": 0x51F3A44632E2C99499CBC131CC15CB09DC1DEAADADE9EB857C77FAF2CF789FEF,
        "gx": 0x5059B2F77E8F9D6AD91E1590D08F0B7CC3D6FA5C182935CA112016ACC9548C94,
        "gy": 0xB877A60CA722B3FBCCF7F89B513E638D073A0749C004DA97FA9E24A2605CC2D0,
        "q": 0xBE9F01AF5BDD5C819EA66455194B6CD95279BD21C4114C4A4CB584A994A25CE3,
    },
    "PBTF-256-5": {
        "p": 0x89445F52A5E032ACB3EB9ACCE5502976E7D61632181ECDAF47B61D357B841E07,
        "a": 0x5B87A9CC9693290EA27C604B569E89468AB3A76EDFF8C47D8AFD5653775A2574,
        "b": 0x26956FF572C7F56293A76FE4746B4A8F8B474E7DDC4E8380905212ED0F215E65,
        "gx": 0x1829E68C94865B3013A040574233ACD2ECF1ABDD9CFDC3DBFDA0FAD131DF56AF,
        "gy": 0x5377DFA1E78352D4191E8526BB3354747612E8A837C9D3A3230D3640421B69ED,
        "q": 0x89445F52A5E032ACB3EB9ACCE5502976E7D61632181ECDAF47B61D357B841E07,
    },
}

ANOMALOUS = {"PBTF-256-3", "PBTF-256-4", "PBTF-256-5"}


def lift_y_square(x_value, y_value, a_value, b_value, prime):
    delta = ((x_value**3 + a_value * x_value + b_value - y_value**2) // prime) % prime
    correction = (delta * inverse_mod(2 * y_value, prime)) % prime
    return y_value + correction * prime


def lift_point_mod_p2(curve_p2, point, a_value, b_value, prime):
    x_value = ZZ(point[0])
    y_value = ZZ(point[1])
    lifted_y = lift_y_square(x_value, y_value, a_value, b_value, prime)
    return curve_p2(x_value, lifted_y)


def formal_log_mod_p(point, prime):
    modulus = prime * prime
    x_value = ZZ(point[0])
    y_value = ZZ(point[1])
    t_value = (-x_value * inverse_mod(y_value, modulus)) % modulus
    return ZZ((t_value // prime) % prime)


def smart_attack(params, public_x, public_y):
    prime = params["p"]
    field = GF(prime)
    curve = EllipticCurve(field, [params["a"], params["b"]])
    generator = curve((params["gx"], params["gy"]))
    public_key = curve((public_x, public_y))

    # Work modulo p^2, which is enough to recover the formal-group coordinate.
    modulus = prime * prime
    curve_p2 = EllipticCurve(Integers(modulus), [params["a"], params["b"]])
    generator_p2 = lift_point_mod_p2(curve_p2, generator, params["a"], params["b"], prime)
    public_p2 = lift_point_mod_p2(curve_p2, public_key, params["a"], params["b"], prime)

    prime_generator = prime * generator_p2
    prime_public = prime * public_p2
    phi_generator = formal_log_mod_p(prime_generator, prime)
    phi_public = formal_log_mod_p(prime_public, prime)
    private_key = ZZ(mod(phi_public / phi_generator, prime))

    return curve, generator, public_key, private_key


def hash_message(message):
    return ZZ(int.from_bytes(hashlib.sha256(message).digest()[:8], "big"))


def sign_message(message, private_key, generator, order):
    digest = hash_message(message)
    while True:
        nonce = ZZ(secrets.randbelow(order - 1) + 1)
        point = nonce * generator
        r_value = ZZ(point[0]) % order
        if r_value == 0:
            continue
        s_value = (inverse_mod(nonce, order) * (digest + private_key * r_value)) % order
        if s_value == 0:
            continue
        return int(r_value), int(s_value)

def connect():
    io = remote(HOST, PORT)
    io.recvuntil(b">")
    io.sendline(b"solver")
    io.recvuntil(b">")
    return io


def get_curve_info(io):
    io.sendline(b"3")
    output = io.recvuntil((b"Choose an option",)).decode("utf-8", "replace")
    name = re.search(r"Name: ([^\n]+)", output).group(1).strip()
    public_x, public_y = map(int, re.search(r"public key: (\d+), (\d+)", output).groups())
    return name, public_x, public_y


def submit_signature(io, signature):
    r_value, s_value = signature
    io.sendline(b"1")
    io.recvuntil(b"r:")
    io.sendline(f"{r_value}".encode())
    io.recvuntil(b"s:")
    io.sendline(f"{s_value}".encode())
    return io.recvuntil((b"}", b"Choose an option")).decode("utf-8", "replace")


def main():
    attempt = 0
    while True:
        attempt += 1
        io = connect()
        try:
            curve_name, public_x, public_y = get_curve_info(io)
            print(f"[attempt {attempt}] curve: {curve_name}", flush=True)
            if curve_name not in ANOMALOUS:
                io.close()
                continue

            params = CURVES[curve_name]
            curve, generator, public_key, private_key = smart_attack(params, public_x, public_y)
            order = params["q"]

            signature = sign_message(TARGET, private_key, generator, order)
            result = submit_signature(io, signature)
            print(result, flush=True)

            flag_match = re.search(r"Pioneers25\{[^}]+\}", result)
            if flag_match:
                print(flag_match.group(0), flush=True)
                return

            print("signature rejected, retrying", flush=True)
        finally:
            io.close()


main()

Running the solver gives output like:

[attempt 1] curve: PBTF-256-2
[attempt 2] curve: PBTF-256-3
 Valid signature!
Welcome  solver
Here is your flag: Pioneers25{g3771ng_5m4r73r_3v3ry_d4y}
Pioneers25{g3771ng_5m4r73r_3v3ry_d4y}

So the flag is:

Pioneers25{g3771ng_5m4r73r_3v3ry_d4y}

I hope this was fun and you enjoyed the writeup, now time to see you in the part 2 of this series.

References

• The Discrete Logarithm Problem on Elliptic Curves of Trace One