2

I've been looking into Elliptic Curve Cryptography, in particular the SECP256K1 spec which is used in Bitcoin and Ethereum. So I understand that the Generator point G is fixed based on the spec and that a 256-bit private key (privKey) is (ideally) truly randomly selected from 1 to 1.157920892373162e+77. The public key (pubKey) is derived from the private key such that the public key is privKey*G where this includes point addition and point doubling operations.

Now what I haven't seemed to figure out yet is that there is a fixed entrance point G which any adversary would need to start at to try and decipher a private key from a public key (assuming a partial rainbow table of values is not used).

So wouldn't that mean the largest value for the private key, which is the furthest amount of steps away from calculating (i.e. 1.157920892373162e+77), is the most secure?

Hence wouldn't private keys below a certain threshold be considered compromised e.g. private keys in the range of 0-1000 for example?

I feel like there is something I'm missing here, any help is appreciated!

Improve this question

1 Answer 1

Reset to default
6

If people in general would more often pick lower integers as private keys than larger integers, then it would be a good strategy for an attacker to start with lower integers.

However, the opposite also holds. If people would more often pick larger numbers, then atackers would ideally start at the end and work their way backwards.

In practice, no such bias exists. As long as people use decent proper random number generation, every integer is just as likely as any other, and it does not matter in what order an attacker tries things. He'll need to go through half of private key range on average regardless.

So no, there is no minimum number to start at. Yes, you have an extremely small chance of picking a number between 1 and 1000. But similarly you have an equal chance to pick a number between 76136428194729137 and 76136428194730136. An attacker has no reason to think you're more likely to pick something between 1 and 1000, so why would an attacker start at?

Also, whenever the attacker has the public key, there exist far faster (but still completely infeasible) algorithms to find the private key. These algorithms inherently operate in random order, so it does not matter.

Improve this answer
3
  • thank you for the well explained answer, I stupidly thought that the Generator point had to be the starting point. In other words I didn't recognize how shortcuts could be made through the range of values using the double and add method and hence an adversary could quite easily start from almost anywhere in that range. This made sense as only being able to use the point addition operation would cause key generation to take a huge amount of time. Silly me, still learning I suppose!
    – Malapeno
    Commented Apr 1, 2018 at 1:43
  • Just a quick question, with the point doubling operation I can skip through the range of multiples as follows: 1*G -> 2*G -> 4*G -> 8*G -> 16*G .... and so on. Am I correct i saying this?
    – Malapeno
    Commented Apr 1, 2018 at 1:45
  • 1
    Yup, absolutely. In practice multiplying a point with a number is done through a variant of a double-and-add algorithm that computes subsequent powers of 2, and adds the ones that have a 1 in the bit representation of the scalar together.
    – Pieter Wuille
    Commented Apr 6, 2018 at 1:29

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.