Legendre Symbol Oracle Breaks ECC

[rdenkye]

Being able to determine whether the scalar corresponding to a point is less than half the order effectively breaks the curve. This is because the security of elliptic curve cryptography rests on the computational intractability of the elliptic curve discrete logarithm problem (ECDLP): given a point Q = k·G, recovering the scalar k is supposed to be infeasibly hard. If a mechanism such as a decision tree constructed from Legendre symbol evaluation can reliably predict, based solely on the coordinates of Q, whether k < n/2 (where n is the order of the group), then it functions as a “bit oracle” for the most significant bit of k. An attacker can exploit this oracle to perform a binary search: query whether k < n/2, restrict the search to the corresponding half of the keyspace, then query the midpoint of the new interval, and repeat. In only ⌈log₂(n)⌉ queries, the entire scalar k can be recovered, reducing the ECDLP from an exponentially hard problem to a polynomially solvable one.

Code:

#!pip install ecdsa

from ecdsa.ellipticcurve import CurveFp, Point

p = 79
a = 0
b = 7
n= 67
Gx = 1
Gy = 18
curve = CurveFp(p, a, b)
G = Point(curve, Gx, Gy)

p6= (p-1) // 6



def LS(p6):
    p6 %= p
    if p6 == 0:
        return 0
    return 1 if pow(p6, (p - 1) // 2, p) == 1 else -1

def in_first34(Q: Point):
    x = Q.x()
    y = Q.y()
    v = LS(y - x + (2*p6))
    if v == -1:
        v = LS(-(x + y))
        if v == -1:
            v = LS((p6+ p6//2) - x - y)
            if v == -1: return 0
            elif v == 0: return 1
            else: return 0
        elif v == 0:
            return 0
        else:
            v = LS(y - x + (3*p6))
            if v == -1:
                v = LS((p-4) - y)
                if v == -1: return 1
                elif v == 0: return 0
                else: return 0
            elif v == 0:
                return 1
            else:
                v = LS(((n+1)//2) - x - y)
                if v == -1: return 0
                elif v == 0: return 0
                else: return 1
    elif v == 0:
        return 1
    else:
        v = LS((p-1) - y)
        if v == -1:
            v = LS(y - x + ((n+1)//2+1))
            if v == -1: return 1
            elif v == 0: return 0
            else:
                v = LS(-(x + y))
                if v == -1: return 0
                elif v == 0: return 0
                else: return 1
        elif v == 0:
            return 0
        else:
            v = LS((p6+1) - x - y)
            if v == -1: return 0
            elif v == 0: return 1
            else: return 0

for k in range(1, n):
    Q = k * G  
    print(k, in_first34(Q))

Code:

1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 0
36 0
37 0
38 0
39 0
40 0
41 0
42 0
43 0
44 0
45 0
46 0
47 0
48 0
49 0
50 0
51 0
52 0
53 0
54 0
55 0
56 0
57 0
58 0
59 0
60 0
61 0
62 0
63 0
64 0
65 0
66 0

[rdenkye]

I've developed a version that works within secp256k1.

[digitalbear]

It doesn’t work for Puzzle 135 because it relies on correlations that only exist on very small toy curves. On secp256k1, even if the private key is known to be in the range 2^135, the points Q=k⋅G are statistically indistinguishable from points generated with any other subrange. The coordinates (x,y) don’t leak whether k is in the first half of an interval. If such a test existed, it would be a bit oracle and would already break ECDLP, which we know is not the case.

[rdenkye]

It doesn’t work for Puzzle 135 because it relies on correlations that only exist on very small toy curves. On secp256k1, even if the private key is known to be in the range 2^135, the points Q=k⋅G are statistically indistinguishable from points generated with any other subrange. The coordinates (x,y) don’t leak whether k is in the first half of an interval. If such a test existed, it would be a bit oracle and would already break ECDLP, which we know is not the case.

Do you think if this worked, the person who discovered it would use it for low-level and inexpensive tasks like solving puzzles?

[digitalbear]

The reward for solving Puzzle 135 is about one million dollars, so it’s definitely worth it and still much easier than a real 2²⁵⁶ key. By the way, have you had any luck using a real Bitcoin key over 120 bits?

[rdenkye]

The reward for solving Puzzle 135 is about one million dollars, so it’s definitely worth it and still much easier than a real 2²⁵⁶ key. By the way, have you had any luck using a real Bitcoin key over 120 bits?

"One million dollars" is a ridiculously small figure compared to the discovery we're talking about. That discovery is capable of solving a problem with a magnitude of 2 to the power of 256. The first thing someone with that capability would do is keep the discovery a secret or ensure no one is certain of its existence.

A point on a curve has 2 valid half-points.
The relevant technique allows finding the correct half. A key of size 2 to the power of 256 can be solved with this technique in 256 operations.
Therefore, if the code above is written for the secp256k1 curve, it is possible to find the private key from any public key in 1 second.

[digitalbear]

I agree with your point about the value of such a discovery — if it worked on real 2^256 keys, it would be far more valuable than any puzzle reward. I’m not arguing against the idea because I dislike it; on the contrary, I would love it to work. I just don’t see a plausible way for it to apply to real Bitcoin keys. Puzzle 135 is still a controlled setup with a keyspace of only 2^135, which is astronomically smaller than the full Bitcoin keyspace. That makes Puzzle 135 far easier to solve and allows you to claim the reward.

[NotATether]

I've developed a version that works within secp256k1.

Have you run this? What is the runtime - operations per second?

[rdenkye]

I've developed a version that works within secp256k1.

Have you run this? What is the runtime - operations per second?

✅ Completed in Step 128.

Calculation String:  ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( 3 * 2) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2) * 2  + 1) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2) * 2) * 2) * 2  + 1) * 2) * 2  + 1) * 2) * 2) * 2  + 1) * 2  + 1) * 2) * 2  + 1) * 2) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2) * 2) * 2) * 2  + 1) * 2) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2) * 2  + 1) * 2) * 2) * 2) * 2  + 1) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2) * 2  + 1) * 2) * 2) * 2) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2) * 2  + 1) * 2) * 2) * 2  + 1) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2) * 2  + 1) * 2  + 1) * 2) * 2) * 2) * 2) * 2) * 2) * 2) * 2  + 1) * 2  + 1) * 2  + 1) * 2  + 1) * 2) * 2) * 2  + 1) * 2) * 2) * 2  + 1)

