Bitcoin Forum
January 19, 2019, 07:29:46 AM
 News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 Home Help Search Login Register More
 Pages: 1 2 [3]  All
 Author Topic: Why is it hard to track backwards from public address to private key?  (Read 4012 times)
Scrat Acorns
Sr. Member

Offline

Activity: 293
Merit: 250

 January 31, 2013, 11:52:38 AM

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.
1547882986
Hero Member

Offline

Posts: 1547882986

Ignore
 1547882986

1547882986
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1547882986
Hero Member

Offline

Posts: 1547882986

Ignore
 1547882986

1547882986
 Report to moderator
1547882986
Hero Member

Offline

Posts: 1547882986

Ignore
 1547882986

1547882986
 Report to moderator
1547882986
Hero Member

Offline

Posts: 1547882986

Ignore
 1547882986

1547882986
 Report to moderator
Vitalik Buterin
Sr. Member

Offline

Activity: 331
Merit: 322

 February 05, 2013, 11:39:53 AMLast edit: February 05, 2013, 07:18:53 PM by Vitalik Buterin

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

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

Argumentum ad lunam: the fallacy that because Bitcoin's price is rising really fast the currency must be a speculative bubble and/or Ponzi scheme.
proff
Newbie

Offline

Activity: 46
Merit: 0

 February 05, 2013, 03:36:59 PM

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

Offline

Activity: 1302
Merit: 1001

 February 05, 2013, 04:21:56 PM

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.

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.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
 Pages: 1 2 [3]  All