2

I understand that the public key q is generated by the point addition of g (some secp256 k1 constant) u times such that u is a big number (private key). This process can be simplified in this diagram below.

Hence the formula follows q=u*j

enter image description here But why cant I use this diagram below and trace back the public key point to the point of the private key by following the tangents back to the original point. I'm sure I could do this in desmos-graphing or something using some pretty simple linear algebra.

2 Answers 2

1

The elliptic curve secp256k1 is defined over the finite field Zp. All the coordinates are 256-bit integers, and all the point additions and coordinates are subject to modulo p.

The large space of numbers and discontinuous nature of elliptic curves makes it infeasible to directly perform a factorization as you posit.

1
  • Ok, that sums it up perfectly.
    – Jamo
    Jun 23, 2022 at 11:25
5

If you naively implement this G * G * G...* G method, you will have to perform an enormous number of operations until get your public key. For instance, if your public key is 2^128, you need to add G to itself 2^128 times, this is computationally unfeasible. However, there is a more optimized algorithm for this, called Double and Add, which computes the public key with O(n) Double and Add step, where n is the bit length of your private key.
However, as far as we know, there is no Deterministically Polynomial Time algorithm to go in the other way. If you go naively again, you'll subtract G from your public key 2^128 times in the above example, until you're left with just G. Again, unfeasible. There is a better algorithm, but is still sub-exponential, and takes an average of 2^128 operations to succeed in secp256k1 (technically O(srqt(n)), where n is the curve order).
The short hawser is: Yes, you can reverse it, but for cryptographically secure keys, you'll need a WHILE until you succeed.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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