Bitcoin Forum

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

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.

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.

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.

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.

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.

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)

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.

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

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.

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

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

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.

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.

Specifically for bitcoin, the generator point is:


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:


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?

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.


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


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.

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

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.

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.

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 (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 (https://www.getmonero.org/library/Zero-to-Monero-2-0-0.pdf)

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

Let me take advantage of your knowledge  :)


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 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 (https://bitcointalk.org/index.php?topic=5245379.msg55190957#msg55190957)

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 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


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

But you have to do this to set up the multisig wallet in the first place. And once it is set up, you can trivially generate billions of addresses with the same multisig requirements.

Certainly not at the moment, but that is generally because it will start at index 0 and work up, generating and checking for balance thousands of addresses in the process. There is no requirement to do this, though. A small change in the code could mean that you could start generating addresses at index 10,000,000 (or any index you choose) and ignore the first 10 million address entirely. If people were serious about only using addresses once, then you could periodically update your wallet to start generating addresses at a higher index and stop paying attention to address you have already used.

That is an example of turning the private key in to different base representations. It is not an example of elliptic curve multiplication.

---

Here is another simple resource regarding elliptic curve multiplication: https://learnmeabitcoin.com/beginners/public_keys

I think a few posts down they explain the point doubling a little. This is still a little confusing. The math used their is what I am trying to get more understanding of.

 How do you apply this G base point in math to get the public key. I know that G multiplied by private key gets the public key. Could you please give a real example of this in action.

To be honest I have no idea if one of the public keys can be retrieved from an aggregate public key, according to the MuSig whitepaper (https://eprint.iacr.org/2018/068.pdf) you need to find the reverse of the formula on page 12.

I don't think that the aggregated public key by itself will be helpful to an adversary though, or an aggregate with too few private keys of the co-signers.



Let's say the adversary wants to steal all the outputs from the transactions on a particular day. They need to know the average number of transactions in a block and that'll give them a rough idea of how many private keys need to be cracked (notwithstanding some transactions have outputs from multiple addresses/private keys), so they can calculate how much computing power they need to crack that many private keys in 10 minutes, the average block creation time.


To 1), I did admit that they would target dormant transactions first, I was just outlining how an attack against addresses with unconfirmed outputs would work.

To 2), it is only necessary to control hashrate if the attacker also wants to steal the unconfirmed outputs in the address as well. This is so they can block the transaction that's taking the outputs away and create their own transaction (normally this isn't possible with a 51% majority but in this case they also have the private keys) to send the unconfirmed bitcoins to their own address.

Because of this, if all addresses were constantly on the move and that all addresses were made to send their entire balance to some empty addresses, then the threat of widespread cracking of private keys is mitigated.

All of the wallets I use can generate an unlimited number of addresses. Which wallet doesn't do this yet?
I can think of other reasons why it isn't practical, for instance for recurring payments.

I recently tried this in Electrum, and to my surprise it created a "normal" wallet with many addresses (although starting with a 3 now). So even with multisig it's very easy to generate many different addresses.

I'm pretty sure some people use this list (https://bitcointalk.org/index.php?topic=5254914.0) trying to find a funded private key. Let them! All they'll do is prove to themselves how secure Bitcoin is. As long as it's properly generated, they'll never find a loaded private key this way.

That seems like a incredibly unlikely scenario, when there are over 1 million bitcoin sitting in P2PK addresses which a known public key which the attacker could target with almost no time limit, as opposed to trying to brute force a public key in <10 minutes. Not to mention several million bitcoin sitting in reused addresses with known public keys. And long before all 1 million bitcoin in P2PK addresses are stolen by quantum computing we will have moved to a quantum resistant algorithm that means attacks on unconfirmed transactions are impossible.

If it ever did come to this, then presumably the attacker would just target RBF enabled transactions first, since they could do so without 51% of the hashrate.

According to Standards for Efficient Cryptography the relationship between order of the generator point and co-factor and number of points on curve is as follows:
h=#E(F_q)/n
where h is the co-factor, #E(F_q) is the number of points on the curve E over F_q where q is an odd prime and n is the order of the base point G (the order of the sub-group generated by this point).
h for secp256k1 curve is equal to 1.

The last explanation completely lost me lol can someone explain simply how to use scalar multiplication now that we know the base point.

Basically you add G by itself k times where k is the private key. But since that is not reasonable there are faster algorithms to perform this depending on the curve. A simple one would be "double and add" method where you convert k to its binary form and for each 1 you perform a point addition (add 2 points) then point double and for each 0 you perform a point doubling (adding to self).
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Double-and-add
The point addition and point doubling is also explained in the above wikipedia link.

Ok thank you. I think I a trying to understand it. So you add g (base point) by itself as many time as the value of the private key. As this isn't feasible their are algorithms to spead up the process?

