Digital Signatures - Introduction to Cryptography with Maple - page 561

occurs. We refer also to [90] for very detailed explanations of the security reduction
for FDH as well as of the ideas underlying the transition from FDH to PSS.
The signature schemes we have seen so far are all standard schemes in which the
signer sends the unencrypted message m with the signature attached (these signa-
tures are often called 'signatures with appendix'). There is an alternative class of
signature schemes, generically called 'signatures with message recovery', in which
only one data unit (an 'enhanced signature') is transmitted—with the goal of saving
bandwidth—and the message is recovered from the enhanced signature and authen-
ticity is checked at the same time. The algorithm that does this is called the Recover
algorithm—it replaces the verification algorithm and either outputs the message in
case it is authentic or declares the signature invalid.
In [20], a version of PSS with message recovery, called PSS-R, is also given. The
security of this scheme is the same as for PSS.

9.5.3 RSASSA-PSS from PKCS #1 v2.1

PSS has been standardized in [154] under the name RSASSA-PSS, where the ini-
tials RSASSA stand for “RSA Signature Scheme with Appendix”. This signature
scheme has a structure similar to that of RSAES-OAEP—replacing the encryption
and decryption algorithms by the signing and verification algorithms—and combines
signature and verification primitives with an encoding method for signatures called
EMSA-PSS; the specific features of PSS are contained in this encoding method.
The message to be signed is first encoded by means of EMSA-PSS and then con-
verted to integer form to which the RSA decryption function is applied to produce
the signature. Verification proceeds in reverse order: first the RSA encryption func-
tion is applied to the signature and the integer obtained is converted to an EMSA-
PSS-encoded message which is then processed according to the PSS verification
algorithm.
We start by describing the required components, for which we use notation similar
to that in [154]. The basic ingredients are essentially the same as in RSAES-OAEP,
described in Sect. 8.3.6.2 , to which we refer for details. They are:

• An RSA public key ( n , e ) and its corresponding private key ( n , d ) , where the bit

length of the modulus n is modBits and its byte length is k .

• A hash function Hash whose outputs are hLen bytes in length.

• A Mask Generating Function (MGF).

• The intended byte length sLen of the seed (or 'salt' in the terminology of [154])

used by the signing algorithm.

• A message M to be signed, given as a byte string of arbitrary length (in practice,

this length is limited by the input size limitation of the hash function used).

• Themaximal bit length emBits of the integer corresponding to the encodedmessage

EM mentioned in the following item. emBits is at least 8 hLen

+ 8 sLen + 9 and it

will be set equal to modBits − 1 in this scheme.