Why is it hard to track backwards from public address to private key?

[World]

THE BETTER video to explain this.

http://www.youtube.com/watch?v=3QnD2c4Xovk

This is symmetric cryptography. Ie. cryptography where the encrypting and decrypting keys are the same. It explains how two people can agree on a shared secret key when their communication is intercepted by a third party, without that third party being able to figure out what the key is. This is called the Diffie-Hellman key exchange.

Bitcoin uses asymmetric cryptography, where the are two keys: the public and the private, and one encrypts and the other decrypts.

ArtOfTheProblem is really good at explaining this stuff for non-mathematicians though. They've also made a video on public key cryptography. This one covers RSA. http://www.youtube.com/watch?v=wXB-V_Keiu8

Really great video! They are good explaining the extreme complex concepts we are dealing with. The important thing, in my opinion, is understanding the one way function.  Both videos explain it with the same color mixing examples.

really liked both videos ^ ,but I would like to see simple video with ECC Public Key Cryptography be the same author Brit Cruise

I asked him and he answered that he'll be making one "in the not too distant future": http://www.youtube.com/watch?v=wXB-V_Keiu8&lcor=1&lc=Ba-m_R8yp790_LA4eLMLqV6QUQ2iJ5Z4T4Iywos68Z4

If you're still interested in learning about ECC, from a tutorial expressed in simple terms, I recommend these two documents by Certicom. The first is an introduction, and the next is a tutorial where you learn the various aspects of ECC and prime fields one step at a time. The latter includes a lot of visual aid, which was a great way to learn it for me.

Introduction: http://www.certicom.com/images/pdfs/WP-ECCprimer.pdf
Tutorial: http://www.certicom.com/index.php/ecc-tutorial

I read all the comments just now,thumbs up thx
Off the top of my head http://www.khanacademy.org/ should set up a BTC donation button great site.

[AsymmetricInformation]

My take on explaining it:
Simplification: PublicKey = PrivateKey*AnotherNumber

So try to answer these questions, and hopefully you'll catch onto the concept real quick.

I multiplied 2 prime integers and got 21.
What two integers did I use?

I multiplied 2 prime integers and got 187.
What two integers did I use?

I multiplied 2 prime integers and got 1688063245889.
What two integers did I use?

ECDSA Public keys (used in bitcoin) are also the product of two large numbers...resulting in a huge product: 6013791818574714160321075769550160928403040221691660914916154278519966847051905 1547600040617210584736371110675553294866150136440087998368169814283413476604.
(Actual ECDSA pubkey I just made).
Factoring this would be tough!

(Thanks to casascius for pointing out my careless screwup that ECDSA are not 2 prime factors).

[casascius]

I multiplied 2 prime integers... (Actual ECDSA pubkey I just made).

RSA instead of ECDSA?  I don't think ECDSA public keys can be created by simply multiplying integers.

Given that the number ends in a 4, I'll bet that one of the integers was 2, or perhaps more realistically, there was a transcription mistake.

[AsymmetricInformation]

I multiplied 2 prime integers... (Actual ECDSA pubkey I just made).

RSA instead of ECDSA?  I don't think ECDSA public keys can be created by simply multiplying integers.

Given that the number ends in a 4, I'll bet that one of the integers was 2, or perhaps more realistically, there was a transcription mistake.

Christ the people on this forum are sharp as a tack! Indeed, I simplified to the two primes example to just explain the basics of public vs private key, and completely forgot that ECDSA's dont work that way when I posed that actual integer PubKey (even though that key was in fact made by multiplying a private key with another number, they arent both primes).

And I thought that was a very clear way of explaining it...now the clarity of the explanation is in danger!

[casascius]

I think you still made your point: you've clearly demonstrated an intractable function, even with just the first three examples.  Someone just learning this isn't actually going to try to factor any large number you throw out, nor are they going to try to use it in any way.  So you had just said it's a real key, but as it turns out it's probably not.  This is not an important detail, so no harm no foul.

[BurtW]

I simplified to the two primes example to just explain the basics of public vs private key, and completely forgot that ECDSA's dont work that way when I posed that actual integer PubKey (even though that key was in fact made by multiplying a private key with another number, they arent both primes).

