<<  >> (p.5)
    Author Topic: re-use of addresses  (Read 5603 times)
    chriswilmer
    Legendary
    *
    Offline Offline

    Activity: 1008
    Merit: 1000


    View Profile WWW
    May 06, 2014, 06:10:49 PM
     #81


    A bitcoin private key, d is (almost) any 256-bit integer (78 digit number).  To find the associated public key, Q, you need to multiply your private key by a special "number" G called the elliptic curve base point:

         Q = d x G

    If you know d (private key) and G, it is fairly straight forward to calculate Q (public key).  Now, if G and Q were normal numbers, we could re-arrange this equation to solve for the private key by division:

         d = Q G

    But G and Q are not normal numbers; they are actually the {x, y} coordinates of points on a special type of curve called an elliptic curve.  Points on elliptic curves can be multiplied by normal numbers (like a private key), but it turns out that it is extremely difficult to "divide" two points on an elliptic curve to get a normal number (to solve for the private key, d).  I use quotes around "divide" because we actually call this problem the "elliptic curve discrete logarithm problem" (ECDLP) and not the division problem.

    Now the reason the security is 128 bits when the private key is 256 bits is because you don't need to brute force every possible key.  You just need to find the value of d that when multiplied by G gives you Q.  There is a bit of a pattern that you can exploit, so to speak.  The fastest known algorithms that allow one to solve the ECDLP (baby-step giant-step, Pollard's rho, etc.), need O(√n) steps.  Since n = 2^256, √2^256 = 2^128.  So using the most efficient algorithm to solve for d if Q and G are known, it should "only" take around 2^128 steps, as opposed to the 2^256 steps it would take to try every possible key by brute force.

    http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Key_sizes

    Isn't hash function SHA-256 plugged in there somewhere?  where does that fit into this?  And even if you knew "G", wouldn't you still have the hash to contend with?  

    In the post you quoted, I was trying to explain elliptic curve multiplication and the discrete logarithm problem in a very simple way.  Elliptic curve multiplication is an example of a trapdoor function that is easy to compute in one direction (multiplying the private key (integer) by the elliptic curve base point to get the public key) but infeasible to compute in reverse (finding the private key given the public key and base point).  

    When you produce an ECDSA signature for a bitcoin transaction, you sign a 256-bit hash, e, of the message (transaction), m, and get a pair of numbers {r, s}.  But in order for anyone to verify that the signature is correct, you must also tell them your public key Q in addition to r and s (and they must know the message, m, that you signed).

    Everyone already knows G because it's a property of the secp256k1 curve.  The act of signing and broadcasting a transaction makes your public key Q known because you need to provide this in order for the network to verify your signature.  Someone could "steal" your funds remaining in the associated bitcoin address if they can solve the problem:

            Q = d x G

    for an unknown d.  But like I explained earlier, it is not presently feasible to find d as the fastest known algorithm still takes 2^128 steps.  If the public key is not known, on the other hand, then someone could "steal" your funds if they try on average 2^160 random 256-bit integers until they find a ripeMD160 collision with your bitcoin address.   I say "steal" because 2^128 and 2^160 are really really big numbers and it's not actually feasible to perform a computation with such a huge number of steps.  


    I've seen you express interest in elliptic curves in a few threads now.  How I learned about them was reading the wikipedia articles (many, many times), reviewing the comments by DeathAndTaxes, DannyHamilton, GMaxwell and a few others regarding these curves.  But what really made it sink in for me was writing code from scratch to sign and verify ECDSA.  I did this in Mathematica so that I didn't have to worry about integer size or modulus operations.  After I did this, l had new respect for the weird properties of elliptic curves and prime numbers too--it's really interesting stuff.  







    Hah, you too! I have nothing to contribute other than to say that I also wrote my own ECDSA program in Mathematica. Doing this also gave me respect for the serious speed efficiencies that "real" implementations must incorporate (I was using a prime field of only 67 elements).
Page 4
Viewing Page: 5