Why does P1363 require RW signature with $0 ≤ s < n/2$?

Question

I'm using an older copy of P1363 Public Key Cryptography was used below. It may (or may not) reflect the current state of affairs.

P1363 has the following requirement in section 8.2.8 IFSP-RW, p. 45:

Output: The signature, which is an integer $s$ such that $0 ≤ s < n/2$

8.2.5 IFVP-RSA1 (p. 43) does not have the same requirement; but 8.2.6 IFSP-RSA2 (p. 44) does have the requirement.

Bernstein does not appear to discuss the requirement in RSA signatures and Rabin–Williams signatures: the state of the art.

What's the purpose of the restricted range on the signature? What threat does the requirement address?

Answer 1

That practice of replacing the result of $y=x^d\bmod N$ (or $y=x^e\bmod N$) by $\hat y=\min(y,N-y)$ is also in ISO/IEC 9796-2:2010 _^(paywalled) and ancestors; I first met that in [INCITS/ANSI]/ISO/IEC 9796:1991, also given in the Handbook of Applied Cryptography, see in particular note 11.36. ISO/IEC 9796 was a broken and now withdrawn signature scheme with message recovery based on RSA or RW, very different from ISO/IEC 9796-2.

With $e=2$ (or more generally even), $\;y^e\bmod N\;=\;(N-y)^e\bmod N$. Thus in a RW signature application, signatures $y$ and $N-y$ are equivalent. One rationale of using $\hat y$ is to choose a canonical signature among $y$ and $N-y$. This allows the verifier to check that the signature is less than $N/2$, which prevents an adversary from turning a signature $y$ into a different but equally acceptable signature $N-y$ (some definition of signature security consider that a break).

With odd $e$ (RSA), there is no such security rationale. However we can still use $\hat y$ rather than $y$, if the low-order bit of $x$ is set to 0 by the padding scheme: if $\hat x=\hat y^e\bmod N$ turn out to be odd, the verifier uses $x=N-\hat x$ instead.

Whatever $e$, the maximum bit size of $\hat y$ is one less than the maximum bit size of $y$ (for arbitrary $x$). That size reduction, however small in proportion, allows:

• Direct re-encryption of $\hat y$ under textbook RSA using a different $N'$ of the same size as $N$, including when $N'<N$, which can happen when encryption and signature keys have modulus specified only by their common bit size (and is bound to happen for one of the two parties in some protocols between peers each using a single key for both encryption and signature, as in the European Digital Tachograph).
• Use of $N$ with $8k+1$ bits with convenient signatures of $k$ bytes; such $N$ have been extensively used in early public-key systems; as illustration, the example given in ISO/IEC 9791:1991, appendix B.1.1, has as 513-bit $N$.
  _{Incidentally, the leftmost 129 bits are all-zero except the leftmost one, which simplifies quotient estimation, perhaps at the price of somewhat easier factorization in particular with NFS, but that was not known at the time.}