To further clarify, in ECC the private key is in fact a large scalar (number) but the public key is not a number at all - it is a point on the chosen eliptical curve.  The public key is a set of two numbers, an X and a Y coordinate in the finite group that makes up the points on the selected eliptical curve.

I explained this in some detail in post number 4 in this very thread:  https://bitcointalk.org/index.php?topic=136933.msg1458864#msg1458864

In the specific set of ECC parameters selected to be used by the Bitcoin system the finite field used for the private keys is in fact a prime field, but the private keys themselves do not need to be prime and will only be prime if you are very lucky and randomly generate a prime number for your private key.

[DeathAndTaxes]

Well the compressed version of public key is a single value.

With the X value and the curve one can compute the Y value.  The y value is deterministic to the x value and the curve. This means the public key can be reduced to just the X value of the point on the curve.

"Compressed" is a misleading term IMHO as there is no compression going.
"Normal" ECSA public key (x-value, y-value)
"Compressed" ECDSA public key (x-value)  y-value is computed at runtime using the curve.

Sadly Bitcoin didn't use compressed keys from the beginning so most of the potential savings is wasted.

[kjj]

You actually need more than just the x-value, because a quadratic is used to find the y-value.  A single bit (parity) will allow you to distinguish between the two possible y-values and pick the correct one.

And in my opinion, it is compression, in the sense of that word that we normally use.  Redundant information is discarded, and enough is kept to reconstruct the original.

-- feel free to stop reading here --

There is a second flag involved in the compression scheme, by the way.  It is for the private key export format.

privkey(int256 value) -> pubkey(int256 x-value,int256 y-value) -> address
privkey(int256 value) -> pubkey(int256 x-value,int256 y-value) -> pubkey(int256 x,bool y-flag) -> address

(x-value,y-value) and (x-value,y-flag) give different hashes, and thus, different addresses.  While doing the ECDSA verification, both pubkeys will give the same result because the y-value is reconstructed if necessary.  But, the bitcoin software watches for transactions based on "secrets", and it only stores one secret per privkey.  So, when exporting a private key, it will attach the flag if the key is compressed, so that the importing wallet knows which secret to watch for, and which address to give to the user.

[proff]

Elliptic curves are 1-dimensional but points on them are not "integers", if that is confusing people. You can visualize a typical elliptic curve as the set of points  (x, y)  in the plane satisfying a certain algebraic equation, and you may speak of integral points or rational points on the curve, but for cryptographic purposes the coordinates should lie in a certain finite field.

Back to complexity, it is worth pointing out that just from the statement of a problem it is not always obvious how hard it is to solve it, and that is what makes life interesting. For example, testing whether a huge number is prime by trying to divide it by 2, 3, 5, and so on will take a huge amount of time, but a 100% reliable way to do it "fast" was not discovered until 2002.

[BurtW]

Elliptic curves are 1-dimensional but points on them are not "integers", if that is confusing people. You can visualize a typical elliptic curve as the set of points  (x, y)  in the plane satisfying a certain algebraic equation, and you may speak of integral points or rational points on the curve, but for cryptographic purposes the coordinates should lie in a certain finite field.

Back to complexity, it is worth pointing out that just from the statement of a problem it is not always obvious how hard it is to solve it, and that is what makes life interesting. For example, testing whether a huge number is prime by trying to divide it by 2, 3, 5, and so on will take a huge amount of time, but a 100% reliable way to do it "fast" was not discovered until 2002.

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.  

The second bold statement is incorrect. The points on the eliptical cuve form a finite group, not a field.

[casascius]

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.  

I am guessing that 1-dimensional refers to the line-like nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are two-dimensional.

[DannyHamilton]

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.

While a plane is two dimentional, I suppose a set of points in a plane could be one dimensional if they all happened to be on the same line in that plane (I doubt this is what was being stated though).

[DannyHamilton]

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.  

I am guessing that 1-dimensional refers to the line-like nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are two-dimensional.

