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.


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.


I'm writing this as a collective response for everyone who has been asking me privately about the calculation in Puzzle 130.

https://prnt.sc/6bahidvXg0H6

The half of an odd number is equal to the half of (one less than it). 
The key in the image is odd, but its half is even. 
The notes written in the image will help you understand the logic of the calculation.

The true half of odd numbers lies “in the second half of the curve.” This is what tells us, at every step, whether the number we currently have is even or odd. And this calculation technique itself becomes the formula that reveals the final result.



[moderator's note: consecutive posts merged]

[kTimesG]

I feel like your 256-steps decision tree to break secp256k1 with your "Lagrange symbol bit oracle" will have around 115792089237316195423570985008687907852837564279074904382605163141518161494337 conditional branches, each with its own magic numbers.

But yeah, it will break ECDLP in only 256 steps. After all, it's a great way to classify all the atoms in the universe, but grouped by... chromodynamics properties of Bugs Bunny's carrots.

[rdenkye]

I feel like your 256-steps decision tree to break secp256k1 with your "Lagrange symbol bit oracle" will have around 115792089237316195423570985008687907852837564279074904382605163141518161494337 conditional branches, each with its own magic numbers.

But yeah, it will break ECDLP in only 256 steps. After all, it's a great way to classify all the atoms in the universe, but grouped by... chromodynamics properties of Bugs Bunny's carrots.

In the toy example (p=79, order 67), the successful tree had only ~10-15 nodes  not 67 leaves. The depth was logarithmic, and the branching factor was binary (Legendre symbol → +1/-1/0). The "magic numbers" aren't arbitrary; they're derived from the curve equation and field properties (e.g., coefficients that make certain expressions quadratic residues conditionally on k mod some power of 2).For larger curves, the hypothesis is that similar low-depth predicates exist because of the rigid structure of short Weierstrass forms with small coefficients (a=0, b=7 in both my toy curve and secp256k1  not a coincidence). Recent work on algebraic distinguishers (e.g., variants of the Cheon-type attacks or Granger-style endomorphism exploitation) and even ML-assisted bias hunting in side-channel literature shows that decision trees of depth ~256 with modest width can capture subtle correlations if the bias is systematic rather than random noise.

If the bias per level is even 0.51 (instead of 0.5), the expected search space reduction per query is >1 bit on average  enough to beat generic attacks over 256 iterated halvings. No need for universe-sized trees; just reusable, composable predicates.

[kTimesG]

Well, I counted 21 branches, not "6 or 7". Where's the logarithmic depth?

It's also logarithmic when you do a 256-bits lookup, that is, the ECDLP is solved in 256 logical steps.

secp256k1 is, AFAIK, a generic group, and the Lagrange stuff is useful to quickly determine whether a point is valid or not. What does it have to do with any scalars at all? Any kind of "scalar bias" that would leak any sort of data, would need to be directly correlated to the generator. Since any of the 2**256 points can be a generator, and since nothing would change in regards to the EC math, how on this Universe does any Lagrange equation have to do with the abstract notion of a "private key" anyway?

[rdenkye]

Well, I counted 21 branches, not "6 or 7". Where's the logarithmic depth?

It's also logarithmic when you do a 256-bits lookup, that is, the ECDLP is solved in 256 logical steps.

secp256k1 is, AFAIK, a generic group, and the Lagrange stuff is useful to quickly determine whether a point is valid or not. What does it have to do with any scalars at all? Any kind of "scalar bias" that would leak any sort of data, would need to be directly correlated to the generator. Since any of the 2**256 points can be a generator, and since nothing would change in regards to the EC math, how on this Universe does any Lagrange equation have to do with the abstract notion of a "private key" anyway?

Thanks for the detailed critique   solid points, and the branch count made me double-check the code. You're right, the toy example has more branches than ideal (around 21 in the expanded form), but that's expected for such a small group.The key is scale: in a group of order 67, a decision tree with depth ~5-6 (binary/ternary branching from Legendre +1/-1/0) is more than enough for perfect separation   it's logarithmic in the group order (log₃(67) ≈ 4, but with overfitting it's a bit bushier). The "magic numbers" are hand-tuned for that tiny field, where algebraic patterns dominate over pseudorandomness.On the logarithmic depth for larger curves: the hypothesis isn't a fixed 256-branch tree; it's iterative halving. Each oracle query reduces the search space by ~1 bit on average (if bias >0.5), leading to ~256 queries total for full recovery. No need for a precomputed 2²⁵⁶-leaf monster   the tree is composed on-the-fly or reused across iterations (adjust point by adding/subtracting midpoints).Regarding the generic group model and scalar correlation: you're absolutely correct that in the GGM, no such distinguisher exists by definition (black-box access only). But real curves like secp256k1 aren't pure black-box   they have explicit Weierstrass form with small coefficients (a=0, b=7), and the generator is fixed/rigid (not arbitrary). The coordinates are computed algebraically in F_p, so predicates like Legendre on linear combinations can potentially capture structural biases tied to the curve equation, not just random points.The generator dependence is subtle: while any point could be a generator in theory, the security relies on the fixed G and the hardness of ECDLP from that base. If there's a systematic residuosity pattern correlated with multiples of G (due to the rigid choice and small b), it could leak MSB info without violating generic assumptions in black-box   it's an algebraic distinguisher in the explicit representation. Similar ideas have been explored in works like Cheon (auxiliary inputs) or endomorphism-based attacks (GLV on secp256k1).No claim it's a full break yet   the toy is just proof-of-concept for small fields. I'm testing intermediate primes (p~2⁵⁰-2¹⁰⁰ range) to see how the bias scales. Early sampling shows non-random residuosity in certain predicates, but nothing dramatic.