Legendre Symbol Oracle Breaks ECC

[kTimesG]

So many things.

Like, why are you saying that G is not arbitrarily chosen? It doesn't have any distinctive properties. Any point can be chosen as G, it would not change the group structure at all, nor its arithmetic.

Scalars are basically a counter relative to "hey, let's count from this element forward", so I don't see how one can ever define a decision tree that doesn't depend strictly on the chosen G.

Endomorphism and GLV are not attacks - they allow some arithmetic shortcuts, but then again, these are agnostic to whichever G is chosen.

In short, for whatever pair of points you choose, the "scalar" relationship between them can fly all over the 2**256 domain, because that relationship only exists because an arbitrary G was chosen. In fact, you can always find some G, such that any two arbitrary points are sequential, or doubles, or whatever. This says nothing about the ECDLP itself.

[rdenkye]

So many things.

Like, why are you saying that G is not arbitrarily chosen? It doesn't have any distinctive properties. Any point can be chosen as G, it would not change the group structure at all, nor its arithmetic.

Scalars are basically a counter relative to "hey, let's count from this element forward", so I don't see how one can ever define a decision tree that doesn't depend strictly on the chosen G.

Endomorphism and GLV are not attacks - they allow some arithmetic shortcuts, but then again, these are agnostic to whichever G is chosen.

In short, for whatever pair of points you choose, the "scalar" relationship between them can fly all over the 2**256 domain, because that relationship only exists because an arbitrary G was chosen. In fact, you can always find some G, such that any two arbitrary points are sequential, or doubles, or whatever. This says nothing about the ECDLP itself.

I can only solve it using the smallest x value. That's all it can explain for now.

[rdenkye]

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.

...

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

Next week when I drop the p=127 oracle, you'll probably say "curve-fitting, not cryptanalysis" again.
But in the meantime, no one will crack it
Come on everyone, let's have some fun!

[rdenkye]

I can only solve it using the smallest x value. That's all it can explain for now.

In curves where the standard base point is not the one with the smallest X coordinate;
We compute the target point using the point with the smallest X. Let's call it k1.
We compute the standard base point using the point with the smallest X. Let's call it k2.
By multiplying k1 by the inverse of k2, I calculate the point's scalar relative to the standard base point.

For Secp256k1;
G is used in the calculation:: (1,29896722852569046015560700294576055776214335159245303116488692907525646231534)
Standart G: (55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)

[gmaxwell]

the security relies on the fixed G and the hardness of ECDLP from that base.

This is just pure jibberish in a group without cofactor, as you can take a problem for from one base and transfer it to any other.  They're all secure or none are secure.

This whole thread is equivalent to saying that it's secure if you have an oracle that can tell you bits of the private key.  True, but not a useful fact. In fact that's what the Legendre symbol is, just getting obscured with terminology.  So it just all sounds like the raving of someone with an AI addiction.

If someone can compute non-trivial properties of the private key from their image in the group then almost all of them translates pretty directly into a break and only with special exception do they not (like being able to identify (-x)G==-(xG)).  But the thing to actually establish there in order to be interesting is the ability to do so on a real cryptographic group, not a toy insecure group.  The fact that being able to do so would translate into a break isn't news.

As an aside, if anyone gets any private offers from the account to sell you his solution please let me know--  scammers pretending cryptographic breakthroughs then ripping people off or giving people malware is a repetitive theme on this forum though these days the LLM delusional are more common.

[rdenkye]

the security relies on the fixed G and the hardness of ECDLP from that base.

This is just pure jibberish in a group without cofactor, as you can take a problem for from one base and transfer it to any other.  They're all secure or none are secure.

This whole thread is equivalent to saying that it's secure if you have an oracle that can tell you bits of the private key.  True, but not a useful fact. In fact that's what the Legendre symbol is, just getting obscured with terminology.  So it just all sounds like the raving of someone with an AI addiction.

If someone can compute non-trivial properties of the private key from their image in the group then almost all of them translates pretty directly into a break and only with special exception do they not (like being able to identify (-x)G==-(xG)).  But the thing to actually establish there in order to be interesting is the ability to do so on a real cryptographic group, not a toy insecure group.  The fact that being able to do so would translate into a break isn't news.

As an aside, if anyone gets any private offers from the account to sell you his solution please let me know--  scammers pretending cryptographic breakthroughs then ripping people off or giving people malware is a repetitive theme on this forum though these days the LLM delusional are more common.

Your warnings are very sensible and necessary. Nevertheless, I am quite disappointed.

[kTimesG]

For Secp256k1;
G is used in the calculation:: (1,29896722852569046015560700294576055776214335159245303116488692907525646231534)

Here's a target point with a 104-bit scalar (relative to your X=1 generator) on secp256k1.

Code:

x = 0xa07f435a9492de13f58845301a81e5544c2648acaf59c9ba6786783dec5ba433
y = 0xbec7ec664d064f084bab48f48019e00c51ebcee4d34d330b0cc54f01cb3cc0f2

Since you claim to break 130 bits in 1.2 seconds or so, I assume recovering the correct private key (relative to your special generator) should be done in nanoseconds or so.

I don't have any special need for you to tell me the key, since I know it already, so it's enough if you simply post the SHA256 of the correct private key.

[rdenkye]

For Secp256k1;
G is used in the calculation:: (1,29896722852569046015560700294576055776214335159245303116488692907525646231534)

Here's a target point with a 104-bit scalar (relative to your X=1 generator) on secp256k1.

Code:

