Topic: How is the calculation of G interpreted (Read 152 times)

yes I'm sorry I'm a novice and I'm trying to learn. anyway thanks for your answers. 

Someone should give that man a forum medal.

Again, that is a bad formulation of your question. You're probably new into this, so you'll get the answers you seek one way or another.

Think of this: How could one key and another share a point? Aren't lines the only ones they “share” points if we represent their functions graphically? For instance, y=x with y=x². They intersect in O(0,0) and in M(1,1).


Now acknowledge that a private key is just a random number. It can't be represented in any axis. The public key is a point in the curve.

Note from my examples that the integer value of 3 is represented in binary as:
11

That's 1*2¹ + 1*2⁰

If we think of G as the zero point, then G+G (which is the same as G*2) would be the first doubling.  We get G*3 by adding the zero point and the first doubling (see how that lines up with the powers of 2?).

You'll see that works again with 15.

That's 1*2³ + 1*2² + 1*2¹ + 1*2⁰

G is the zero point
G*2 is the first doubling (G+G)
G*4 is the second doubling (G*2 + G*2)
G*8 is the third doubling (G*4 + G*4)

We get G*15 by adding the zero point with each of those doublings (once again lining up with the powers of 2).

You can do the same with your k value.
Convert your k value from your original post from Hex to Binary.  You'll get
1110001110110000110001000100001010011000111111000001110000010100100110101111101 1111101001100100010011001011011111011100100100100001001111010111001000001111001 0001100100100110111001001101001100101001001001010110011001000110110111100001010 0101011100001010101

As such, you can see that you'll need to perform 255 point-doublings. Then add together 123 of those points, specifically the doublings that line up with the 1's in that binary value:

The 255th doubling, 254th doubling, 253rd doubling, 249th doubling, 248th doubling, 247th doubling, 245th doubling, 244th doubling, ... and so on down to ... , 6th doubling, 4th doubling, 2nd doubling, and G itself.


The private key is not a point.  It's an integer.  It tells you how many times you need to add G + G + ... to get to the public key. Knowing that, you can use the binary value of k to determine which of the point doublings of G need to be added together as seen above.

If I were going to write software that needed to calculate public keys from private keys VERY QUICKLY, then I'd probably not bother calculating all those doublings every time.  Instead, I'd just pre-calculate the 255 different points that are associated with the doublings and store them somewhere in the software.  Then I could just perform the additions of the points associated with the doublings based on the binary value of the private key.  The average number of additions I'd need to perform for any private key would be 128, and the worst case maximum number of additions would be 256.

is there a common point between the private key and the public key ?

wouaaa thank you

The first thing to understand is that G is a point on the secp256k1 curve, it is not an integer.  Therefore it has 2 values, an X-coordinate, and a Y-coordinate.

The next thing to understand is that when you see it written that the public key is G multiplied by the private key, it is NOT talking about algebraic multiplication.  It is NOT two integers being multiplied by each other. Instead, it is referring to a process known as elliptic curve point multiplication.  This multiplication is performed by adding the Point G to itself repeatedly, where the private key k is the number of times to perform that addition (G + G + G +  ... + G + G). Elliptic curve addition is NOT performed by adding together integers. It's performed by finding a line that passes through the two points and determining the point where that line intersects the curve, then reflecting that point across the x-axis to find the y-value of the other point that has that same x-value.   If a point is being added to itself, then you don't have 2 separate points to connect with a line, so instead of a line passing through both points, you use the line that is tangent to the curve at that point.

So, to calculate G * 3 you would:

1. Calculate the line tangent to the curve that passes through point G, and determine the X and Y coordinates where that line intersects the curve.
2. Find the other point on the curve that shares the same x-value. This new point would be G*2.
3. Calculate the line that passes through both G and G*2, and determine the X and Y coordinates where that line intersects the curve.
4. Find the other point on the curve that shares the same x-value. This new point would be G*3.

If you want to calculate G*4 you have two options...

