if my private key is 123456789123456789, doesn't that mean I have to dot G point that many times to generate my pubkey? there must be a shortcut to generate pubkey, otherwise the time complicity of generating the pubkey is the same compare to brutal force from trying from 1 to k? Am I missing anything here?

enter image description here

according to the article here: https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

it looks like generating pubkey from a random generated private key(which could be a 32 bytes BigInteger) requires to dot many times = integer value of the private key. which is impossible considering the key size for the private key is 2^256(32 bytes key space).

  • This sounds exactly like what someone with a private key of 123436789123456789 would say... May 24 '21 at 17:43

There are a number of more efficient algorithms to compute the multiplication than just the naive method described. A simple one is double-and-add where the point is repeatedly doubled and then added with previous doublings in order to calculate the final public key. There are a number of more complicated methods which are more efficient.

You can read about these on Wikipedia.

  • that's exactly what I was hoping for. thank you.
    – linehrr
    May 11 '18 at 12:59

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.