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.
Document | Description |
---|---|
PKCS #1 | RSA encryption and signature |
PKCS #2 | Merged with PKCS #1 |
PKCS #3 | Diffie–Hellman key exchange |
PKCS #4 | Merged with PKCS #1 |
PKCS #5 | Password-based cryptography |
PKCS #6 | Extension of X.509 public-key certificates |
PKCS #7 | Syntax of cryptographic messages |
PKCS #8 | Syntax and encryption of private keys |
PKCS #9 | Attribute types for use in PKCS #6, #7, #8 and #10 |
PKCS #10 | Syntax for certification requests |
PKCS #11 | Cryptoki, an application programming interface (API) |
PKCS #12 | Syntax of transferring personal information (private keys, certificates and so on) |
PKCS #13 | Elliptic curve cryptography (under preparation) |
PKCS #15 | Syntax for cryptographic token (like integrated circuit card) information |
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.
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/u2 (neglecting the cost of CRT combination).
So an RSA modulus is of the form n = r1r2 . . . ru with u ≥ 2 and with pairwise distinct primes r1, . . . , ru. For the sake of conformity with the older versions of the standard, the first two primes are given the alternate special names p := r1 and q := r2. PKCS #1 does not mention any specific way of choosing the prime divisors ri 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(r1 – 1, r2 – 1, . . . , ru – 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 (ri, di, ti) for each i = 3, . . . , u. The meanings of these quantities are as follows:
p | = | r1 |
q | = | r2 |
dP | ≡ | e–1 (mod p – 1) |
dQ | ≡ | e–1 (mod q – 1) |
qInv | ≡ | q–1 (mod p) |
di | ≡ | e–1 (mod ri – 1) |
ti | ≡ | (r1 . . . ri–1)–1 (mod ri) |
For the sake of consistency, one should store the CRT coefficient (mod r2), that is, p–1 (mod q). In order to ensure compatibility with older versions of PKCS, q–1 (mod p) is stored instead.
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.
Input: RSA public key (n, e) and message/signature representative x. Output: The ciphertext/message representative y. Steps: if (x < 0) or (x ≥ n) { Return “Error: representative out of range”. } y := xe (mod n). |
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.
Input: RSA private key K and the ciphertext/message representative y. Output: The message/signature representative x. Steps: if (y < 0) or (y ≥ n) { Return “Error: representative out of range”. } |
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.
Function | Hash of the empty string |
---|---|
SHA-1 | da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709 |
SHA-256 | e3b0c442 98fc1c14 9afbf4c8 996fb924 27ae41e4 649b934c a495991b 7852b855 |
SHA-384 | 38b060a7 51ac9638 4cd9327e b1b1e36a 21fdb711 14be0743 4c0cc7bf 63f6e1da 274edebf e76f65fb d51ad2f1 4898b95b |
SHA-512 | cf83e135 7eefb8bd f1542850 d66d8007 d620e405 0b5715dc 83f4a921 d36ce9ce 47d0d13c 5d85f2b0 ff8318d2 877eec2f 63b931bd 47417a81 a538327a f927da3e |
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.
Input: The recipient’s public key (n, e), the message M (an octet string of length mLen) and an optional label L whose default value is the empty string. Output: The ciphertext C of octet length k. Steps: /* Check lengths */ if (L is longer than what H can handle) { Return “Error: label too long”. } /* For example, for SHA-1 the input must be of length ≤ 261 – 1 octets. */ if (mLen > k – 2hLen – 2) { Return “Error: message too long”. } /* Encode M to EM (EME–OAEP encoding 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.
Input: The recipient’s private key K, the ciphertext C to be decrypted and an optional label L (the default value of which is the null string). Output: The decrypted message M. Steps: if (the length of L is more than the limitation of H) or (the length of C is not k octets)
|
Input: The encoded message EM and the label L. Output: The EME–OAEP decoded message M. Steps: lHash := H(L). |
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.
Input: The message M (an octet string) to be signed, the private key K of the signer. Output: The signature S (an octet string of length k). Steps:
|
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.
Input: The message M, the signature S to be verified and the signer’s public key (n, e). Output: Verification status of the signature. Steps: if (the length of S is not k octets) { Return “Signature not verified”. }
if (status is “consistent”) { Return “Signature verified”. } else { Return “Signature not verified”. } |
Input: The message M (an octet string), the encoded message EM (an octet string of length emLen = ⌈emBits/8⌉) and the maximum bit length emBits of OS2I(EM). One should have emBits ≥ 8hLen + 8sLen + 9. Output: Decoding status: “consistent” or “inconsistent”. Steps: if (M is longer than what H can handle) { Return “inconsistent”. } |
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.
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.
Input: The recipient’s public key (n, e) and the message M (an octet string). Output: The ciphertext C which is an octet string of length k. Steps: if (mLen > k – 11) { Return “Error: message too long”. }
|
Input: The recipient’s private key K and the ciphertext C (an octet string). Output: The plaintext message M (an octet string of length ≤ k – 11). Steps: if (the length of the ciphertext is not k octets) { Return “decryption error”. }
Try to decompose EM = 00 ‖ 02 ‖ PS ‖ 00 ‖ M, where PS is an octet string of length ≥ 8 and containing only non-zero octets. if (the above decomposition is unsuccessful) { Return “decryption error”. } |
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.
Function | The string hashAlgo |
---|---|
MD2 | 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10 |
MD5 | 30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 |
SHA-1 | 30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 |
SHA-256 | 30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 |
SHA-384 | 30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 |
SHA-512 | 30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 |
Input: The signer’s private key K and the message M to be signed (an octet string). Output: The signature S (an octet string of length k). Steps:
|
Input: The signer’s public key (n, e), the message M (an octet string) and the signature S to be verified (an octet string of length k). Output: Verification status of the signature. Steps: if (the length of S is not k octets) { Return “Signature not verified”. }
if (EM = EM′) { Return “Signature verified”. } else { Return “Signature not verified”. } |
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.
Input: p, g and optionally l. Output: The shared secret SK (an octet string of length k). Steps: Alice generates a random . /* If l is specified, one should have 2l–1 ≤ x < 2l. */ Alice computes y := gx (mod p). Alice converts y to an octet string PV := I2OS(y, k). Alice sends the public value PV to Bob. Alice receives Bob’s public value PV′. Alice converts PV′ to the integer y′ := OS2I(PV′). Alice computes z := (y′)x (mod p) (with 0 < z < p). Alice transforms z to the shared secret SK := I2OS(z, k). |
52.14.151.45