Is it possible via brute force to derive a private key from a public key (such as a website's SSL certificate)? If so, how much computing power would you need to make it feasible, compared to say, current supercomputers? I thought it involved factoring prime numbers, or a similar function that's easy to compute forward, but not mathematically possible (to our current understanding) to compute in reverse, reducing cracking to a brute force scenario.
2
-
2Possible, yes, just as you say. Which reduces your question to "how much computing power" which is not something succinctly answerable.– schroeder ♦Mar 25, 2014 at 22:34
-
I think it would be answerable... It is similar to "How long would it take to brute force a SHA-1 password hash assuming the password was eight characters long?". Except substitute hash for RSA private key, eight characters for 4096 bits.– JohnMar 26, 2014 at 14:03
Add a comment
|
1 Answer
I think you are confusing quite a few things here:
First of all: There are only very few crypto schemes that are perfectly secure from an information theoretic standpoint. One of these schemes is the One-time pad. One might argue that Quantum cryptography is a field that looks promising in this regard, too. However, none of these are practical and are only used by secret agencies or universities researching the topic.
In practice we are stuck with algorithms that are computationally secure. This basically includes all the things you usually have in mind when talking about cryptography, e.g. AES, RSA, DH, ECC. When the key sizes get big enough, it is infeasible with our current understanding of mathematics and technology to come up with a computer able to crack these schemes. Some of these schemes are prone to theoretical attacks based on quantum computers, although this doesn't yet matter in practice. Nevertheless there are algorithms good enough to withstand even these sort of attacks by the sheer complexity of the calculations involved.
I thought it involved factoring prime numbers, or a similar function that's easy to compute forward, but not mathematically possible (to our current understanding) to compute in reverse, reducing cracking to a brute force scenario.
Factoring prime numbers concerns RSA, which is probably the most prevalent public key crypto system used in SSL/TLS. It is true that in theory it can be done, but it is not feasible in practice, at least when the generated keys are good enough. There have been quite a few instances in the past, where it turned out the key creation process wasn't as random as thought, making it possible to guess the private key. I recommend you to watch the following lecture from Daniel J. Bernstein, Nadia Heninger and Tanja Lange, if you want to get funny insights into how RSA can be broken in some cases.
Other schemes, such as DH are based on a completely different set of problems, e.g. the discrete logarithm problem. This has nothing to do with factoring primes, but is thought to be similarly hard, which is the reason why the key sizes are quite the same for both set of problems, e.g. 1024 - 4096 bits.
Elliptic curve cryptography (ECC) is yet another field of cryptography, that is based on a generalization of the discrete logarithm problem with the advantage that the involved keys are much smaller, while the level of security remains the same.
In essence: Yes, most of our current day crypto systems can be broken in theory, but it doesn't matter for practical purposes. With our current understanding of the math and technology involved, even government agencies like the NSA can't build computers powerful enough to crack these schemes in this way.
