Bitcoin Forum
March 29, 2024, 08:02:32 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 [3]  All
  Print  
Author Topic: Why is it hard to track backwards from public address to private key?  (Read 4260 times)
Scrat Acorns
Sr. Member
****
Offline Offline

Activity: 293
Merit: 250



View Profile
January 31, 2013, 11:52:38 AM
 #41

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.  Tongue
1711699352
Hero Member
*
Offline Offline

Posts: 1711699352

View Profile Personal Message (Offline)

Ignore
1711699352
Reply with quote  #2

1711699352
Report to moderator
In order to get the maximum amount of activity points possible, you just need to post once per day on average. Skipping days is OK as long as you maintain the average.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711699352
Hero Member
*
Offline Offline

Posts: 1711699352

View Profile Personal Message (Offline)

Ignore
1711699352
Reply with quote  #2

1711699352
Report to moderator
Vitalik Buterin
Sr. Member
****
Offline Offline

Activity: 330
Merit: 397


View Profile
February 05, 2013, 11:39:53 AM
Last edit: February 05, 2013, 07:18:53 PM by Vitalik Buterin
 #42

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 Offline

Activity: 46
Merit: 0


View Profile
February 05, 2013, 03:36:59 PM
 #43

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! Smiley  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 Offline

Activity: 1302
Merit: 1024



View Profile
February 05, 2013, 04:21:56 PM
 #44

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
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!