In the Digital Signature Algorithm, is there a reason why the larger prime parameter should be an $N$-bit prime where $N$ is a multiple of 64 ?

Is this strictly necessary for proper working of the algorithm?


The algorithm would work fine without the restriction, although it's debatable whether NIST owns the name DSA and you would have to call it something else, the way non-RSA-licensed implementations of RC4 were for a long time called ARCFOUR (alleged RC4) or similar. How about Schnorr Patent Evading Digital Signature SPEDS?

Why did NIST do it (originally, see next)? AFAICT 'everyone knows' they wanted to reduce the amount of testing needed to ensure that multiple, different implementations would provably meet the standard and (as a result) interoperate with each other reliably, while still allowing designers and possibly users to choose tradeoffs of cost vs security. I don't think I've seen that rationale officially documented anywhere, but they certainly have done essentially the same thing with other algorithms and standards, most notably AES (which supports only 3 key sizes and 1 block size, though the underlying algorithm Rijndael supports quite a few more).

Also note the originally permitted sizes 512 to 1024 by 64 -- which still survive in a good deal of software that hasn't been updated -- have officially been obsolete for a long time. Change Notice 1 to FIPS186-2 in Oct. 2001 restricted p to only 1024 (with q still 160); after a long delay FIPS186-3 in June 2009 added p 2048 or 3072 (with q 224 or 256 in the former case and 256 in the latter) -- while 1024 2048 3072 are multiples of 64, they are not all the multiples of 64 in that range, and do not provide nearly the 'fine tuning' that the old list did.

Although in contrast RSA and DH were defined and usually are implemented for any bit size (sufficiently large to provide the desired security) in practice people almost always use powers of two or 'halfway between' sizes: 512 768 1024 1536 2048 3072 4096 -- and FIPS186-3 specifies key generation for RSA signatures (for US govt use) that only allows n sizes 1024 2048 3072.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.