Bitcoin Forum

I've gotten so many good replies for technical questions before that I have to abuse the good brains on this forum some more.

Why is it hard to track backwards from public address to private key?
I don't have a higher degree in math, but in the kind of math I'm used to, if I have a formula and the unknowns, I'm usually able to solve this given a little time.
Why doesn't this hold true in cryptography, and especially in elliptic curve cryptography?
Why is it hard to find the private key when you have both the formula and the output?

The one-way function is the basis of public-key cryptography generally. A simple example: take two extremely large primes p and q. Multiplying them yields a composite N but it is very difficult to derive p and q if given N.

From a mathematical non-super expert.

Not exactly.

The public key is calculated by "multiplying" the private key (a very large random number) by a point on the curve.  The multiplication operation is not trivial but it basically involves starting at a known point on the curve and then moving to another point on the curve n times where n is the private key so a very large number of moves.

So the operation you are talking about is:  given a seemingly totally random point on the eliptical curve exactly how many times did I "move" from the original point to get here.

Without more grounding in finite field math, etc. at some point you have to trust that given a point on the curve it is, for all practical purposes, impossible to figure out how many moves it took to get there.

A bit more detail.

The points on the eliptical curve form a group.  Being a group means that there is a defined addition operator.  

    P2 = P0 + P1

Since there is a defined way to add two points to get a third point there is a way to add a point to itself and get a second point:

    P1 = P0 + P0

You can also do this as many time as you need to so

    P1 = P0 + P0 + ... + P0 + P0

So this defines the scalar multiplication operation:

    Pn = P0 + P0 + ... + P0 + P0 = n * P0

Where n is the number of times you added point P0 to itself.

To finish up we define the exact curve we are going to use, the exact starting point we are going to use to generate all the key pairs and the finite field we are going to use for the private keys.

If G is the agreed to starting point then the public key (point) P, private key (scalar) p, keypair (P, p) is simply defined as P = p * G where * is the scalar multiplcation defined above.

I hope that helps.  Let me know if you have any more questions.

In the philosophical sense, we don't really know why some problems are harder than others.  It is an open question, and widely considered to be the most important questions in the field of computer science.

What you described is "large integer factorization" which is one method used in public private key cryptography but not the method used by Bitcoin.  It is the method used in RSA for example.  Elliptical curve cryptography used by Bitcoin uses a different method called "discrete logarithm problem" as outline by BurtW above.  The major advantage of ECC is that it is more efficient with key sizes.  256 bit ECC has roughly the same strength as 3072 bit RSA.

Still ECC can be somewhat difficult to grasp so large integer factorization is useful as an example of a generic problem which is computationally simple to solve (find the product of two large prime numbers) but for which the reverse requires too much computation to be feasible (given a large non-prime number find its prime factors). It is important to note that both RSA and ECC "work" because no efficient solution for the "reverse" has been found .... yet.  If someone were to discover a computationally efficient method of factoring massive numbers then RSA and other algorithms which rely on the premise that factoring large numbers will remain infeasible* will fail.  Likewise if someone were to discover a computationally efficient method to solve discrete logarithms algorithms then algorithms like ECC would fail.

This is different than finding a cryptographic flaw in a particular algorithm as the ramifications are more profound. Essentially when using an algorithm based on large integer factorization or discrete logarithms we are making an assumption that the "reverse" solution will continue to remain computationally infeasible.  If that assumption ends up being disproven then the very basis for the cipher is false.  Understand that in mathematics we can't definitively prove that a more efficient solution doesn't exist.  We are making a calculated assumption based on both theory and the body of cryptographic research (where for example finding a solution for factoring prime numbers in polynominal time likely would get you the nobel prize) that these problems will remain infeasible.