Result:              ✅ 1103873984953507439627945351144005829577 ✅


puzzle 130, 1  second.

[digitalbear]

Have you tried Puzzle 135? If you can solve Puzzle 130 in just one second, Puzzle 135 should be easy too.

[rdenkye]

Have you tried Puzzle 135? If you can solve Puzzle 130 in just one second, Puzzle 135 should be easy too.

If I can assure you of this, my kidnapping won't take two days. It's essential that I appear to be a joker, as I mentioned above.

[Redni]

I ran an empirical test on your claim. Here are the results:

Your toy curve (p=79, n=67): 98.5% accuracy — impressive!

secp256k1 (actual Bitcoin curve): 49.0% accuracy — literally worse than a coin flip.

The problem is obvious: your decision tree was hand-crafted for that specific toy curve. The "magic numbers" (p6, thresholds, branch conditions) don't generalize — they're overfitted to p=79.

I also ran statistical analysis on Legendre symbol correlations:

Curve	L(y) correlation	L(x*y) correlation
Toy (p=79)	0.424	0.667
secp256k1	0.048	noise

On secp256k1, there's no statistically significant correlation between Legendre symbols of point coordinates and the position of k in the keyspace. The differences are within random noise (0.01-0.08 across thousands of samples).

This is expected. If such a correlation existed, it would be a fundamental weakness in the curve that would have been discovered decades ago by actual cryptographers.

