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?