I wrote:
> I think the main point of the smaller group in DSA is to get small
> signatures.
And it should also gets a bit faster, with smaller exponents. Which
might be an advantage also for DH, but I don't know if that's considered
important?
> 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).
Let me say a bit more about this. There's one class of "abstract"
discrete logarithm algorithms which work on any group where the group
operations are computable.
If n is the size of the group, there's an "obvious" meet-in-the-middle
algorithm with O(sqrt(n)) computation and O(sqrt(n)) storage: To find x
such that g^x = y, let s = ceil(sqrt(s)). First tabulate g^{k s} for k =
0, 1, ..., s. Then compute y g^{-m}, for m = 0, 1, ..., and stop when
you get a value which is present in the table. Then x = k s + m.
(Different time-memory tradeoffs are possible, of course).
Even better is to use the Pollard-rho discrete log algorithm, with
computation O(sqrt(n)), and very little storage.
As far as I'm aware, these abstract group algorithms are the best known
for directly attacking the DSA subgroup, or for attacking the elliptic
curve groups used for cryptographic purposes.
On the other hand, to compute discrete logarithms in the multiplicative
group of Z_p, there's the index calculus algorithm which is somewhat
similar to the number number field sieve factoring algorithm, and with
similar computational complexity (I'm not sure exactly what the
complexity is, though. But a *lot* better than O(sqrt(n))).
To break DSA, it's the attacker's choice to try the index calculus
algorithm on the large group, or the pollard-rho algorithm on the
smaller subgroup. Parameters should be chosen so that both attacks are
too expensive. But for reasonable parameters, the cost should be roughly
the same, e.g., it makes little sense to increase the size of p to 4096
bits, while sticking to only 160 bits for q.
I think it's a bit curious that each of the discrete logarithm above are
closely related to a factoring algorithm.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
_______________________________________________
nettle-bugs mailing list
[email protected]
http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
