6.3. RSA Standards

The public-key cryptography standards (PKCS) [254] refer to a set of standard specifications proposed by the RSA Laboratories. A one-line description of each of these documents is given in Table 6.3. In the rest of this section, we concentrate only on the documents PKCS #1 and #3.

6.3.1. PKCS #1

PKCS #1 describes RSA encryption and RSA signatures. In this section, we summarize Version 2.1 (dated 14 June 2002) of the standard. This version specifies cryptographically stronger encoding procedures compared to the older versions. More specifically, the optimal asymmetric encryption procedure (OAEP [18]) for RSA encryption is incorporated in the Version 2.0 of PKCS #1, whereas the new probabilistic signature scheme (PSS [19]) is introduced in Version 2.1. This latest draft also includes encryption and signature schemes compatible with older versions (1.5 and 2.0). However, adoption of the new algorithms is strongly recommended for enhanced security.

RSA keys

PKCS #1 Version 2.1 introduces the concept of multi-prime RSA, in which the RSA modulus n may have more than two prime divisors. For RSA encryption and decryption to work properly, we only need n to be square-free (Exercise 4.1). Using u > 2 prime divisors of n increases efficiency and does not degrade the security of the resulting system much, as long as u is not very large. More specifically, if T is the time for RSA private-key operation without CRT, then the cost of this operation with CRT is approximately T/u² (neglecting the cost of CRT combination).

So an RSA modulus is of the form n = r₁r₂ . . . r_u with u ≥ 2 and with pairwise distinct primes r₁, . . . , r_u. For the sake of conformity with the older versions of the standard, the first two primes are given the alternate special names p := r₁ and q := r₂. PKCS #1 does not mention any specific way of choosing the prime divisors r_i of n, but encourages use of primes that make factorization of n difficult.

An RSA public exponent is an integer e, 3 ≤ e ≤ n – 1, with gcd(e, λ(n)) = 1, where λ(n) := lcm(r₁ – 1, r₂ – 1, . . . , r_u – 1). An RSA public key is a pair (n, e) with n and e chosen as above.

The RSA private key corresponding to (n, e) can be stored in one of the two formats. In the first format, one maintains the pair (n, d) with the private exponent d so chosen as to make ed ≡ 1 (mod λ(n)). In the second format, one stores the five quantities (p, q, dP, dQ, qInv) and, if u > 2, the triples (r_i, d_i, t_i) for each i = 3, . . . , u. The meanings of these quantities are as follows:

For the sake of consistency, one should store the CRT coefficient (mod r₂), that is, p^–1 (mod q). In order to ensure compatibility with older versions of PKCS, q^–1 (mod p) is stored instead.

RSA key operations

The RSA public-key operation is used to encrypt a message or to verify a signature. The PKCS draft calls these primitives RSAEP (encryption primitive) and RSAVP1 (verification primitive). It is implemented in a straightforward manner as in Algorithm 6.1.

Algorithm 6.1. RSA encryption/signature verification primitive

The RSA decryption or signature-generation primitive is called RSADP or RSASP1 and is given in Algorithm 6.2. The operation depends on the format in which the private key K is stored. The correctness of the primitive is left to the reader as an easy exercise.

Algorithm 6.2. RSA decryption/signature generation primitive

RSAES–OAEP encryption scheme

The encryption scheme RSAES–OAEP is based on the optimal asymmetric encryption procedure (OAEP) proposed by Bellare and Rogaway [18, 98]. In this procedure, a string of length slightly less than the size of the modulus n is probabilistically encoded using a hash function and the encoded message is subsequently encrypted. The probabilistic encoding makes the encryption procedure semantically secure and (provably) provides resistance against chosen-ciphertext attacks. Under this scheme, an adversary can produce a ciphertext, only if she knows the corresponding plaintext. Such an encryption scheme is called plaintext-aware. Given an ideal hash function, Bellare and Rogaway’s OAEP is plaintext-aware.

RSAES–OAEP uses a label L which is hashed by a hash function H. One may take L as the empty string. Other possibilities are not specified in the PKCS draft. SHA-1 (or SHA-256 or SHA-384 or SHA-512) is the recommended hash function. The hash values (in hex) of the empty string under these hash functions are given in Table 6.4.

The length of the hash output (in octets) is denoted by hLen. For SHA-1, hLen = 20. The RSA modulus n is assumed to be of octet length k. The octet length mLen of the input message M must be ≤ k–2hLen–2. RSAES–OAEP uses a mask-generation function designated as MGF (see Algorithm 6.11 for a recommended realization).

Algorithm 6.3 describes the RSA–OAEP encryption scheme which employs the EME–OAEP encoding scheme described in Algorithm 6.4. The use of a random seed makes the encryption probabilistic. We use the notation ‖ to denote string concatenation and ⊕ to denote bit-wise XOR.

