Why we can not access the private key from the public key?

[crytolog]

I would like to explain why it is almost impossible to find the private key from  public key, in a simple and different way, although it seems very confusing.

modular arithmetic is the easiest way to understand this.


x mod (y) = z
x = private key
mod (y) = 256-sha algorithm
z = public key


8 mod (7) = 1 and in all cases 8 will result in 1. But if we know 1(z), trillions of alternatives have to be tried to reach 8. 15,22,29,36,43,50 ......... these all yield 1 with respect to mod 7. Therefore, while reaching the public key from the private key takes place in milliseconds, it is impossible to access the private key from the public key.

Of course, the background of the event is more complicated, I simply wanted to explain it in a different way.

[tinopener]

I always imagine it as an MD5Sum / hash / checksum type thing...

... although I suddenly realise that may be a bit simplistic.

[cr1776]

I would like to explain why it is almost impossible to find the private key from  public key, in a simple and different way, although it seems very confusing.

modular arithmetic is the easiest way to understand this.


x mod (y) = z
x = private key
mod (y) = 256-sha algorithm
z = public key


8 mod (7) = 1 and in all cases 8 will result in 1. But if we know 1(z), trillions of alternatives have to be tried to reach 8. 15,22,29,36,43,50 ......... these all yield 1 with respect to mod 7. Therefore, while reaching the public key from the private key takes place in milliseconds, it is impossible to access the private key from the public key.

Of course, the background of the event is more complicated, I simply wanted to explain it in a different way.

How about:  given the one way hash function, it is akin to having a huge piece of paper with a photo (or writing) on it and putting it through an atomic shredder.  It is easy to go from paper to atoms, but it would be nearly impossible to go from atoms to paper configuration you had before.  Sure you possible *could* do it, but it would likely take billions of times more years than are left in the universe.

You could repeat the process with as many duplicates of the original as you wanted and get the same results, but going from atoms to paper wouldn't get any easier.


(Merely explaining how a hash function works, e.g. SHA, not all the details in bitcoin)

[tinopener]

How about:  given the one way hash function, it is akin to having a huge piece of paper with a photo (or writing) on it and putting it through an atomic shredder.  It is easy to go from paper to atoms, but it would be nearly impossible to go from atoms to paper configuration you had before.  Sure you possible *could* do it, but it would likely take billions of times more years than are left in the universe.

You could repeat the process with as many duplicates of the original as you wanted and get the same results, but going from atoms to paper wouldn't get any easier.

This has visualised it a bit more for me, so thanks cr1776.

This is the sort of stuff you have to sleep on, because you will never "feel it" just by reading a couple of internet posts.

[o_e_l_e_o]

So first of all, there are no hash functions involved in converting a bitcoin private key in to a public key. The process you are looking for is called elliptic curve multiplication.

In elliptic curve multiplication, you take two points on a curve and draw a straight line between them, or draw a tangent line to a single point. These lines will intersect the curve at one additional point. You do this many times - drawing a line and marking the point. The number of times you do this being your private key. This is easy to work forwards - draw a line, mark the point. Draw a new line, mark the point. Draw a new line, mark the point. And so on.

Now imagine trying to work backwards. I mark two points on a curve and say to you "Figure out how many hops it took me to get from point A to point B". Where do you start? There is nowhere to start, other than just starting at 1 hop and testing every possible number of hops until you reach the right answer. This is the (very simplified) essence of elliptic curve multiplication. It is easy to go forwards - just draw the lines and mark the points - but it is essentially impossible to go backwards - work out how many hops between two points, without simply starting at the beginning and drawing all the lines yourself.

[DannyHamilton]

EDIT: See correction from o_e_l_e_o in the next post below this one.  I made a dumb mistake in this post and his clears it up.  The point I'm making is still accurate, but the numerical representation is wrong.

So first of all, there are no hash functions involved in converting a bitcoin private key in to a public key. The process you are looking for is called elliptic curve multiplication.

In elliptic curve multiplication, you take two points on a curve and draw a straight line between them, or draw a tangent line to a single point. These lines will intersect the curve at one additional point. You do this many times - drawing a line and marking the point. The number of times you do this being your private key. This is easy to work forwards - draw a line, mark the point. Draw a new line, mark the point. Draw a new line, mark the point. And so on.