In that case we are starting to alter the way the terms are typically used in mathematics.  A line is one dimensional, but the only curve that is one dimensional is the curve that happens to also be a line.  Most curves (those that are actually curvy and not straight) exist in two dimensions.

[BurtW]

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.  

I am guessing that 1-dimensional refers to the line-like nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are two-dimensional.

That is a stretch.

Well made myself laugh anyway.

[kjj]

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.  

I am guessing that 1-dimensional refers to the line-like nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are two-dimensional.

In that case we are starting to alter the way the terms are typically used in mathematics.  A line is one dimensional, but the only curve that is one dimensional is the curve that happens to also be a line.  Most curves (those that are actually curvy and not straight) exist in two dimensions.

No, sorry, your math is outdated (by like a century, or at the very least 45 years if you start counting from 1967).

The crisis in Mathematics that resulted from Peano's non-differentiable monster curves was successfully resolved.  We even have the word fractal now specifically to describe curves where the Hausdorff Dimension is not equal to the topological or Euclidean dimension.

[casascius]

Please explain what you mean by 1-dimensional in this context especially when you go on to say "the set of points  (x, y)  in the plane", here the word plane implying two dimensions.  

I am guessing that 1-dimensional refers to the line-like nature of the curve, much like your position on a winding street can be described as a distance from an origin (a single value), even though your latitude and longitude are two-dimensional.

That is a stretch.

Well made myself laugh anyway.

No, sorry, your math is outdated (by like a century, or at the very least 45 years if you start counting from 1967).

This is a thread started by someone trying to learn the basics of what a public and private key is.  The fact that it's diverged this far off topic and is now "my math knowledge is better than your math knowledge" is embarrassing for us as a community.

[DannyHamilton]

This is a thread started by someone trying to learn the basics of what a public and private key is.  The fact that it's diverged this far off topic and is now "my math knowledge is better than your math knowledge" is embarrassing for us as a community.

Nah. Cryptography is a complicated mathematical study.  There are various levels of knowledge, and as people attempt to explain in the simplest terms possible some of these complex concepts, others who understand the mathematics better see a need to either correct an error (so that everyone can learn and avoid the error in the future) or clarify an explanation that might otherwise have been misleading.

I do agree however that this conversation has drifted far enough from the original question that there probably isn't much need to continue the discussion any farther.

[proff]

This has nothing to do directly with complexity or with cryptography (public key or otherwise) now, just with the nature of elliptic curves.

They are 1-dimensional as algebraic varieties, the same way a line or a circle is 1-dimensional. A circle is a good example: the set of points in the plane satisfying

  x^2 + y^2 = 1

is a circle, even though we have embedded it in a (2-dimensional) plane and are using two coordinates  (x, y). The set of all points  (x, y)  is the entire 2-dimensional plane, while the set of only those points satisfying  x^2 + y^2 = 1  is 1-dimensional. If you feel like describing a point on a circle using a single coordinate, you can do it using stereographic projection, which gives a correspondence between points on a line and points on the circle.

An elliptic curve is also 1-dimensional in this sense. Instead of  x^2 + y^2 = 1  you have a different equation, for example  y^2 = x^3 + a x + b. It is not "fractal" but smooth.

That is all pretty abstract, but what is important in this context is that since we are doing algebra we can plug in elements of any field for  x  and  y.  For the purposes of cryptography we want to use a finite field. Which finite field, and which elliptic curve for that matter? There is a list of standard curves published by NIST and others. The coordinates of a point on the curve then lie in a certain finite field, while the set of all points on the curve form an interesting finite group.

If you are implementing elliptic-curve cryptography, as in Bitcoin, unless you have a good reason you are better off just using one of the standard recommended curves. You do not need to numb your brain with too much detail to get started on the implementation side; it is more important to have a general understanding of how everything works. You can worry about specific mathematical details if and when they come up.

[BurtW]

just using one of the standard recommended curves.

Thanks for the great write up and explaination.

BTW for those that don't know or may be interested in looking it up Bitcoin uses the standard recommended curve secp256k1.

[DeathAndTaxes]

More info on secp256k1

https://en.bitcoin.it/wiki/Secp256k1
http://www.secg.org/collateral/sec2_final.pdf (page 15)