<p>No.</p>

<p>A rainbow table is simply a memory-cpu tradeoff that allows you to find preimages of a function faster by having a precomputed table with some of the entries.</p>

<p>In order to construct a rainbow table for bitcoin private/public keys, you still have to first iterate through all the keys at least once. It doesn't matter that only part of the keypairs will end up in your rainbow table - you still have to go through all them.</p>

<p>That is an impossible task. There are 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336 valid private keys to go through. To put that in perspective: if you would put a computer on every square micrometer of earth (1/1600th of the cross section of a human hair) that can compute as many public keys per second as the entire Bitcoin mining network does hashes per second at the time of writing (4 exahash/s), it would take you 120000 times the age of the universe to go through all keys.</p>

<p>And, even if somehow you had an oracle that could give you the rainbow table, it would need to be impossibly large to make cracking private keys practical. If your table had a trillion entries, it would only make cracking a trillion times faster. That's still utterly impossible.</p>

CC BY-SA 3.0
2017-05-12T11:46:13.543Z
High up in the north, in the land called Svithjod, there stands a rock. It is a hundred miles high and a hundred miles wide. Once every thousand years a little bird comes to this rock to sharpen its beak.

[When the rock has thus been worn away](http://www.maths.manchester.ac.uk/~cds/articles/svithjod.html), then Pieter's computation will be complete.
Russell O'Connor
CC BY-SA 3.0
2018-02-19T04:04:36.480Z
Yeah, but what if Bitcoin is around in 120000 times the age of the universe? I'm worried because we might have a dip.
Christian Findlay
CC BY-SA 3.0
2017-05-12T05:37:59.543Z
2017-05-12T05:37:59.543Z
Pieter Wuille
<p>Thanks for the large bitcoin collider (LBC) link. Had a long look at it but it's way over my head. Seems they are finding private keys regularly that fit active accounts with some BTC on them. That's an an alarming sight. Especially since this is still running on a tiny scale.</p>

<p>Then I came across this excellent post:
<a href="https://www.reddit.com/r/btc/comments/65mjm3/bitcoin_wallets_under_siege_from_collider_attack/dgbudsk/" rel="nofollow noreferrer">https://www.reddit.com/r/btc/comments/65mjm3/bitcoin_wallets_under_siege_from_collider_attack/dgbudsk/</a>
As to why the LBC seems to have already found private keys to active accounts, he answered:</p>

<blockquote>
  <p>The wallets they've attacked so far are not generic random-private-key
  bitcoin wallets as the usual ones, but they've been specifically
  crafted to be broken. They belong mostly to the puzzle transaction
  which contains many "easy" private keys.</p>
</blockquote>

<p>What does that mean?</p>

<p>I'm not entirely sure these are all talking about the same approach/problem, but I think it's similar in the end: How hard is it to find a private key to a specific active bitcoin address or any of the active bitcoin addresses? I hope dyoniziz from reddit is correct.</p>

CC BY-SA 3.0
2017-05-06T02:11:51.647Z
LBC will only ever find keys that were generated with insecure random number generators. Anything else requires astronomical amounts of computation power which the technology is designed to withstand, so don't let it scare you.
Pieter Wuille
CC BY-SA 3.0
2017-05-07T10:31:54.253Z
Can you elaborate? I don't understand why keys generated with random number generators would be more likely to be found by the LBC? I thought LBC just goes through the possible keys methodically, from start to finish so to speak?
John
CC BY-SA 3.0
2017-05-07T16:06:07.280Z
Things generated with insecure random number generators are easier to find by trying to mimick the algorithm they used. A good random number generator produces numbers that are indistinguishable from random, so every search pattern is as good as any other. And the key space is so massively large that it is impossible to ever hit one by chance again.
Pieter Wuille
CC BY-SA 3.0
2017-05-12T06:57:35.143Z
@PieterWuille "it will *only ever*" – when they calculate for long enough, the will find everything. we will see how fast computing can be in our livetime and if bitcoin breaks over it. I also feel quite comfortable right now, but that *can* change, we have to face that.
vv01f
CC BY-SA 3.0
2017-05-12T07:30:14.357Z
Good luck, then.
Pieter Wuille
CC BY-SA 3.0
2017-05-06T01:34:53.750Z
2017-05-06T01:34:53.750Z
John
<p>Lets say, I have 101 private keys generated by a pseudo-RNG, but I lost one.  Theoretically, I think its possible to use 100 private/public pairs to crack the missing one.  Because , while the actual number space is crazy large, the pseudo-RNG number space is limited by the floating point space of the hardware itself.  Also, I think it is possible to create a rainbow table from the 100 which makes it more accessible.  If I am wrong, someone please explain.</p>

CC BY-SA 4.0
2021-02-03T02:59:29.837Z
I downvoted. This answer is completely wrong. A properly designed PRNG does not let anyone derive information about the state or other outputs given a known outputs; it would be completely broken if that was the case. No floating point is used anywhere. Rainbow tables are completely useless as I explain in my own answer below.
Pieter Wuille
CC BY-SA 4.0
2021-02-04T04:20:15.550Z
I have a college textbook, "Making and Breaking Codes", written by Paul Garrett and it is 4th year text in mathematical encryption degree which says otherwise.   
Some old ones are crackable. There's also PRNG cracking software such as Mandarino which has allowed some people to make money cheating online casinos.  The internal state of the PRNG supposedly can be discovered since it is actually a deterministic algolrithm.  So, being properly designed would include some random data such as CPU temp, fan speed, mouse movements etc.  But PRNG from the year 2000 might not have included that.
jalalideen
CC BY-SA 4.0
2021-01-30T08:10:34.530Z
2021-01-30T08:10:34.530Z
jalalideen
<p>indeed that would theoretically be possible. such a table luckily is very large. for more read e.g. on the <a href="https://lbc.cryptoguru.org/" rel="nofollow noreferrer">large bitcoin collider</a>. if an active address means that is spends money, then the pubkey is revealed which makes it easier to attack. as long as an address only received money it is protected better by the 2nd hashing layer.</p>

<p>lbc can be ignored but they walk systematically through the keyspace from small difficulty to large by entropy. easy to find keys are just a bait to have more people involved. @Pieter: of course weak RNG is a problem, but that was not in question; we better get some open hardware standards for TRNG.</p>

<p>interestingly people vote this down. we have to face it: there are problems with the implementation of bitcoin apart from just scalability. the hashing was not well thought through and the ecc algo (Secp256k1: T=(p,a,b,G,n,h); <strong>a=0</strong>, b=7 … h=1. see <a href="https://media.ccc.de/v/31c3_-_6295_-_de_-_saal_2_-_201412281645_-_krypto_fur_die_zukunft_-_ruedi#video&amp;t=1618" rel="nofollow noreferrer">slide by ruedi</a>) got the parameter a nulled without any good reason (performace is not a good argument at all in means of crypto). cryptography does not honor weaknesses, small they may be.</p>

CC BY-SA 3.0
2017-05-12T06:06:43.403Z
No change to the hashing algorithm would make keys generated with an insecure RNG secure. I have no clue what ecc parameters you're talking about.
Pieter Wuille
CC BY-SA 3.0
2017-05-12T06:45:40.373Z
@PieterWuille 1st nobody claimed, if so point me there plz, and 2nd you hopefully know. math is not secret: [ruedi on 31c3](https://media.ccc.de/v/31c3_-_6295_-_de_-_saal_2_-_201412281645_-_krypto_fur_die_zukunft_-_ruedi#video&t=1618); Secp256k1: `T=(p,a,b,G,n,h)`; **a=0**, b=7 … h=1.
vv01f
CC BY-SA 3.0
2017-05-12T07:29:05.370Z
Yes, a=0 is a conscious choice that makes certain operations faster. There are no known attacks against that choice.
Pieter Wuille
CC BY-SA 3.0
2017-05-12T08:22:58.363Z
I know, you know, but is no good argument still. Go ask the cryptographers around, they will tell you like that one did if they are sane. Altering crypto-implementation for performance is simply one of the things you should not do if you have the choice.
vv01f
CC BY-SA 3.0
2017-05-12T14:36:07.620Z
Nothing was altered. Secp256k1 was an elliptic curve standardized by the SECG before Bitcoin existed. Satoshi just picked one curve before EC was cool, and ended up picking a different standard than what the rest of world went with. It was an unusual choice at worst, but not a bad one
Pieter Wuille
CC BY-SA 3.0
2017-05-13T19:35:13.423Z
I've downvoted, because this answer doesn't provide useful information. "Theoretically possible" should be properly quantified and "problems with the implementation of bitcoin" should be substantiated with credible evidence, because as presented here the post completely overstates the actual possibility of such an attack and could alarm uninformed readers.
Murch
CC BY-SA 3.0
2017-05-05T17:20:40.377Z
2017-05-12T08:23:43.250Z
2017-05-12T08:23:43.250Z
vv01f
<p>I understand that the public key is kept hidden until a bitcoin transaction is made, at which point the public key has to be revealed to prove that you created the transaction with your private key. Until then, only a hash of your public key is ever shared, know as your bitcoin address. </p>

<p>Once my public key is known, would it be possible for someone to lookup my private key in a rainbow table ? </p>

CC BY-SA 3.0
2017-05-13T19:38:54.297Z
Such a rainbow table already exists at [directory.io](http://directory.io). ;) However, you'll find that the site is a tongue-in-cheek joke explained by Pieter's answer below.
Murch
CC BY-SA 3.0
2017-05-29T10:41:50.463Z
Technically, directory.io is not a rainbow table as it computes the keys on the fly. It's close to impossible to store all keys in a table.
q9f
<security><private-key><public-key>
Can rainbow tables be used to find private keys from public keys?
Chris
# Can rainbow tables be used to find private keys from public keys?

(Asked by: username_0 on 2017-05-05)

I understand that the public key is kept hidden until a bitcoin transaction is made, at which point the public key has to be revealed to prove that you created the transaction with your private key. Until then, only a hash of your public key is ever shared, know as your bitcoin address.

Once my public key is known, would it be possible for someone to lookup my private key in a rainbow table ?

**Tags:** security, private-key, public-key

> **Comments:**
> **username_1**: Such a rainbow table already exists at [directory.io](http://directory.io). ;) However, you'll find that the site is a tongue-in-cheek joke explained by username_3's answer below.  
> **username_2**: Technically, directory.io is not a rainbow table as it computes the keys on the fly. It's close to impossible to store all keys in a table.  

---

## 4 answers

### Answer by username_3 on 2017-05-12. Score: 6

No.

A rainbow table is simply a memory-cpu tradeoff that allows you to find preimages of a function faster by having a precomputed table with some of the entries.

In order to construct a rainbow table for bitcoin private/public keys, you still have to first iterate through all the keys at least once. It doesn't matter that only part of the keypairs will end up in your rainbow table - you still have to go through all them.

That is an impossible task. There are 115,792,089,237,316,195,423,570,985,008,687,907,852,837,564,279,074,904,382,605,163,141,518,161,494,336 valid private keys to go through. To put that in perspective: if you would put a computer on every square micrometer of earth (1/1600th of the cross section of a human hair) that can compute as many public keys per second as the entire Bitcoin mining network does hashes per second at the time of writing (4 exahash/s), it would take you 120000 times the age of the universe to go through all keys.

And, even if somehow you had an oracle that could give you the rainbow table, it would need to be impossibly large to make cracking private keys practical. If your table had a trillion entries, it would only make cracking a trillion times faster. That's still utterly impossible.

> **Comments:**
> **username_4**: High up in the north, in the land called Svithjod, there stands a rock. It is a hundred miles high and a hundred miles wide. Once every thousand years a little bird comes to this rock to sharpen its beak.  [When the rock has thus been worn away](http://www.maths.manchester.ac.uk/~cds/articles/svithjod.html), then username_3's computation will be complete.  
> **username_5**: Yeah, but what if Bitcoin is around in 120000 times the age of the universe? I'm worried because we might have a dip.  

---

### Answer by username_6 on 2017-05-06. Score: 2

Thanks for the large bitcoin collider (LBC) link. Had a long look at it but it's way over my head. Seems they are finding private keys regularly that fit active accounts with some BTC on them. That's an an alarming sight. Especially since this is still running on a tiny scale.

Then I came across this excellent post:
<https://www.reddit.com/r/btc/comments/65mjm3/bitcoin_wallets_under_siege_from_collider_attack/dgbudsk/>
As to why the LBC seems to have already found private keys to active accounts, he answered:

> The wallets they've attacked so far are not generic random-private-key
> bitcoin wallets as the usual ones, but they've been specifically
> crafted to be broken. They belong mostly to the puzzle transaction
> which contains many "easy" private keys.

What does that mean?

I'm not entirely sure these are all talking about the same approach/problem, but I think it's similar in the end: How hard is it to find a private key to a specific active bitcoin address or any of the active bitcoin addresses? I hope dyoniziz from reddit is correct.

> **Comments:**
> **username_3**: LBC will only ever find keys that were generated with insecure random number generators. Anything else requires astronomical amounts of computation power which the technology is designed to withstand, so don't let it scare you.  
> **username_6**: Can you elaborate? I don't understand why keys generated with random number generators would be more likely to be found by the LBC? I thought LBC just goes through the possible keys methodically, from start to finish so to speak?  
> **username_3**: Things generated with insecure random number generators are easier to find by trying to mimick the algorithm they used. A good random number generator produces numbers that are indistinguishable from random, so every search pattern is as good as any other. And the key space is so massively large that it is impossible to ever hit one by chance again.  
> **username_7**: @username_3 "it will *only ever*" – when they calculate for long enough, the will find everything. we will see how fast computing can be in our livetime and if bitcoin breaks over it. I also feel quite comfortable right now, but that *can* change, we have to face that.  
> **username_3**: Good luck, then.  

---

### Answer by username_8 on 2021-01-30. Score: -1

Lets say, I have 101 private keys generated by a pseudo-RNG, but I lost one. Theoretically, I think its possible to use 100 private/public pairs to crack the missing one. Because , while the actual number space is crazy large, the pseudo-RNG number space is limited by the floating point space of the hardware itself. Also, I think it is possible to create a rainbow table from the 100 which makes it more accessible. If I am wrong, someone please explain.

> **Comments:**
> **username_3**: I downvoted. This answer is completely wrong. A properly designed PRNG does not let anyone derive information about the state or other outputs given a known outputs; it would be completely broken if that was the case. No floating point is used anywhere. Rainbow tables are completely useless as I explain in my own answer below.  
> **username_8**: I have a college textbook, "Making and Breaking Codes", written by Paul Garrett and it is 4th year text in mathematical encryption degree which says otherwise.    Some old ones are crackable. There's also PRNG cracking software such as Mandarino which has allowed some people to make money cheating online casinos.  The internal state of the PRNG supposedly can be discovered since it is actually a deterministic algolrithm.  So, being properly designed would include some random data such as CPU temp, fan speed, mouse movements etc.  But PRNG from the year 2000 might not have included that.  

---

### Answer by username_7 on 2017-05-05. Score: -3

indeed that would theoretically be possible. such a table luckily is very large. for more read e.g. on the [large bitcoin collider](https://lbc.cryptoguru.org/). if an active address means that is spends money, then the pubkey is revealed which makes it easier to attack. as long as an address only received money it is protected better by the 2nd hashing layer.

lbc can be ignored but they walk systematically through the keyspace from small difficulty to large by entropy. easy to find keys are just a bait to have more people involved. @username_3: of course weak RNG is a problem, but that was not in question; we better get some open hardware standards for TRNG.

interestingly people vote this down. we have to face it: there are problems with the implementation of bitcoin apart from just scalability. the hashing was not well thought through and the ecc algo (Secp256k1: T=(p,a,b,G,n,h); **a=0**, b=7 … h=1. see [slide by ruedi](https://media.ccc.de/v/31c3_-_6295_-_de_-_saal_2_-_201412281645_-_krypto_fur_die_zukunft_-_ruedi#video&t=1618)) got the parameter a nulled without any good reason (performace is not a good argument at all in means of crypto). cryptography does not honor weaknesses, small they may be.

> **Comments:**
> **username_3**: No change to the hashing algorithm would make keys generated with an insecure RNG secure. I have no clue what ecc parameters you're talking about.  
> **username_7**: @username_3 1st nobody claimed, if so point me there plz, and 2nd you hopefully know. math is not secret: [ruedi on 31c3](https://media.ccc.de/v/31c3_-_6295_-_de_-_saal_2_-_201412281645_-_krypto_fur_die_zukunft_-_ruedi#video&t=1618); Secp256k1: `T=(p,a,b,G,n,h)`; **a=0**, b=7 … h=1.  
> **username_3**: Yes, a=0 is a conscious choice that makes certain operations faster. There are no known attacks against that choice.  
> **username_7**: I know, you know, but is no good argument still. Go ask the cryptographers around, they will tell you like that one did if they are sane. Altering crypto-implementation for performance is simply one of the things you should not do if you have the choice.  
> **username_3**: Nothing was altered. Secp256k1 was an elliptic curve standardized by the SECG before Bitcoin existed. Satoshi just picked one curve before EC was cool, and ended up picking a different standard than what the rest of world went with. It was an unusual choice at worst, but not a bad one  
> **username_1**: I've downvoted, because this answer doesn't provide useful information. "Theoretically possible" should be properly quantified and "problems with the implementation of bitcoin" should be substantiated with credible evidence, because as presented here the post completely overstates the actual possibility of such an attack and could alarm uninformed readers.  

---

