Author

Topic: Public key from private key in elliptic curve (Read 1132 times)

full member
Activity: 205
Merit: 105
December 02, 2016, 08:37:55 AM
#7
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 Smiley

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.
full member
Activity: 224
Merit: 117
▲ Portable backup power source for mining.
December 02, 2016, 07:59:41 AM
#6
There is no exponentiation on the elliptic curve. There is only addition, and therefore multiplication. Here 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.
full member
Activity: 205
Merit: 105
December 02, 2016, 02:52:42 AM
#5
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 are some multiplication algorithms, and no there is no Karatsuba.
full member
Activity: 224
Merit: 117
▲ Portable backup power source for mining.
December 01, 2016, 07:57:58 PM
#4
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.
newbie
Activity: 14
Merit: 0
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).
Ok, thanks.
hero member
Activity: 672
Merit: 504
a.k.a. gurnec on GitHub
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).
newbie
Activity: 14
Merit: 0
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.
Jump to: