How to calculate the public key, compute point P and create signature using ECDSA?

Question

I'm quite new to the intricacies of bitcoin cryptography and ECDSA and elliptic curve cryptography has me quite stymied. I am faced with a curve with the equation: y^2 = x^3 + 7 of order N=39 with subgroups of the order n = 13 and generator point G = (8,1). We also sign the message J with the private key 8. I'm supposed to figure out the public key, point P using a random number i=5 and also create the signature (r,s).

For the public key, I believe I understand the bare basics. Using elliptic curve multiplication, one can gain the public key using Kpub = k_priv * G. Using the doubling method, with my example, this would be 2 x G = 2G, 2 x 2G = 4G, 2 x 4G = 8G. But I'm very confused as to how to exactly compute this. I could not find any calculators online that could help me understand the steps either.

As for the Point P generation with random number i=5, I'm completely lost and the same goes for the signature.

Any help in calculation, or better yet, an explanation as to how this works would be highly appreciated!

Thanks.

Answer 1

The double and add method uses each number's binary representation to perform the computation. Taking a big-endian representation of a number, from left to right, if the n-th bit is 1, then you double the current value and add the original element to it. If it's 0, you just double.

In your example, where the scalar is 8: 8 is 1000 in binary, we start from the left. The first bit is not relevant, you start by the second one. You start with G, with is the same as private key 1. The second bit (left to right) is 0, so you just double. 1G + 1G = 2G
The third bit is also 0, just double again. 2G + 2G = 4G
The fourth bit (and last one at the right) is also 0, you make a final double. 4G + 4G = 8G
At the end, you get 8G, but making only 3 additions!

For i=5, 5 is 101 in binary. Start with G again:
The second bit is 0, just double: G + G = 2G
The third bit is 1, so you double and add G. 2G + 2G = 4G, 4G + G = 5G

To double means take wherever point and add it to itself, as A + A = 2A. Each addition is a standard elliptic curve point addition, inside your group.