* Sometimes people will say impossible but that is technically incorrect.  Given enough resources (namely energy & time) these problems are solvable so they definately are not impossible.  Also given the random nature you could in theory brute force a key on the very first attempt.  Infeasible means that while theoretically possible to have any reasonable chance of success in any reasonable amount of time would require a scenario which is highly implausible (i.e. building a dysons sphere around the sun, turning all matter in the solar system into a giant super computer and use the output of the sun to power an attempt to break the key"). 

And there's still one more step protecting an address's private key, because the address is a one way hash of the public key rather than the public key itself. As long as you never reuse addresses that you have sent coins out of, your public key will never be exposed. It is exposed when you send coins though, because it is included to validate the signature on the transaction from the private key.

Can I try?

A = B + C + D

or

12 = 3 + 4 + 5

If all you have is 12, then you wouldn't know if it was 9 + 2 + 1 or 7 + 3 + 2 or whatever was the original formula. You'd have to do trial and error or what is known as brute force; try every possibility.

I think it doesn't actually work this way, but for illustration purposes this might be easier to understand.

So it can be done, given enough time. But that time is measured in centuries or millennia. In fact, that's what the vanity address generator does. Try typing an entire public key though, and it will estimate for you how long it takes.

Hmmm.

Well once a public key is found as I described above it is a point (an X and a Y coordinate)

In the Bitcoin system the next step is to hash the public key to create a public key address.   The public key addresses you know and love (starts with a 1 then a bunch of characters and digits) is not a public key.  It is a specific digest of a public key.

What you put into vanitygen is a desired public key address (hash) pattern (like 1BurtW...) not an actual public key.

And the answer to how long it takes to "go though all the possibilites" is, for all practical purposes, FOREVER.  So no, currently it cannot be done.

THE BETTER video to explain this.

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

The programmer of vanitygen specifically mentioned that it is indeed a brute force cracker. So for normal usage, you can type a short pattern, like 1Dabs, and it will look for all public key addresses that begin with that pattern. This is why there are so many 1Dice public keys.

But you can input a pattern that is just as long as the maximum length of a public key. It will find a match to that pattern, after the whole world is already dead. We know it will. We just won't be alive to see it. There is an almost negligible chance it will be found while we live, but the chance of the computer failing first is a lot higher, given that the chance of the world failing is also higher. (But people can make redundant arrays of independent computers ... ... blah blah blah.)

It can be done, and it will be done. But not in the next 10,000 years. It's a matter of semantics, I don't like using the word FOREVER to replace 10,000 years. I mean, I've been told that 2 seconds is a lifetime (in a life or death situation.)

Imagine I select a single atom out of all the atoms in our galaxy.

Now you try to find the same atom I selected by randomly selecting atoms and then seeing if it is the one I selected.

Sounds pretty difficult.  I would take you basically forever to do that, right?

That (finding the matching atom) is a smaller problem than finding one of the keypairs with a given hash.

Your estimate is a bit high.  A reasonable estimate of the number of atoms in our galaxy is more on the order of 10⁶⁹.  There are approximately 1.46x10⁴⁸ possible bitcoin addresses.  Selecting a single atom out of our Solar System might be a closer estimate (perhaps still a bit high though)

Your estimate is VERY low. 10,000 is only 10⁴.  Perhaps a match could be found by a single person after trying for 10,000,000,000 (10¹⁰) years?  But since the sun will likely burn out in around 5x10⁹ years, it would seem there might be a problem keeping the computer running that long.  If the computer can't run long enough to find the match, then you can safely say FOREVER.

At the risk of belabouring your point, (leaving philosophical questions aside!) sometimes one can prove that one problem is harder than another. If problem A can be solved in a certain number of steps while problem B takes strictly more, we can say that B is harder. The proof that B requires so-and-so many steps may then provide some insight as to "why". The real challenge is to resolve some of the many open questions; eg. we do not know why NP is harder than P — if we did then presumably someone could translate that insight into a proof!

In short, people indeed do not know why these problems are hard. It is just taken on faith, since nobody yet knows a fast way to solve them.

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.

^ Yup. It's probably a good idea to watch both the videos. Or the whole series from the beginning.

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

There is an old survey paper called "The Tale of One-Way Functions" by Leonid Levin. Unfortunately it is not written to be accessible without a strong background in theoretical computer science. Nevertheless, at the end he gives a simple example of a "complete" one-way function, which perhaps gives a feel for why inverting such functions should be difficult: consider a set of square tiles marked with a letter at each corner. Starting with a row of such tiles, we would like to extend it to a square by filling in the rows below it one tile at a time, with the rule that we may put down a tile only if it is the unique tile whose corners match what is already there:

+---+---+
|a x|x c|
|e r|r z|
+---+---+
|e r|r z|
|n s|s z|  
+---+---+

The one-way function takes as input the top row of tiles, internally expands it to a square, and outputs the bottom row (if we get stuck, just output the top row). By definition, this is easy to compute, just by looking through the permitted set of tiles at each step and checking what fits. The trouble is to go backwards...

Summary: computing the top row given the bottom (or a private key given a public key, or...) is hard because there are too many possibilities to check, too many to go through in "a little time".

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.

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).

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!

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.

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 (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.

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.

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.

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.

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.

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).

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.

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).

