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)