I need a guiding hand to explain me elliptic curve cryptography

[BlackHatCoiner]

Bitcoin's pay-to-public-key-hash is a standard transaction that, in stead of recording the receiver public key in the blockchain, record only the ripdem160(sha256(pKey)). For spending it, one mus provide a key that it's hash is equal to the value in blockchain. The use of two different algorithms is made to reduce the chance of an attacker find the right hash using pre-image or some  attack to the hash. To broken a p2pkh you must broken both sha256 and ripdem160, as well find the right public key to create the pre-image (only a limited set o public keys on the whole space). Theoretically, if you find a good way to calculate the discrete log and use it to broke bitcoin keys, you will not go so far, because you don't know what public key look for (except for the very first transactions, and in case of key reuse)

But the guide says that the original public key can be found inside the locking script, the attacker don't have to find any hashes:

[JuleAdka]

But the guide says that the original public key can be found inside the locking script, the attacker don't have to find any hashes:
https://i.imgur.com/xzzqrYX.png

That is the input

For spending it, one mus provide a key that it's hash is equal to the value in blockchain.

By the way, for proven the ownership of one UTXO locked by a p2pkh script you must: provide the public key and a valid signature for it. Then the coins are locked again in a new p2pkh, and until the owner sped it again the public key will be kept secret. That's why you shouldn't re-use addressees, the public key will be disclosed after the firs transaction.

[o_e_l_e_o]

But the guide says that the original public key can be found inside the locking script, the attacker don't have to find any hashes

That script is only revealed when a transaction is made from that address.

To send bitcoin to an address, you do not need to know the public key, and the public key is not part of the transaction. All you need to know is the public key hash (for P2PKH addresses), which we communicate with each other in the form of addresses. When you send a bitcoin transaction to an address, your wallet extracts the public key hash from the address you provide and includes it in the script along with some other generic instructions known as opcodes.

To spend bitcoins from an address, you need to provide the public key which matches the public key hash in the script. The public key you provide is hashed, checked against the public key hash, and then the signature you provide is checked against the public key. All of this is stored in the transaction data, which is broadcast to the blockchain.

So, if an address has only received bitcoin, then the public key will still be known only to the owner of that address (unless they have shared it with other people). As soon as you spend bitcoin from an address, then the public key is written to the blockchain and publicly viewable by anyone.

[BlackHatCoiner]

So, if an address has only received bitcoin, then the public key will still be known only to the owner of that address (unless they have shared it with other people). As soon as you spend bitcoin from an address, then the public key is written to the blockchain and publicly viewable by anyone.

I understand that we can't find the public key of an address that has never sent any coins. But about the addresses that have sent coins, as we discussed above, if we have someone's public key it is possible to reverse it back to private key.

(Although I still don't get why we can't devide x*G with G and get the private key)

[o_e_l_e_o]

if we have someone's public key it is possible to reverse it back to private key.

At the moment, no, it is not possible.

As described above, being able to reverse elliptic curve multiplication is what is known as the elliptic curve discrete logarithm problem (ECDLP). It is essentially unsolved, in that we have no method of reversing this process other than simply brute forcing, which is infeasible over such a large search space.

Think back to the curves we drew on the previous page. If I give you a starting point (G) and a final point (P), how can you divide the two? You can't. The only way is to start at G and keep adding G to itself until you reach point P, or start at point P and keep subtracting G until you reach point G.

[j2002ba2]

But about the addresses that have sent coins, as we discussed above, if we have someone's public key it is possible to reverse it back to private key.

Yes it is "possible". But it's currently infeasible.

2¹²⁸ Jumps * 300 W / 1.6e9 Jumps/s / 3600 s/hour = 1.77e28 Wh
You'd have to spend 1.77 YWh (yotta-watt-hours), just to have a fifty-fifty chance of finding out the number.

This is the total output of 2,000,000,000,000,000 big nuclear reactors for one year.

Or 17 seconds of the total energy output of the sun.

Of course knowing something about the private key, any bits of information, could greatly help reduce that number.

[BlackHatCoiner]

2¹²⁸ Jumps * 300 W / 1.6e9 Jumps/s / 3600 s/hour = 1.77e28 Wh
You'd have to spend 1.77 YWh (yotta-watt-hours), just to have a fifty-fifty chance of finding out the number.