The crisis in Mathematics that resulted from Peano (http://en.wikipedia.org/wiki/Giuseppe_Peano)'s non-differentiable monster curves (http://en.wikipedia.org/wiki/Space-filling_curve) was successfully resolved.  We even have the word fractal (http://en.wikipedia.org/wiki/Fractal) now specifically to describe curves where the Hausdorff Dimension (http://en.wikipedia.org/wiki/Hausdorff_dimension) is not equal to the topological or Euclidean dimension.

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.

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.

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.

More info on secp256k1

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

It is worth noting that even if ECC were to fall today, cold storage addresses would still be secure.

Of course if that were to happen the price would plummet making your cold storage (at least temporarily) worthless.  :P

The key distinction between high-school math and the math used in cryptography is that cryptography is discrete. That is, in high school math your answer could be 8.56, 8.57, 8.565, 8.564, etc, with infinite granularity between any two values. You also have continuity, which means that you can find always find some distance such that within that distance for the inputs the outputs are always within a certain (arbitrarily small) range. Thus, even if you algebraic efforts fail, you can always apply methods like Newtonian approximation and get an answer in the end.

Discrete math is different. Consider the following problem:

Find integers x and y such that 120x - 23y = 1.

How would you solve that? With "normal" methods, you can't. It looks like an underdetermined system (and it is), and the requirement to have integers means that you can't just do the old trick of fixing a random x and finding y to match it. You do not get the benefits of continuity because there is no granularity. The answer is (-9,47), but in order to do that you need to do a series of reduction steps in the form of the Extended Euclidean Algorithm (http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)

Now, consider a second problem:

Find integer x such that the last ten digits of 3^x are 3147595467

This one is harder. You have to use tricks like the Chinese Remainder Theorem (http://en.wikipedia.org/wiki/Chinese_remainder_theorem), and even then a lot of computational effort is required.

Now for the really hard problem:

Find integers x,y such that x * y = 8340368351292114898806993735182512787836108384416112375142633921308502660867470 5717333990587055137541907379907772161559852062233059312453755072535705574833391 32157327857301030605921850352045823680907

We have some shortcuts to help you here, but even then the problem is currently just on the fringes of computability. Add a few more digits and it becomes intractable. The reason is that the hardness of the problem does not come from simplifying a complex equation or finding roots to a polynomial; rather, it comes from the fact that the answers have to be integers, and so you're dealing with a world that is discrete. Thus, you can easily find many instances where the expression x*y - n, where n is the above number, come very very close to zero, but those cases are all useless in helping you find the (unique up to swapping x and y and negating both) solution to the above expression.

To amplify, in the type of computation we are considering everything is discrete; cf the Church-Turing Thesis (or just consider what types of programs the computer you are using this very moment will actually run). Real numbers per se are ineffable! :)  Not just in cryptography.

Another issue, even without real numbers, is that manipulating very very big integers takes longer than manipulating small integers. Seems obvious, but if you only count the number of arithmetic steps and ignore the size of the integers (or precision of "real" numbers) then factoring becomes easy (polynomial number of steps).

Great post, you really get right to the heart of it.

In real numbers, you can feed an error term back into the algorithm to improve a guess.  In discrete math, and even worse, modular discrete math, you don't get any error term, so you can't get any feedback.  Well, you can get a little, here and there.  Better algorithms attempt to extract the tiny bits of feedback, which in some cases makes them much better than simple brute force, but that is just a reduction in badness, it doesn't get you down into polynomial territory.

The catch is that we really don't know why we can't get feedback. *  And we can't prove that feedback is impossible either.  For all we know, there is some trick just waiting to be discovered that will reduce a big lump of currently impossible problems to triviality.

* The Wikipedia example is (3^k)%17=13.  If you try solving it, you can see that classical techniques for using the error term to improve successive guesses don't help you much, but why we haven't been able to find any techniques that do work is, again, one of the biggest open questions in mathematics today.