Using memory dependent hashes works better if one is a small server since one will rarely have a lot of people sending in their passwords at the same time, so the RAM space you need isn't that large. If you are a large organization then this doesn't work as well because you then need room to be able to do many such calculations functionally simultaneously.
Meh. If you are a large organization, you can afford more.
Anyway, the point is that you should turn it up as much as you can afford.
I agree that there's a linear v. exponential difference there(although for many of these it is more like linear and subexponential due to algorithms like the number field sieve),
Yes, NFS is subexponential, but not very "sub". And anyway, RSA is old, broken crypto which should be migrated away from.
but the rest of your comment is essentially wrong. We keep keys just long enough that we consider it to be highly unlikely that they are going to be vulnerable, but not much more than that.
I hate to resort to appeal to authority, but the actual analysis required to prove it is way more effort than I have time for this morning. Take a look at keylength.com, it has a host of authoritative references.
Heh. In my previous reply I actually typed a long section about why RSA is a weak counterexample to my argument, but deleted it because it's nitpicking. Since you chose to pick that nit...
It's a valid counterexample because RSA key generation, and, to a much lesser extent, RSA private key operations, are computationally expensive enough to stress low-end devices (an issue I often have to deal with... I'm responsible for some of the core crypto subsystems in Android). But it's a weak counterexample because RSA is not modern crypto. It's ancient, outmoded, we have some reasons to suspect that factoring may not be NP hard, using it correctly is fraught with pitfalls, and it's ridiculously expensive computationally. And even still, the common standard of 2048-bit keys is secure for quite some time to come. As that stackoverflow article you linked mentions, the tendency has been to choose much larger-than-required keys (not barely large enough) rather than tracking Moore's law.
So, yeah, if you use an outdated, ridiculously expensive algorithm, and you do it on very low-spec hardware, and you want it to be secure for a very long time then, yeah, you might end up having to use barely-large-enough key sizes.
Don't do that. For asymmetric crypto use ECC. Preferably with an Edwards curve, so you don't have to deal with niggling suspicions that the curve is weak in some obscure way known only to the NSA.