How to generate a public key from a private key using Elliptic Curve Digital Signature Algorithm

Question

I'm trying to understand the graphical basis that underlies the discreet logarithmic Elliptic Curve Digital Signature Algorithm (ECDSA) introduced in Chapter 4 of "Mastering Bitcoin" by Andreas Antonopolous: https://github.com/aantonop/bitcoinbook/blob/develop/ch04.asciidoc

Andreas says a point in an elliptic curves can be added to itself by drawing a tangent, finding the intersection, then reflecting the new point on the x-axis. This makes no sense to me, but for now I'll just blindly believe. Then K = k * G, where k is the private key, G is a constant "Generator Point" and K is the public key.

Then he shows the attached figure which graphically shows how to get from G to 8G.

1. Is "8" the private key in this example?
2. Given K and G, it doesn't seem like this function would be irreversible. Am I missing something or does it only become irreversible in the discrete logarithmic equivalent.

Answer 1

1. Yes.
2. Imagine that all you can see is the point at G, and the point at 8G. You're trying to determine how many times the point was added. And the number isn't 8, it's somewhere between 1 and 2^256.

Am I missing something or does it only become irreversible in the discrete logarithmic equivalent.

I have no idea what that means; I'll leave that for someone else to answer.

Answer 2

Actually, from what I understood about ECDSA, by reading this blog, in K= k*G, k is not the primary key, it's just a random number. and the x coordinate of K is known as R and using R, k and the private key we determine S.

R = x coordinate(k*G)

S = k^-1 (z + dA * R) mod p

where dA is the private key

Please read that blog to get a good understanding of ECDSA.

Now to determine k from K and G, there's no point subtraction or point division, so we cannot get the random number k directly from K and G by K/G. But as @StephenM347 mentioned in the comment, a brute force attack is possible, but not possible with the current computational power

Answer 3

Is "8" the private key in this example?

Answer: Yes.

Given K and G, it doesn't seem like this function would be irreversible. Am I missing something or does it only become irreversible in the discrete logarithmic equivalent.

Avoiding deeper technical informations, that fucntion infact is reversible. The assumption of its safety is based on the fact that the time to compute the reverse operation is way too much to be practically executed with the current processing power technology.

Anyway any weighting advance in Quantum Computing could represent a further step towards the weakening of the ECDSA elliptic curve based encryption.

As is well known if QC would become a reality in terms of equipments, any encryption algorithm based on the aforementioned method would suddendly become vulnerable with not so much efforts to be spent.

That's why I strongly support cryptocurrencies projects which endorse XMSS signatures instead of ECDSA for the long term quantum resilience. A good example of the last mentioned technology is QRL https://theqrl.org