1. Calculate the line tangent to the curve that passes through point G, and determine the X and Y coordinates where that line intersects the curve.
2. Find the other point on the curve that shares the same x-value. This new point would be G*2.
3. Calculate the line that passes through both G and G*2, and determine the X and Y coordinates where that line intersects the curve.
4. Find the other point on the curve that shares the same x-value. This new point would be G*3.
5. Calculate the line that passes through both G and G*3, and determine the X and Y coordinates where that line intersects the curve.
6. Find the other point on the curve that shares the same x-value. This new point would be G*4.

Or, to save some time, once you have G*2, you could just

1. Calculate the line tangent to the curve that passes through point G*2, and determine the X and Y coordinates where that line intersects the curve.
2. Find the other point on the curve that shares the same x-value. This new point would be G*4.

If you want to calculate G*15, you could...

1. Calculate the line tangent to the curve that passes through point G, and determine the X and Y coordinates where that line intersects the curve.
2. Find the other point on the curve that shares the same x-value. This new point would be G*2.
3. Calculate the line that passes through both G and G*2, and determine the X and Y coordinates where that line intersects the curve.
4. Find the other point on the curve that shares the same x-value. This new point would be G*3.
5. Repeat this for each new point for a total of 14 calculated lines when you've finally gotten to G*15

Or, to save some time, you could just

1. Calculate the line tangent to the curve that passes through point G, and determine the X and Y coordinates where that line intersects the curve.
2. Find the other point on the curve that shares the same x-value. This new point would be G*2.
3. Calculate the line tangent to the curve that passes through point G*2, and determine the X and Y coordinates where that line intersects the curve.
4. Find the other point on the curve that shares the same x-value. This new point would be G*4.
5. Calculate the line tangent to the curve that passes through point G*2, and determine the X and Y coordinates where that line intersects the curve.
6. Find the other point on the curve that shares the same x-value. This new point would be G*8.
7. Calculate the line that passes through both G*8 and G*4, and determine the X and Y coordinates where that line intersects the curve.
8. Find the other point on the curve that shares the same x-value. This new point would be G*12.
9. Calculate the line that passes through both G*12 and G*2, and determine the X and Y coordinates where that line intersects the curve.
10. Find the other point on the curve that shares the same x-value. This new point would be G*14.
11. Calculate the line that passes through both G and G*14, and determine the X and Y coordinates where that line intersects the curve.
12. Find the other point on the curve that shares the same x-value. This new point would be G*15.

Same result, but only need to calculate 6 lines instead of 14.

The bigger k is, the more time that you save by using the doubling and adding together some of those doubled points in place of iterating over every single addition of G.

I will make an example to see if I understood

example k = 0c1c14 = 1100 0001 1100 0001 0100

g*8 + g*4 + g + g .......

is this it ?

Through repeated doubling, and selectively adding G to the result based on the bits of K.

For example, if k was 0b1101 = 13, first you'd take G, multiply it by 8 (because left-most bit is 1), then you add it to G*4 (next bit is 1), then to G (because next bit is 0 followed by 1).

in simple terms, it's done like this:

G      <===> 1 101
2G+G     <===> 1 01
4G+2G   <===> 0 1
8G+4G+G   <===> 1

Each iteration, the entire result is doubled, and if the next bit is 1, a G is added.

Note: This algo is vulnerable to side-channel attacks. Other algorithms such as Montgomery Ladder don't have this flaw.

excuse me for this confusion I just want to know how to calculate k*G

the calculation written in all letters

That's kinda nonsense. By reading this, I understand that you're multiplying k with G as an uncompressed public key and then you add G as a compressed public key which isn't valid.

---

So, let's focus on the title's question;

Now, that's not a good wording. One may understand that you're asking how can you multiply a number with G. Another may understand that you want to know how G was chosen. Judging by the post's content, I've no idea what you wanna know. Could you describe what's your problem?

G_uncompresssed =  "0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"

G_compressed = "0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798"

k = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
G = Point(gx, gy, curve=secp256k1)

K = k*G =====> K = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855*0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C 4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8+0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798