1 "Jump" is equal with 300 Watts? One Jump?? Leaving a fan on max doesn't burn that much in 1 hour. Why does one jump requires that much energy? What process does it do?

[j2002ba2]

2¹²⁸ Jumps * 300 W / 1.6e9 Jumps/s / 3600 s/hour = 1.77e28 Wh
You'd have to spend 1.77 YWh (yotta-watt-hours), just to have a fifty-fifty chance of finding out the number.

1 "Jump" is equal with 300 Watts? One Jump?? Leaving a fan on max doesn't burn that much in 1 hour. Why does one jump requires that much energy? What process does it do?

You sound very confused.

Let me make it more clear.


           Number-of-jumps: 2^128
                 NV100 TDP: 300 W
    NV100 jumps per second: 1.6e9
number of seconds per hour: 3600

So:
  wattseconds per jump: 300 / 1.6e9
    watthours per jump: (300/1.6e9)/3600
    Wh per 2^128 jumps: 2^128 * (300/1.6e9)/3600

[pooya87]

reversing a hash is simply impossible and will always be impossible until the end of time

Yes. But there is another problem: it is always possible to find some preimage for any hash. RIPEMD-160 has 160 bits, secp256k1 has 256 bits, so assuming uniform distribution there are around 2^96 collisions for each address. And assuming that hash functions are regularly broken every few years, I really don't know what will be broken faster: hash functions used to generate addresses or elliptic curves.

finding a preimage is not going to help because that new message still has to be a valid public key and that adds a bigger complexity on top of such an attack. and by the way even the "broken" hash algorithms such as SHA1 are still unbroken when it comes to this type of attack. in other words we still can not find m₂ by only having h=hash(m₁) even if h is SHA1.

About 90 years ago Kurt Gödel found out, that one cannot make such "impossible" statements.

that's true and there may be something done in the future but my comment was mainly about "reversing" a hash. meaning finding message by having the hash which is simply impossible and will always be impossible because of the way hash algorithms are defined. i always like to use this example, imagine you have a very simple formula x+y=z and you know the result (z) is 10. it doesn't matter how much computing power, or what kind of crazy mathematics algorithm you use, you can never reverse x+y=10 to find x and y. there is just no way. what you can do is finding different x and y that can give same result which is the same as finding collision but not being able to reverse it.

SHA256 "solved" means cheap mining, leaving ASIC farms in the dust. One could easily mine 300 coins/day without being noticed, no need to announce anything to the big world.

that's not how bitcoin works. there is this thing called difficulty which would adjust and prevent blocks from being found too fast. on top of that if there were any kind of progress in breaking SHA256 most of the internet would be at a much bigger danger. meanwhile bitcoin simply could switch to another mining algorithm.

[j2002ba2]

About 90 years ago Kurt Gödel found out, that one cannot make such "impossible" statements.

that's true and there may be something done in the future but my comment was mainly about "reversing" a hash. meaning finding message by having the hash which is simply impossible and will always be impossible because of the way hash algorithms are defined. i always like to use this example, imagine you have a very simple formula x+y=z and you know the result (z) is 10. it doesn't matter how much computing power, or what kind of crazy mathematics algorithm you use, you can never reverse x+y=10 to find x and y. there is just no way. what you can do is finding different x and y that can give same result which is the same as finding collision but not being able to reverse it.

SHA256 "solved" means cheap mining, leaving ASIC farms in the dust. One could easily mine 300 coins/day without being noticed, no need to announce anything to the big world.

that's not how bitcoin works. there is this thing called difficulty which would adjust and prevent blocks from being found too fast. on top of that if there were any kind of progress in breaking SHA256 most of the internet would be at a much bigger danger. meanwhile bitcoin simply could switch to another mining algorithm.

There are two things here: reversing hash to "a message", and reversing a hash to "the message". Depending on "the message", it is way more impossible than just "a message".

Mining is "a message" one, and can be viewed as finding small number of bits (currently less than 80), which produce corresponding zero bits in the output of a complex single hash function (changing with each new block, selected transactions, etc.).

So, we could view that hash as 80-bit input 80-bit output one.

