Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

All the articles I read on the web about DSA keep telling me that the size of the hash needs to be truncated so that the bit length is equal to or lesser than the bit length of the prime number of the field.

For example, Wikipedia says:

  • Choose an approved cryptographic hash function H. [...] The hash output may be truncated to the size of a key pair.
  • Choose an N-bit prime q. N must be less than or equal to the hash output length.

But why exactly do we need this? What's wrong with using a 256-bit hash with a 160-bit prime?

I tried looking on the web, but I keep getting results that explain me how to truncate the hash, not why.

share|improve this question
up vote 5 down vote accepted

During verification you perform $u_1 = H ( m ) w \bmod{q}$ would return the same $u_1$ for multiple hash values. In general you only want one hash to succeed, even if it is unlikely that an adversary can generate a hash that equals $n q + H(m) w$.

Of course this means that any hash with the leftmost bits identical to the org. hash is also acceptable, but at least you don't have to perform $\bmod{q}$ over an extensively large number.

For modular arithmetic any input (base value for modular exponentiation) larger than the modulus contains spurious information.

share|improve this answer
Thanks for the update PicPuc. I should remember to use \bmod instead of \mod! – Maarten Bodewes Aug 27 '15 at 20:02
if you follow the formalism of the wikipedia link, I think you mean $u_1$ instead of $u^1$ – 111 Aug 28 '15 at 13:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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