DSA key length

Brian M. Carlson karlsson@hal-pc.org
Thu Jul 25 21:36:02 2002

Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Wed, Jul 24, 2002 at 06:16:55PM -0400, Daniel Carrera wrote:
> Alright, thanks a lot for all the help.  I understand all this much better
> how.
> I still don't understand the 1024-bit limit on DSA.
> I've read that DSA has similar strength as RSA and ElGamal, that the key
> shouldn't be too small and so on.

Actually, DSA and Elgamal are based on the Discrete Logarithm Problem.
RSA is based on the Integer Factorization Problem. If you can solve the
DLP, you can solve the IFP, but the converse is not necessarily true.
Therefore, from a purely scientific standpoint, DSA and Elgamal are
slightly better choices. Some people prefer RSA from a historical
standpoint because it has been used in PGP and many other standards
from the beginning of crypto time. It's really personal preference.

> Why is 1024 the limit for DSA when people recommend 2048 for RSA and
> ElGamal?

This is because of the lovely US government. DSA was originally
supposed to be limited to 512 bits; however, everyone made a big fuss
over it. So, it was raised to 1024 bits. You should ask the people that
wrote FIPS 186 (I think that's it) why they made such a foolish
decision. Nothing says that you have to, except DSS. Also section 12.6
of the OpenPGP standard states (or at least strongly implies that you
must) be limited to 1024 bits. AFAIK, only P1363{,a} do not have this
requirement for DSA.

Brian M. Carlson <karlsson@hal-pc.org> <http://decoy.wox.org/~bmc> 0x560553=
This is NOT a repeat.

Content-Type: application/pgp-signature
Content-Disposition: inline

Version: GnuPG v1.1.90 (GNU/Linux)
Comment: Ubi libertas, ibi patria.

Signature policy: http://decoy.wox.org/~bmc/openpgp/policy.tex