Correct. k is always usually big so you can't really add G by itself k times, that would take forever. But with these algorithms (like the one above) the number of operations is significantly reduced. For example you have 256 bits and if all were 1 you end up performing 256 point addition and 256 point double which isn't going to take that much compared to adding G to itself ~2²⁵⁶ times.

Thanks for your help I have a much  better understanding. Still don't understand 2 things:

1) how to multiply 2 hexadecimal strings. I would assume the point G would need to be converted into 1 decimal string? If not please clarify.

2) The amount of times G is added to itself  to get the public key is the amount of private key. In which format is the private key in for this to be possible.

1. You can't multiply strings, you perform arithmetic on numbers. So you have to first convert the string representation of the number to an integer then start the "math". In this case you should convert the hexadecimal string to a 256 bit integer using the big endian notation.

2. Same as #1, the private key is also a number with at most 256 bits. Again you convert the string representation (in this case usually base58 (https://en.bitcoin.it/wiki/Base58Check_encoding) instead of base16 since that's the common encoding for WIFs) then use that in the multiplication code.

k isn't necessarily big. k could be 1.

To expand on pooya87's answer here - it doesn't really matter what format the private key is in. The private key is simply a number between 1 and (just smaller than) 2²⁵⁶. It doesn't matter if you represent that in base10, base16, base58, binary, or whatever. It is the same number.

Lets say your private key was 50. Rather than calculate G + G + G + ... + G, which would require 49 operations, you can instead do the following:
This only requires 7 operations instead of 49.

Thank you for that. What is the best method/easiest  method of doing this math. To me it seems easier to make both G and k a number. Decimal or binary? This is easier to do for k than it is for G. Probably my final question as I have a much greater understanding now. I still can't visually comprehend and equation where G is know but now a number.

I gave you a working example in decimal and handling all of the 256 Bit's in the private key.

Thank you yes as I see that. I will study it a bit more.

That post was very helpful in showing how to get the correct number to add G to itself I appreciate that thank you.

The big missing link is still G. As G is an X and Y value in hex. How do you get it to 1 number to add it to itself. This is the only bit I am struggling with. I have every piece of the puzzle but one very large piece which is G lol

If G was one hex string I could easily enough convert it to binary and do the same thing as you did in the other post with the private key. As it is 2 coordinates I am struggling.

Please clear this up for me.

Thanks

GX : 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 -> 55066263022277343669578718895168534326250603453777594175500187360389116729240
GY : 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 ->32670510020758816978083085130507043184471273380659243275938904335757337482424

55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

G as 2 decimal strings x and y.

you have the wrong target.. you haven't to convert G to a scalar ("1 number" as you say) to add it to itself. G is a point in a 2D discrete space (the domain of EC) and there is a algorithm (and a nice visual representation of it in the special case in which the space is continuous and not discrete) for the sum of that kind of points.

For sure the links about ECs many of us have provided contain that kind of info.


LATE EDIT

I'm thinking that somewhere you could find about "compression" to represent an EC point as a single value, not two: but don't get confused, it's just a way to use less space to store it but you don't get a proper number/scalar... meaning with "proper" something you can do COMMON algebra with

Ok much appreciated thank you

You are at point 1G these are the x and y coordinates on the elliptic curve.
Now if you want to move to lets say 2G, then you leave 1G and start running in a straight line until, at some point, you intersect the curve again and that is going to be 2G.
Keep running in a straight line and you will pass 3G and 4G and etc. on to the point that represents your Private key x*G or Better said G*x.
These are all just x and y points on the curve.

These points represent your public key.
When you only have this public key, its a mystery to know how many times jumps of G it took to get there.
If you know the Private key, it's easy to check and calculate the public key, but if you only have the public key it's hard to find the private key.

Therein lies the rub.

Geometrically, to add a point P to itself you draw a line tangent to the curve at that point. That line will intersect the curve at exactly one other point, which we call -R. You then reflect that point over the x axis to find R, and that point (R) is 2P.

To add two points together, which we will call P and Q, you draw a straight line between those two points. That line will intersect the curve at exactly one other point, which we call -R. You then reflect that point over the x axis to find R.

Algebraically, things are little more complicated. Let's take the second example above - adding points P and Q together to find R.

P + Q = R

First, we need to break this down in to the x and y coordinates.

(x_p, y_p) + (x_q, y_q) = (x_r, y_r)

Now, we need to find the slope, s, of the straight line which we have drawn between points P and Q.

s = (y_q - y_p)/(x_q - x_p)

The equations for calculating R are as follows:

x_r = s² - x_p - x_q
y_r = -y_p + s(x_p - x_r)

