I need a guiding hand to explain me elliptic curve cryptography

[BlackHatCoiner]

I know that the people that will reply here, have replied again multiple times on previous posts about similar questions. Since I've dived in bitcoin the last 6 months, I would like to understand the maths behind it.

I understand how we can reach from public key to address, but not how we end up to public key from private key. I saw this guide which explains how public keys work. Although, I have my queries and I couldn't find a better place.

So we have an elliptic curve:




We choose a generator point randomly(?), I guess the computer knows the x and y coordinates (that must be randomly chosen):




After that it says that if we multiply G by 2 we get this:



Why did the tangent intersect with the "2"? I don't understand this and why it helps. Is it random? It can't be, because according to learnmeabitcoin.com after all these bounces that we will make to the curve, private key number of times, we have to somehow prove that we own a public key. If the tangent was drawn randomly then even if I gave you the private key you couldn't draw what I had drawn. You would only have the number which I multiplied G.

Secondly, what would we do if we multiplied by 3? Would we continue from the 2G point or from a different one. In this picture it shows messy that it multiplies G with private key number of times:



I don't understand how all these straight lines have something in common.

Also, how can you multiply G? Isn't is just a point on the axis? Not a real number.

Oof... Help me.  

[PawGo]

Ask Computerphile 

https://www.youtube.com/watch?v=NF1pwjL9-DE

[o_e_l_e_o]

Why did the tangent intersect with the "2"? I don't understand this and why it helps. Is it random?

No, it is not random. A tangent line is defined as a line which just touches the graph at the given point, and matches the slope of the curve at the point. Essentially, it is a straight line which lies parallel to the curve at that point. Simply the continue that straight line and it will intersect the elliptic curve at exactly one other point.

Secondly, what would we do if we multiplied by 3? Would we continue from the 2G point or from a different one.

To get 3G, you would add G and 2G. To do this, draw a straight line between G and 2G. It will intersect the curve at exactly one other point. This point is -3G. Reflect across the x axis to find 3G.

[BlackHatCoiner]

To get 3G, you would add G and 2G. To do this, draw a straight line between G and 2G. It will intersect the curve at exactly one other point. This point is -3G. Reflect across the x axis to find 3G.

Like that?





Edit:



Is this 3G?

[o_e_l_e_o]

Like that?

No.

So the first line you have drawn between G and 2G is partially correct - but you need to keep drawing past 2G until that line hits the curve at another point. That point is -3G. Then once you've found -3G, draw a vertical line from -3G and you will find 3G.

Like this:

[BlackHatCoiner]

Yes but if the first G is randomly chosen and the coordinates of public key are given to someone he can't prove he owns the public key, even if he has the private key. The G is something unknown, meaning that he can't start our `painting` if he only has the number we multiply G. This is what I don't get...

[o_e_l_e_o]

Yes but if the first G is randomly chosen

G is not randomly chosen. G is known as the generator point, and is the same for every private/public key pair in bitcoin. Specifically, it is:

Code:

Compressed: 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798

Or

Uncompressed: 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

The reason it can be compressed is because you don't have to store the y coordinate; it is sufficient to store the x coordinate and whether the y coordinate is positive or negative, and the y coordinate can be calculated.

[BlackHatCoiner]

And why someone can't simply divide 3G with G and get the 3?

[bigvito19]

Yes but if the first G is randomly chosen and the coordinates of public key are given to someone he can't prove he owns the public key, even if he has the private key. The G is something unknown, meaning that he can't start our `painting` if he only has the number we multiply G. This is what I don't get...

So G is the secret then, that you are trying to look for?

[JuleAdka]

And why someone can't simply divide 3G with G and get the 3?

Because this operation isn't defined on elliptic curves, most specially in a curve defined over a discreet field, this leads to the "discreet logarithm problem" that are an unsolved problem so far.
if you are using a curve over, let's say, the real numbers set, you can calculate it. But for cripto, usually the curves are defined over a set mod(p).

secp256k1 is defined over the set mod(p), where p is:

Code:

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
p = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1

