NIST FIPS 186-5 日本語訳

(Supersedes FIPS 186-4)

Digital Signature Standard (DSS)

CATEGORY: COMPUTER SECURITY

SUBCATEGORY: CRYPTOGRAPHY

Information Technology Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899-8900

This publication is available free of charge from: https://doi.org/10.6028/NIST.FIPS.186-5

Published: February 3, 2023

U.S. Department of Commerce Gina M. Raimondo, Secretary

National Institute of Standards and Technology Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

The Federal Information Processing Standards Publication (FIPS) series of the National Institute of Standards and Technology (NIST) is the official series of publications relating to standards and guidelines developed under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331.

Comments concerning FIPS publications are welcomed and should be addressed to the Director, Information Technology Laboratory, National Institute of Standards and Technology, 100 Bureau Drive, Stop 8900, Gaithersburg, MD 20899-8900.

Charles H. Romine, Director Information Technology Laboratory

This standard specifies a suite of algorithms that can be used to generate a digital signature. Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature as evidence in demonstrating to a third party that the signature was, in fact, generated by the claimed signatory. This is known as non-repudiation since the signatory cannot easily repudiate the signature at a later time.

Keywords: computer security; cryptography; digital signatures; Federal Information Processing Standards; public key cryptography.

Federal Information Processing Standards Publication 186-5

Published: February 3, 2023

Effective: February 3, 2023 (see the Implementation Schedule)

Announcing the

Federal Information Processing Standards Publications (FIPS) are developed by the National Institute of Standards and Technology (NIST) under 15 U.S.C. 278g-3, and issued by the Secretary of Commerce under 40 U.S.C. 11331.

Signature generation uses a private key to generate a digital signature; signature verification uses a public key that corresponds to but is not the same as the private key. Each signatory possesses a private and public key pair. Public keys may be known by the public; private keys must be kept secret. Anyone can verify the signature by employing the signatory’s public key. Only the user that possesses the private key can perform signature generation.

A hash function is often used in the signature generation process to obtain a condensed version of the data to be signed; the condensed version of the data is often called a message digest. The message digest is input to the digital signature algorithm to generate the digital signature. The hash functions to be used are specified in FIPS 180, Secure Hash Standard (SHS), and FIPS 202, SHA-3: Permutation-Based Hash and Extendable-Output Functions. FIPS-approved digital signature algorithms shall be used with appropriate approved functions (e.g., hash functions such as those specified in FIPS 180 or FIPS 202).

The digital signature is provided to the intended verifier along with the signed data. The verifying entity verifies the signature by using the claimed signatory’s public key and the same hash function that was used to generate the signature. Similar procedures may be used to generate and verify signatures for both stored and transmitted data.

This standard supersedes FIPS 186-4. In the future, additional digital signature schemes may be specified and approved in FIPS publications or in NIST Special Publications.

Agencies are advised that digital signature key pairs shall not be used for other purposes.

a. Specified in a Federal Information Processing Standards Publication (FIPS), b. Adopted in a FIPS or NIST recommendation, or c. Specified in the list of approved security functions for FIPS 140-3.

Similarly, the use of a product containing an implementation that conforms to this standard does not guarantee the security of the overall system in which the product is used. The responsible authority in each agency or department shall ensure that an overall implementation provides an acceptable level of security.

Since a standard of this nature must be flexible enough to adapt to advancements and innovations in science and technology, this standard will be reviewed every five years in order to assess its adequacy.

National Institute of Standards and Technology (2023) Digital Signature Standard (DSS). (Department of Commerce, Washington, D.C.), Federal Information Processing Standards Publication (FIPS) NIST FIPS 186-5. https://doi.org/10.6028/NIST.FIPS.186-5

Federal Information Processing Standards Publication 186-5

This standard defines methods for digital signature generation that can be used for the protection of binary data (commonly called a message) and for the verification and validation of those digital signatures. Three techniques are approved.

The Digital Signature Algorithm (DSA) is no longer specified in this standard and may only be used to verify previously generated digital signatures. Complete specifications may be found in Federal Information Processing Standard (FIPS) 186-4 [7].

This standard includes requirements for obtaining the assurances necessary for valid digital signatures. Methods for obtaining these assurances are provided in SP 800-89, Recommendation for Obtaining Assurances for Digital Signature Applications [8]. Information about the key lengths used for generating and verifying digital signatures and the time frames during which they are assumed to be secure are provided in SP 800-131A [9]. Note that the algorithms in this standard are not expected to provide resistance to attacks from a large-scale quantum computer. Digital signature algorithms that will provide security from quantum computers will be specified in future NIST publications.

Approved — FIPS-approved and/or NIST-recommended. An algorithm or technique that is either 1) specified in a FIPS or NIST Recommendation, 2) adopted in a FIPS or NIST Recommendation, or 3) specified in a list of NIST-approved security functions.

Assurance of domain parameter validity — Confidence that the domain parameters are arithmetically correct.

Assurance of possession — Confidence that an entity possesses a private key and any associated keying material.

Assurance of public key validity — Confidence that the public key is arithmetically correct.

Bias — With respect to the uniform distribution on \([0, n-1]\), the bias is defined to be the maximum value of \(\left\{ \mathit{probability}(S) - \left(\frac{|S|}{n}\right) \right\}\) taken over all subsets \(S\) of \([0, n-1]\). This measures the maximum advantage that an adversary has in predicting any event.

Bit string — An ordered sequence of zeros and ones. The leftmost bit is the most significant bit of the string. The rightmost bit is the least significant bit of the string.

Certificate — A set of data that uniquely identifies a public key (which has a corresponding private key) and an owner that is authorized to use the key pair. The certificate contains the owner’s public key and possibly other information and is digitally signed by a Certification Authority (i.e., a trusted party), thereby binding the public key to the owner.

Certification Authority (CA) — The entity in a Public Key Infrastructure (PKI) that is responsible for issuing certificates and exacting compliance with a PKI policy.

Claimed signatory From the verifier’s perspective, the claimed signatory is the entity that purportedly generated a digital signature.

Destroy — An action applied to a key or a piece of secret data. After a key or a piece of secret data is destroyed, no information about its value can be recovered.

Digital signature — The result of a cryptographic transformation of data that, when properly implemented, provides a mechanism for verifying origin authentication, data integrity, and signatory non-repudiation.

Domain parameter seed — A string of bits that is used as input for a domain parameter generation or validation process.

Domain parameters — Parameters used with cryptographic algorithms that are usually common to a domain of users. An ECDSA or EdDSA cryptographic key pair is associated with a specific set of domain parameters.

Entity — An individual (person), organization, device, or process. Used interchangeably with “party.”

Equivalent process — Two processes are equivalent if the same output is produced when the same values are input to each process (either as input parameters, as values made available during the process, or both).

Hash function — A function on bit strings in which the length of the output is fixed. Approved hash functions (such as those specified in FIPS 180 [10] and FIPS 202 [11]) are designed to satisfy the following properties:

Hash value — See “message digest.”

Intended signatory An entity that intends to generate digital signatures in the future.

Key — A parameter used in conjunction with a cryptographic algorithm that determines its operation. Examples applicable to this standard include:

Key pair — A public key and its corresponding private key.

Message — The data that is signed. Also known as “signed data” during the signature verification and validation process.

Message digest — The result of applying a hash function to a message. Also known as a “hash value.”

