Getting X and Y coordinates of ECDSA public key from private key

[lopidas]

How can I count them from private key and Secp256k1 parameters. Can anybody give me mathematical notation for x and y?

[oleganza]

You might find this useful:

Guide to Elliptic Curve cryptography by Hankerson, Menezes, Vanstone.
http://cdn.preterhuman.net/texts/cryptography/Hankerson,%20Menezes,%20Vanstone.%20Guide%20to%20elliptic%20curve%20cryptography%20(Springer,%202004)(ISBN%20038795273X)(332s)_CsCr_.pdf

[lopidas]

Please, don't blame me for being lazy, but I am not native english and mathematical notation of
x and y from those parameters and private key would really help me.

[TierNolan]

Please, don't blame me for being lazy, but I am not native english and mathematical notation of
x and y from those parameters and private key would really help me.

There isn't a simple formula.

In fact, it can take a computer 1 millisecond to do all the calculations, if you have it the private key.

[lopidas]

Indeed I don't care the formula will really help me

[TierNolan]

Indeed I don't care the formula will really help me

Well, you have to start with "G".  This point counts as the equivalent of 1.

This point is

Gx = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Gy = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Double

You can double a point (x, y) using the doubling formula

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

num = 3 * x * x mod p

dem = 2 * y mod p

lambda = num * modInverse(dem) mod p

Rx = (lambda * lambda) - 2 * x mod p
Ry = ((x - Rx) * lambda) - y mod p

The result is (Rx, Ry)

Addition

You can add 2 points (x1, y1) and (x2, y2) using

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

num = (y1 - y2) mod p

dem = (x1 - x2) mod p

lambda = num * modInverse(dem) mod p

Rx = (lambda * lambda) - x1 - x2 mod p
Ry = ((x1 - Rx) * lambda) - y1 mod p

Multiplication

The way to do this is "double and add".

You start with G and double it.  That gives you 2G.  You double again and get 4G and then 8G and so on.

You do this until you have 256 numbers.  

You add some of them together using the add formula.  You only include numbers where that bit is one in the binary representation.

There is info on wikipedia, but the formalas are broken at the moment.

This page has the 2 formulas.

A private key is just a number, and you multiply it by G.

If your private key was 25, then you would do it like this

25 = 11001 (in binary)

25 = 16 + 8 + 1

25 * G = 16 * G + 8 * G + 1 * G

You can work out 16G, 8G and G by just doubling G over and over.  You then add them together.

16G + 8G + G = 25G

Like I said, it is pretty complex and will take a while to actually compute.  The modular inverse function is slow.

[jaesyn]

tl;dr: Private key is the scalar coefficient of a EC Point multiplication. If your private key is d, then your public key Q would be:  Q=d*G.


Bitcoin's Elliptic Curve satisfies the equation:  y² = x³ + 7.

Every public key must be a point on the curve, so you can substitute the point's X and Y into the equation to see if it is a valid point.

The addition operation is defined for EC points, so if you know any two points on the curve, then you can "add" them together to get a third point that is also on the curve.  Multiplication is an extension of this, so if you want to multiply a point by some number, then you can add it to itself that many times.  Note that in practice, there are algorithms to make multiplication more efficient than repeated addition.

Private keys are the scalar coefficient used in point multiplication.  There is one special point defined, known as the Generator, that is multiplied by a private key in order to produce a public key.  This is often noted as G, and the point multiplication operation itself is often noted as k*G for a scalar value k. Note that "*" here is not the same as what we think of as multiplication for real numbers.

Gx=79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

It is a common notation to represent scalar values as lowercase letters, and EC Points as uppercase letters when they are mixed in the same equations.

The entire system is contained within a finite field F_p, where p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F. This means that all scalar operations are performed (mod p), so the largest value needed for the scalar multiplier or the x/y coordinates of the resulting point is a 256-bit number. But, because of this modular math, you quickly lose the relationship between the scalar value k and the resulting point k*G.  

The modular math, plus the complexity of how to represent point addition as an algebraic equation, is what makes point multiplication a one-way function: easy to perform, but extremely difficult to undo. That is, if you know the (x,y) point for k*G, it is currently extremely difficult to determine what k was.  This is the Elliptic Curve Discrete Log Problem, and is the underpinning of security for ECDSA.

Wikipedia entry on Elliptic Curves: http://en.wikipedia.org/wiki/Elliptic_curve
Wikipedia entry on EC Point Multiplication: http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication

[lopidas]

So all I need to do is
x=priv key*Gx mod p
y=priv key*Gy mod p

Is this right?

[TierNolan]

So all I need to do is
x=priv key*Gx mod p
y=priv key*Gy mod p

Is this right?

No.  Elliptic curve "multiply" doesn't mean multiply the x and y coordinates (mod p).

You have to use the double and add formulas to build up the multiply.  Like I said, it is pretty complex.

A + B isn't just (Ax + Bx, Ay + By)

You have to use the formula and A + A has a special double formula.  The standard one won't work.

Multiply by 25 means 16 + 8 + 1

2G = double(G)
4G = double(2G)
8G = double(4G)
16G = double(8G)

Then 25G = 16G + 8G + G

[lopidas]

 ::)I understand this I meant * as sign of EC point multiplication.  
Is that right?

[TierNolan]

::)I understand this I meant * as sign of EC point multiplication.  
Is that right?

You don't multiply by x and y. 

k * G doesn't mean (k * Gx, k * Gy)

[itod]

lambda = num * modInverse(dem) mod p

Just to add to this detailed explanation what seems to be the way how modInverse is calculated, it's:
modInverse(dem) mod p
is equivalent to
dem^(p-2) mod p
Is this correct?

[lopidas]

I understand '*' is this  http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication operation.
And it is
X=Gx*priv mod p
Y=Gy*priv mod p

[TierNolan]

Just to add to this detailed explanation what seems to be the way how modInverse is calculated, it's:
modInverse(dem) mod p
is equivalent to
dem^(p-2) mod p
Is this correct?

That would give you the modular inverse, yes.  You can do the power thing efficiently too.

You can also use the extended Euclidean algorithm.  That should be faster.

I understand it is this http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication operation.

The link doesn't work for me, but right, you need to use an EC Point multiply scheme.  There are a couple of different ways to do it.

[lopidas]

But what is then y^2= x^3+7 needed for?

Are cofactor and order  used only for checking?

[TierNolan]

But what is then y^2= x^3+7 needed for?

It tells you if a point is actually on the curve.

Only (approx) half of the x values have a valid value for y.

Are cofactor and order  used only for checking?

Private keys should be modded against the order, but it won't give you the wrong answer.

[prezbo]

You should really read this. We use the '+' symbol but it's define very differently in the elliptic curve group than what people are used to. It's pretty basic math so I don't think you'll have problems understanding it and it will help you a lot with understanding the formulas given to you by TierNolan.

I don't know why you would want to re-invent warm water though. There are several well tested libraries for most programming languages that will do this 'dirty work' for you.