Algorithm 6.3. RSA–OAEP encryption scheme

The matching decryption operation is shown in Algorithm 6.5 which calls the EME–OAEP decoding procedure of Algorithm 6.6. The only error message that the decryption and decoding algorithms issue is decryption error. This is to ensure that an adversary cannot distinguish between different kinds of errors, because such an ability of the adversary may lead her to guess partial information about the decryption process and thereby mount a chosen-ciphertext attack.

Algorithm 6.4. RSA–OAEP encoding scheme

Algorithm 6.5. RSA–OAEP decryption scheme

Algorithm 6.6. RSA–OAEP decoding scheme

RSASSA–PSS signature scheme with appendix

RSASSA–PSS employs the probabilistic signature scheme proposed by Bellare and Rogaway [19]. Under suitable assumptions about the hash function and the mask-generation function, the RSASSA–PSS scheme produces secure signatures which are also tight in the sense that forging RSASSA–PSS signatures is computationally equivalent to inverting RSA.

Algorithm 6.7. RSASSA–PSS signature generation

Algorithm 6.8. RSASSA–PSS encoding

RSASSA–PSS signature generation (Algorithm 6.7) uses the EMSA–PSS encoding method (Algorithm 6.8). Verification (Algorithm 6.9) uses the EMSA–PSS decoding method (Algorithm 6.10). We assume that k is the octet length of the RSA modulus n. Let modBits denote the bit length of n. The encoded message is of length emLen = ⌈(modBits – 1)/8⌉ octets. The probabilistic behaviour of the encoding scheme is incorporated by the use of a random salt, the octet length of which is sLen. A hash function H that produces hash values of octet length hLen is employed.

Algorithm 6.9. RSASSA–PSS signature verification

Algorithm 6.10. RSASSA–PSS decoding

A mask-generation function

A mask-generation function (MGF1) is specified in the PKCS #1 draft. It is based on a hash function H. The mask-generation function is deterministic in the sense that its output is completely determined by its input. However, the (provable) security of OAEP and PSS schemes are based on the pseudorandom nature of the output of the mask-generation function. This means that any part of the output should be statistically independent of the other parts. MGF1 derives this pseudorandomness from that of the underlying hash function H.

Algorithm 6.11. Mask-generation function MGF1

The RSA encryption scheme of PKCS #1, Version 1.5

The older encryption scheme RSAES–PKCS1–v1_5 is no longer recommended, since this scheme is not plaintext-aware, that is, with high probability, an adversary can generate ciphertexts without knowing the corresponding plaintexts. This allows the adversary to mount chosen-ciphertext attacks. The new drafts of PKCS #1 include this old scheme for backward compatibility. Encryption and decryption for RSAES–PKCS1–v1_5 are given in Algorithms 6.12 and 6.13. Here, k is the octet length of the modulus.

Algorithm 6.12. RSA–PKCS1 encryption scheme

Algorithm 6.13. RSA–PKCS1 decryption scheme

The RSA signature scheme of PKCS #1, Version 1.5

The older RSA signature scheme RSASSA–PKCS1–v1_5 is not known to have security loopholes. (Nevertheless, the provably secure PSS scheme is recommended for future applications.) RSASSA–PKCS1–v1_5 uses EMSA–PKCS1–v1_5 message encoding procedure (Algorithm 6.16). The signature generation and verification procedures are given in Algorithms 6.14 and 6.15. Here, k denotes the octet length of the modulus n.

The EMSA–PKCS1–v1_5 message encoding procedure (Algorithm 6.16) uses a hash function H. Although a member of the SHA family is recommended for future applications, MD2 and MD5 are also supported for compliance with older application. An octet string hashAlgo is used whose value depends on the underlying hash algorithm and is given in Table 6.5.

Algorithm 6.14. RSA–PKCS1 signature generation

Algorithm 6.15. RSA–PKCS1 signature verification

Algorithm 6.16. EMSA–PKCS1 encoding

6.3.2. PKCS #3

PKCS #3 describes the Diffie–Hellman key-exchange algorithm. The draft assumes the existence of a central authority which generates the domain parameters that include a prime p of octet length k, an integer g satisfying 0 < g < p and optionally a positive integer l. The integer g need not be a generator of , but is expected to be of sufficiently large multiplicative order modulo p. The integer l denotes the bit length of the private Diffie–Hellman key of an entity. Values of l ≪ 8k can be chosen for efficiency. However, for maintaining a desired level of security l should not be too small. Since the central authority determines p, g (and l), individual users need not bother about the generation of these parameters.

During a Diffie–Hellman key-exchange interaction of Alice with Bob, Alice performs the steps described in Algorithm 6.17. Bob performs an identical operation which is omitted here.

Algorithm 6.17. PKCS3 Diffie–Hellman key-exchange scheme