1

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).

Improve this question
1
  • This sounds exactly like what someone with a private key of 123436789123456789 would say...
    – Hamish Gibson
    Commented May 24, 2021 at 17:43

1 Answer 1

Reset to default
3

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.

Improve this answer
1
  • that's exactly what I was hoping for. thank you.
    – linehrr
    Commented May 11, 2018 at 12:59

Your Answer

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

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