0

One way to defeat public key encryption would be to make a list of all public and private key pairings. For 128-bit and 256-bit keys, there are lots of possible pairs:

2^128 = 3.40e38
2^256 = 1.16e77

Google might have 15 exabytes of data storage (1.7e17). They'd have to increase that capacity by more than 10 billion to store even just the 128-bit keys (which are perhaps not used much).

On the other hand, it's a problem of scale rather than computational difficulty. Is there anything to stop the NSA (or its international counterparts) from simply brute-forcing it? How would we know?

adam.baker
  • 657
  • 6
  • 9
  • 4
    I'm voting to close this question as off-topic because this question seems fundamentally flawed, and some parts can't be answered. I think it would generate more discussion than anything – RoraΖ Apr 05 '16 at 11:22
  • It's irrelevant to ask about the possibility of a brute force attack? – adam.baker Apr 06 '16 at 03:16
  • I'm saying it's off-topic to ask a question that will generate more debate than a concrete answer. – RoraΖ Apr 06 '16 at 11:35
  • Well, I guess we can disagree about that. It's a question about numbers and estimating the computing power of potential adversaries. The answers address the issues, in my opinion. – adam.baker Apr 06 '16 at 11:39

2 Answers2

4

I think you have a fundamental misunderstanding of this aspect of crypto. Firstly, public/private keypairs are not bruteforced, those are typically factored. And they come in sizes much higher than 128 or 256 bits. They are much more complex to understand than symmetric crypto. You seem to be talking about symmetric keys, which do not come in "key pairs" but are single keys that work both ways.

Secondly, 2128 is much more than 3.40e28. I'm not sure where you got that number. The fact is, there is no possible way to store that much. To put it into perspective, there are only roughly 1080 proton masses in the entire universe, which means that even if every single proton and neutron stored a single bit, we could only store roughly 1080 bits of data. Even if all the grains of sand on the earth could store a bit of data, you still couldn't store 2128 in it.

You also have to remember that each key is not one byte, but 32 bytes (for 256 bit keys) or 16 bytes (for 128 bit keys), which adds up to a lot more, though even if it were a single bit each, there would be no possible way to store it all.

There are many questions and answers all over the internet explaining how long it would take to look through even a 2128 keyspace, and why it is so utterly impractical with classical computers. I suggest you read through some of those.

forest
  • 66,706
  • 20
  • 212
  • 270
  • As Lekensteyn pointed out below, 2^128 = 3.40e38, which is <<1e80. It is commonly stated that IPv6, which uses 128-bit addresses, gives every grin of sand on Earth an IP, which gives you the correct scale. Obviously, it is still infeasible to store the keys, but not impossible if we have access to resources outside Earth. – billc.cn Apr 05 '16 at 14:46
  • Can “brute force” not be used to mean “trying all the possibilities”, e.g., looking up the private key that goes along with the public key for all possible combinations? – adam.baker Apr 06 '16 at 03:23
  • What does "look up the private key that goes along with the public key" mean? All possible combinations of public keys would be impossible to store anyway. And no, verifying that a private key pairs with a given public key is not considered brute forcing. Brute forcing is by definition the exhaustive search of a finite keyspace. – forest Apr 06 '16 at 03:27
3

2^128 = 3.40e38 (not 3.40e28). Let's assume that the XKCD assumption is right and 15 EB (1.5e19) is reasonable. Then you are still 19 orders of magnitude away from storing all 2^128 items.

If brute-forcing is already not feasible, then enumeration of all possible combinations for storage is equally hard.

Lekensteyn
  • 6,088
  • 6
  • 39
  • 62
  • 2^128 is 3.40e38 items each of which needs at least 8 bytes storage and probably some overhead to be usable (if usability were actually possible) so that's roughly one more order. – dave_thompson_085 Apr 10 '18 at 04:10