Given a good hashing function, the probability of being able to get the desired output is 1/2 (for equal number of input and output bits).

Let's look at a hypothetical O(2^n/2) algorithm.

While everyone else would be doing 2⁸⁰ work, the smart algo would be doing only 2⁴⁰.

Such algorithm would be complex, so it would take certain fixed time to get the result, let's say 300 seconds (5 min).

Getting 33% of the hashrate means adding 50% more hashrate than the current one. Adding hashrate should be incremental, with increase about 0.2% per day. This amounts to 250 days til reaching the desired 1/3 of the total.



Reversing p2pkh is way more complex - if we view transformation from private key to public key as a hash function, then we have a sequence of 3 hash funcs., the first one being the most complex, but aslo the lousiest.

With the n/2 hypothetical algo, we get complexity 2⁸⁰ of both operations and memory requirements, which is way beyond what's available now.

But it looks like possible in the future. One day, when a memory cell is of size 9x9x9 nm, a cube with size only 1 meter would contain 2⁸⁰ bits.

The algorithm is hypothetical, and we might never know if anybody found it.

But such memory, and corresponding computers are achievable with todays technology. It's only matter of time, and desire to get rid of the current chip-based stuff.

[o_e_l_e_o]

There are two things here: reversing hash to "a message", and reversing a hash to "the message". Depending on "the message", it is way more impossible than just "a message".

The point pooya is making is that finding a collision is not the same as reversing the process. The input to SHA256 can be any message up to around 2 million terabytes. The output will always be 32 bytes. Therefore there are potentially million of messages which will give the same output. Even if you could search the entire space and find all the inputs which match a hash, you still haven't reversed the process.

[pooya87]

There are two things here: reversing hash to "a message", and reversing a hash to "the message". Depending on "the message", it is way more impossible than just "a message".

The point pooya is making is that finding a collision is not the same as reversing the process. The input to SHA256 can be any message up to around 2 million terabytes. The output will always be 32 bytes. Therefore there are potentially million of messages which will give the same output. Even if you could search the entire space and find all the inputs which match a hash, you still haven't reversed the process.

exactly, this.
additionally on topic of addresses even if you were able find a collision (i believe the correct term is second-preimage attack) it may not even start with 0x02/0x03 to begin being a valid public key or start with those bytes but be a valid point on curve.

So, we could view that hash as 80-bit input 80-bit output one.

just because some bits are zero doesn't mean your output size is smaller. it is still 32 bytes or 256 bits. and on top of that you still have to compute and do the same exact work to find those bits too and make sure they are zero.

Reversing p2pkh is way more complex - if we view transformation from private key to public key as a hash function, then we have a sequence of 3 hash funcs., the first one being the most complex, but aslo the lousiest.

again you can't view them as the same. they are very different.

[BlackHatCoiner]

Wherever I use blue symbols (*, +)  I mean ECC multiplication/addition.
So, to sum up, if you want to generate a signature you need to calculate r and s. The r is equal with the x-coordinate of (RandomNumber*G) mod N (the number of points in the field). The s is the ((HashOfThingToSign + r*privkey)*(modinv(RandomNumber, N))) % N.

In order to verify it we need to give someone two points on the curve and then he/she will be able to locate the third one that touches the curve. Just like that:

If the x-coordinate of the third point is equal with the x-coordinate of r, then it's verified.

• The point 1 is (message/s)*G.
• The point 2 is publickey*(r/s)
• The point 3 will be point 1 + point 2.

Am I saying anything wrong?

