Digital Signature - A Classical Introduction to Cryptography: Applications for Communications Security - page 254

10.2.5 PKCS#1

The PKCS (Public-Key Cryptography Standards) that we saw in Chapter 9 also includes
a signature scheme based on RSA. Here we give details about the signature scheme of
the PKCS#1v1.5 standard (Ref. [13]).

We are given a modulus n of k bytes. In order to sign a message, we proceed as
follows.

1. We hash the message, for instance with MD5, and get a message digest.
2. We encode the message digest and the identifier of the hash algorithm.
3. We pad it with a zero byte to the left, then with many (at least 8) FF bytes in
order to reach a length of k − 2 bytes, then with a 01 byte. We obtain k − 1

bytes.
4. This byte string is converted into an integer.
5. We compute the plain RSA signature.
6. We convert the result into a string of k bytes.

The verification is then straightforward.

1. We convert the signature into an integer. We reject it if it is greater than the
modulus.
2. We perform the plain RSA verification and obtain another integer.
3. We convert back the integer into a byte string.
4. We check that the string has the 00 || 01 || FF ··· FF || 00 || D format for a byte

string D .
5. We decode the data D and obtain the message digest and the hash algorithm.
We check that the hash algorithm is acceptable.
6. We hash the message and check the message digest.

The PKCS#1v2.1 (Ref. [14]) includes another signature scheme which uses the
padding scheme called PSS (as for Probabilistic Signature Scheme), which is similar
to the OAEP (Optimal Asymmetric Encryption Padding) (see Section 9.3.8).

10.3 ElGamal Signature Family

In his PhD, Taher ElGamal studied the application of the discrete logarithm in cryp-
tography (see Refs. [63-65]). The ElGamal signature started a dynasty of signature
schemes based on the discrete logarithm problem.

10.3.1 ElGamal Signature

The original ElGamal signature scheme is defined as follows. We use a cryptographic
hash function H .