On Fri 2013-12-06 15:12:57 -0500, Niels Möller wrote:
I think the main point of the smaller group in DSA is to get small signatures.
And discrete logs in the large group and discrete logs in the small subgroup are of comparable difficulty, because there's more structure in the larger group ("index calculus" is the name of the trick, iirc).
cool, thanks, i'll look into that further.
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.
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.
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.
what do you think?
--dkg