Non-repudiation — A service that is used to provide assurance of the integrity and origin of data in such a way that the integrity and origin can be verified and validated by a third party as having originated from a specific entity in possession of the private key (i.e., the signatory).

Owner — A key pair owner is the entity authorized to use the private key of a key pair.

Party — An individual (person), organization, device, or process. Used interchangeably with “entity.”

Per-message secret number — A secret random number that is generated prior to the generation of each digital signature.

Public Key Infrastructure (PKI) — A framework that is established to issue, maintain, and revoke public key certificates.

Prime number generation seed — A string of random bits that is used to begin a search for a prime number with the required characteristics.

Private key — A cryptographic key that is used with an asymmetric (public key) cryptographic algorithm. The private key is uniquely associated with the owner and is not made public. The private key is used to compute a digital signature that may be verified using the corresponding public key.

Probable prime — An integer that is believed to be prime based on a probabilistic primality test. There should be no more than a negligible probability that the so-called probable prime is actually composite.

Provable prime — An integer that is either constructed to be prime or is demonstrated to be prime using a primality-proving algorithm.

Pseudorandom — A process or data produced by a process is said to be pseudorandom when the outcome is deterministic yet also effectively random as long as the internal action of the process is hidden from observation. For cryptographic purposes, “effectively random” means “computationally indistinguishable from random within the limits of the intended security strength.”

Public key — A cryptographic key that is used with an asymmetric (public key) cryptographic algorithm and is associated with a private key. The public key is associated with an owner and may be made public. In the case of digital signatures, the public key is used to verify a digital signature that was generated using the corresponding private key.

Security strength — A number associated with the amount of work (i.e., the number of operations) that is required to break a cryptographic algorithm or system.

Shall — Used to indicate a requirement of this standard.

Should — Used to indicate a strong recommendation but not a requirement of this standard. Ignoring the recommendation could result in undesirable results.

Signatory — The entity that generates a digital signature on data using a private key.

Signature generation The process of using a digital signature algorithm and a private key to generate a digital signature on data.

Signature validation — The (mathematical) verification of the digital signature and obtaining the appropriate assurances (e.g., public key validity, private key possession, etc.).

Signature verification The process of using a digital signature algorithm and a public key to verify a digital signature on data.

Signed data — The data or message upon which a digital signature has been computed. Also see “message.”

Subscriber — An entity that has applied for and received a certificate from a Certificate Authority.

Trusted third party (TTP) — An entity other than the key pair owner and verifier that is trusted by the owner or the verifier or both. Sometimes shortened to “trusted party.”

Verifier — The entity that verifies the authenticity of a digital signature using the public key.

ANS — American National Standard

CA — Certification Authority

DRBG — Deterministic Random Bit Generator¹

DSA — Digital Signature Algorithm²

ECDSA — Elliptic Curve Digital Signature Algorithm

EdDSA — Edwards Curve Digital Signature Algorithm³

FIPS — Federal Information Processing Standard

FFC — Finite Field Cryptography

NIST — National Institute of Standards and Technology

PKCS — Public Key Cryptography Standard

PKI — Public Key Infrastructure

RSA — Rivest, Shamir, Adleman⁴

SHA — Secure Hash Algorithm

SP — NIST Special Publication

TTP — Trusted Third Party

XOF — Extendable-Output Function

\(a \bmod n\) — The unique remainder \(r\), \(0 \le r \le (n - 1)\), when integer \(a\) is divided by the positive integer \(n\). For example, \(23 \bmod 7 = 2\).

\(b \equiv a \bmod n\) — There exists an integer \(k\) such that \(b - a = kn\); equivalently, \(a \bmod n = b \bmod n\).

\(d\) — 1. For RSA, the private signature exponent of a private key.

\(e\) — The public verification exponent of an RSA public key.

\(G\) — The base point of an elliptic curve.

\(\mathrm{GCD}(a, b)\) — Greatest common divisor of the integers \(a\) and \(b\).

\(\mathrm{Hash}(M)\) — The result of a hash computation (message digest or hash value) on message \(M\) using an approved hash function.

\(k\) — A per-message secret number.

\(\mathrm{LCM}(a, b)\) — The least common multiple of the integers \(a\) and \(b\).

\(\mathrm{len}(a)\) — The length of the bit string that is the shortest possible binary representation of the (non-negative) integer \(a\); i.e. the integer \(L\), where \(2^{L-1} \le a < 2^{L}\).

\(M\) — The message that is signed using the digital signature algorithm.

\(\min(a, b)\) — The minimum of the two positive integers \(a\) and \(b\).

\(n\) — 1. For RSA, the modulus. The bit length of \(n\), i.e. \(\mathrm{len}(n)\), is considered to be the key size.

\((n, d)\) — An RSA private key, where \(n\) is the modulus, and \(d\) is the private signature exponent.

\((n, e)\) — An RSA public key, where \(n\) is the modulus, and \(e\) is the public verification exponent.

\(p\) — 1. For RSA, a prime factor of the modulus \(n\).

\(q\) — For RSA, a prime factor of the modulus \(n\).

\(Q\) — An ECDSA or EdDSA public key, which is a point on an elliptic curve.

\((r, s)\) or \((R, S)\) — An ECDSA, or EdDSA digital signature, where \(r\) and \(s\) (or \(R\) and \(S\)) are the digital signature components.

\(\text{SHA-}x(M)\) — The result when \(M\) is the input to the SHA-\(x\) hash function, where SHA-\(x\) is specified in FIPS 180 or FIPS 202.

\(\oplus\) — Bitwise logical “exclusive-or” on bit strings of the same length; for corresponding bits of each bit string, the result is determined as follows: \(0 \oplus 0 = 0\), \(0 \oplus 1 = 1\), \(1 \oplus 0 = 1\), or \(1 \oplus 1 = 0\). Example: \(01101 \oplus 11010 = 10111\)

\(+\) — Addition

\(\times\) — Multiplication

\(/\) — Division

\(a \parallel b\) — The concatenation of two strings \(a\) and \(b\). Either \(a\) and \(b\) are both bit strings, or both are byte strings.

\(\lceil a \rceil\) — The ceiling of \(a\): the smallest integer that is greater than or equal to \(a\). For example, \(\lceil 5 \rceil = 5\), \(\lceil 5.3 \rceil = 6\), and \(\lceil -2.1 \rceil = -2\).

\(\lfloor a \rfloor\) — The floor of \(a\); the largest integer that is less than or equal to \(a\). For example, \(\lfloor 5 \rfloor = 5\), \(\lfloor 5.3 \rfloor = 5\), and \(\lfloor -2.1 \rfloor = -3\).

\(|a|\) — The absolute value of \(a\); \(|a|\) is \(-a\) if \(a < 0\); otherwise, it is simply \(a\). For example, \(|2| = 2\), and \(|-2| = 2\).

\([a, b]\) — The interval of integers between and including \(a\) and \(b\). For example, \([1, 4]\) consists of the integers 1, 2, 3 and 4.

\(\{, a, b, \ldots\}\) — Used to indicate optional information.

0x — The prefix to a bit string that is represented in hexadecimal characters.

\([n]X\) — The elliptic curve point \(X\) added to itself n times, for \(n > 1\).

A digital signature is an electronic analog of a written signature that can be used to provide assurance that the claimed signatory signed the information. In addition, a digital signature may be used to detect whether or not the information was modified after it was signed (i.e., to detect the integrity of the signed data). These assurances may be obtained whether the data was received in a transmission or retrieved from storage. A properly implemented digital signature algorithm that meets the requirements of this standard can provide these services.

