|
Title: How is a public key calculated from a private key using ecc? Post by: Anonymous Kid on October 02, 2018, 07:39:21 AM As I understand it a pub key is calculated by;
u = random number (private key) (x, y) = G = Base point uG = P = public key my question is, if its possible to calculate the pub key with uG then since you are doing u computations already, can't you just calculate the private key from P? Just brute force G as many times as needed until you arrive at P. Obviously I am misunderstanding something. Is P calculated in a more efficient way than just u*G? Title: Re: How is a public key calculated from a private key using ecc? Post by: tromp on October 02, 2018, 08:03:58 AM > Obviously I am misunderstanding something. Is P calculated in a more efficient way than just u*G?
Yes; u*G is computed in time logarithmic in u, not linear in u as you seem to think. For instance 13*G is computed as 2 * (2 * (2 * G + G)) + G. Title: Re: How is a public key calculated from a private key using ecc? Post by: Anonymous Kid on October 02, 2018, 08:27:33 AM Yes; u*G is computed in time logarithmic in u, not linear in u as you seem to think. For instance 13*G is computed as 2 * (2 * (2 * G + G)) + G. Ah yes. This makes a lot more sense. Thanks. Title: Re: How is a public key calculated from a private key using ecc? Post by: aplistir on October 02, 2018, 12:57:23 PM my question is, if its possible to calculate the pub key with uG then since you are doing u computations already, can't you just calculate the private key from P? Just brute force G as many times as needed until you arrive at P. The numbers are so big that brute forcing is not possible with the technology that we currently have. Even if all the existing computers would be used simultaneously for only that purpose, it would still take more than 10000 years to brute force ONE bitcoin key. (Much, much more than 10000 years.) Yes; u*G is computed in time logarithmic in u, not linear in u as you seem to think. For instance 13*G is computed as 2 * (2 * (2 * G + G)) + G. Correct, but I think the same can be more clearly explained in the way it is actually done: First pre-calculate the values: G, 2*G, 4*G, 8*G, 16*G, 32*G ....... 2²⁵⁶*G Then these pre-calculated values are used for getting any desired value by using only addition. eg: 13*G= 8*G+4*G+G This is faster, because you do not have to do the same multiplications every time. You can just use addition. And to do this you only need to keep the 256 precalculated values in memory. Title: Re: How is a public key calculated from a private key using ecc? Post by: andytoshi on October 02, 2018, 02:03:25 PM Not to detract from the main point, but if you were implementing this multiplication yourself, using the "powers of two" ladder is a bad idea for security reasons. Specifically, for each 1 bit in your secret key you're adding 2^i*G, while for each 0 bit you're not doing anything. Somebody timing your algorithm could easily determine how many powers of 2 you added, i.e. how many bits in your secret key are 1.
In general, you want to use a multiplication algorithm that never puts secret data into if-conditionals [1] or into array indices [2][3]. It is possible to efficiently do this, which I think is actually even more surprising than the fact that you can do the multiplication in sublinear time. One such algorithm, though by no means the most efficient one, is as follows (a special case of [4], unless I screwed it up): 1. Compute x' = (x + 2^256 - 1)/2 mod the secp256k1 curve order. The bits of this number have a special property: if you interpret all the 0's as -1's, they also represent the original secret key x. See [5], top of page 9. 2. Compute G, -G, 2G, -2G, 4G, -4G, ..., 2^256G, -2^256G and put them in an array P. 3. Compute the sum of { x_i'*P[2*i + 1] + (1 - x_i')*P[2*i] } over each bit x'_i of x'. [1] "Don't branch on secret data" is folklore, I don't have a citation for it. [2] https://cryptojedi.org/peter/data/chesrump-20130822.pdf [3] http://www.tau.ac.il/~tromer/papers/cache.pdf [4] https://github.com/bitcoin-core/secp256k1/pull/546 [5] https://eprint.iacr.org/2012/309.pdf |