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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ The question body seems much narrower than the question title. Would you care to edit them to make them match? Are you asking "What are the future directions in cryptography?" (very broad) or "What is the likely future of public-key cryptography?" (you got a good answer) or "What are the future directions in breaking RSA?" (closer to what you ask in the body of your question). $\endgroup$– D.W.Jan 3, 2013 at 5:01
-
1$\begingroup$ And, by the way, welcome to Crypto.SE! $\endgroup$– D.W.Jan 3, 2013 at 5:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Thanks for the thoughtful answer - it helps me think about what I'm looking for. One thing is, I the ECC direction does provide the kind of answer I was looking for - maybe because it's a qualitative difference rather than simply quantitative. My follow-up question is, have there been break-through developments in methodology, say in ECC, or factoring, that would make the enormous integer-size aspect irrelevant? You already answered this in a way, but can you recommend reading, papers, books, etc? Thanks very much! $\endgroup$ Jan 6, 2013 at 17:50
-
$\begingroup$ @PatrickColeman: I'm not sure what you mean by a 'break-through development in methodology'. Why ECC works with a relatively small curve (say, 256 bit) is a lack of a break-through, that is, the lack of a practical way to compute the discrete log. $\endgroup$– ponchoJan 10, 2013 at 18:21