-1
$\begingroup$

I am generating ECC private keys. however I noticed that since ECC private key is just a BigInteger. e.g. spec256k1 says private key is anywhere between [0~2^256-1].

my question is, if everyone is using Random(32) to generate a 32bytes private key, there is not likely but still possible situation that 2 people could generate the same private key. therefore also same public key.

so if this happens on blockchain like Bitcoin or Etheruem, does that mean those 2 people are in theory sharing the same account? or wallet address?

maybe I am missing some details here. Please guide me.

Edit:

thanks for everyone's answer here.

the reason why I was asking this is because first I wonder if there is any protection against collision in the system. however, if there is, and you are told you had a collision, that basically means you figured out someone else's private key...

second reason is, I was considering generating a long(64bits) and then cast into BigInteger(32bytes) to be the private key. however, that will have a much higher collision chance due to the fact that I will only have a private key space of 2^64.

$\endgroup$
  • $\begingroup$ I believe that is correct, not likely but possible $\endgroup$ – Richie Frame May 17 '18 at 0:34
  • $\begingroup$ If you pick 64 bits uniformly at random and the remaining 192 as zero, you are practically guaranteed never to get someone else's key, but you'll likely get a collision after a billion keys, and someone else can probably guess one of your keys with a large but plausible distributed computing effort. $\endgroup$ – Squeamish Ossifrage May 17 '18 at 15:17
  • $\begingroup$ @SqueamishOssifrage actually, if you knew the format of the keys (i.e. which bits were zero), then someone could run a Big Step/Little Step attack, and recover your key with a laptop (circa $2^{32}$ space and time) $\endgroup$ – poncho May 17 '18 at 15:40
4
$\begingroup$

Assume that there are $2^{50}$ keys out there. Then calculating one of these keys by chance is $2^{50} \over 2^{255}$ for each calculation or a chance of one in $2^{205}$. Now say that you generate $2^{64}$ keys then you'd still only have a chance of one out of $2^{91}$ of hitting the right key.

Note that making sure that you hit a key would however require $2^{50}$ tests, and knowledge of $2^{50}$ operations by the public key of course. To test a single key the situation is significantly worse, the chance of finding it after $2^{64}$ tries is only one out of $2^{191}$.

Chances of hitting the right key increase somewhat if you make sure you make sure that you don't generate the same key again. For instance you could start at a specific value and then simply test each following value. But that won't increase your chances by much and the calculation is too hairy to do here.

This is always what cryptography relies on: that you cannot just guess the private key. There is no cryptosystem to protect against that. And there doesn't need to be because the chance of generating a matching private key is negligible.

And think about it, I could guess the value of a coin as well. There is no protection against that either.


Note that a chance of one in $2^{91}$ is one in 2475880078570760549798248448 or one in 2 octillion 475 septillion 880 sextillion 78 quintillion 570 quadrillion 760 trillion 549 billion 798 million 248 thousand 448 (using the short scale).

$\endgroup$
  • $\begingroup$ In other words, you are 23000 times more likely to win the full Powerball jackpot 4 times in a row than you are of generating the same key as another person $\endgroup$ – Richie Frame May 17 '18 at 0:19
  • $\begingroup$ @RichieFrame That's probably not true. The Powerball jackpot is probably more gameable than a uniform random 256-bit RNG! (bugs in the RNG aside) $\endgroup$ – Squeamish Ossifrage May 17 '18 at 0:42
  • $\begingroup$ To be more precise, if there are $x$ keys generated, the probability that two of them will happen to be the same is approximately $x^2 / 2^{257}$ (assuming $x \lll 2^{128}$). If we assume $x = 2^{50}$ bitcoin keys are generated worldwide (that's about 100,000 per person on the planet), that gives us a collision probability of about $2^{-157}$; considerably less than the value you give $\endgroup$ – poncho May 17 '18 at 0:47
  • $\begingroup$ I assumed that there would be $2^{128}$ bitcoin keys, which is computationally infeasible by itself (never mind practical). Searching for a collision is kind of pointless if you cannot use it afterwards. $\endgroup$ – Maarten Bodewes May 17 '18 at 1:47
  • $\begingroup$ Actually, if there are $2^{128}$ bitcoin keys generated, the probability that there is a repeat somewhere in there is pretty decent. Of course, finding that pair might be a tad problematic... $\endgroup$ – poncho May 17 '18 at 2:38

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.