x = 0xa07f435a9492de13f58845301a81e5544c2648acaf59c9ba6786783dec5ba433
y = 0xbec7ec664d064f084bab48f48019e00c51ebcee4d34d330b0cc54f01cb3cc0f2

Since you claim to break 130 bits in 1.2 seconds or so, I assume recovering the correct private key (relative to your special generator) should be done in nanoseconds or so.

I don't have any special need for you to tell me the key, since I know it already, so it's enough if you simply post the SHA256 of the correct private key.

I couldn't find the key. LLM was deceiving me, or they were saying "don't click on the link". The point wasn't really about proof, but I'm giving up anyway.

[JackMazzoni]

The Oracle only deals with the x coordinate which is already displayed not directly with the K. It is useless.

[rdenkye]

The Oracle only deals with the x coordinate which is already displayed not directly with the K. It is useless.

Yes. It doesn't work.

[ThewsyRum]

How do you propose generating this decision tree for secp256k1? To find the constants that correctly separate the points of this curve, you would need to "train" your tree with the data. But how do you train a model on a space of 2^256 points that you cannot enumerate? Can you generate this decision tree on a real curve without iterating over all the points? Because if you need to iterate to build the tree, your attack is slower than brute force.

You have simply created a rule that works only because the dataset is tiny enough to be manually classified. If a direct and simple correlation existed between the coordinates and the most significant bit of the scalar k that was independent of group size, wouldn't ECC have been broken decades ago? Why does this supposed correlation vanish into statistical noise the moment we move from toy curves to real ones?

[rdenkye]

How do you propose generating this decision tree for secp256k1? To find the constants that correctly separate the points of this curve, you would need to "train" your tree with the data. But how do you train a model on a space of 2^256 points that you cannot enumerate? Can you generate this decision tree on a real curve without iterating over all the points? Because if you need to iterate to build the tree, your attack is slower than brute force.

You have simply created a rule that works only because the dataset is tiny enough to be manually classified. If a direct and simple correlation existed between the coordinates and the most significant bit of the scalar k that was independent of group size, wouldn't ECC have been broken decades ago? Why does this supposed correlation vanish into statistical noise the moment we move from toy curves to real ones?

The tree was just one example.
It's impossible for me to go into detail right now, but I'll step up the pace over time.

Everyone seems convinced that the only way forward is for the x’s to collide like in Pollard's Kangaroo yet far fewer believe the x’s could simply sit down, talk it through, and resolve things without any collision at all. Let’s try to be a little more constructive.

Meanwhile, everyone is anxiously awaiting the quantum catastrophe from advancing Shor's algorithm. While we're all waiting for Shor... shall we say 'short from the x’s'?

[kTimesG]

far fewer believe the x’s could simply sit down, talk it through, and resolve things without any collision at all. Let’s try to be a little more constructive.

Probably because if that would be the case, it would break several proved theorems, like Fermat's or Lagrange's. The X values are simply element identifiers, or tags, or colors, they have zero correlation to any cycle reindexing, which is always relative.

[rdenkye]

far fewer believe the x’s could simply sit down, talk it through, and resolve things without any collision at all. Let’s try to be a little more constructive.

Probably because if that would be the case, it would break several proved theorems, like Fermat's or Lagrange's. The X values are simply element identifiers, or tags, or colors, they have zero correlation to any cycle reindexing, which is always relative.

If the coordinates were just labels, they wouldn't form a rectangle with their siblings and cousins, in my opinion.
Sibling points with the same y value  those sharing cube roots  their sum goes to the curve's order.
With symmetries, 6 points form a rectangle.
And as an unexplored possibility... could a special comparison between a point's position in the rectangle and its half-point's position in its own rectangle reveal another feature that goes beyond mere labeling?
I'm already upset with Fermat anyway, no problem.

[ActiveC]

This is not working on secp256k1. Do not waste time on this, it is useless.

Since the topic title like this is misleading, please change it!

[rdenkye]

On the secp256k1 field prime p, if you set a = 1, not every b value produces a valid elliptic curve. Some b values make the curve singular. Singular means the curve stops being a proper elliptic curve and becomes a degenerate shape; in that case, standard elliptic-curve operations like point addition are not reliable, and the group structure does not hold.

Therefore, when working with a = 1, you should detect and exclude the b values that make the curve singular beforehand. That is exactly what the code I shared does: it computes and lists the singular b values for a = 1 over the secp field (typically there are two, and they are negatives of each other modulo p).

Code:

#secp256k1 alanında (p) “singular” b değerlerini (Δ=0) tek satırda bulmak
#y² = x³ + x + b mod p için Δ=0 (singular) koşulundan b köklerini çıkarma (secp256k1 p)
#Elliptic curve singularity check: finding b such that 4a³+27b²≡0 (mod p) on secp256k1 field prime

from sympy import mod_inverse, sqrt_mod
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 1
target = -4 * pow(a, 3, p) * mod_inverse(27, p) % p
roots = sqrt_mod(target, p, all_roots=True)
print(roots)

Code:

[11842912595111486228085625214058158124919313799234703649739607102117954628595,
 103949176642204709195485359794629749728350670866405860389717976905790880043068]

11842912595111486228085625214058158124919313799234703649739607102117954628595, 103949176642204709195485359794629749728350670866405860389717976905790880043068

I couldn’t find these specific numbers anywhere, so I’m leaving a note here for future reference in some explanations I plan to write. I will also add the scalar values that cause the anomaly on the secp256k1 field prime p, i.e., the cases where p equals n. That will probably be a first as well.

[rdenkye]

This is not working on secp256k1. Do not waste time on this, it is useless.

Since the topic title like this is misleading, please change it!

Yes, I tried it too, it didn't work.