Yes but if the first G is randomly chosen and the coordinates of public key are given to someone he can't prove he owns the public key, even if he has the private key. The G is something unknown, meaning that he can't start our `painting` if he only has the number we multiply G. This is what I don't get...

G is just a convention, for the point where the calculations begins. There is some optimizations that can be done, but in general terms, every point on the curve can be a generator point. For computing a given public key, just take the secret and multiply it for G. Your result is the public key.
Elliptic curve cryptographic (or ECC) assumes that when you have a curve defined over a discreet set of numbers, is impossible to do the inverse operations (subtraction and division), because to do so, you need compute something called  a discrete logarithm(DL).
Your computer can calculate logarithm over the real numbers set because there is a serie, called Taylor Serie that is a numerical approximation of the result (i.e gives the sabe output to a given input). But this series are ONLY defined over real numbers, and without a method to compute it, the only way to solve is via brute force.
We use brute force methods for solve small logarithms or to factor small number, but for really big numbers, like 2¹²³, this method keeps useless. This makes the safety of ECC and RSA respectively.
And because it, we can easily calculate the public key via multiply (no DL here), but we can't make the inverse, find out the private key from the public (a DL need to be solved).

Maybe you can thought whether there is some way to solve DL. Yes, there is! But with digital computer and numbers in a big order (2²⁵⁶) it will take forever. (Pollard's Kangaroo is an example)

[moderator's note: consecutive posts merged]

[BlackHatCoiner]

-snip-

Thank you for your time on writing this. You mentioned some maths' phrases like discrete logarithm or Taylor Series that are unknown to me. You said, though, that in order to reverse the result of a public key we need the discrete logarithm. A computer calculates only in real numbers, so it cannot reverse it. Here's my question. Can a human do it? Or is it mathematically impossible?

Also, I'm not fully sure why a computer calculates only in real numbers since it can calculate x * G on an elliptic curve shape. For example, how all these incredibly many bounces are calculated on the axis within 1 second?

[JuleAdka]

-snip-

Thank you for your time on writing this. You mentioned some maths' phrases like discrete logarithm or Taylor Series that are unknown to me. You said, though, that in order to reverse the result of a public key we need the discrete logarithm. A computer calculates only in real numbers, so it cannot reverse it. Here's my question. Can a human do it? Or is it mathematically impossible?

Also, I'm not fully sure why a computer calculates only in real numbers since it can calculate x * G on an elliptic curve shape. For example, how all these incredibly many bounces are calculated on the axis within 1 second?

Sorry for the terms, I talk about it on my day-by-day and missuppose that everyone know it!

Discrete logarithm are logarithms function with discrete numbers (integers are discrete, for example)

Series are not more then a sum of simple terms with a former rule: like x+x²+x³+x⁴... is formed from sum (xⁿ) where sum() is just the sum of all terms.

Taylor Series are some special ones that gives the same (or close to) the result of another. For exemplo, how carry out in a CPU that only knows basic math (sum, subtract...) functions like sin(x). We use this Series to get the result, like this:
https://wikimedia.org/api/rest_v1/media/math/render/svg/3e8311bbbeac9364f73b437929aa85c71715a7a8

Here's my question. Can a human do it? Or is it mathematically impossible?

Yes! What is the log of 4 in base 2; two, of course. But, why? I know that 2² is 4, and I also know that the log ₂(4) is a number n, that when I take 2^a it returns 4. This method is called "imediate" or "intuitive", and works for small number. But for big numbers, the process becomes hard. Imagine hand-calculate log_12334434343(34234325654767454)? So, isn't mathematically impossible (there is methods to solve then) but is HARD.

Also, I'm not fully sure why a computer calculates only in real numbers since it can calculate x * G on an elliptic curve shape. For example, how all these incredibly many bounces are calculated on the axis within 1 second?

Because taking the process on the "right" direction (private -> public) not involves DLs. Is basically ordinary math, but to go backwards you should solve a DL, hence this function is so called "an one way function". This is the point you should keep in mind (sorry if I'm being boring) in one way: ordinary math, in the other way: DLs.

[BlackHatCoiner]

Yes! What is the log of 4 in base 2; two, of course. But, why? I know that 2² is 4, and I also know that the log ₂(4) is a number n, that when I take 2^a it returns 4. This method is called "imediate" or "intuitive", and works for small number. But for big numbers, the process becomes hard. Imagine hand-calculate log_12334434343(34234325654767454)? So, isn't mathematically impossible (there is methods to solve then) but is HARD.

So a computer cannot solve it, because of lack of intelligence? Can't it approach it at least?

Anyway, so this is why you should never reveal your public keys? Because the procedure of reversing a public key is easier than reversing a SHA256 hash to its original string? I'm asking because on this public-key guide it says that public keys can be seen on the blockchain.

[pooya87]

Because the procedure of reversing a public key is easier than reversing a SHA256 hash to its original string?

you can't use the term "easier" for something that is not possible.
reversing a hash is simply impossible and will always be impossible until the end of time. no matter how much computing power is invented in the future because of how hash functions work.
reversing a public key (to find private key) is currently impossible because of the math behind elliptic curve and will remain impossible in the foreseeable future. but some day (maybe a couple of decades) it could be reversed with more computing power and a much more efficient algorithm to solve ECDLP.

[j2002ba2]

So a computer cannot solve it, because of lack of intelligence? Can't it approach it at least?

Let's have two points with coordinates (x1, y1), (xk, yk), and let (xk, yk) = k * (x1, y1).
Then
k² ≈ x1/xk
k² ≈ x1/xk * (1 - (k⁶ - 1) / y1²) = x1/xk * (1 - (k⁶ - 1) / (x1³ + 7) )
and so on...

[bigvito19]

Well it was already said that Pollard's Kangaroo the best script at this point can search for private keys with the public key but still can take a long time with that especially with bigger keys or bigger search range. Unless someone knows another approach to shorten the search range.

[vjudeu]

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.

(xk, yk) = k * (x1, y1)

Point multiplication in ECDSA is not that simple.

[j2002ba2]

you can't use the term "easier" for something that is not possible.
reversing a hash is simply impossible and will always be impossible until the end of time. no matter how much computing power is invented in the future because of how hash functions work.

I wouldn't count on that.

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

It turned out, that there are infinite number of not-yet-known facts about the natural numbers, which are not achievable by any finite set of theorems.

So, it's quite probable, that there's a theorem, which makes ECDLP, or reversing sha256 really easy.

If we deal with n-bit numbers:
For ECDLP I would guess a lower bound of O(n^c), c being a constant.
SHA256, or any hash function, should be at most O(2^n/2), possibly with O(2^n/2) memory as well. With some kind of probabilistic method, it might be even lower.

On the bright side, eventually this would be found by someone. Anyone smart enough to achieve this, would be smart enough to keep it for himself.

ECDLP solved means easy access to any coin with know pubkey(s). I doubt that early bitcoins would be touched though, it's too obvious.

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.

[o_e_l_e_o]

For example, how all these incredibly many bounces are calculated on the axis within 1 second?

Because they don't need to be. Like standard arithmetic, where 2x + 3x = 5x, or where 2*5 + 7*5 = 9*5, the same holds true for elliptic curve multiplication.

Let's say you want to multiply the generator point by 20. You do not need to do G+G+G+G+....+G 20 times. Instead, you can do the following:

Code:

G+G=2G
2G+2G=4G
4G+4G=8G
8G+8G=16G
16G+4G=20G

So, instead of doing 20 calculations, you only have to do 5.

[JuleAdka]

So a computer cannot solve it, because of lack of intelligence? Can't it approach it at least?

I don't would to say "lack of intelligence", even we use numeric approximations for munch cases. Both computers and humans can't deal with big numbers without a "easy way" to do.

Anyway, so this is why you should never reveal your public keys? Because the procedure of reversing a public key is easier than reversing a SHA256 hash to its original string? I'm asking because on this public-key guide (https://learnmeabitcoin.com/technical/public-key) it says that public keys can be seen on the blockchain.

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)

[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