|
Title: Public key from private key in elliptic curve Post by: userbits on October 28, 2016, 12:07:57 AM How to get bitcoin public key from private key on elliptic curve mathematically?
I know 2 operations with the points on elliptic curve. It is double & add. Multiply is double & add combinations depending from values of bits in numeric constant of private key. Title: Re: Public key from private key in elliptic curve Post by: btchris on October 28, 2016, 01:26:48 AM It sounds like you pretty much already know the answer, or maybe I don't understand the question?
On the secp256k1 elliptic curve used by Bitcoin, there is a point that's called the "base point generator", often denoted G. It was arbitrarily chosen (by Certicom I believe, or whoever defined the secp256k1 curve parameters). A private key is simply a 32-byte (approx.) long integer. A public key is a point on the curve-- it is found by taking the point G multiplied by the private key (via the double & add method, or some other). Title: Re: Public key from private key in elliptic curve Post by: userbits on October 28, 2016, 01:37:47 AM It sounds like you pretty much already know the answer, or maybe I don't understand the question? Ok, thanks.On the secp256k1 elliptic curve used by Bitcoin, there is a point that's called the "base point generator", often denoted G. It was arbitrarily chosen (by Certicom I believe, or whoever defined the secp256k1 curve parameters). A private key is simply a 32-byte (approx.) long integer. A public key is a point on the curve-- it is found by taking the point G multiplied by the private key (via the double & add method, or some other). Title: Re: Public key from private key in elliptic curve Post by: ArcCsch on December 02, 2016, 12:57:58 AM A private key is simply a 32-byte (approx.) long integer. A public key is a point on the curve-- it is found by taking the point G multiplied by the private key (via the double & add method, or some other). No, it is the exponential of the private key.publickey=basevalue^privatekey The discrete logarithm is hard in many groups, but, as far as I know, division is easy (division is different from factoring, to divide, you need the product and one factor, factoring is deducing both factors from just the product, which is much harder). The address is the hash of the public key. Also, you don't need the double and add to multiply, you can use school multiplication (O(n^2)) or the Karatsuba algorithm (O(n^log2(3))). The related square-and-multiply method is used for fast exponentiation. Title: Re: Public key from private key in elliptic curve Post by: Manfred Macx on December 02, 2016, 07:52:42 AM No, it is the exponential of the private key. publickey=basevalue^privatekey The discrete logarithm is hard in many groups, but, as far as I know, division is easy (division is different from factoring, to divide, you need the product and one factor, factoring is deducing both factors from just the product, which is much harder). The address is the hash of the public key. Also, you don't need the double and add to multiply, you can use school multiplication (O(n^2)) or the Karatsuba algorithm (O(n^log2(3))). The related square-and-multiply method is used for fast exponentiation. There is no exponentiation on the elliptic curve. There is only addition, and therefore multiplication. Here (https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) are some multiplication algorithms, and no there is no Karatsuba. Title: Re: Public key from private key in elliptic curve Post by: ArcCsch on December 02, 2016, 12:59:41 PM There is no exponentiation on the elliptic curve. There is only addition, and therefore multiplication. Here (https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication) are some multiplication algorithms, and no there is no Karatsuba. I did not know that, I am now confused about why it is called the discrete logarithm and not discrete division, division and the logarithm are vastly different; since elliptic curves are abelian, the "logarithm" and the "root" are the same problem, this makes no sense, it could as easily be called the discrete root problem.Title: Re: Public key from private key in elliptic curve Post by: Manfred Macx on December 02, 2016, 01:37:55 PM I did not know that, I am now confused about why it is called the discrete logarithm and not discrete division, division and the logarithm are vastly different; since elliptic curves are abelian, the "logarithm" and the "root" are the same problem, this makes no sense, it could as easily be called the discrete root problem. I think it's called discrete logarithm because it's analogous to the discrete log in a group. I guess technically it should be called discrete division :) Elliptic curves are interesting because we can define addition of the curve points and therefore get groups defined over elliptic curves. A point can be added to itself also. That is what leads to generating public keys from private keys in analogy to finite groups. In finite groups we would pick a random number (with some constraints) and then use it as the exponent of the generator of the finite (and cyclic) group. In elliptic curve crypto we also pick a random number (with some constraints) and the multiply (repeatedly add) the generator to itself that many times. The random number is the private key, the result of exponentiation/addition is the public key. |