3
$\begingroup$

According to wikipedia, when generating a signature for ECDSA, you do the following (among other things):

  1. Calculate $e=\operatorname{HASH}(m)$, where $\operatorname{HASH}$ is a cryptographic hash function, such as SHA-2.
  2. Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bit length of the group order $n$.

$z$ is later used to calculate $s$.

Anyway, my question is... what if $L_n$ is larger than the bit length of $e$?

For example, SHA256 has is 256 bits long. secp384r1, in contrast, has a bit length of 384 bits.

$\endgroup$

1 Answer 1

8
$\begingroup$

What happens when the hash output is smaller than the group size is perfectly defined by FIPS 186-4; namely, nothing special. The hash output is still interpreted as an integer (using big-endian notation). Yes, that integer is in a range that is naturally smaller than the complete range of integers modulo the group order. For all we know, this does not seem to be that much an issue, from a security point of view (contrary to the generation of the per-signature secret value $k$, which must be uniform among the whole range).

The general process is the following: if the curve (sub)group order is $n$, of length $z = \lceil \log_2 n \rceil$ bits, the hash output, if larger than $z$ bits, is first truncated to its first (leftmost) $z$ bits. The possibly truncated result is interpreted as an integer using big-endian notation; that integer, which is then necessarily less than $2^z$, is further reduced modulo $n$. Thanks to the truncation, this modular reduction is inexpensive, since the value to reduce is less than $2n$, so it can be done with a single conditional subtraction. When the hash output length is strictly less than $z$ bits, e.g. with SHA-256 used with secp384r1, then there is no truncation (it's already small enough) and the modular reduction is trivial (the value is already smaller than $n$).

It shall be noted that FIPS 186-4 (section 6.4) and ANSI X9.62 recommend using with each curve a hash function with a somewhat "matching" strength. NIST defines 15 curves: for each of five formal "strengths" (80, 112, 128, 192 and 256 bits), the recommended hash function has output length exactly twice the strength, and there are three standard NIST curves whose subgroup order length is at least twice the strength. Thus, when using the recommended hash function for a curve, there is never any truncation. On the other hand, the curve subgroup order nay be quite larger than the hash output; for instance, curve B-283, the binary non-Koblitz standard NIST curve for strength 128, the subgroup order has length 282 bits, i.e. quite larger than the 256-bit output of the recommended hash function for that curve (SHA-256).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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