In what ways might a basepoint be compromised?

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: ? on December 31, 2024, 01:56:32 AM

This is a quote I found in this forum from gmaxwell

Quote

Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin.

I couldn't find much literature on this so I asked chatGPT which explained to me (quite possibly incorrectly) that:

Under normal circumstances d * G = Q (where d is the private key, G is the basepoint, Q is the public key, '*' represents scalar multiplication.) But if you were aware of a deeper relationship, by design or otherwise, where s * H = G (s is a scalar in the range of 2-N, H is a valid point on the curve) This would allow you to solve any private key in the system instantly, no ECDLP required, because you can substitute in d * (s*H) = G and solve it algebraically.

So can someone tell me if this is correct or incorrect?

I have struggled for days trying to understand this. If someone could let me know, maybe even make a python example that uses an example basepoint with a hidden relationship to demonstrate how it would work. That would mean a lot to me and anyone else interested in the same thing.

Regardless of whether or not SECP256k1's basepoint was chosen with a hidden relationship in mind, those hidden relationships still exist theoretically right? It's just another interesting way of looking at ECDLP.

Thank you

maybe this can help.Superfast method for solve ECDLP but for specific privkeys

Quote

Now I understand. It is slightly more complicated than that.
Private keys are not multiple of 18051648. Private keys are power of z mod q, where z is a primitive root mod q.

z =115481771728459905245102424859900657047113141323743738905491223467302634970004

like G^privkey

https://github.com/cysecud/ecc_weak_keys/issues/2

obtainhigh

newbie

Activity: 8

Merit: 1

Quote from: ? on December 31, 2024, 01:56:32 AM

This is a quote I found in this forum from gmaxwell

Quote

Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin.

I couldn't find much literature on this so I asked chatGPT which explained to me (quite possibly incorrectly) that:

Under normal circumstances d * G = Q (where d is the private key, G is the basepoint, Q is the public key, '*' represents scalar multiplication.) But if you were aware of a deeper relationship, by design or otherwise, where s * H = G (s is a scalar in the range of 2-N, H is a valid point on the curve) This would allow you to solve any private key in the system instantly, no ECDLP required, because you can substitute in d * (s*H) = G and solve it algebraically.

So can someone tell me if this is correct or incorrect?

I have struggled for days trying to understand this. If someone could let me know, maybe even make a python example that uses an example basepoint with a hidden relationship to demonstrate how it would work. That would mean a lot to me and anyone else interested in the same thing.

Regardless of whether or not SECP256k1's basepoint was chosen with a hidden relationship in mind, those hidden relationships still exist theoretically right? It's just another interesting way of looking at ECDLP.

Thank you

Basepoint (G) in Elliptic Curves:
The basepoint GG is a predefined point on the curve used for all cryptographic operations in Bitcoin (SECP256k1 curve).
The elliptic curve cryptography (ECC) system relies on the discrete logarithm problem (ECDLP), which is considered infeasible to solve under normal conditions.

Hidden Relationships Between Points:
If GG, the basepoint, was chosen with a hidden relationship G=s⋅HG=s⋅H (where HH is another curve point and ss is a known scalar), the party aware of ss could trivially break the system. They could compute private keys dd without solving ECDLP.

Substitution Exploit:
If d⋅G=Qd⋅G=Q (where QQ is the public key), substituting G=s⋅HG=s⋅H results in:
d⋅(s⋅H)=Q
d⋅(s⋅H)=Q Knowing ss, dd can be solved algebraically.

Theoretical Implications:
Even if SECP256k1's basepoint GG was chosen securely, hidden relationships theoretically exist between points on any elliptic curve due to its mathematical structure.

Python Example

Here’s a Python script to demonstrate how such a relationship could theoretically work if a hidden scalar ss was known:

Code:

from ecdsa import SECP256k1, ellipticcurve

# Define the SECP256k1 curve and its order
curve = SECP256k1.curve
order = SECP256k1.order

# Choose a hidden scalar `s` and generate a hidden basepoint H
s = 1337 # Hidden scalar
H = SECP256k1.generator # Use SECP256k1's generator as our hidden point H
G = s * H # Compute a new basepoint G based on H

# Generate a private key d
d = 42 # Example private key

# Compute the public key Q
Q = d * G

