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
pgp4p0CU4fHfD.pgp
Description: PGP signature
_______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
