5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the update PicPuc. I should remember to use \bmod instead of \mod! $\endgroup$
    – Maarten Bodewes ♦
    Commented Aug 27, 2015 at 20:02
  • $\begingroup$ if you follow the formalism of the wikipedia link, I think you mean $u_1$ instead of $u^1$ $\endgroup$
    – 111
    Commented Aug 28, 2015 at 13:30

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