Finding base point in elliptical curve = Bitcoin done

[release]

Correct me if I am wrong but if someone can reverse engineer you G or base point from public key then they can work backwards to get your private key and steal Bitcoins of any wallet?

We know the mathematical formula for eliptical curve and that public key is the base point multiplied over and over? Doesn't seem impossible to end Bitcoin all together is someone can figure that out.

With the emergence of quantum computers I'm not sure I am satisfied with the level of security of Bitcoin any more

[1713996329]

1713996329

[1713996329]

1713996329

[ranochigo]

No one can figure out how to do this with a classical computer in operations lesser than 2^128. With Shor's algorithm and a sufficiently powerful quantum computer, the number of operations can be shortened to 128^3.

The question lies in the effectiveness in quantum computers in cracking asymmetrical cryptography (ECDSA, RSA) etc. As of now, the most efficient quantum computers are not anywhere close to be able to crack them in a reasonable amount of time. It's important to note that quantum annealing is not very suitable for the job, if at all. With Bitcoin, the likelihood of someone breaking SHA256, RIPEMD-160 and ECDSA with a quantum computer is fairly low so not reusing addresses could give you a boost of security. The only timeframe they'll have is the amount of time between the transaction is broadcasted and confirmed.

The impact of quantum computers affects much more than Bitcoin. It'll negate the usefulness of most asymmetrical algorithms.

Conversely, if someone figures out the solution to P = NP, we can probably end cryptography so there's that.

[BlackHatCoiner]

Correct me if I am wrong but if someone can reverse engineer you G or base point from public key then they can work backwards to get your private key and steal Bitcoins of any wallet?

Correct, but except the last part. In order to reverse the public key to private, you'll need to know what's the public key. An address that has never spent, has never revealed its public key as well.

We know the mathematical formula for eliptical curve and that public key is the base point multiplied over and over? Doesn't seem impossible to end Bitcoin all together is someone can figure that out.

At the moment, a computer cannot do that mathematical reversal. The "easiest" way to achieve what you're saying is by brute-forcing which is stupidly hard.

With the emergence of quantum computers I'm not sure I am satisfied with the level of security of Bitcoin any more

I don't think that quantum computers will affect it that much. If that reversal will be ever possible in the distant future, we can face it pretty easily. As I told you, sending funds on addresses that have never spent before.

[pooya87]

There is nothing to "reverse engineer" about the generator point of an elliptic curve, they are just points that are located on the curve. On top of that the fact that private key to public key is an irreversible operation is not about the generator point G but about the fact that the math behind it is irreversible. In other words if you have a point P and know that P is k*G you have no way of finding k even though you have both P and G.

[baro77]

Just two point to underline imho:

- you do not reverse engineer "G" because G is well known.. what you would need to reverse is private key p, given public key P and their relation P=pG (where multiplication is not the usual one, otherwise the task would be trivial) [EDIT: already written by pooya87, we have answer this topic almost at the same time and I didn't see his]

- avoiding address reuse is very important because QC can give some speedup in the above task, but far less improvement in hash inversion... but BTC addresses are the hashes of public keys, and the public keys are exposed only when you spend an UTXO... so spending UTXO = unwrapping public key from the protective envelope of the hash... so better not reusing that public key/address because in the meanwhile a future super QC could have gained the private key.. by the way, that's why oldest P2PK UTXO (pay to public key utxo) would be more at risk than P2PKH (pay to public key hash - aka address)

[o_e_l_e_o]

With Bitcoin, the likelihood of someone breaking SHA256, RIPEMD-160 and ECDSA with a quantum computer is fairly low so not reusing addresses could give you a boost of security.

Hashing algorithms and elliptic curve multiplication are not similarly susceptible to being broken by quantum computers.

As you say, breaking elliptic curve multiplication will experience an exponential speed up when being attacked with Shor's algorithm by a quantum computer. Attacking a hashing algorithm with Grover's algorithm will, at best, provide only a quadratic speed up. Something like SHA256 would still require 2¹²⁸ operations to break. Not reusing addresses essentially makes it impossible for quantum computers to steal your coins until we can perform 2¹²⁸ operations in a reasonable space of time, which is likely to be centuries away.

An address that has never spent, has never revealed its public key as well.

Correct, provided you have not exposed the public key in another way, such as revealing your master public key or signing a message.

[NotATether]

- avoiding address reuse is very important because QC can give some speedup in the above task, but far less improvement in hash inversion... but BTC addresses are the hashes of public keys, and the public keys are exposed only when you spend an UTXO... so spending UTXO = unwrapping public key from the protective envelope of the hash... so better not reusing that public key/address because in the meanwhile a future super QC could have gained the private key.. by the way, that's why oldest P2PK UTXO (pay to public key utxo) would be more at risk than P2PKH (pay to public key hash - aka address)

I don't think single-use addresses everywhere is practical because the majority of wallets work with a fixed amount of addresses unless you generate more of them. And in certain setups like multisig you cannot conveniently transfer everything to a second multisig address and those are where the majority of riches are stored. And also really old P2PK addresses people mined to in the early days and forgot about are even more valuable.

So the question is now, how practical it is for an adversary to compute the list of all bitcoin addresses with a balance [and actually they don't even have to do that, as LoyceV already has such a list] and then given that there are millions of addresses, they still need thousands of compute minutes to crack them all, depending on the average number of transactions in a block.

I'm assuming an attacker is more interested in active addresses than dormant ones, though they will probably get the dormant addresses first because even if you have the private key to someone else's address, if they are moving some coins in an unconfirmed non-RBF transaction then you need to also gain control of a majority of the hashrate, a politically impossible task. Dormant addresses aren't moving anything anywhere.

But then again, if someone gets access to the attacker's cracking tech then they can use it to move off their coins so instead of seeing the activity of cracking any private key as enriching someone, people should see it as a way to destroy the network.

[o_e_l_e_o]

I don't think single-use addresses everywhere is practical because the majority of wallets work with a fixed amount of addresses unless you generate more of them.

Any HD wallet should be capable of generating billions of addresses.

And in certain setups like multisig you cannot conveniently transfer everything to a second multisig address and those are where the majority of riches are stored.

Why not? Setting up multisig HD wallets is very easy.

I'm assuming an attacker is more interested in active addresses than dormant ones, though they will probably get the dormant addresses first because even if you have the private key to someone else's address, if they are moving some coins in an unconfirmed non-RBF transaction then you need to also gain control of a majority of the hashrate, a politically impossible task.

There will be a long time between having a quantum computer which can reverse elliptic curve multiplication, and having a quantum computer which can reverse elliptic curve multiplication in <10 minutes. I would assume that if someone managed to develop a quantum computer with such capabilities in complete privacy and unbeknownst to the word (which is highly unlikely), then they will first target some long dormant P2PK address, since it will initially likely take weeks to months to obtain the private key.

[release]

It was mentioned above that point G is already known. Can you please elaborate on that. I wasn't aware of this.

[pooya87]

It was mentioned above that point G is already known. Can you please elaborate on that. I wasn't aware of this.

Every Elliptic Curve is an unlimited number of points that satisfy its equation. We select one of these points and use it as the generator point (we add this point to itself repeated times to generate all the other points) which will then limit the number of points on that curve to a finite group. The generator point for sek9256k1 curve can create a little less than 2²⁵⁶ points (known as the order of the curve or N) on its curve.

[o_e_l_e_o]

Specifically for bitcoin, the generator point is:

Code:

x = 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Every single bitcoin private and public key pair uses the same generator point, so anyone (or any piece of software) using the same private key will always generate the same public key. The equation is simply:

Code:

K = k*G

Where:

K = Public key
k = Private key
G = Generator point

[release]

Specifically for bitcoin, the generator point is:

Code:

x = 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y = 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

Every single bitcoin private and public key pair uses the same generator point, so anyone (or any piece of software) using the same private key will always generate the same public key. The equation is simply:

Code:

K = k*G

Where:

K = Public key
k = Private key
G = Generator point

Ok thank you very much for that.

So public key is literally private key multiplied by the generator point you mentioned above?

The above is in hex? To do the math it would be in decimal?

If I wanted to do it manually or apply it to python script, how would I format my private key and generator point?

[NotATether]

I don't think single-use addresses everywhere is practical because the majority of wallets work with a fixed amount of addresses unless you generate more of them.

Any HD wallet should be capable of generating billions of addresses.

Yeah but won't there be disk lag from reading all those addresses from the wallet file? That's why I think conventional systems can't load more than a couple thousand addresses in under a minute. But I'd definitely be interested in benchmarks for that on Core.

And in certain setups like multisig you cannot conveniently transfer everything to a second multisig address and those are where the majority of riches are stored.

Why not? Setting up multisig HD wallets is very easy.

I was referring to the human factor in communicating to your cosigners your master public keys.

So public key is literally private key multiplied by the generator point you mentioned above?

The above is in hex? To do the math it would be in decimal?

If I wanted to do it manually or apply it to python script, how would I format my private key and generator point?

It's not arithmetic multiplication, it's a special kind of multiplication that takes two points in a curve and calculates a third point also in the curve. And those numbers are in hex, not decimal.

Python 3 can handle arbitrarily large numbers out of the box, so just put 0x in front of those numbers to represent your points.

[release]

Thank you. Can you please explain this math or point me in a direction where I can read up on it more.

[ranochigo]

Yeah but won't there be disk lag from reading all those addresses from the wallet file? That's why I think conventional systems can't load more than a couple thousand addresses in under a minute. But I'd definitely be interested in benchmarks for that on Core.

Electrum definitely cannot handle thousands of address at once. For Core, I know there's significant lag after a certain threshold of transactions on slower computers. I'm not exactly sure what causes the lag but if I had to guess it's probably the addresses' metadata and not the number of keys it's contained. Reusing of keys is not the default behavior of Bitcoin Core anyways, since it generates new key for each transaction.

I was referring to the human factor in communicating to your cosigners your master public keys.

Forgive me because I didn't really do a thorough reading on TapRoot or Schnorr for that matter. With key aggregation, is it still possible to derive the individual public keys used for the transaction using the single public key revealed in such a transaction? My understanding that the individual public keys are not known but only the aggregated key will be within the script.

But again, it does make sense if the aggregated public key can be used to obtain something that can still be used to sign transactions to produce a valid signature. Please CMIIW.

[baro77]

Thank you. Can you please explain this math or point me in a direction where I can read up on it more.

First time I read about EC curves was on Antonopolous's Mastering Bitcoin, here the chapter 4: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch04.asciidoc

of course online you can find a lot of resources about EC because they are deeply studied

A good document to go deeper staying in cryptocurrency domain is Zero2Monero 2nd edition chapter 2 https://www.getmonero.org/library/Zero-to-Monero-2-0-0.pdf

[pooya87]

Thank you. Can you please explain this math or point me in a direction where I can read up on it more.

https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

[baro77]

Let me take advantage of your knowledge  

Every Elliptic Curve is an unlimited number of points that satisfy its equation. We select one of these points and use it as the generator point (we add this point to itself repeated times to generate all the other points) which will then limit the number of points on that curve to a finite group. The generator point for sek9256k1 curve can create a little less than 2²⁵⁶ points (known as the order of the curve or N) on its curve.

your answer seems very well suited for the OP level, but dealing a bit more with details, would it be correct to say that the number of points the generator can create is the cyclic subgroup order, different from curve order by a cofactor?

[BASE16]

Ok thank you very much for that.

So public key is literally private key multiplied by the generator point you mentioned above?

The above is in hex? To do the math it would be in decimal?

If I wanted to do it manually or apply it to python script, how would I format my private key and generator point?

Base16 is commonly used but you can do it in base10 if you want. 

Here is an example in Decimal: https://bitcointalk.org/index.php?topic=5245379.msg55190957#msg55190957

[baro77]

So the question is now, how practical it is for an adversary to compute the list of all bitcoin addresses with a balance [and actually they don't even have to do that, as LoyceV already has such a list] and then given that there are millions of addresses, they still need thousands of compute minutes to crack them all, depending on the average number of transactions in a block.

do you mean trying to guess a private/public key pair and hoping to have gotten one with funds?... if so, why are you referring to number of transactions in a block?

I'm assuming an attacker is more interested in active addresses than dormant ones, though they will probably get the dormant addresses first because even if you have the private key to someone else's address, if they are moving some coins in an unconfirmed non-RBF transaction then you need to also gain control of a majority of the hashrate, a politically impossible task. Dormant addresses aren't moving anything anywhere.

I cannot understand your attack-scenario:
1) why an attacker should be more interested in active addresses than dormant ones? (I think to early times dormant P2PK with a lot of value)
2) why attacker needs to control hashrate? I suppose the attacked wouldn't have knowledge of being attacked until it sees the malicious transaction in mempool, and if  that transaction is a non-RBF one, it would be included in a block as a normal transaction without possibility to block it (unless the attacked can control the hashrate): so hashrate indipendence seems more a feature than a problem for an attacker who has discovered a someone else private key

But then again, if someone gets access to the attacker's cracking tech then they can use it to move off their coins so instead of seeing the activity of cracking any private key as enriching someone, people should see it as a way to destroy the network.

I believe to get your point, but I guess we could assume an attack via a new paradigm as QC -if any- could happen when tech availability is not widespread: in that case it seems just stealing, not destroying the system because the attacked couldn't react with the same tools triggering an escalation