4

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
    The public key is a point, the private key is an integer. – Felipe Voloch May 16 '14 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. – Mine May 18 '14 at 16:56
  • 1
    I'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 Voloch May 18 '14 at 17:10
9

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

curve addition

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

  • 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? – Mine May 19 '14 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. – Meni Rosenfeld May 20 '14 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. – Mine May 21 '14 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. – Felipe Voloch May 21 '14 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 – Mine May 21 '14 at 7:52
0

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.

  • 1
    You mean we store the x and the sign of y in reference to the public key, not the private key, right? – Mine May 18 '14 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. – user13413 May 19 '14 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? – Mine May 20 '14 at 1:43
  • You mean "x and the sign of y", right? – Nate Eldredge May 20 '14 at 15:00
  • 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)? – Mine May 21 '14 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.