Figure 1: Digital Signature Processes⁵

A digital signature algorithm includes a signature generation process and a signature verification process. A signatory uses the generation process to generate a digital signature on data; a verifier uses the verification process to verify the authenticity of the signature. Each signatory has a public and private key and is the owner of that key pair. As shown in Figure 1, the private key is used in the signature generation process. The key pair owner is the only entity that is authorized to use the private key to generate digital signatures. In order to prevent other entities from claiming to be the key pair owner and using the private key to generate fraudulent signatures, the private key must remain secret. The approved digital signature algorithms are designed to prevent an adversary who does not know the signatory’s private key from generating a valid signature as the signatory on a different message. In other words, signatures are designed so that they cannot be forged. A number of alternative terms are used in this standard to refer to the signatory or key pair owner. An entity that intends to generate digital signatures in the future may be referred to as the intended signatory. Prior to the verification of a signed message, the signatory is referred to as the claimed signatory until such time as adequate assurance can be obtained of the actual identity of the signatory. The public key is used in the signature verification process (see Figure 1). The public key need not be kept secret, but its integrity must be maintained. Anyone can verify a correctly signed message using message digest and the public key. For both the signature generation and verification processes of RSA, ECDSA, and HashEdDSA, the message (i.e., the signed data) is converted to a fixed-length representation of the message by means of an approved hash function. Both the original message and the digital signature are made available to a verifier. A verifier requires assurance that the public key is used to verify that a signature actually belongs to the entity that claims to have generated a digital signature (i.e., the claimed signatory). That is, a verifier requires assurance that the signatory is the actual owner of the public/private key pair used to generate and verify a digital signature. This assurance can only be provided if the owner’s identity and public key are bound together, such as in a certificate issued from a public key infrastructure. A verifier also requires assurance that the key pair owner actually possesses the private key associated with the public key and that the public key is a mathematically correct key. These assurances tell the verifier that if the digital signature can be correctly verified using the public key, the digital signature is valid (i.e., the key pair owner really signed the message). Digital signature validation includes both (mathematically) verifying the digital signature and obtaining the appropriate assurances. The following are reasons why such assurances are required:

10

Figure 2: Initial Setup by an Intended Signatory

Technically, a key pair used by a digital signature algorithm could also be used for purposes other than digital signatures (e.g., for key establishment). However, a key pair used for digital signature generation and verification as specified in this standard shall not be used for any other purpose. See SP 800-57, Part 1 [12], on key usage for further information.

A number of steps are required to enable a digital signature generation or verification capability in accordance with this standard. All parties that generate digital signatures shall perform the initial setup process as discussed in Section 3.1. Digital signature generation shall be performed as discussed in Section 3.2. Digital signature verification and validation shall be performed as discussed in Section 3.3.

Figure 2 depicts the steps that are performed prior to generating a digital signature by an entity intending to act as a signatory.

For the ECDSA and EdDSA algorithms (including HashEdDSA), the intended signatory shall first obtain appropriate domain parameters, either by generating the domain parameters itself or by obtaining domain parameters that another entity has generated. Having obtained the set of domain parameters, the intended signatory shall obtain assurance of the validity of those domain parameters; approved methods for obtaining this assurance are provided in SP 800-89 [8] (also see SP 800-186, Appendix D.1). Note that the RSA algorithm does not use domain parameters.

Each intended signatory shall obtain a digital signature key pair that is generated as specified for the appropriate digital signature algorithm, either by generating the key pair itself or by obtaining the key pair from a trusted party. The intended signatory is authorized to use the key pair and is the owner of that key pair. Note that if a trusted party generates the key pair, that party needs to be trusted not to masquerade as the owner, even though the trusted party knows the private key.

After obtaining the key pair, the intended signatory (now the key pair owner) shall obtain (1) assurance of the validity of the public key and (2) assurance that they actually possess the associated private key. Approved methods for obtaining these assurances are provided in SP 800-89.

A digital signature verifier requires assurance of the identity of the signatory. Depending on the environment in which the digital signatures are generated and verified, the key pair owner (i.e., the intended signatory) may register the public key and establish proof of identity with a mutually trusted party. For example, a certification authority (CA) could sign credentials containing an owner’s public key and identity to form a certificate after being provided with proof of the owner’s identity. Systems for certifying credentials and distributing certificates are beyond the scope of this standard. Other means of establishing proof of identity (e.g., by providing identity credentials along with the public key directly to a prospective verifier) may be employed as long as system users and/or agents trusted to act on their behalf determine that those methods meet their security requirements.

For RSA, ECDSA, and HashEdDSA, prior to the generation of a digital signature, a message digest shall be generated on the information to be signed using an appropriate approved hash function.

Depending on the digital signature algorithm to be used, additional information shall be obtained. For example, a random per-message secret number shall be obtained for ECDSA but is not required for EdDSA and RSA.

Figure 3: Digital Signature Generation

Using the selected digital signature algorithm, the signature private key, the message or message digest, and any other information required by the digital signature process, a digital signature shall be generated in accordance with this standard.

The signatory may optionally verify the digital signature using the signature verification process and the associated public key (see Section 3.3). This optional verification serves as a final check to detect otherwise undetected signature generation computation errors; this verification may be prudent when signing a high-value message, when multiple users are expected to verify the signature, or if the verifier will be verifying the signature at a much later time.

Figure 3 depicts the steps that are performed by an intended signatory (i.e., the entity that generates a digital signature).

In order to verify a digital signature, the verifier shall obtain the public key of the claimed signatory, which is (usually) based on the claimed identity. If ECDSA or EdDSA (including HashEdDSA) have been used to generate the digital signature, the verifier shall also obtain the domain parameters. The public key and domain parameters may be obtained, for example, from a certificate created by a trusted party (e.g., a CA) or directly from the claimed signatory. For RSA, ECDSA, and HashEdDSA, a message digest shall be generated on the data whose signature is to be verified (i.e., not on the received digital signature) using the same hash function that was used during the digital signature generation process. The received digital signature is verified in accordance with this standard using the appropriate digital signature algorithm, the domain parameters (if appropriate), the public key, and the message or newly computed message digest. If the verification process fails, no inference can be made as to whether the data is correct, only that – in using the specified public key and the specified signature format – the digital signature cannot be verified for that data.

Before accepting the verified digital signature as valid, the verifier shall have (1) assurance of the signatory’s claimed identity, (2) assurance of the validity of the domain parameters (for ECDSA and EdDSA, including HashEdDSA), (3) assurance of the validity of the public key, and (4) assurance that the claimed signatory actually possessed the private key that was used to generate the digital signature at the time that the signature was generated. Methods for the verifier to obtain these assurances are provided in SP 800-89. Note that assurance of domain parameter validity may have been obtained during initial setup (see Section 3.1).

Figure 4 depicts the digital signature verification and validation process that is performed by a verifier (e.g., the intended recipient of the signed data and associated digital signature). Note that the figure depicts a successful verification and validation process (i.e., no errors are detected). If the verification and assurance processes are successful, the digital signature shall be considered valid. However, if a verification or assurance process fails, the digital signature shall be considered invalid. An organization’s policy shall govern the action to be taken for an invalid digital signature. Such policies are outside of the scope of this standard. Guidance for determining the timeliness of digitally signed messages is addressed in SP 800-102, Recommendation for Digital Signature Timeliness [13].

