Finding base point in elliptical curve = Bitcoin done

[release]

The big missing link is still G. As G is an X and Y value in hex. How do you get it to 1 number to add it to itself.

you have the wrong target.. you haven't to convert G to a scalar ("1 number" as you say) to add it to itself. G is a point in a 2D discrete space (the domain of EC) and there is a algorithm (and a nice visual representation of it in the special case in which the space is continuous and not discrete) for the sum of that kind of points.

For sure the links about ECs many of us have provided contain that kind of info.


LATE EDIT

I'm thinking that somewhere you could find about "compression" to represent an EC point as a single value, not two: but don't get confused, it's just a way to use less space to store it but you don't get a proper number/scalar... meaning with "proper" something you can do COMMON algebra with

Ok much appreciated thank you

[BASE16]

I gave you a working example in decimal and handling all of the 256 Bit's in the private key.

That post was very helpful in showing how to get the correct number to add G to itself I appreciate that thank you.

The big missing link is still G. As G is an X and Y value in hex. How do you get it to 1 number to add it to itself. This is the only bit I am struggling with. I have every piece of the puzzle but one very large piece which is G lol

If G was one hex string I could easily enough convert it to binary and do the same thing as you did in the other post with the private key. As it is 2 coordinates I am struggling.

Please clear this up for me.

Thanks

You are at point 1G these are the x and y coordinates on the elliptic curve.
Now if you want to move to lets say 2G, then you leave 1G and start running in a straight line until, at some point, you intersect the curve again and that is going to be 2G.
Keep running in a straight line and you will pass 3G and 4G and etc. on to the point that represents your Private key x*G or Better said G*x.
These are all just x and y points on the curve.

These points represent your public key.
When you only have this public key, its a mystery to know how many times jumps of G it took to get there.
If you know the Private key, it's easy to check and calculate the public key, but if you only have the public key it's hard to find the private key.

Therein lies the rub.

[o_e_l_e_o]

The big missing link is still G. As G is an X and Y value in hex. How do you get it to 1 number to add it to itself. This is the only bit I am struggling with.

Geometrically, to add a point P to itself you draw a line tangent to the curve at that point. That line will intersect the curve at exactly one other point, which we call -R. You then reflect that point over the x axis to find R, and that point (R) is 2P.

To add two points together, which we will call P and Q, you draw a straight line between those two points. That line will intersect the curve at exactly one other point, which we call -R. You then reflect that point over the x axis to find R.

Algebraically, things are little more complicated. Let's take the second example above - adding points P and Q together to find R.

P + Q = R

First, we need to break this down in to the x and y coordinates.

(x_p, y_p) + (x_q, y_q) = (x_r, y_r)

Now, we need to find the slope, s, of the straight line which we have drawn between points P and Q.

s = (y_q - y_p)/(x_q - x_p)

The equations for calculating R are as follows:

x_r = s² - x_p - x_q
y_r = -y_p + s(x_p - x_r)

[release]

Ok so the X and Y coordinates both get multiplied the same? So for example:
G X: 1000
G Y: 2000

If private key is 180 (128+32+16+4)
G X will look something like:
G+G=2G
2G+2G=4G
4G+4G=8G
8G+8G=16G
16G+16G=32G
32G+32G=64G
64G+64G=128G
128G+32G+16G+4G=180G

Therefore G X=180000

Do similar with G Y and get 360000

So in the example public key will be:
X: 180000
Y: 360000

This is obviously simplified. Please tell me I am on the right track here.

Appreciate your help!

[o_e_l_e_o]

This is obviously simplified. Please tell me I am on the right track here.

I'm afraid not. It's not as simple as just multiplying the two coordinates by the private key.

If we assume your private key is 180 as in your example, then we do indeed follow the G+G=2G scheme you have laid out to reach 180G in the fewest number of steps.

However, we have to use the equations I've given above (and a couple of others) at each step to calculate the next point.

As a very rough example*, if we take the point P = (1000, 2000) as you have used.