Your "Puzzle 130 solved in 1 second" claim remains unverified. If you actually have a working oracle for secp256k1:
1. Post the code
2. Solve Puzzle 135 and claim the ~$1M reward
3. Or at minimum, provide a verifiable proof (signed message from a puzzle address)

Until then, this is just another "I broke Bitcoin but won't prove it" post.

[rdenkye]

I ran an empirical test on your claim. Here are the results:

Your toy curve (p=79, n=67): 98.5% accuracy — impressive!

secp256k1 (actual Bitcoin curve): 49.0% accuracy — literally worse than a coin flip.

The problem is obvious: your decision tree was hand-crafted for that specific toy curve. The "magic numbers" (p6, thresholds, branch conditions) don't generalize — they're overfitted to p=79.

I also ran statistical analysis on Legendre symbol correlations:

Curve	L(y) correlation	L(x*y) correlation
Toy (p=79)	0.424	0.667
secp256k1	0.048	noise

On secp256k1, there's no statistically significant correlation between Legendre symbols of point coordinates and the position of k in the keyspace. The differences are within random noise (0.01-0.08 across thousands of samples).

This is expected. If such a correlation existed, it would be a fundamental weakness in the curve that would have been discovered decades ago by actual cryptographers.

Your "Puzzle 130 solved in 1 second" claim remains unverified. If you actually have a working oracle for secp256k1:
1. Post the code
2. Solve Puzzle 135 and claim the ~$1M reward
3. Or at minimum, provide a verifiable proof (signed message from a puzzle address)

Until then, this is just another "I broke Bitcoin but won't prove it" post.

First of all, for the curve p=79, the ratio is 100.
And yes, I didn't solve it, it was a joke.
You're right

[rdenkye]

I ran an empirical test on your claim. Here are the results:

Your toy curve (p=79, n=67): 98.5% accuracy — impressive!

secp256k1 (actual Bitcoin curve): 49.0% accuracy — literally worse than a coin flip.

The problem is obvious: your decision tree was hand-crafted for that specific toy curve. The "magic numbers" (p6, thresholds, branch conditions) don't generalize — they're overfitted to p=79.

I also ran statistical analysis on Legendre symbol correlations:

Curve	L(y) correlation	L(x*y) correlation
Toy (p=79)	0.424	0.667
secp256k1	0.048	noise

On secp256k1, there's no statistically significant correlation between Legendre symbols of point coordinates and the position of k in the keyspace. The differences are within random noise (0.01-0.08 across thousands of samples).

This is expected. If such a correlation existed, it would be a fundamental weakness in the curve that would have been discovered decades ago by actual cryptographers.
But it should be as simple as what I write.

Your "Puzzle 130 solved in 1 second" claim remains unverified. If you actually have a working oracle for secp256k1:
1. Post the code
2. Solve Puzzle 135 and claim the ~$1M reward
3. Or at minimum, provide a verifiable proof (signed message from a puzzle address)

Until then, this is just another "I broke Bitcoin but won't prove it" post.

Okay, I'll issue a challenge. Since it's possible to do this for toy curves, try creating a 100% successful example for any curve greater than 79 (where a=0 and b=7) and where the order is prime?
But it should be as simple as what I write.

[Redni]

First of all, for the curve p=79, the ratio is 100.

You're right — I used threshold k <= 33 instead of k <= 34 (your function is called "in_first34" after all). My off-by-one error.

That said, 100% accuracy on a 67-point curve where you hand-crafted the decision tree by inspecting all cases is not impressive — it's enumeration disguised as an algorithm.

Okay, I'll issue a challenge. Since it's possible to do this for toy curves, try creating a 100% successful example for any curve greater than 79 (where a=0 and b=7) and where the order is prime?

That's not how burden of proof works. You claimed to have broken ECC. You need to demonstrate it scales.