# Recover d knowing the relationship G = s * H
# Step 1: Substitute G = s * H into Q = d * G -> Q = d * (s * H)
# Step 2: Rearrange -> d = Q / (s * H)

# Recover d algebraically
recovered_d = (Q * s.inverse_mod(order)) * H.inverse_mod(order)

print("Original private key:", d)
print("Recovered private key:", recovered_d)
assert d == recovered_d, "Private key recovery failed!"

?

Activity: -

Merit: -

Quote from: gmaxwell on December 31, 2024, 03:24:45 AM

Chatgpt is really frequently bad, this is an example of it.

Take any field element s on the finite field of the curve order P. Compute H = (1/s) *G. Tada, you now have an "H" of the form in the example: s * H = G. This doesn't have any security implication at all. It's a relation easily computed for any element on the field of curve-order.

The choice of G doesn't have any security relevance in any ordinary usage.

It only has relevance in special and somewhat contrived usage. E.g. I want to convince you that I don't know the discrete log of some point with respect to G. So I do something like pick that point with sha256. So you think "oh surely you can't know the discrete log of that, it was selected by a hash!" and that would be generally true unless G itself was generated based on this supposedly "nothing up my sleeve" point (causing the relationship between them to be known). To avoid this risk any protocol that needs a nothing-up-my-sleeve point should construct it by using a hash that includes G, which proves (absent a hash collision) that G couldn't have been created as some multiple of the nums point.

If this isn't making much sense to you it's because there are relatively few reasons to have a nothing up my sleeve point, and none when it comes to ordinary bitcoin usage. They're required in some zero knowledge proof setups.

Thank you for the reply. it is making sense now. Even if I had knowledge of a relationship s * H = G ... Substituting d * (s*h)=Q and shuffling around still leaves you with Q' = d*H which is a ECDLP.

I have heard that the NIST standards that define G don't give any reason why... and some have said "Oh look at that... they might know something we dont!" But from what you are saying... There's really nothing to know.

gmaxwell

staff

Activity: 4326

Merit: 8951

Chatgpt is really frequently bad, this is an example of it.

Take any field element s on the finite field of the curve order P. Compute H = (1/s) *G. Tada, you now have an "H" of the form in the example: s * H = G. This doesn't have any security implication at all. It's a relation easily computed for any element on the field of curve-order.

The choice of G doesn't have any security relevance in any ordinary usage.

It only has relevance in special and somewhat contrived usage. E.g. I want to convince you that I don't know the discrete log of some point with respect to G. So I do something like pick that point with sha256. So you think "oh surely you can't know the discrete log of that, it was selected by a hash!" and that would be generally true unless G itself was generated based on this supposedly "nothing up my sleeve" point (causing the relationship between them to be known). To avoid this risk any protocol that needs a nothing-up-my-sleeve point should construct it by using a hash that includes G, which proves (absent a hash collision) that G couldn't have been created as some multiple of the nums point.

If this isn't making much sense to you it's because there are relatively few reasons to have a nothing up my sleeve point, and none when it comes to ordinary bitcoin usage. They're required in some zero knowledge proof setups.

?

Activity: -

Merit: -

This is a quote I found in this forum from gmaxwell

Quote

Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin.

I couldn't find much literature on this so I asked chatGPT which explained to me (quite possibly incorrectly) that:

Under normal circumstances d * G = Q (where d is the private key, G is the basepoint, Q is the public key, '*' represents scalar multiplication.) But if you were aware of a deeper relationship, by design or otherwise, where s * H = G (s is a scalar in the range of 2-N, H is a valid point on the curve) This would allow you to solve any private key in the system instantly, no ECDLP required, because you can substitute in d * (s*H) = G and solve it algebraically.

So can someone tell me if this is correct or incorrect?

I have struggled for days trying to understand this. If someone could let me know, maybe even make a python example that uses an example basepoint with a hidden relationship to demonstrate how it would work. That would mean a lot to me and anyone else interested in the same thing.

Regardless of whether or not SECP256k1's basepoint was chosen with a hidden relationship in mind, those hidden relationships still exist theoretically right? It's just another interesting way of looking at ECDLP.

Thank you

Topic: In what ways might a basepoint be compromised? (Read 147 times)