Bitcoin Forum
November 23, 2017, 07:10:23 PM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Why is it hard to track backwards from public address to private key?  (Read 3977 times)
NeoCortX
Newbie
*
Offline Offline

Activity: 22



View Profile WWW
January 16, 2013, 11:59:32 PM
 #1

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?

Learn how to build prudent privacy at prudentPrivacy.com
1511464223
Hero Member
*
Offline Offline

Posts: 1511464223

View Profile Personal Message (Offline)

Ignore
1511464223
Reply with quote  #2

1511464223
Report to moderator
Join ICO Now A blockchain platform for effective freelancing
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1511464223
Hero Member
*
Offline Offline

Posts: 1511464223

View Profile Personal Message (Offline)

Ignore
1511464223
Reply with quote  #2

1511464223
Report to moderator
1511464223
Hero Member
*
Offline Offline

Posts: 1511464223

View Profile Personal Message (Offline)

Ignore
1511464223
Reply with quote  #2

1511464223
Report to moderator
nobbynobbynoob
Hero Member
*****
Offline Offline

Activity: 756


Annuit cœptis humanae libertas


View Profile WWW
January 17, 2013, 12:04:05 AM
 #2

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.

Earn Free Bitcoins!   Earn bitcoin via BitcoinGet
BTC tip: 1PKkvuwC24Vqjv9odigXs1QVzE66jEJqmb (if <200 µBTC, please donate to charity)
LTC tip: LRqXaNdF79QHvhPpS5AZdEJZnLiNnAkJvq (if <Ł0,05, please donate to charity)
BurtW
Legendary
*
Offline Offline

Activity: 2100

All paid signature campaigns should be banned.


View Profile WWW
January 17, 2013, 12:07:43 AM
 #3

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2100

All paid signature campaigns should be banned.


View Profile WWW
January 17, 2013, 12:25:40 AM
 #4

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
kjj
Legendary
*
Offline Offline

Activity: 1302



View Profile
January 17, 2013, 12:26:44 AM
 #5

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.

p2pcoin: a USB/CD/PXE p2pool miner - 1N8ZXx2cuMzqBYSK72X4DAy1UdDbZQNPLf - todo
I routinely ignore posters with paid advertising in their sigs.  You should too.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
January 17, 2013, 12:37:00 AM
 #6

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.

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"). 
Atruk
Hero Member
*****
Offline Offline

Activity: 700



View Profile
January 17, 2013, 12:58:17 AM
 #7

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.

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.  Eliptical 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 in the context as a generic problem which is easy to calculate but infeasible to reverse.   It is important to note that both RSA and ECC "work" because no efficient solution of the reverse has been found .... yet.  If someone were to discover a computationally efficient method of factoring massive numbers then RSA and other algorithms based on large integer factorization would fail.  Likewise if someone were to discover a computationally efficient method to solve discrete logarithms algorithms like ECC would fail.  This is different than finding a cryptographic flaw in a particular algorithm.

Essentially "large integer factorization" is based on the premise that it will remain exponentially more difficult to factor the product of primes and thus by chosing primes of sufficient size one can ensure the amount of work required to factor the product of those primes is beyond the capabilities of current technology.  Its strength comes from that premise and if it is flawed then all algorithms based on that premise will have no cryptographic strength.

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.

Dabs
Staff
Legendary
*
Online Online

Activity: 1876



View Profile
January 17, 2013, 01:35:28 AM
 #8

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.

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
BurtW
Legendary
*
Offline Offline

Activity: 2100

All paid signature campaigns should be banned.


View Profile WWW
January 17, 2013, 02:50:07 AM
 #9

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Polvos
Hero Member
*****
Offline Offline

Activity: 597



View Profile
January 17, 2013, 06:32:11 AM
 #10

THE BETTER video to explain this.

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

Dabs
Staff
Legendary
*
Online Online

Activity: 1876



View Profile
January 22, 2013, 12:58:09 AM
 #11

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

Escrow Service (Services) - GPG ID: 32AD7565, OTC ID: Dabs
All messages concerning escrow or with bitcoin addresses are GPG signed. Please verify.
CompTIA A+, Microsoft Certified Professional, MCSA: Windows 10; Windows Server 2012, MCSE: Cloud Platform and Infrastructure; Productivity; Messaging
BurtW
Legendary
*
Offline Offline

Activity: 2100

All paid signature campaigns should be banned.


View Profile WWW
January 22, 2013, 03:45:16 AM
 #12

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
DannyHamilton
Legendary
*
Offline Offline

Activity: 1988



View Profile
January 22, 2013, 05:01:59 AM
 #13

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.
Your estimate is a bit high.  A reasonable estimate of the number of atoms in our galaxy is more on the order of 1069.  There are approximately 1.46x1048 possible bitcoin addresses.  Selecting a single atom out of our Solar System might be a closer estimate (perhaps still a bit high though)

. . . I don't like using the word FOREVER to replace 10,000 years . . .
Your estimate is VERY low. 10,000 is only 104.  Perhaps a match could be found by a single person after trying for 10,000,000,000 (1010) years?  But since the sun will likely burn out in around 5x109 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.

proff
Jr. Member
*
Offline Offline

Activity: 46


View Profile
January 22, 2013, 02:26:29 PM
 #14

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.


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.

Want to learn more? Consulting / tutoring / distance learning available. PM me !
Support open-access research! Please donate: 123456hi6ofP4zAEbddqiN4Dn5m8gdXXdU
runeks
Legendary
*
Offline Offline

Activity: 952



View Profile WWW
January 23, 2013, 01:38:51 AM
 #15

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
Polvos
Hero Member
*****
Offline Offline

Activity: 597



View Profile
January 23, 2013, 04:59:13 PM
 #16

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.

runeks
Legendary
*
Offline Offline

Activity: 952



View Profile WWW
January 23, 2013, 05:33:50 PM
 #17

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

Activity: 746



View Profile
January 23, 2013, 11:47:28 PM
 #18

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

Supporting people with beautiful creative ideas. Bitcoin is because of the developers,exchanges,merchants,miners,investors,users,machines and blockchain technologies work together.
proff
Jr. Member
*
Offline Offline

Activity: 46


View Profile
January 25, 2013, 12:56:22 PM
 #19

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

Want to learn more? Consulting / tutoring / distance learning available. PM me !
Support open-access research! Please donate: 123456hi6ofP4zAEbddqiN4Dn5m8gdXXdU
runeks
Legendary
*
Offline Offline

Activity: 952



View Profile WWW
January 26, 2013, 05:23:24 PM
 #20

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
Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!