Reducing the Search Space in Bitcoin ECDLP Puzzles Using Public Key Shifting

Bitcoin public key puzzles present a fascinating challenge based on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP). As the puzzle index increases, the private key is chosen from exponentially larger ranges, making brute-force approaches infeasible for higher-numbered puzzles like puzzle #135.

The Problem

In Bitcoin puzzle #135, the private key is known to lie within the range:

2^134 ≤ k < 2^135

This results in a total keyspace of 2¹³⁴ possibilities — far too large to search exhaustively with current hardware.

Proposed Strategy: Public Key Shifting

This article introduces a strategy to reduce the effective keyspace by shifting the public key and transforming the private key range to a smaller, symmetric range centered around zero. This method is based entirely on mathematical properties of elliptic curves.

Step 1: Represent the Key with an Offset

Let’s express the private key k as:

k = 0x400000000000000000000000000000000 + x

Here, x ranges from 1 to 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF. Thus, the public key becomes:

P = k·G = (offset + x)·G = offset·G + x·G

Subtracting the offset component from the target public key P gives:

P' = P - offset·G = x·G

Step 2: Reduce the Upper Bound Further

To reduce the range further, we shift again by half of the subrange:

midpoint = 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF / 2

So now:

P'' = P' - midpoint·G = (x - midpoint)·G

Now the search range becomes symmetric around zero:

−midpoint ≤ x − midpoint ≤ +midpoint

Which means we only need to brute-force values of x from 1 to midpoint, reducing the effective search space to 2¹³².

Why This Helps

• The original space of 2¹³⁴ keys is reduced to 2¹³² keys — a 75% reduction in brute-force workload.
• We can apply efficient search techniques like m-ary exponentiation, precomputed tables, or point compression filtering.
• The symmetric range opens up potential optimizations such as exploiting negation symmetry (e.g., if −kG = P'', then kG = −P'').

Implementation Sketch

Assuming you have access to scalar multiplication and point addition/subtraction over secp256k1, the steps are:

offset = 0x400000000000000000000000000000000
midpoint = 0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

P = point_from_pubkey("02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16")
P1 = point_subtract(P, scalar_multiplication(G, offset))
P2 = point_subtract(P1, scalar_multiplication(G, midpoint))

for x in range(1, midpoint):
    if scalar_multiplication(G, x) == P2:
        private_key = offset + midpoint + x
        print("FOUND:", hex(private_key))
  

Limitations and Next Steps

Even with this optimization, 2¹³² is still a massive search space. This technique becomes more powerful when combined with:

• Low Hamming Weight Key Search: Target only private keys with very few 1-bits
• Linear key structure search: Try k = a·2^64 + b·2^32 + c with small values
• x-coordinate filtering: Only compute for points whose x starts with the same byte(s) as the target

Conclusion

This shifting technique reduces the Bitcoin puzzle’s search space by a factor of 4. It is mathematically correct and can be implemented easily in any EC-aware toolchain. While not enough to crack puzzle #135 alone, this method is a solid foundation for more advanced, layered attacks.

If you're working on Bitcoin puzzles or other ECDLP challenges, give this approach a try — or help refine it further.