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

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.
• How would you imagine going from 2G to G? – David Schwartz Oct 27 '14 at 23:18

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.

• Technically speaking, it's not irreversible. The blind brute force algorithm (pick private key = 1, test, if not the right pub key then increment private key and try again) would work, although the best known algorithm to solve the Elliptic Curve DLP takes roughly O(n^(1/2)) steps, where n is the order of the Elliptic Curve Group. For Secp256k1, that means about 2^128 steps, which is just completely infeasible (until quantum computers become a reality). – morsecoder Oct 27 '14 at 23:47
• Sure, it's actually just generic baby-step giant-step or Pollards Rho method, I think, which are collision algorithms. Pollard Rho is slightly slower but a lot less memory intensive. You can either look those up, or I can send you my honors thesis, which I did on ECC. – morsecoder Oct 28 '14 at 0:41
• – Wizard Of Ozzie Oct 28 '14 at 0:44
• @WizardOfOzzie A good read! I think you meant to link to royalforkblog.com/2014/09/04/ecc – Nick ODell Oct 28 '14 at 0:53
• I'm on Android so can't edit but feel free to delete the wrong link or edit it if I don't do so first! – Wizard Of Ozzie Oct 28 '14 at 2:11

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

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

Is "8" the private key in this example?