6

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

  • 2
    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
  • Try royalforkblog.com – 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
0

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

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.