Question

I'm taking a course in cryptography, and I would value any comments. This is not too technical a question, but more about directions or strategy in cryptography. My question is, is public key cryptography, for instance, "just" a question of the difficulty of dealing with large integers? I can understand that factoring a product of two large primes is time-consuming. Is there a basic belief that new methods of factoring might be developed, which will lead to breaking some cyphers, or pushing the number-size requirements ever higher? Or do industry pros look more toward ever-faster, ever-large-number-handling capabilities as the most likely future?

Answer 1

If you're asking about the likely future for public key cryptography, then my opinion is that we are likely to see a transition (gradually over the next number of years) from things such as RSA and DH, and into Elliptic Curve Cryptography.

This is because ECC is just more efficient; we know that we can break RSA and DH in subexponential time; that means that as computers get faster, and we need to make the problems more difficult, the modulii that we need to use for RSA and DH get larger a lot quicker than you would naively expect. On the other hand, with ECC, the curve sizes don't grow very much at all. So, instead of going to increasingly large RSA key sizes, I expect that people will gradually transition to ECC (as people become more comfortable with it).

If a new factoring method is found (which, personally, I don't expect), then all that would do is make that transition happen that much faster.

What would be a real game changer would be if someone was able to build a real quantum computer; a large enough one would be able to break RSA and ECC easily. There are public key algorithms that don't appear to be solvable by a quantum computer (at least, not significantly easier than a conventional one); we'd transition to such an algorithm instead.