Question:  Since every time that we sign a message the RandomNumber is different, then how do we end up with the same signature? Signature is (r, s) and thus, r is included in a part of it. It should change the final result if the r changed every time we signed a message. (I've tried it with electrum and with c# libraries)

[NotATether]

Wherever I use blue symbols (*, +)  I mean ECC multiplication/addition.
So, to sum up, if you want to generate a signature you need to calculate r and s. The r is equal with the x-coordinate of (RandomNumber*G) mod N (the number of points in the field). The s is the ((HashOfThingToSign + r*privkey)*(modinv(RandomNumber, N))) % N.

You are correct.

In order to verify it we need to give someone two points on the curve and then he/she will be able to locate the third one that touches the curve. Just like that:

If the x-coordinate of the third point is equal with the x-coordinate of r, then it's verified.

• The point 1 is (message/s)*G.
• The point 2 is publickey*(r/s)
• The point 3 will be point 1 + point 2.

Yes.

Question:  Since every time that we sign a message the RandomNumber is different, then how do we end up with the same signature? Signature is (r, s) and thus, r is included in a part of it. It should change the final result if the r changed every time we signed a message. (I've tried it with electrum and with c# libraries)

We don't. That's the whole point of using a random number. You should not be able to make the same signature (r,s) from the same message and public key, because otherwise there are equations around which allow you to derive the private key from the (r,s) values of different signatures.

[BlackHatCoiner]

We don't. That's the whole point of using a random number. You should not be able to make the same signature (r,s) from the same message and public key, because otherwise there are equations around which allow you to derive the private key from the (r,s) values of different signatures.

But if you sign a message with electrum you'll notice that with the given private key and message, you will always get the same signature.

Example:

Private key (WIF for electrum):

Code:

p2pkh:L1su5NnMTMEknGUD5pyp4nAFt3oGMMk497Cv6xS6xKgtoMr52omx

Message:

Code:

Hello World

Signature:

Code:

H2qfLmf7hB/RII5Z1F6ks3O6xh2S1yZeHTW1oY5O7UeYKT7RXNOtR9Q1n9MRgSeScfqo8AZMox7W8SKOha2Cm8o=

The random number remains always the same, this is probably the reason why the signature does too. I'd like to make another question: How can you verify a signature by only having the address? Doesn't ECC require a public key? Not a hash of the public key.

[o_e_l_e_o]

The random number remains always the same, this is probably the reason why the signature does too.

That's because the random number isn't actually random. The number is calculated deterministically using the hash of your private key and your message, so the same message signed with the same private key will always produce the same signature (provided the client you are using follows this standard). This standard is called RFC6979.

I'd like to make another question: How can you verify a signature by only having the address? Doesn't ECC require a public key? Not a hash of the public key.

It is possible to calculate the usually 2 possible public keys from knowledge of the message and the signature. Those public keys can then be turned in to addresses and checked against the known address to see if either one of them matches. This feature of ECDSA is known as Public Key Recovery.

[BlackHatCoiner]

It is possible to calculate the usually 2 possible public keys from knowledge of the message and the signature. Those public keys can then be turned in to addresses and checked against the known address to see if either one of them matches. This feature of ECDSA is known as Public Key Recovery.

Oh, got it! That's why it's possible to verify by only having the address on ECDSA. Because you can extract the public key from the signature. I was curious, since you can't do that on ECIES and I was wondering if same thing happened for ECDSA.

This standard is called RFC6979.

I guess that with this standard, that I searched but it was too long to read, there aren't any equations which allow you to derive the private key from the (r,s) values of different signatures as NotATether said.

[NotATether]

It is possible to calculate the usually 2 possible public keys from knowledge of the message and the signature. Those public keys can then be turned in to addresses and checked against the known address to see if either one of them matches. This feature of ECDSA is known as Public Key Recovery.

I wonder why nobody thought of that before. The ability to recover your public key from just a message and a signature sounds powerful, especially when you consider there are tools out there for brute-forcing the private key out of the public key.

It also can be used even if there haven't been any outgoing transactions from that address (which has the side effect of addresses for which message and signature pairs are publicly known are potentially vulnerable to quantum computing).

[fxsniper]

I am interesting to know more about elliptic curve cryptography

Do anybody have an example calculate math?

I mean put number to variable and calculate it
I would like to see and read an example to more understand

from private key number calculate to get 2 X,Y public point


and if want to code from scratch (with out use library)
what formula each step calculate

[o_e_l_e_o]

what formula each step calculate

To add the points P and Q to find the resulting point R, the equation will be as follows:

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

The first step to working out (x_r, y_r) is to work out the slope, s, of the straight line joining points P and Q:

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

Or, if adding a point to itself, you work out the slope of the line tangent to that point using this equation:

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

You would then use the following equations to calculate the coordinates for R:

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

There is a worked example of this here: https://www.herongyang.com/EC-Cryptography/Algebraic-Point-Addition-Example.html