undefined | Better HN

0 pointstptacek11y ago0 comments

I think I'm probably confusing terms here; you're referring to the size of "a", and I'm referring to the size of "p".

Perhaps 'pbsd will be around in a bit to resolve whether the index calculus will push the size of p or a first; my understanding is that it's bounded by the size of the modulus, and that most of the work it does is independent of the specific element of the group you're attacking.

I am definitely a lot fuzzier on DH key sizes than on RSA; we're getting into cryptanalytic attacks that don't have a lot of relevance to the kind of work I do.

0 comments

pbsd11y ago

The NFS complexity for factorization and discrete logarithm is asymptotically the same. In practice, the matrix step is more costly in discrete logarithm, but this should increase the bit security by at most a handful of bits, which is not enough to justify differentiating DL estimates from RSA estimates.

This refers to the size of p, the prime modulus. Sizes of exponents and/or subgroups are not affected by the complexity of the NFS, so they generally only need to be twice the target bit security to avoid birthday-type attacks.

tptacekOP11y ago

So it's the size of p that matters most in practice, assuming other parameters are sane.

j / k navigate · click thread line to collapse