Digital Signatures - Understanding Cryptography - page 265

Let's have a closer look at RSA-PSS. Almost always in practice, the message it-
self is not signed directly but rather the hashed version of it. Hash functions compute
a digital fingerprint of messages. The fingerprint has a fixed length, say 160 or 256
bit, but accepts messages as inputs of arbitrary lengths. More about hash functions
and the role the play in digital signatures is found in Chap. 11.
In order to be consistent with the terminology used in standards, we denote the
message with M rather than with x . Figure 10.2 depicts the encoding procedure
which is known as Encoding Method for Signature with Appendix (EMSA) Proba-
bilistic Signature Scheme (PSS).

Encoding for the EMSA Probabilistic Signature Scheme

Let be the size of the RSA modulus in bits. The encoded message EM

has a length

| n |

( | n |− 1) / 8 bytes such that the bit length of EM is at most

| 1 bit.

1. Generate a random value salt .
2. Form a string M by concatenating a fixed padding padding 1 , the hash
value mHash = h ( M ) and salt .
3. Compute a hash value H of the string M .
4. Concatenate a fixed padding padding 2 and the value salt to form a data
block DB .
5. Apply a mask generation function MGF to the string M to compute the
mask value dbMask . In practice, a hash function such as SHA-1 is often
used as MGF .
6. XOR the mask value dbMask and the data block DB to compute
maskedDB .
7. The encoded message EM is obtained by concatenating maskedDB ,the
hash value H and the fixed padding bc .

n |−

After the encoding, the actual signing operation is applied to the encoded mes-
sage EM , e.g.,

EM d s = sig k pr ( x ) ≡ mod n

The verification operation then proceeds in a similar way: recovery of the salt value
and checking whether the EMSA-PSS encoding of the message is correct. Note that
the receiver knows the values of padding 1 and padding 2 from the standard.
The value H in EM is in essence the hashed version of the message. By adding
a random value salt prior to the second hashing, the encoded value becomes proba-
bilistic. As a consequence, if we encode and sign the same message twice, we obtain
different signatures, which is a desirable feature.