Daniel Kahn Gillmor dkg@fifthhorseman.net writes:
cool, thanks, i'll look into that further.
You can start with Handbook of Applied Cryptography, sec. 3.6 (available as pdfs at http://cacr.uwaterloo.ca/hac/).
For DH, I don't think there's any particular reason to prefer to work in a small subgroup. But I may be missing something, of course.
I can think of a few, but i'm not sure how legitimate they are:
One is based on minimized entropy: If you know your small subgroup is of size q, then you need less entropy to choose your secret A in the DH key exchange, since it never needs to exceed q.
I doubt this matters, if you have a decent and properly seeded pseudorandomness generator.
another might be efficiency of modular exponentiation: if you use exponentiation by squaring, then the cost of calculating A' = g^A mod p where A < q should be O(log_2(q)) instead of O(log_2(p)) where A < p. So if q has half the bits of p, you'd halve the amount of computation.
I think this is true also for more sophisticated exponentiation algorithms. Cost is linear in exponent size.
The second modular exponentiation (B'^A mod p) would be similarly faster. Both of these factors seem like they might be significant in a TLS endpoint that terminates many DHE sessions per second, but i haven't profiled them.
Could well be. I'd like to hear what Nikos says about this.
Regards, /Niels