Ok so the X and Y coordinates both get multiplied the same? So for example:
G X: 1000
G Y: 2000

If private key is 180 (128+32+16+4)
G X will look something like:
G+G=2G
2G+2G=4G
4G+4G=8G
8G+8G=16G
16G+16G=32G
32G+32G=64G
64G+64G=128G
128G+32G+16G+4G=180G

Therefore G X=180000

Do similar with G Y and get 360000

So in the example public key will be:
X: 180000
Y: 360000

This is obviously simplified. Please tell me I am on the right track here.

Appreciate your help!

I'm afraid not. It's not as simple as just multiplying the two coordinates by the private key.

If we assume your private key is 180 as in your example, then we do indeed follow the G+G=2G scheme you have laid out to reach 180G in the fewest number of steps.

However, we have to use the equations I've given above (and a couple of others) at each step to calculate the next point.

As a very rough example*, if we take the point P = (1000, 2000) as you have used.

To find the slope of the tangent to that point, we use the following equation (where a is taken from the curve parameters, in bitcoin's case a = 0):

s = (3x_p² + a)/(2y_p)

So s = (3*1000² + 0)/(2*2000)
s = 3,000,000 / 4,000
s = 750

Now, using the two equations I gave above to work out the coordinates of R (given that we are doubling P, and so P and Q are the same point):

x_r = s² - x_p - x_q
x_r = 750² - 1000 - 1000
x_r = 560,500

y_r = -y_p + s(x_p - x_r)
y_r = -2000 + 750(1000 - 560,500)
y_r = −419,627,000

So if G = (1000, 2000), then 2G = (560,500, -419,627,000)

---

*Now, without defining a curve, its parameters, or a field, then what I have written is essentially meaningless - but it gives you an illustration of what you need to do to multiply points on an elliptic curve.

Ok thank you.

Could you please show  me what 4G and 8G looks like in my example. Thank you. I am gaining a better understanding it would help if I see it in action. Thanks

I want to again prefix by saying this example is meaningless, and not really representative of a real elliptic curve. I am simply plugging your numbers in to the necessary equations.

Given that G has the coordinates x = 1000 and y = 2000
Then 2G has the coordinates x = 560,500 and y = -419,627,000

To calculate 4G then, let P = 2G.

s = (3x_p² + a)/(2y_p)
s = (3*(560,500)² + 0)/(2*(-419,627,000))
s = -1,122.99822...

x_r = s² - x_p - x_q
x_r = (-1,122.99822)² - 560,500 - 560,500
x_r = 140,125.00713...

y_r = -y_p + s(x_p - x_r)
y_r = -(-419,627,000) + (-1,122.99822)(560,500 - 140,125.00713)
y_r = -52,453,369.65954...

So 4G has coordinates x = 140,125.00713 and y = -52,453,369.65954

You could also verify this by doing 2G + G = 3G, and then doing 3G + G = 4G, and seeing that your result matches your result for 2G + 2G = 4G (it does).

Here is another example using much smaller numbers on a define curved of y² = x³ - 7x + 10
https://www.herongyang.com/EC-Cryptography/Algebraic-Point-Addition-Example.html

If we search for a curve y² = x³ + d passing through (1000,2000) then d = -996,000,000. Such big d would give enormous coordinates very fast. Well, small d would grow almost as fast too. Elliptic curve security is based on this effect to a large extent.

A "smaller" curve would be y² = x³ + 12 with G=(-2,2). The curve is of rank 1, isomorphic to secp256k1 curve mod p, G being the point with smallest height.
2*G = (13, -47)
3*G = (-74/225, 11674/3375)
4*G = (27313/8836, -5352937/830584)
5*G = (14932678/8994001, 109819305542/26973008999)
...

The numbers grow very fast, n*G needs at least 2ⁿ bits to represent just the numerator of x coordinate. y grows even faster.

To some extent this could be mitigated by using curves of rank > 1. This means a curve with more than one rational generator. One could relatively easy find a curve of rank 8, the smallest one (in absolute value) is d=−2520963512. The average x would need at least 2⁷³ bits to just represent its numerator (when multiplying by <2²⁵⁶).

The highest rank of publicly known curve, isomorphic to secp256k1, is 16. The x coordinate numerator (~2⁴⁵ bits) would fit the RAM of modern supercomputer.

There's no known (easy) way to lift a point mod p to a rational numbers one. It is at least as hard as ECDLP.

Hello j2002ba2

If we have a G index of 2 ** 38 or let's call it a group, its name is BASE38.

example BASE10 key = 8167645757840975234255102487877016845485722317550747028405241086210041306983 * G


29713722170858000878998072904785719749218414354075310360368316055 * BASE38 == 8167645757840975234255102487877016845485722317550747028405241086210041306983 * G

Is it right to think like that?