But for reference: the next curve y² = x³ + 7 with prime order is p=127, n=127, G=(1,32). Go ahead and show us the oracle for that one.

The reason your p=79 oracle works is because with only 66 non-identity points, you can manually construct a decision tree that partitions them correctly. For p=127 you'd need a more complex tree. For secp256k1 (n ≈ 2²⁵⁶), it's computationally impossible to find such a tree — and there's no theoretical reason one should exist.

What would be convincing:
- Show the algorithm that generates these decision trees
- Demonstrate it on p=127, p=521, p=1279
- Explain the mathematical basis for why Legendre symbols would correlate with scalar position

Your p=79 result is curve-fitting, not cryptanalysis.

[rdenkye]

First of all, for the curve p=79, the ratio is 100.

You're right — I used threshold k <= 33 instead of k <= 34 (your function is called "in_first34" after all). My off-by-one error.

That said, 100% accuracy on a 67-point curve where you hand-crafted the decision tree by inspecting all cases is not impressive — it's enumeration disguised as an algorithm.

Okay, I'll issue a challenge. Since it's possible to do this for toy curves, try creating a 100% successful example for any curve greater than 79 (where a=0 and b=7) and where the order is prime?

That's not how burden of proof works. You claimed to have broken ECC. You need to demonstrate it scales.

But for reference: the next curve y² = x³ + 7 with prime order is p=127, n=127, G=(1,32). Go ahead and show us the oracle for that one.

The reason your p=79 oracle works is because with only 66 non-identity points, you can manually construct a decision tree that partitions them correctly. For p=127 you'd need a more complex tree. For secp256k1 (n ≈ 2²⁵⁶), it's computationally impossible to find such a tree — and there's no theoretical reason one should exist.

What would be convincing:
- Show the algorithm that generates these decision trees
- Demonstrate it on p=127, p=521, p=1279
- Explain the mathematical basis for why Legendre symbols would correlate with scalar position

Your p=79 result is curve-fitting, not cryptanalysis.

The claim that "there is no adaptive method for SECP256K1" is just an assumption. It's assumed to be so because no one has done it to date.
I asked about a new example curve before you did. I'll wait a while.
If no one can do it, I'll write it myself. First, let's see if anyone can do it, even if it's a toy curve.

[rdenkye]

Thanks for the comments. Yes, the curve I gave as an example is small and a toy curve I already stated that upfront. But I carefully read the criticisms, and there seems to be a misunderstanding: this attack is not in the same category as classical ECDLP solvers like Pollard Rho, baby-step giant-step, or known index calculus variants.

The oracle here is a decision tree derived from the quadratic residuosity properties (Legendre/Jacobi symbol) of the coordinates over the field. In small curves, this tree can be found via brute force because the group is small. But why should it be impossible in large curves?

Although secp256k1 itself was chosen with “rigid” design criteria, the x and y coordinates are still over a finite field and connected by a simple equation in Weierstrass form: y² = x³ + 7. The constants in this equation (a=0, b=7) and the special form of the prime p (defined as -2³²-977) can actually create hidden patterns in the quadratic characteristics.

Recall: works like Smart (1999) and Nguyen-Shparlinski (2000) showed that ECDLP can be weakened with auxiliary inputs. My observation is similar if we can find an algebraic predicate in the point coordinates that correlates with the MSB (which we did in the toy curve), it behaves like a variant of the hidden number problem and reduces the effective search space logarithmically.

I haven’t yet derived the full tree on the large curve (computational cost is high), but preliminary analyses indicate that some linear combinations (e.g., x + cy + d) show statistical bias in residuosity. This bias provides 100% separation in the small curve and could still be 50%+ε in the large curve which is enough (especially if combined with lattice reduction).

More details coming soon. Be patient.


I'm looking forward to seeing if someone can produce a similarly simple solution for a curve over p=127. If no one manages to do it within a week, I'll write it up myself.