2
$\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.

Improve this question
$\endgroup$
4
  • $\begingroup$ I believe that is correct, not likely but possible $\endgroup$
    – Richie Frame
    May 17, 2018 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, 2018 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, 2018 at 15:40
  • $\begingroup$ Technically ECDSA does not allow privatekey == 0 or >= the order of the generator and group; see crypto.stackexchange.com/questions/30269/… . Since the privatekey normally should be random, and the chance of a random value violating these constraints is tiny, in practice people sometimes don't bother with them. Nevertheless I would consider someone writing a spec who doesn't even mention them ignorant or negligent, and not trust any crypto code they produce. $\endgroup$
    – dave_thompson_085
    Jan 27, 2020 at 3:03

2 Answers 2

Reset to default
8
$\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).

Improve this answer
$\endgroup$
8
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 2:38
0
$\begingroup$

It's worse than that. There can be a collision even using different private keys.

Each (standard) Bitcoin transaction to you is sent to a 160-bit hash of your public key (a.k.a., your address). Anyone who owns a public key that has same hash will be able to spend your coins. So that's a 80 bits of security, since only half of the keyspace has to be searched, on average, before a match is found [EDIT: a 50% probability of finding match between two previously searched keys, not necessarily ones on the blockchain. See comments.]

The Bitcoin blockchain has ~30 million (25 bits of) public key hashes available to be spent right now. To find a match for any of them, this drops your search space by 25 bits down to 135 bits, leaving 67.5 bits of security "overall".

If two different public keys produce the same hash, and both sign for the same UTXO at the same time, it would be up to the miner to choose which one makes it in.

Another bit or so of security is lost because the public keys are hashed twice to make the address, so it's possible for the first hash to be different yet produce a matching second hash.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 2^80 only gives you a collision which allows you to steal from yourself, not very useful. Hitting someone else's key requires a preimage at 2^159 single-target, reduced to about 2^134 for multi-target as you correctly say. Unless quantum :-) $\endgroup$
    – dave_thompson_085
    Jan 27, 2020 at 3:08
  • $\begingroup$ @dave_thompson_085 Thanks. Very good to know! :)) $\endgroup$
    – dsharhon
    Jan 28, 2020 at 0:18

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.