Figure 4: Digital Signature Verification and Validation⁶

Prior versions of this standard specified the DSA. This standard no longer approves the DSA for digital signature generation. However, the DSA may be used to verify signatures generated prior to the implementation date of this standard. See FIPS 186-4 [7] for the specifications for the DSA.

The use of the RSA algorithm for digital signature generation and verification is specified in IETF RFC 8017, Public Key Cryptography Standard (PKCS) #1: RSA Cryptography Specifications Version 2.2 [2]. This standard imposes additional restrictions, which are enumerated below (see Section 5.4).

An RSA digital signature key pair consists of an RSA private key, which is used to compute a digital signature, and an RSA public key, which is used to verify a digital signature. An RSA digital signature key pair shall not be used for other purposes (e.g., key establishment).

An RSA public key consists of a modulus \(n\), which is the product of two positive prime integers \(p\) and \(q\) (i.e., \(n = pq\)) and a public key exponent \(e\). Thus, the RSA public key is the pair of values \((n, e)\) and is used to verify digital signatures. The size of an RSA key pair is commonly considered to be the length of the modulus \(n\) in bits (\(nlen\)).

The corresponding RSA private key consists of the same modulus \(n\) and a private key exponent \(d\) that depends on \(n\) and the public key exponent \(e\). Thus, the RSA private key is the pair of values \((n, d)\) and is used to generate digital signatures. Note that an alternative method for representing \((n, d)\) using the Chinese Remainder Theorem (CRT) is allowed (see Sections 6.2 and 6.3 of SP 800-56B [14]).

In order to provide security for the digital signature process, the two integers \(p\) and \(q\) and the private key exponent \(d\) shall be kept secret. Guidance on the protection of these values is provided in SP 800-57, Part 1. The modulus \(n\) and the public key exponent \(e\) may be made known to anyone.

This standard specifies the use of a modulus whose bit length is an even integer and greater than or equal to 2048 bits. Furthermore, this standard specifies that \(p\) and \(q\) be of the same bit length – namely, half the bit length of \(n\). The maximum security strength of RSA schemes associated with the bit length of the modulus is specified in NIST SP 800-57, Part 1 [12].

Approved hash functions shall be used during the generation of key pairs and digital signatures. When used during the generation of an RSA key pair (as specified in this standard), the length in bits of the hash function output block shall meet or exceed the security strength associated with the bit length of the modulus \(n\) (see SP 800-57, Part 1).

The security strength associated with the RSA digital signature process is no greater than the minimum of the security strength associated with the bit length of the modulus and the security strength of the hash function that is employed (see Table 3 in SP 800-57, Part 1). The (maximum) security strengths associated with certain RSA modulus lengths and approved hash functions used during the digital signature process are provided in SP 800-57, Part 1. Both the security strength of the hash function used for the digital signature and the security strength associated with the bit length of the modulus \(n\) shall meet or exceed the security strength required for the digital signature process.

The security strength of the hash function used should be greater than or equal to the security strength of the modulus since, otherwise, the security strength of the digital signature process is reduced to a level no greater than that provided by the hash function.

A CA should use a modulus whose length \(nlen\) is equal to or greater than the bit-length of every modulus used by its subscribers. For example, if the subscribers are using \(nlen = 2048\), then the CA should use \(nlen \ge 2048\). SP 800-57, Parts 1 and 3 [12, 15], provide further information about comparable security strength guidance.

Criteria for the generation of RSA key pairs are provided in Appendix A.1.1.

When RSA parameters are randomly generated (i.e., the primes \(p\) and \(q\) and, optionally, the public key exponent \(e\)), they shall be generated using an approved random bit generator. The (pseudo) random bits produced by the random bit generator shall be used as seeds for generating RSA parameters. Prime number generation seeds shall be kept secret or destroyed when the modulus \(n\) is computed. If any prime number generation seed is retained (e.g., to regenerate the RSA modulus \(n\) or as evidence that the generated prime factors \(p\) and \(q\) were generated in compliance with this standard), then the seed shall be kept secret and shall be protected. The strength of this protection shall be (at least) equivalent to the protection required for the associated private key.

Guidance on the protection of key pairs is provided in SP 800-57, Part 1. The secure use of digital signatures depends on the management of an entity’s digital signature key pair as follows:

17 owner possessed the correct private key at the time the signature was generated (i.e., the private key that is associated with the public key used to verify the digital signature) (see Section 3.3).

The intended signatory shall have assurances as specified in Section 3.1. Prior to accepting a digital signature as valid, the verifier shall have assurances as specified in Section 3.3.

IETF RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2 [1], defines mechanisms for encrypting and signing data using the RSA algorithm. In particular, it specifies two digital signature processes and corresponding formats: RSASSA-PKCS1-v1.5 and RSASSA-PSS. Both of these signature schemes are approved for use, but additional constraints are imposed in addition to those specified in the IETF RFC.

Or (if the DigestInfo is selected by its location with respect to the last byte of padding),

Only if the extracted DigestInfo has the appropriate form shall the signature verification process continue. Assuming that this is the case, the following two checks shall be performed:

Only upon successful verification of both the algorithm identifier and the length of the digest value shall the extracted digest value be used as the recovered hash value during the verification of the digital signature.

Note that PKCS #1 was initially developed by RSA Laboratories in 1991 and has been revised as multiple versions. This standard references version 2.2 as published in IETF RFC 8017.

The mask generation function MGF1, to be used with RSASSA-PSS, is specified in Section B.2.1 of RFC 8017. This standard allows the use of SHAKE128 or SHAKE256 as alternative mask generation functions. The output length in bits of the alternative mask generation function is \(8 \times (\mathit{emLen} - \mathit{hLen} - 1)\), where “emLen – hLen – 1” is the output length in bytes of the MGF. See RFC 8017 for the definitions of “emLen” and “hLen”. Concretely, in step 9 of Section 9.1.1 of RFC 8017, instead of dbMask = MGF1(H, emLen – hLen - 1), set either dbMask = \(\mathrm{SHAKE128}(H, 8 \times (\mathit{emLen} - \mathit{hLen} - 1))\) or \(\mathit{dbMask} = \mathrm{SHAKE256}(H, 8 \times (\mathit{emLen} - \mathit{hLen} - 1))\). Similarly, for step 7 of Section 9.1.2, instead of dbMask = MGF1(H, emLen – hLen – 1), then dbMask = \(\mathrm{SHAKE128}(H, 8 \times (\mathit{emLen} - \mathit{hLen} - 1))\) or \(\mathit{dbMask} = \mathrm{SHAKE256}(H, 8 \times (\mathit{emLen} - \mathit{hLen} - 1))\).

19

This standard (FIPS 186-5) specifies (in Section 6.4) methods for digital signature generation and verification using the Elliptic Curve Digital Signature Algorithm (ECDSA). Specifications for the generation of the domain parameters used during the generation and verification of digital signatures are included in SP 800-186, Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters [5]. ECDSA is the elliptic curve analog of DSA. ECDSA keys shall not be used for any other purpose (e.g., key establishment).

Deterministic ECDSA (Section 6.3.2) is a variant of ECDSA, where a per-message secret number is a function of the message that is signed, thereby resulting in a deterministic mapping of messages to signatures. This variant does not impact the signature verification process. IETF RFC 6979, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) [4], describes this deterministic digital signature generation procedure. The use of deterministic ECDSA may be desirable for devices that do not have a good source of quality random numbers.

For signature schemes, secrecy of the private key is critical. This is especially true with deterministic signature schemes, which return a unique signature computed from the hash of the private key and the message. Care must be taken to protect implementations against attacks, such as side-channel attacks or fault attacks [17, 18, 19, 20, 21, 22]. A cryptographic device may leak critical information with side-channel analysis or attacks that allow internal data or keying material to be extracted without breaking the cryptographic primitives. It is also important to verify the correctness of group arithmetic computations for ECC implementations. These types of attacks may be of particular concern for hardware implementations of deterministic signature schemes, as well as embedded or IoT devices and smartcards.

ECDSA and deterministic ECDSA require that the private/public key pairs used for digital signature generation and verification be generated with respect to a particular set of domain parameters. These domain parameters may be common to a group of users and may be public. Domain parameters may remain fixed for an extended time period.

Domain parameters for ECDSA and deterministic ECDSA are of the form \((q, FR, h, n, Type, a, b, G, \{domain\_parameter\_seed\})\), where q is the field size, FR is an indication of the basis used, a and b are two field elements that define the equation of the curve, Type indicates the elliptic curve model used, G is a base point of prime order on the curve (i.e., \(G = (x_G, y_G)\)), n is the order of the point G, and h is the cofactor (which is equal to the order of the curve divided by n). The domain_parameter_seed is the domain parameter seed and is an optional bit string that is present if the elliptic curve was generated from the seed in a verifiable fashion.

This standard specifies four ranges for the bit length of n (see Table 1).

Table 1: ECDSA Security Parameters

ECDSA and deterministic ECDSA are defined for two arithmetic fields: the finite field GF(p) and the finite field \(\mathrm{GF}(2^m)\). For the field GF(p), p is required to be an odd prime.

NIST-recommended curves for ECDSA are provided in SP 800-186, Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters.

It is recommended that the security strength associated with the bit length of n and the security strength of the hash function be the same unless an agreement has been made between participating entities to use a stronger hash function. A hash function that provides a lower security strength than is associated with the bit length of n shall not be used. If the length of the output of the hash function is greater than the bit length of n, then the leftmost len(n) bits of the hash function output block shall be used in any calculation using the hash function output during the generation or verification of a digital signature.

Normally, a CA should use a bit length of n whose assessed security strength is equal to or greater than the assessed security strength associated with the bit length of n used by its subscribers. For example, if its subscribers are using 256-bit moduli (assessed to have a security strength of 128 bits), then a CA should use a modulus n whose bit length is equal to or greater than 256 bits (therefore having an assessed security strength equal to or greater than 128 bits). SP 800-57, Parts 1 and 3 [12, 15], provide additional information about the comparable security strength guidance.

Each key pair shall be correctly associated with one specific set of domain parameters (e.g., by a public key certificate that identifies the domain parameters associated with the public key). The domain parameters shall be protected from unauthorized modification until the set is deactivated (if and when the set is no longer needed). The same domain parameters may be used for more than one purpose (e.g., the same domain parameters may be used for both digital signatures and key establishment). However, using different domain parameters reduces the risk that key pairs generated for one purpose could be accidentally used for another purpose.

21

An ECDSA or deterministic ECDSA key pair consists of a private key d and a public key Q, which are associated with a specific set of domain parameters (i.e., d, Q, and the domain parameters are mathematically related to each other). The private key is normally used for a period of time (i.e., the cryptoperiod); the public key may continue to be used as long as digital signatures that have been generated using the associated private key need to be verified (i.e., the public key may continue to be used beyond the cryptoperiod of the associated private key). See SP 800-57, Part 1, for further guidance.

(Deterministic) ECDSA keys shall only be used for the generation and verification of (deterministic) ECDSA digital signatures.

A digital signature key pair d and Q is generated for a set of domain parameters (q, FR, h, n, Type, a, b, G, {domain_parameter_seed}). Methods for the generation of d and Q are provided in Appendix A.2.

The secure use of digital signatures depends on the management of an entity’s digital signature key pair as specified in Section 5.2. Moreover, there are three additional requirements that pertain to ECDSA:

A new secret random number k, \(0 < k < n\), shall be generated prior to the generation of each digital signature for use during the signature generation process. This secret number shall be protected from unauthorized disclosure and modification. The secret number k may be generated either randomly (see Section 6.3.1) or in a deterministic way (see Section 6.3.2).

The value \(k^{-1} = k^{-1} \bmod n\) is the multiplicative inverse of k with respect to multiplication modulo n (i.e., \(0 < k^{-1} < n\) and \(1 \equiv (k^{-1} k) \bmod n\)). This inverse is required for the signature generation process. A technique is provided in Appendix B.1 for deriving \(k^{-1} \bmod n\) from k.

For (non-deterministic) ECDSA, both k and \(k^{-1}\) may be pre-computed since knowledge of the message to be signed is not required for the computations. When k and \(k^{-1}\) are pre-computed, their confidentiality and integrity shall be protected in the same manner as the private key.

Methods for randomly generating the per-message secret number are provided in Appendices A.3.1 and A.3.2.

Deterministic ECDSA is a variant of ECDSA where the per-message secret number is a function of the message that is signed and the private key, thereby resulting in a deterministic mapping of messages to signatures. This protects against attacks arising from generating signatures with insufficient randomness in the per-message secret number that would reveal a private key. Deterministic ECDSA may be desirable for devices that do not have a good source of quality random numbers for generating the per-message secret number.

The method for deterministically generating the per-messsage secret number is provided in Appendix A.3.3

An ECDSA or deterministic ECDSA digital signature (r, s) shall be generated as specified in Section 6.4.1 using:

A digital signature shall be verified as specified in Section 6.4.2 using the same domain parameters and hash function that were used during signature generation.

An approved hash function or an XOF shall be used during the generation of digital signatures. Approved XOFs are SHAKE128 and SHAKE256, which are specified in FIPS 202. When SHAKE128 or SHAKE256 is used as an XOF in Sections 6.4.1 and 6.4.2 below, its output length shall be 256 or 512 bits, respectively.

The security strength associated with the ECDSA digital signature process is no greater than the minimum of the security strength associated with the bit length of n and the security strength of the hash function (or XOF) that is employed. Both the security strength of the hash function (or XOF) used and the security strength associated with the bit length of n shall meet or exceed the security strength required for the digital signature process. The security strengths for the ranges of the bit lengths of n and for each hash function are provided in Table 3 of SP 800-57, Part 1. The security strengths for collision resistance for XOFs is provided in FIPS 202.

The security strength associated with the bit length of n and the security strength of the hash function (or XOF) should be the same unless an agreement has been made between participating entities to use a stronger hash function. When the length of the output of the hash function (or XOF) is greater than the bit length of n, then the leftmost n bits of the hash function (or XOF) output block shall be used in any calculation using the hash function (or XOF) output during the generation or verification of a digital signature. A hash function (or XOF) that provides a lower security strength than the security strength associated with the bit length of n ordinarily should not be used since this would reduce the security strength of the digital signature process to a level no greater than that provided by the hash function (or XOF).

Inputs:

Output: A pair of integers \((r, s)\), each in the interval \([1, n-1]\)

Process:

A value \(k\) shall be generated at each invocation of the signature generation algorithm. The private key \(d\) and the per-message secret numbers \(k\) and \(k^{-1}\) shall be protected from unauthorized disclosure and modification. The per-message secret numbers \(k\) and \(k^{-1}\) may be pre-computed if \(k\) is randomly generated. If these numbers are pre-computed, their confidentiality and integrity shall be protected in the same manner as the private key.

Note that in the case of deterministic ECDSA, if \(r = 0\) or \(s = 0\), then generating a new per-message secret \(k\) will again lead to the same values for \(r\) and \(s\). Statistically, this is extremely unlikely to happen. However, should it occur, the signature generation algorithm aborts and outputs failure.

Inputs:

Output: Accept or reject the signature over \(M\) as originating from the owner of public key \(Q\).

Process:

From Section 6.2.2, the validity of the domain parameters shall be assured prior to the verification and validation of a digital signature. The validity of the public key \(Q\) should also be checked (see Appendix D.1 of SP 800-186 [5]).

The intended signatory shall have assurances as specified in Section 3.1. Prior to accepting a signature as valid, the verifier shall have assurances as specified in Section 3.3.

The Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using a variant of a Schnorr signature based on twisted Edwards curves. See SP 800-186 for details on curves approved for use with EdDSA.

Prehash EdDSA (HashEdDSA) is a version of EdDSA where the EdDSA signature is generated on the hash of the message rather than the message itself. Prehash EdDSA is described in Section 7.8.

IETF RFC 8032 [6] describes the elliptic curve Edwards-curve Digital Signature Algorithm (EdDSA) and specifies parameters for the edwards25519 and edwards448 curves\(^{8}\). It also specifies the prehash version HashEdDSA. EdDSA signatures are deterministic; a unique value computed from the hash of the private key and the message is used in the signature generation process. This process protects against attacks arising from generating signatures with insufficient randomness for the per-message secret number.

Care must be taken to protect implementations against attacks, such as side-channel attacks and fault attacks [17, 18, 19, 20, 21, 22]. A cryptographic device may leak critical information with side-channel analysis or attacks that allow internal data or keying material to be extracted without breaking the cryptographic primitives. It is also important to verify the correctness of group arithmetic computations for ECC implementations. These types of attacks are of particular concern for hardware implementations of deterministic signature schemes, as well as in embedded or IoT devices and smartcards.

The security of the EdDSA signature scheme relies on the choices of domain parameters. The domain parameters for EdDSA include \(G\) as a base point of prime order on the curve (i.e., \(G = (x_G, y_G)\)), \(n\) as the order of the point \(G\), \(d\) as the private key, \(Q\) as the public key, an integer \(b\), and an integer \(c\) (\(c\) is 3 for Ed25519 and 2 for Ed448). Note that secret scalars for EdDSA are multiples of \(2^c\). Additionally, \(H\) is a cryptographic hash function or XOF (extendable-output function) used during signature generation. \(H\) shall be one of the following, depending on which curve is used (per IETF RFC 8032):

It is noted that Ed25519 is intended to provide approximately 128-bits of security, and Ed448 is intended to provide approximately 224-bits of security. Future Special Publications may allow other parameter sets or specify a randomized version of EdDSA.

Parameter values used in EdDSA are coded as octet strings, and integers are coded using little-endian convention (i.e., a 32-octet string \(h = h[0], \ldots, h[31]\) represents the integer \(h[0] + 2^{8} \times h[1] + \cdots + 2^{248} \times h[31]\)). The most significant byte is \(h[31]\), and the least significant byte \(h[0]\).

For a curve point \((x,y)\) with coordinates in the range \(0 \le x, y < p\), first encode the \(y\)-coordinate as a little-endian string of 32 octets for Ed25519 or 57 octets for Ed448. For Ed25519, the most significant bit of the final octet is always zero, while for Ed448, the most significant octet is always zero. To form the encoding of the point, copy the least significant bit of the \(x\)-coordinate to the most significant bit of the final octet.

For point decoding or “decompression,” square roots modulo p are needed. To decompress an encoded point for EdDSA:

The following routines describe simplified cases to compute square roots for \(p \equiv 3 \bmod 4\) or \(p \equiv 5 \bmod 8\). Let \(u = y^2 - 1\) and \(v = d y^2 - a\).

For both cases, if \(x = 0\) and \(x_0 = 1\), point decoding fails. If \(x \bmod 2 = x_0\), then the \(x\)-coordinate is \(x\). Otherwise, the \(x\)-coordinate is \(p - x\).

EdDSA public keys have exactly b bits, and EdDSA signatures have exactly 2b bits. The value b is a multiple of 8, therefore, public key and signature lengths are an integral number of octets.

For Ed25519, \(b\) is 256, so the private key is 32 octets. For Ed448, \(b\) is 456, and the private key is 57 octets. See IETF RFC 8032. The method to generate the public-private key \((d, Q)\) pair is provided in Appendix A.2.3.

The secure use of digital signatures depends on the management of an entity’s digital signature key pair. Key pair management requirements for EdDSA are the same as for ECDSA, which are provided in Section 6.2.2.

EdDSA signatures are deterministic. The signature is generated using the hash of the private key and the message using the procedure below or an equivalent process.

Inputs:

Output: The signature \(R \| S\), where \(R\) is an encoding of a point and \(S\) is an octet string of a given length of a little-endian encoded value.

Process:

As specified in IETF RFC 8032, the EdDSA signature of a message M under a private key d is defined as the 2b-bit string R || S. The octet strings R and S are derived as follows:

Interpret \(\mathit{digest}\) as a little-endian integer.

Inputs:

Output: Accept or reject the signature over M as originating from the owner of public key Q. Process:

Interpret \(\mathit{digest}\) as a little-endian integer \(u\).

The Prehash Edwards-Curve Digital Signature Algorithm (HashEdDSA) is a version of the EdDSA digital signature scheme. The main difference is that HashEdDSA generates a signature on the hash of the message \(M\), unlike EdDSA which signs the message \(M\) directly. The domain parameters and key generation for HashEdDSA are exactly the same as for EdDSA with the two options denoted Ed25519ph and Ed448ph.

Below are the signature generation and verification processes for Ed25519ph and Ed448ph. Section 7.8.3 explains potential reasons for choosing between HashEdDSA and EdDSA.

29

Inputs:

Output: The signature R || S, where R is an encoding of a point, and S is a little-endian encoded value.

Process:

As specified in IETF RFC 8032, the HashEdDSA signature of a message M under a private key d is defined as the 2b-bit string R || S. The octet strings R and S are derived as follows:

In either instance, interpret r as a little-endian integer.

Interpret digest as a little-endian integer.

Inputs:

Output: Accept or reject the signature over M as originating from the owner of public key Q. Process:

Interpret digest as a little-endian integer t.

A difference between EdDSA and its prehash version is that HashEdDSA generates a signature on the hash of the message M, unlike EdDSA which signs the message M directly. As a result, EdDSA must hash the message twice while HashEdDSA only needs to hash once. Another difference is that with EdDSA the whole message M must be either buffered or read from its storage twice. Thus, for long messages, it is expected that HashEdDSA will have better performance.

It should be noted that even if it is feasible to compute collisions on the hash function (or XOF) used, there is believed to be no adverse effect on the security of EdDSA. This property is not true for HashEdDSA since collisions can result in forged messages.

32

Discrete logarithm cryptography (DLC) is divided into finite field cryptography (FFC) and elliptic curve cryptography (ECC). The difference between the two is the type of mathematics that is used. DSA is an example of FFC, and ECDSA is an example of ECC. Other examples of DLC are the Diffie-Hellman and MQV key agreement algorithms, which have both FFC and ECC forms.

The most common example of integer factorization cryptography (IFC) is RSA.

This appendix specifies methods for the generation of ECC key pairs, secret numbers, and IFC key pairs. All generation methods require the use of an approved, properly instantiated deterministic random bit generator (DRBG). The DRBG shall have a security strength equal to or greater than the security strength associated with the key pairs and secret numbers to be generated. See SP 800-57, Part 1, for guidance on security strengths and key sizes.

This appendix does not indicate the required conversions between bit strings and integers. When required by a process in this appendix, the conversion shall be accomplished as specified in Appendix B.2.

A.1 IFC Key Pair Generation

Key pairs for IFC consist of a public key \((n, e)\) and a private key \((n, d)\) where \(n\) is the modulus and product of two prime numbers, \(p\) and \(q\). The security of IFC depends on the quality and secrecy of these primes and the private exponent \(d\). The primes \(p\) and \(q\) shall be generated using one of the following methods:

Using methods 1 and 2, p and q with lengths equal to one half the length of the modulus are generated.

B. Both p and q are randomly generated prime numbers that satisfy the following additional conditions (Primes with Conditions):

where \(p_1\), \(p_2\), \(q_1\) and \(q_2\) are called auxiliary primes of \(p\) and \(q\).

The minimum lengths for each of the auxiliary primes \(p_1, p_2, q_1\), and \(q_2\) are dependent on nlen, where nlen is the length of the modulus \(n\) in bits. Note that nlen is also called the key size. The lengths of the auxiliary primes may be fixed or randomly chosen, subject to the restrictions in Table A.1. The maximum length is determined by nlen (the sum of the length of each auxiliary prime pair) and whether the primes \(p\) and \(q\) are probable primes or provable primes (e.g., for the auxiliary prime pair \(p_1\) and \(p_2\), \(\mathrm{len}(p_1) + \mathrm{len}(p_2)\) shall be less than a value determined by nlen whether \(p_1\) and \(p_2\) are generated to be probable or provable primes).⁹

For different values of nlen (i.e., different key sizes), random primes or primes with conditions are methods allowed for the generation of \(p\) and \(q\).

In addition, all IFC keys shall meet the following criteria in order to conform to this standard, FIPS 186-5:

(b) The exponent e shall be an odd positive integer such that:

Note that the value of e may be any value that meets constraint 1(b) (i.e., e may be either a fixed value or a random value).

That is, the inequality in (a) holds, and \(1 \equiv (ed) \bmod \mathrm{LCM}(p - 1, q - 1)\).

In the extremely rare event that \(d \le 2^{nlen/2}\), then new values for \(p\), \(q\), and \(d\) shall be determined. A different value of \(e\) may be used, although this is not required.

Any hash function used during the generation of the key pair shall be approved.

An approved method that satisfies the constraints of Appendix A.1.1 shall be used for the generation of IFC random primes \(p\) and \(q\) that are provably prime (see case A.1). One such method is provided in Appendices A.1.2.1 and A.1.2.2. For this method, a random seed is initially required (see Appendix A.1.2.1); the length of the seed is equal to twice the security strength associated with the modulus \(n\). After the seed is obtained, the primes can be generated (see Appendix A.1.2.2).

A.1.2.1 Get the Seed The following process or its equivalent shall be used to generate the seed for this method: Input: nlen The intended bit length of the modulus n.

Output: status The status to be returned, where status is either SUCCESS or FAILURE.

seed The seed. If status = FAILURE, a value of zero is returned as the seed.

The following process or its equivalent shall be used to construct the random primes p and q (to be used as factors of the RSA modulus n) that are provably prime:

Input: nlen The intended bit length of the modulus n. e The public verification exponent. seed The seed obtained using the method in Appendix A.1.2.1.

Output: status The status of the generation process, where status is either SUCCESS or FAILURE. When FAILURE is returned, zero values shall be returned as the other parameters. p and q The private prime factors of n.

Process:

A.1.3 Generation of Random Primes that are Probably Prime

An approved method that satisfies the constraints of Appendix A.1.1 shall be used for the generation of IFC random primes p and q that are probably prime (see case A.2). In addition, the security strength of the instance of the DRBG mechanism (see Section 8.4 in SP 800-90A, Rev. 1 [16]) used in the algorithm below shall be equal to or greater than the security strength associated with nlen as specified in SP 800-57, Part 1.

The following process or its equivalent shall be used to construct the random probable primes p and q (to be used as factors of the RSA modulus n):

Input:

nlen — The intended bit length of the modulus n.

e — The public verification exponent.

a, b — (Optional parameters) Numbers from the set {1, 3, 5, 7} that may be used to add the further requirements \(p \equiv a \bmod 8\), \(q \equiv b \bmod 8\).

Output:

status — The status of the generation process, where status is either SUCCESS or FAILURE.

p and q — The private prime factors of n. When FAILURE is returned, zero values shall be returned as p and q.

Process:

This section specifies an approved method for the generation of the IFC primes \(p\) and \(q\) with the additional conditions specified in Appendix A.1.1, case B.1, where \(p\), \(p_1\), \(p_2\), \(q\), \(q_1\), and \(q_2\) are all provable primes. For this method, a random seed is initially required (see Appendix A.1.2.1); the length of the seed is equal to twice the security strength associated with the modulus \(n\). After the first seed is obtained, the primes can be generated. Let \(bitlen_1\), \(bitlen_2\), \(bitlen_3\), and \(bitlen_4\) be the bit lengths for \(p_1\), \(p_2\), \(q_1\), and \(q_2\), respectively, in accordance with Table A.1. The following process or its equivalent shall be used to generate the provable primes:

nlen — The intended bit length of the modulus \(n\).

e — The public verification exponent.

seed — The seed obtained using the method in Appendix A.1.2.1.

status — The status of the generation process, where status is either SUCCESS or FAILURE. If FAILURE is returned, then zeros shall be returned as the values for \(p\) and \(q\).

\(p\) and \(q\) — The private prime factors of \(n\).

This section specifies an approved method for the generation of the IFC primes \(p\) and \(q\) with the additional conditions specified in Appendix A.1.1, case B.2, where \(p_1\), \(p_2\), \(q_1\), and \(q_2\) are provably prime, and \(p\) and \(q\) are probably prime. For this method, a random seed is initially required (see Appendix A.1.2.1); the length of the seed is equal to twice the security strength associated with the modulus \(n\). After the first seed is obtained, the primes can be generated.

Let \(bitlen_1\), \(bitlen_2\), \(bitlen_3\), and \(bitlen_4\) be the bit lengths for \(p_1\), \(p_2\), \(q_1\), and \(q_2\), respectively, in accordance with Table A.1. The following process or its equivalent shall be used to construct \(p\) and \(q\).

nlen — The intended bit length of the modulus \(n\).

e — The public verification exponent.

seed — The seed obtained using the method in Appendix A.1.2.1.

a, b — (Optional parameters) Numbers from the set {1, 3, 5, 7} that may be used to add the further requirements \(p \equiv a \bmod 8\), \(q \equiv b \bmod 8\).

status — The status of the generation process, where status is either SUCCESS or FAILURE. If FAILURE is returned, then zeros shall be returned as the values for \(p\) and \(q\).

\(p\) and \(q\) — The private prime factors of \(n\).

Process:

Comment: Generate four primes \(p_1\), \(p_2\), \(q_1\), and \(q_2\) that are provably prime (steps 5.1, 5.2, 6.1, and 6.2).

An approved method that satisfies the constraints of Appendix A.1.1 shall be used for the generation of IFC primes p and q that are probably prime and meet the additional constraints of Appendix A.1.1 (see case B.3). For this case, the prime factors \(p_1\), \(p_2\), \(q_1\), and \(q_2\) are also probably prime.

Four random numbers \(X_{p1}\), \(X_{p2}\), \(X_{q1}\), and \(X_{q2}\) are generated, from which the prime factors \(p_1\), \(p_2\), \(q_1\), and \(q_2\) are determined. \(p_1\), \(p_2\), and an additional random number \(X_p\) are then used to determine p, and \(q_1\), \(q_2\), and a random number \(X_q\) are used to obtain q. Let \(bitlen_1\), \(bitlen_2\), \(bitlen_3\), and \(bitlen_4\) be the bit lengths for \(p_1\), \(p_2\), \(q_1\), and \(q_2\), respectively, chosen in accordance with Table A.1.

The following process or its equivalent shall be used to generate p and q:

nlen — The intended bit length of the modulus n.

e — The public verification exponent.

a, b — (Optional parameters) Numbers from the set {1, 3, 5, 7} that may be used to add the further requirements \(p \equiv a \bmod 8\), \(q \equiv b \bmod 8\).

status — The status of the generation process, where status is either SUCCESS or FAILURE. If FAILURE is returned, then zeros shall be returned as the values for p and q.

p and q — The private prime factors of n.

Process:

An ECDSA key pair d and Q is generated for a set of domain parameters (q, FR, a, b {, domain_parameter_seed}, G, n, h). Two methods are provided for the generation of the private key d and public key Q in sections A.2.1 and A.2.2. One of these two methods shall be used to generate d and Q for both ECDSA and deterministic ECDSA.

In this method, more bits are requested from the DRBG than are needed for d so that the bias produced by the mod function in step 6 is negligible.

The following process or its equivalent may be used to generate an ECDSA key pair.

Input:

The domain parameters that are used for this process. n is a prime number, and G is a point on the elliptic curve.

Output:

Process:

Table A.2: Minimum recommended and required output length l of the DRBG when used for deriving an ECDSA private key via modular reduction for the recommended curves over prime fields GF(p).

In this method, a random number is obtained and tested to determine that it will produce a value of d in the correct range. If d is out of range, an ERROR is returned.

The following process or its equivalent may be used to generate an ECDSA key pair:

Input:

The domain parameters that are used for this process. n is a prime number, and G is a point on the elliptic curve.

Output:

Process:

Comment: Check that \(N \ge 224\); see Table 1 (Section 6.1.1).

EdDSA public keys have exactly b bits, and EdDSA signatures have exactly 2b bits. The value b is a multiple of 8. Therefore, public key and signature lengths are an integral number of octets. For Ed25519, b is 256, so the private key is 32 octets. For Ed448, b is 456, and the private key is 57 octets. See IETF RFC 8032.

The following process or its equivalent may be used to generate an EdDSA key pair.

Inputs:

Output: Valid public-private key pair (d, Q) for domain parameters D. The private key d is a string of b bits, while the public key Q is the encoding of an elliptic curve point.

Process:

ECDSA requires the generation of a new secret number k for each message to be signed. This section provides two methods for the generation of a pseudorandom integer in the interval [1, n−1]. Both methods use the output of a cryptographically strong DRBG and convert this to an integer in this interval where the respective methods differ in how these reduce bias. The method of Section A.3.1 uses additional randomness to ensure that biases introduced during the conversion process are negligible in practice, whereas the method of Section A.3.2 simply checks whether the random output is in the requested interval.

Two methods are provided for the random generation of k; one of these two methods or another approved method shall be used. The cryptographic routine in which these values are used shall know which of these methods has been used.

The valid values of n are provided in Section 6.1.1. Let inverse(k, n) be a function that computes the inverse of a (non-negative) integer k with respect to multiplication modulo the prime number n. A technique for computing the inverse is provided in Appendix B.1.

This method uses a cryptographically strong DRBG to produce a random bit string that is at least 64 bits longer than the bit-size of the requested random integer k in the interval [1, n−1]. More bits are requested from the DRBG than are needed for k so that statistical bias introduced by the modular reduction step is negligible.

The following procedure or its equivalent may be used to generate a random integer in the interval [1, n−1].

Outputs:

Process:

This method uses a cryptographically strong DRBG to produce a random bit string that has the same bit-size as the requested random integer k in the interval \([1, n-1]\). The value of k in the requested range is determined by this bit string. This non-deterministic procedure removes bias in practice.

In this method, a random number is obtained and tested to determine that it will produce a value of k in the correct range. If k is out of range, an ERROR is returned.

The following procedure or its equivalent may be used to generate a random integer per-message secret number in the interval \([1, n-1]\).

Input:

Outputs:

Process:

The deterministic ECDSA signature is generated using the value k, obtained by using the hash of the message M and the private key d as inputs to a deterministic secret number generation process that is based on the HMAC_DRBG specified in SP 800-90A [16]. HMAC_DRBG shall be used with the same hash function as the one used to process the message M prior to signature generation. The generation process is also provided in Section 3.2 of IETF RFC 6979. In this method, the private key d is concatenated with the hash of the message to be signed and used as a seed to instantiate the generation process (i.e., the HMAC_DRBG). Then, nlen bits are requested where nlen is the length in bits of n, the order of the point G. The result is a candidate for k. If k does not lie in the interval \([1, n-1]\), additional nlen-bit outputs are requested until the candidate for k lies in the required interval. Note that this method for generating the per-message secret number does not affect the actual signature generation process but does provide a different signature than is produced using the randomly generated value of k (see Section 6.3.1).

Let hashlen be the length of the hash function output in bits.

Inputs:

Output: Secret number k.

Process:

While (\(k = 0\)) OR (\(k \ge n\)), do

Equivalently, the HMAC_DRBG may be used to generate k; see Section 3.3 in IETF RFC 6979. Note that a new HMAC_DRBG instance is instantiated for each signature generation process.

Key pair generation and per-message secret number generation for ECDSA require random values generated in the interval \([1, n-1]\). This appendix provides two methods which both use the output of an approved (i.e., cryptographically strong) DRBG and convert this to an integer in this interval. The respective methods differ in how they reduce bias.

The method of Appendix A.4.1 reduces the output of this DRBG modulo \(n - 1\) while ensuring that any bias introduced during this conversion process is negligible in practice, whereas the method of Appendix A.4.2 simply checks whether the random output is in the requested interval.

This method uses the output of an approved DRBG in the interval \([0, N-1]\) and converts it to an integer in the interval \([0, n-1]\), simply reducing this output modulo \(n-1\) while ensuring that any biases introduced during this conversion process are negligible in practice. If \(n - 1\) does not divide \(N\), this invariably introduces some bias, no matter the quality of the input distribution, which is easy to determine from \(N\) and \(n\). In particular, if the bit-length of \(N\) is sufficiently larger than that of \(n\), the bias introduced by the modular reduction operation is negligible in practice. The same is true if \(N\) is close to a multiple of \(n\) (e.g., if \(n\) is close to a power of two, and the input distribution is generated by a strong DRBG with a fixed bit-length output). The method ensures that outputs are in the interval \([1, n-1]\).

Inputs:

Output: Integer \(x\) in the interval \([1, n-1]\), or INVALID.