To find the slope of the tangent to that point, we use the following equation (where a is taken from the curve parameters, in bitcoin's case a = 0):

s = (3x_p² + a)/(2y_p)

So s = (3*1000² + 0)/(2*2000)
s = 3,000,000 / 4,000
s = 750

Now, using the two equations I gave above to work out the coordinates of R (given that we are doubling P, and so P and Q are the same point):

x_r = s² - x_p - x_q
x_r = 750² - 1000 - 1000
x_r = 560,500

y_r = -y_p + s(x_p - x_r)
y_r = -2000 + 750(1000 - 560,500)
y_r = −419,627,000

So if G = (1000, 2000), then 2G = (560,500, -419,627,000)


*Now, without defining a curve, its parameters, or a field, then what I have written is essentially meaningless - but it gives you an illustration of what you need to do to multiply points on an elliptic curve.

[release]

This is obviously simplified. Please tell me I am on the right track here.

I'm afraid not. It's not as simple as just multiplying the two coordinates by the private key.

If we assume your private key is 180 as in your example, then we do indeed follow the G+G=2G scheme you have laid out to reach 180G in the fewest number of steps.

However, we have to use the equations I've given above (and a couple of others) at each step to calculate the next point.

As a very rough example*, if we take the point P = (1000, 2000) as you have used.

To find the slope of the tangent to that point, we use the following equation (where a is taken from the curve parameters, in bitcoin's case a = 0):

s = (3x_p² + a)/(2y_p)

So s = (3*1000² + 0)/(2*2000)
s = 3,000,000 / 4,000
s = 750

Now, using the two equations I gave above to work out the coordinates of R (given that we are doubling P, and so P and Q are the same point):

x_r = s² - x_p - x_q
x_r = 750² - 1000 - 1000
x_r = 560,500

y_r = -y_p + s(x_p - x_r)
y_r = -2000 + 750(1000 - 560,500)
y_r = −419,627,000

So if G = (1000, 2000), then 2G = (560,500, -419,627,000)


*Now, without defining a curve, its parameters, or a field, then what I have written is essentially meaningless - but it gives you an illustration of what you need to do to multiply points on an elliptic curve.

Ok thank you.

Could you please show  me what 4G and 8G looks like in my example. Thank you. I am gaining a better understanding it would help if I see it in action. Thanks

[o_e_l_e_o]

I want to again prefix by saying this example is meaningless, and not really representative of a real elliptic curve. I am simply plugging your numbers in to the necessary equations.

Given that G has the coordinates x = 1000 and y = 2000
Then 2G has the coordinates x = 560,500 and y = -419,627,000

To calculate 4G then, let P = 2G.

s = (3x_p² + a)/(2y_p)
s = (3*(560,500)² + 0)/(2*(-419,627,000))
s = -1,122.99822...

x_r = s² - x_p - x_q
x_r = (-1,122.99822)² - 560,500 - 560,500
x_r = 140,125.00713...

y_r = -y_p + s(x_p - x_r)
y_r = -(-419,627,000) + (-1,122.99822)(560,500 - 140,125.00713)
y_r = -52,453,369.65954...

So 4G has coordinates x = 140,125.00713 and y = -52,453,369.65954

You could also verify this by doing 2G + G = 3G, and then doing 3G + G = 4G, and seeing that your result matches your result for 2G + 2G = 4G (it does).

Here is another example using much smaller numbers on a define curved of y² = x³ - 7x + 10
https://www.herongyang.com/EC-Cryptography/Algebraic-Point-Addition-Example.html

[j2002ba2]

If we search for a curve y² = x³ + d passing through (1000,2000) then d = -996,000,000. Such big d would give enormous coordinates very fast. Well, small d would grow almost as fast too. Elliptic curve security is based on this effect to a large extent.

A "smaller" curve would be y² = x³ + 12 with G=(-2,2). The curve is of rank 1, isomorphic to secp256k1 curve mod p, G being the point with smallest height.
2*G = (13, -47)
3*G = (-74/225, 11674/3375)
4*G = (27313/8836, -5352937/830584)
5*G = (14932678/8994001, 109819305542/26973008999)
...

The numbers grow very fast, n*G needs at least 2ⁿ bits to represent just the numerator of x coordinate. y grows even faster.

To some extent this could be mitigated by using curves of rank > 1. This means a curve with more than one rational generator. One could relatively easy find a curve of rank 8, the smallest one (in absolute value) is d=−2520963512. The average x would need at least 2⁷³ bits to just represent its numerator (when multiplying by <2²⁵⁶).

The highest rank of publicly known curve, isomorphic to secp256k1, is 16. The x coordinate numerator (~2⁴⁵ bits) would fit the RAM of modern supercomputer.

There's no known (easy) way to lift a point mod p to a rational numbers one. It is at least as hard as ECDLP.

[mamuu]

If we search for a curve y² = x³ + d passing through (1000,2000) then d = -996,000,000. Such big d would give enormous coordinates very fast. Well, small d would grow almost as fast too. Elliptic curve security is based on this effect to a large extent.

A "smaller" curve would be y² = x³ + 12 with G=(-2,2). The curve is of rank 1, isomorphic to secp256k1 curve mod p, G being the point with smallest height.
2*G = (13, -47)
3*G = (-74/225, 11674/3375)
4*G = (27313/8836, -5352937/830584)
5*G = (14932678/8994001, 109819305542/26973008999)
...

The numbers grow very fast, n*G needs at least 2ⁿ bits to represent just the numerator of x coordinate. y grows even faster.

To some extent this could be mitigated by using curves of rank > 1. This means a curve with more than one rational generator. One could relatively easy find a curve of rank 8, the smallest one (in absolute value) is d=−2520963512. The average x would need at least 2⁷³ bits to just represent its numerator (when multiplying by <2²⁵⁶).

The highest rank of publicly known curve, isomorphic to secp256k1, is 16. The x coordinate numerator (~2⁴⁵ bits) would fit the RAM of modern supercomputer.

There's no known (easy) way to lift a point mod p to a rational numbers one. It is at least as hard as ECDLP.

Hello j2002ba2

If we have a G index of 2 ** 38 or let's call it a group, its name is BASE38.

example BASE10 key = 8167645757840975234255102487877016845485722317550747028405241086210041306983 * G


29713722170858000878998072904785719749218414354075310360368316055 * BASE38 == 8167645757840975234255102487877016845485722317550747028405241086210041306983 * G

Is it right to think like that?