Can two private keys generate the same (public) Bitcoin address?

Question

I know that private key is generated randomly by wallet. Is it possible that wallet generate the same address which is used in Bitcoin?

In other words: Given two private keys k_a ≠ k_b, is it possible that they both generate the same public Bitcoin address?

Answer 1

Yes, you can have two keys generate the same address.

There are 2^160 possible addresses, and 2^256 possible private keys, so each address corresponds to roughly 2^(256-160)=2^96 private keys. Any of these will generate the same address and thus be able to spend the money owned by that address. Since 2^160 is so large, however, it would take a near-eternity to find any collisions.

Whether two private keys can generate the same public key is another question. I think the answer is yes, but I am not sure on that. The public key in uncompressed form consists of two 256-bit numbers, which are X and Y coordinates on an elliptic curve. However, the compressed form is just the X coordinate plus a bit, from which you can calculate the whole public key. This means the space is (at most) 2^257. Unless there is a one-to-one mapping due to the mathematical properties of the cryptography used, each compressed public key corresponds to roughly 0.5 private keys (with the same distribution you'd get from picking a random number from 1 to 2^257, 2^256 times), so some private keys will collide, while others will not.

Actually finding any pair of different private keys that generate the same public key or address would be quite difficult. Either it would involve a huge amount of computation and/or luck, or it would be due to finding a serious vulnerability in the algorithm(s) used.

Answer 2

private keys above the group order have the same addresses as the keys starting at 0.

0000000000000000000000000000000000000000000000000000000000000000 fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141  1MsHWS1BnwMc3tLE8G35UXsS58fKipzB7a
0000000000000000000000000000000000000000000000000000000000000001 fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364142  1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm
0000000000000000000000000000000000000000000000000000000000000002 fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364143  1LagHJk2FyCV2VzrNHVqg3gYG4TSYwDV4m
0000000000000000000000000000000000000000000000000000000000000003 fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364144  1NZUP3JAc9JkmbvmoTv7nVgZGtyJjirKV1

...

000000000000000000000000000000014551231950b75fc4402da1732fc9bebb fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc  1HtRa3HaTfX4eDrTzkZWfnLD9cZAyhMDEd
000000000000000000000000000000014551231950b75fc4402da1732fc9bebc fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd  1FvN1jJU6kQCub9nQFuJhdfixpBdngxLme
000000000000000000000000000000014551231950b75fc4402da1732fc9bebd fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe  1JHzdjEL4xQ7yifAaQQKAfqPyAN92vfstP
000000000000000000000000000000014551231950b75fc4402da1732fc9bebe ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff  12M4QznuNZH2BRVbLK8SKvNqGTPJpCpST7