In the ECDSA algorithm, the Bitcoin private key is supposedly a point on the graph (or is it?). But the private key is a single integer, and not x,y coordinates. Is the integer, by itself, the x value or the y value? If it is x, then what is y? If it is y, then what is x?
3
-
3The public key is a point, the private key is an integer.– Felipe VolochMay 16, 2014 at 3:59
-
Then what is the "P" (note capital P, not lower case so its not the prime number for modding)? Almost every graph I see showing the conversion of the private key to the public key shows a "P" and a "Q". If P = 9 (just an integer) and Q = 14,5, then how do you get the public key from that or what would it be? I can't seem to find an example that works.– MineMay 18, 2014 at 16:56
-
1I've suggested you look at certicom.com/index.php/ecc-tutorial on another thread. P,Q usually denote points and should have two coordinates.– Felipe VolochMay 18, 2014 at 17:10
Add a comment
|
2 Answers
The basic elliptic curve operation is addition of points. The operation of applying this addition repeatedly is called the scalar multiplication of a point by an integer.
The private key is the 'scalar', the point being multiplied is the 'Generator' point, the result is the public key.
Scalar multiplication is basically repeated addition. Multiplying the Generator point by 5 means: calculating G+G+G+G+G.
You calculate this by first calculating G2= G+G, then G4=G2+G2, then G5=G4+G.
The curve formula
The formula for the curve used by bitcoin calculations is as follows:
y^2 == x^3 + 7 ( mod p )
where p = 2^256 - 2^32 - 977
Points on the curve
a point (x,y) is on the curve if it matches the above equation
Curve Addition
Curve addition is best visualized geometrically
image from certicom
Elliptic curve cryptography does not use floating point values for it's coordinates, all calculations are done in integers modulo a large prime ( mentioned above, named p ). But the method of calculating the sum of 2 points remains the same.
adding points
Add points P1=(x1,y1) and P2=(x2,y2), resulting in Psum= (xsum, ysum)
slope = (y1-y2)/(x1-x2)
xsum = slope^2 - (x1+x2)
ysum = slope*(x1-xsum)-y1
point doubling
if P1 and P2 are the same point, the above adding formula would involve a division by zero, so a different formula is needed to calculate P+P
slope = 3 * x^2 / (2*y)
xdbl = slope^2 - 2*x
ydbl = slope *(x-xdbl)-y
ecdsa keys
For ECDSA a generator point G was chosen.
The private key is just an integer, lets name it k.
The public key is the generator point added to itself k number of times. In other words, multiplied by k.
If you choose your privatekey unwisely, say 1, your public key would equal the generator point, this address: 1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm
As you can see, it was even used recently.
What makes ECDSA a useful crypto system, is that it is easy to calculate a public key from a privatekey, but not the other way around. Another way of putting this is that multiplication is easy, but there is no (easy) division algorithm on an elliptic curve.
Example code
See this gist for an example in python
answered May 19, 2014 at 7:08
-
All the code and equations I read for the point addition and multiplication require two sets of x and y coordinates (they don't show how to work with just the integer) that result in a 3rd x,y coordinate. Since the private key is supposed to be one of those, how do I convert it into the x,y coordinate?– MineMay 19, 2014 at 18:25
-
2@Mine - As was explained, the private key is an integer (modulo the prime p). You multiply it by the generator point G to get the public key. Multiplication is repeated addition. For example, if the private key is 9, the public key is G+G+G+G+G+G+G+G+G. You use the point addition formula for that. To make it more efficient you use a variant of "exponentiation by squaring" - you calculate 2G=G+G, 4G=2G+2G, 8G=4G+4G, 9G=8G+G. May 20, 2014 at 9:22
-
...I get that the y1 and x1 are Gx and Gy, but your "addition" section shows two x's and two y's, with no specification of where they came from. At that point in your equation, the only x,y coordinate I can see is the Gx and Gy.– MineMay 21, 2014 at 1:24
-
@Mine Let's try again. Let's say your private key is the number 3. Your public key is 3G. How do we compute that? First you need to compute 2G. So you use the formula that William describe for point doubling, which only needs one pair (x_1,y_1) as input and produces a new pair (x_2,y_2) as output. The first pair represents G and the second pair represents 2G. Now you use William's addition formula with these two pais as input to produce 2G+G which is 3G, your public key. If your public key is a bigger integer you will have to do this many times, as Meni described. May 21, 2014 at 3:53
-
I get the doing it multiple times thing, but I can't seem to get the equations right even once. Anyone know of a good online calculator (or heck, a freeware calculator) that can do these things without scientific notation? I've run the equation several times now and I can't even get it right with a private key of 2 or 3. Using web 2.0 scientific calculator but it seems to do odd things including not always selecting the entire number when i'm copying and pasting– MineMay 21, 2014 at 7:52
The public key is a point, the private key is a 256 bit integer. We don't actually store the point as x,y as part of the public key though, we store x and the sign of y to save space.
-
1You mean we store the x and the sign of y in reference to the public key, not the private key, right?– MineMay 18, 2014 at 17:06
-
Right, I've edited my answer to that effect. The private key is just a 256 bit integer, though some of the upper range is invalid for our curve. May 19, 2014 at 0:58
-
All the equations to find out the public key show the G x,y value being multiplied by an x,y value, not just an integer, any idea how to convert the private key into an x,y value?– MineMay 20, 2014 at 1:43
-
-
in the point multiplication and point addition there are TWO x values and TWO y values that are required to get the public key. how, exactly, do you get the second set of x,y values when all you have is one x,y coordinate (being Gx,Gy) and an integer (private key)?– MineMay 21, 2014 at 3:18