Now imagine trying to work backwards. I mark two points on a curve and say to you "Figure out how many hops it took me to get from point A to point B". Where do you start? There is nowhere to start, other than just starting at 1 hop and testing every possible number of hops until you reach the right answer. This is the (very simplified) essence of elliptic curve multiplication. It is easy to go forwards - just draw the lines and mark the points - but it is essentially impossible to go backwards - work out how many hops between two points, without simply starting at the beginning and drawing all the lines yourself.

More importantly...

Drawing as much as 2²⁵⁶ lines to find the second point (the public key) would take a horribly long time if we actually needed to draw all those lines to get to the public key from the private key.  Hoevere, elliptic curves have this very nice property that allows us to take short-cuts in the "multiplication" direction, but there are no equivalent short-cuts known for the reverse.

For example:
If I draw a tangent line to a single point (P), the resulting intersection point is P². If I then draw a line tangent to the point (P²), the resulting intersection point is (P²)² or P⁴. This is the exact same point as I would have gotten if I had drawn a line connecting P and P² (to get P³) and then drawn a line connecting P and P³ to get P⁴. I can keep doing that to make bigger jumps, so tangent to P⁴ will give me (P⁴)² which is P⁸, and tangent to P8 will give me P¹⁶.

Notice that after drawing only 256 lines, I've gotten to P^{115792089237316195423570985008687907853269984665640564039457584007913129639936} (that's P^A where A = 2^256). No need to draw 115792089237316195423570985008687907853269984665640564039457584007913129639936 lines, I can just draw 256 of them.

If I want P^{6277101735386680763835789423207666416102355444464034512896} (that's P^A where A = 2⁶⁴ + 2¹²⁸), then I can just draw 128 tangent lines.  Keep track of where the 64th point was, and where the final (128th) point is, and just connect those 2 points.  Again, no need to draw 6277101735386680763835789423207666416102355444464034512896 lines, it was sufficient to just draw 129 of them.

These short-cuts are what allows a computer to calculate the public key in a fraction of a second.  The math to find an intersecting point from a tangent (or from connecting 2 other points) is pretty simple and super fast and there isn't a need to do it more than a few hundred times.

However, there are no equivalent short-cuts going backwards. To find out what power of P a public key is, you have to start with P, then calculate P² by drawing the tangent and see if the resulting intersection point is the public key. If not, then you need to draw a line connecting P and P² to get P³ and see if the resulting intersection point is the public key. If not, then you need to draw a line connecting P and P³ to get P⁴ and see if the resulting intersection point is the public key. If not, then you need to draw a line connecting P and P⁴ to get P⁵ and see if the resulting intersection point is the public key, and so on.  If the public key is P^{6277101735386680763835789423207666416102355444464034512796}, you won't know that until you've drawn (or calulated) 6277101735386680763835789423207666416102355444464034512796 lines.  Sure, you could connect P⁶ and P¹² in order to find out where P⁷² is, but if the public key was P⁶⁸ you'll have skipped over it and never know. You still need to go back and check all the values P¹² through P⁷².
[/list]

[o_e_l_e_o]

Sure, you could connect P⁶ and P¹² in order to find out where P⁷² is, but if the public key was P⁶⁸ you'll have skipped over it and never know. You still need to go back and check all the values P¹² through P⁷².

You have given a good explanation, but your terminology and math are slightly off, particular in this sentence.

When you draw a tangent line to point P, and reflect the other intersecting point over the x axis, the resulting point is not P², but rather P+P = 2P. Similarly, if you were to have two points, 6P and 12P, and you were to draw a line between them and reflect the third intersecting point over the x axis, the resulting point is not 72P but rather 18P.

[DannyHamilton]

Sure, you could connect P⁶ and P¹² in order to find out where P⁷² is, but if the public key was P⁶⁸ you'll have skipped over it and never know. You still need to go back and check all the values P¹² through P⁷².

You have given a good explanation, but your terminology and math are slightly off, particular in this sentence.

When you draw a tangent line to point P, and reflect the other intersecting point over the x axis, the resulting point is not P², but rather P+P = 2P. Similarly, if you were to have two points, 6P and 12P, and you were to draw a line between them and reflect the third intersecting point over the x axis, the resulting point is not 72P but rather 18P.

Thanks. I'm pretty sure I knew that 2 years ago, but I've been focussing on other things for a couple of years and clearly I made a dumb mistake.  I'll leave it for now, since the point that I was trying to make (that there are short-cuts in one direction that don't exist in the other direction) still comes out even with my mistake, and I don't have the time or motivation to go back and clean up that post.  Hopefully anyone that takes the time to read it will see your correction.