FIPS 186-5
FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION(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

FOREWORD
The Federal Information Processing Standards Publication (FIPS) series of the National Institute ofStandards and Technology (NIST) is the official series of publications relating to standards andguidelines 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

Abstract
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 theidentity 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 theclaimed 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.

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Federal Information Processing Standards Publication 186-5
Published: February 3, 2023
Effective: February 3, 2023 (see the Implementation Schedule)
Announcing the

DIGITAL SIGNATURE STANDARD (DSS)
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 Secretaryof Commerce under 40 U.S.C. 11331.
1. Name of Standard: Digital Signature Standard (DSS) (FIPS 186-5).
2. Category of Standard: Computer Security. Subcategory. Cryptography.
3. Explanation: This standard specifies algorithms for applications requiring a digital signature
rather than a written signature. A digital signature is represented in a computer as a string of bits
and computed using a set of rules and parameters that allow the identity of the signatory and theintegrity of the data to be verified. Digital signatures may be generated on both stored andtransmitted data.
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 userthat 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 hashfunctions to be used are specified in FIPS 180, Secure Hash Standard (SHS), and FIPS 202, SHA3: Permutation-Based Hash and Extendable-Output Functions. FIPS-approved digital signaturealgorithms shall be used with appropriate approved functions (e.g., hash functions such as thosespecified 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 functionthat 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.
iFIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

4. Approving Authority: Secretary of Commerce.
5. Maintenance Agency: Department of Commerce, National Institute of Standards andTechnology, Information Technology Laboratory, Computer Security Division.
6. Applicability: This standard is applicable to all federal departments and agencies for theprotection of sensitive unclassified information that is not subject to section 2315 of Title 10,
United States Code, or section 3502 (2) of Title 44, United States Code. This standard shall be
used in designing and implementing public key-based signature systems that federal departments
and agencies operate or that are operated for them under contract. The adoption and use of thisstandard are available to private and commercial organizations.
7. Applications: A digital signature algorithm allows an entity to authenticate the integrity ofsigned data and the identity of the signatory. The recipient of a signed message 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. A digital signature algorithm is intended for use in electronic mail,electronic funds transfer, electronic data interchange, software distribution, data storage, and otherapplications that require data integrity assurance and data origin authentication.
8. Implementations: A digital signature algorithm may be implemented in software, firmware,
hardware, or any combination thereof. NIST has developed a validation program to test
implementations for conformance to the algorithms in this standard. Information about thevalidation program is available at https://csrc.nist.gov/projects/cmvp. Examples for each digital
signature algorithm are available at https://csrc.nist.gov/projects/cryptographic-standards-andguidelines/example-values.
Agencies are advised that digital signature key pairs shall not be used for other purposes.
9. Other Approved Security Functions: Digital signature implementations that comply withthis standard shall employ cryptographic algorithms, cryptographic key generation algorithms, andkey establishment techniques that have been approved for protecting Federal Governmentsensitive information. Approved cryptographic algorithms and techniques include those that areeither:a. Specified in a Federal Information Processing Standards Publication (FIPS),
b. Adopted in a FIPS or NIST recommendation, orc. Specified in the list of approved security functions for FIPS 140-3.
10. Export Control: Certain cryptographic devices and technical data regarding them are subject
to federal export controls. Exports of cryptographic modules implementing this standard andtechnical data regarding them must comply with these federal regulations and be licensed by the
Bureau of Industry and Security of the U.S. Department of Commerce. Information about export
regulations is available at: https://www.bis.doc.gov.
11. Patents: The algorithms in this standard may be covered by U.S. or foreign patents.
ii

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

12. Implementation Schedule: This standard becomes effective immediately upon final
publication. To facilitate a transition to FIPS 186-5, FIPS 186-4 remains in effect for a period of
one year following the publication of this standard, after which FIPS 186-4 will be withdrawn.
During this period, agencies may elect to use cryptographic modules and practices that conform tothis standard, or may elect to continue to use FIPS 186-4. The implementation schedule forcryptographic modules undergoing validation through the Cryptographic Module Validation
Program will be posted on NIST’s webpage at https://csrc.nist.gov/projects/cmvp under Notices.
13. Specifications: Federal Information Processing Standard (FIPS) 186-5 Digital SignatureStandard (affixed).
14. Qualifications: The security of a digital signature system is dependent on maintaining thesecrecy of the signatory’s private keys. Signatories shall, therefore, guard against the disclosureof their private keys. While it is the intent of this standard to specify general security requirements
for generating digital signatures, conformance to this standard does not ensure that a particular
implementation is secure. It is the responsibility of an implementer to ensure that any module that
implements a digital signature capability is designed and built in a secure manner.
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 anacceptable level of security.
Since a standard of this nature must be flexible enough to adapt to advancements and innovationsin science and technology, this standard will be reviewed every five years in order to assess its
adequacy.
15. Waiver Procedure: The Federal Information Security Management Act (FISMA) does notallow for waivers to Federal Information Processing Standards (FIPS) that are made mandatory by
the Secretary of Commerce.
16. Where to Obtain Copies of the Standard: This publication is available by accessing
https://csrc.nist.gov/publications. Other computer security publications are available at the same
website.
17. How to Cite this Publication: NIST has assigned NIST FIPS 186-5 as the publication
identifier for this FIPS, per the NIST Technical Series Publication Identifier Syntax. NIST
recommends that it be cited as follows:
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
18. Inquiries and comments: Inquiries and comments about this FIPS may be submitted to
fips186-comments@nist.gov.

iii

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Federal Information Processing Standards Publication 186-5
Specifications for the
DIGITAL SIGNATURE STANDARD (DSS)
Table of Contents
1. INTRODUCTION .................................................................................................................................... 1
2. GLOSSARY OF TERMS, ACRONYMS, AND MATHEMATICAL SYMBOLS ...................................... 2
2.1

TERMS AND DEFINITIONS ................................................................................................................. 2

2.2

ACRONYMS ..................................................................................................................................... 52.3

MATHEMATICAL SYMBOLS................................................................................................................ 6

3. GENERAL DISCUSSION ....................................................................................................................... 94

3.1

INITIAL SETUP ............................................................................................................................... 11

3.2

DIGITAL SIGNATURE GENERATION.................................................................................................. 12

3.3

DIGITAL SIGNATURE VERIFICATION AND VALIDATION ....................................................................... 13

THE DIGITAL SIGNATURE ALGORITHM (DSA) ............................................................................... 16

5. THE RSA DIGITAL SIGNATURE ALGORITHM ................................................................................. 16
5.1

RSA KEY PAIR GENERATION ......................................................................................................... 16

5.2

RSA KEY PAIR MANAGEMENT ....................................................................................................... 17

5.3

ASSURANCES ................................................................................................................................ 18

5.4

PKCS #1 ..................................................................................................................................... 18
5.4.1

Mask Generation Functions in RSASSA-PSS ............................................................... 19

6. THE ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM (ECDSA) ............................................ 20
6.1

6.2

6.3

6.4

ECDSA DOMAIN PARAMETERS ..................................................................................................... 20
6.1.1

Domain Parameter Generation ...................................................................................... 20

6.1.2

Domain Parameter Management................................................................................... 21

PRIVATE/PUBLIC KEYS .................................................................................................................. 22
6.2.1

Key Pair Generation ...................................................................................................... 22

6.2.2

Key Pair Management ................................................................................................... 22

ECDSA PER-MESSAGE SECRET NUMBER GENERATION ................................................................. 22
6.3.1

Generation of Per-Message Secret Number for ECDSA .............................................. 22

6.3.2

Generation of the Per-Message Secret Number for Deterministic ECDSA .................. 23

ECDSA DIGITAL SIGNATURE GENERATION AND VERIFICATION ........................................................ 23
6.4.1

ECDSA Signature Generation Algorithm ....................................................................... 24

6.4.2

ECDSA Signature Verification Algorithm ....................................................................... 25iv

FIPS 186-5
6.5

DIGITAL SIGNATURE STANDARD (DSS)

ASSURANCES ................................................................................................................................ 25

7. THE EDWARDS-CURVE DIGITAL SIGNATURE ALGORITHM (EDDSA) ........................................ 26
7.1

EDDSA PARAMETERS ................................................................................................................... 26

7.2

ENCODING .................................................................................................................................... 26

7.3

DECODING .................................................................................................................................... 27

7.4

EDDSA KEY PAIR GENERATION..................................................................................................... 27

7.5

KEY PAIR MANAGEMENT................................................................................................................ 28

7.6

EDDSA SIGNATURE GENERATION ................................................................................................. 28

7.7

EDDSA SIGNATURE VERIFICATION ................................................................................................ 29

7.8

THE PREHASH EDWARDS-CURVE DIGITAL SIGNATURE ALGORITHM (HASHEDDSA).......................... 29
7.8.1

HashEdDSA Signature Generation ............................................................................... 30

7.8.2

HashEdDSA Signature Verification ............................................................................... 31

7.8.3

Differences between EdDSA and HashEdDSA ............................................................. 31

APPENDIX A: KEY PAIR GENERATION .................................................................................................. 33
A.1

A.2

A.3

A.4

IFC KEY PAIR GENERATION ........................................................................................................... 33
A.1.1

Criteria for IFC Key Pairs ............................................................................................... 33

A.1.2

Generation of Random Primes that are Provably Prime ............................................... 35

A.1.3

Generation of Random Primes that are Probably Prime ............................................... 37

A.1.4

Generation of Provable Primes with Conditions Based on Auxiliary Provable Primes . 38

A.1.5

Generation of Probable Primes with Conditions Based on Auxiliary Provable Primes . 40

A.1.6

Generation of Probable Primes with Conditions Based on Auxiliary Probable Primes . 42

ECC KEY PAIR GENERATION ......................................................................................................... 43
A.2.1

ECDSA Key Pair Generation using Extra Random Bits ................................................ 44

A.2.2

ECDSA Key Pair Generation by Rejection Sampling .................................................... 45

A.2.3

EdDSA Key Pair Generation.......................................................................................... 46

ECDSA PER-MESSAGE SECRET NUMBER GENERATION ................................................................. 47
A.3.1

Per-Message Secret Number Generation Using Extra Random Bits ............................ 47

A.3.2

Per-Message Secret Number Generation of Private Keys by Rejection Sampling ....... 48

A.3.3

Per-Message Secret Number Generation for Deterministic ECDSA............................ 49

RANDOM VALUES MOD N................................................................................................................ 50
A.4.1

Conversion of a Bit String to an Integer mod n via Modular Reduction......................... 51

A.4.2

Conversion of a Bit String to an Integer mod n via the Discard Method........................ 51

APPENDIX B: GENERATION OF OTHER QUANTITIES ......................................................................... 53
B.1

COMPUTATION OF THE INVERSE VALUE .......................................................................................... 53

B.2

CONVERSION BETWEEN BIT STRINGS, INTEGERS, AND OCTET STRINGS ........................................... 54
B.2.1

Conversion of a Bit String to an Integer ......................................................................... 54

B.2.2

Conversion of an Integer to a Bit String ......................................................................... 54v

FIPS 186-5

B.3

DIGITAL SIGNATURE STANDARD (DSS)

B.2.3

Conversion of an Integer to an Octet String ................................................................. 55

B.2.4

Conversion of a Bit String to an Octet String ................................................................ 55

PROBABILISTIC PRIMALITY TESTS................................................................................................... 56
B.3.1

Miller-Rabin Probabilistic Primality Test ........................................................................ 57

B.3.2

Enhanced Miller-Rabin Probabilistic Primality Test ....................................................... 58

B.3.3(General) Lucas Probabilistic Primality Test.................................................................. 59

B.4

CHECKING FOR A PERFECT SQUARE .............................................................................................. 60

B.5

JACOBI SYMBOL ALGORITHM ......................................................................................................... 61

B.6

SHAWE-TAYLOR RANDOM_PRIME ROUTINE.................................................................................... 63

B.7

TRIAL DIVISION ............................................................................................................................. 65

B.8

SIEVE PROCEDURE ....................................................................................................................... 65

B.9

COMPUTE A PROBABLE PRIME FACTOR BASED ON AUXILIARY PRIMES ............................................. 66

B.10 CONSTRUCT A PROVABLE PRIME (POSSIBLY WITH CONDITIONS) BASED ON CONTEMPORANEOUSLYCONSTRUCTED AUXILIARY PROVABLE PRIMES................................................................................ 68
APPENDIX C: CALCULATING THE REQUIRED NUMBER OF ROUNDS OF TESTING USING THE
MILLER-RABIN PROBABILISTIC PRIMALITY TEST ........................................................................ 72
C.1

THE REQUIRED NUMBER OF ROUNDS OF THE MILLER-RABIN PRIMALITY TESTS................................ 72

C.2

GENERATING PRIMES FOR RSA SIGNATURES ................................................................................ 73

APPENDIX D: REFERENCES ................................................................................................................... 74
APPENDIX E: REVISIONS (INFORMATIVE) ............................................................................................ 77

List of Figures
FIGURE 1: DIGITAL SIGNATURE PROCESSES ..................................................................................................... 9
FIGURE 2: INITIAL SETUP BY AN INTENDED SIGNATORY .................................................................................... 11
FIGURE 3: DIGITAL SIGNATURE GENERATION .................................................................................................. 13
FIGURE 4: DIGITAL SIGNATURE VERIFICATION AND VALIDATION ....................................................................... 15vi

FIPS 186-5

1.

DIGITAL SIGNATURE STANDARD (DSS)

Introduction

This standard defines methods for digital signature generation that can be used for the protectionof binary data (commonly called a message) and for the verification and validation of thosedigital signatures. Three techniques are approved.
(1) The RSA digital signature algorithm is specified in the Internet Engineering Task Force
Request for Comments (IETF RFC) 8017 [1] and was previously specified in Public Key
Cryptography Standard (PKCS) #1 [2]. FIPS 186-5 approves the use of implementationsof either or both of these standards and specifies key pair generation, as well as additional
requirements.
(2) The Elliptic Curve Digital Signature Algorithm (ECDSA) is specified in this standard.
ECDSA was originally specified in American National Standards (ANS) X9.62 [3](withdrawn). A variant of ECDSA with a deterministic signature generation procedureknown as deterministic ECDSA is also approved and specified in IETF RFC 6979 [4].
Recommended elliptic curves for Federal Government use of ECDSA (including
deterministic ECDSA) are provided in NIST Special Publication (SP) 800-186 [5].
(3) The Edwards Curve Digital Signature Algorithm (EdDSA) is specified in IETF RFC
8032 [6]. FIPS 186-5 approves the use of EdDSA and specifies additional requirements.
Recommended elliptic curves for Federal Government use of EdDSA are provided in SP
800-186 [5]. Also included is HashEdDSA, a version of EdDSA where the EdDSA
signature is generated on the hash of the message rather than the message itself.
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 inFederal 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 thisstandard 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.

1

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

2.

Glossary of Terms, Acronyms, and Mathematical Symbols

2.1

Terms and Definitions

Approved

FIPS-approved and/or NIST-recommended. An algorithm ortechnique 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 ofpossession

Confidence that an entity possesses a private key and any associatedkeying 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 �𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝(𝑆𝑆) − � �� 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 mostsignificant 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 acorresponding private key) and an owner that is authorized to use
the key pair. The certificate contains the owner’s public key andpossibly other information and is digitally signed by a Certification
Authority (i.e., a trusted party), thereby binding the public key to theowner.

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

Claimed signatory

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

Destroy

An action applied to a key or a piece of secret data. After a key or apiece of secret data is destroyed, no information about its value canbe recovered.

2

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Digital signature

The result of a cryptographic transformation of data that, whenproperly implemented, provides a mechanism for verifying origin
authentication, data integrity, and signatory non-repudiation.

Domain parameterseed

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 usuallycommon to a domain of users. An ECDSA or EdDSA cryptographic
key pair is associated with a specific set of domain parameters.

EntityAn 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:
1. (One-way) It is computationally infeasible to find any inputthat maps to any new pre-specified output
2. (Collision-resistant) It is computationally infeasible to find any
two distinct inputs that map to the same output.

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:1. The computation of a digital signature from data, and
2. The verification of a digital signature.

Key pair

A public key and its corresponding private key.

Message

The data that is signed. Also known as “signed data” during thesignature verification and validation process.

Message digest

The result of applying a hash function to a message. Also known asa “hash value.”3

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Non-repudiation

A service that is used to provide assurance of the integrity and originof data in such a way that the integrity and origin can be verified andvalidated 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 ofeach 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 withthe owner and is not made public. The private key is used tocompute a digital signature that may be verified using thecorresponding 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 aslong 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 adigital signature that was generated using the corresponding private
key.
4

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Security strength

A number associated with the amount of work (i.e., the number ofoperations) that is required to break a cryptographic algorithm orsystem.

Shall

Used to indicate a requirement of this standard.

ShouldUsed to indicate a strong recommendation but not a requirement of
this standard. Ignoring the recommendation could result inundesirable 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 andobtaining 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.

2.2

Acronyms

ANS

American National Standard

CA

Certification Authority

5

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

DRBG

Deterministic Random Bit Generator 1

DSA

Digital Signature Algorithm 2

ECDSA

Elliptic Curve Digital Signature Algorithm

EdDSA

Edwards Curve Digital Signature Algorithm 3

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 4

SHA

Secure Hash Algorithm

SP

NIST Special Publication

TTP

Trusted Third Party

XOF

Extendable-Output Function

2.3

Mathematical Symbols

a mod nThe unique remainder r, 0 ≤ r ≤ (n – 1), when integer a is divided
by the positive integer n. For example, 23 mod 7 = 2.

b ≡ a mod n

There exists an integer k such that b – a = kn; equivalently, a modn = b mod n.

d

1. For RSA, the private signature exponent of a private key.
2. For ECDSA and EdDSA, the private key.

e

The public verification exponent of an RSA public key.

G

The base point of an elliptic curve.

GCD(a, b)

Greatest common divisor of the integers a and b.

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.

1

Specified in SP 800-90A

2Specified in FIPS 186-4

3

Specified in IETF RFC 8032

4

Algorithm specified in PKCS #1 and IETF RFC 8017

6

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

LCM(a, b)

The least common multiple of the integers a and b.

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𝐿𝐿−1 ≤ 𝑎𝑎 < 2𝐿𝐿 .

M
min(a, b)n

The message that is signed using the digital signature algorithm.
The minimum of the two positive integers a and b.

1. For RSA, the modulus. The bit length of n, i.e. len(n), is
considered to be the key size.
2. For ECDSA or EdDSA, the order of the base point of theelliptic curve. The bit length of 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 publicverification exponent.

p

1. For RSA, a prime factor of the modulus n.
2. Size of the finite field GF(p)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 andS) are the digital signature components.

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.

⊕

Bitwise logical “exclusive-or” on bit strings of the same length; forcorresponding bits of each bit string, the result is determined asfollows: 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, or 1 ⊕ 1 = 0.
Example: 01101 ⊕ 11010 = 10111+

Addition×

Multiplication/

Divisiona || b

The concatenation of two strings a and b. Either a and b are both
bit strings, or both are byte strings.
7

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)aThe ceiling of a: the smallest integer that is greater than or equal toa. For example, 5 = 5, 5.3 = 6, and –2.1 = –2.

a

The floor of a; the largest integer that is less than or equal to a. For
example, 5 = 5, 5.3 = 5, and –2.1 = −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, …}Used to indicate optional information.

0x

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

[n]XThe elliptic curve point X added to itself n times, for 𝑛𝑛 > 1.

8

FIPS 186-5

3.

DIGITAL SIGNATURE STANDARD (DSS)

General Discussion

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 wasreceived in a transmission or retrieved from storage. A properly implemented digital signaturealgorithm that meets the requirements of this standard can provide these services.

Figure 1: Digital Signature Processes 5
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 apublic and private key and is the owner of that key pair. As shown in Figure 1, the private key isused 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 fromclaiming to be the key pair owner and using the private key to generate fraudulent signatures, theprivate key must remain secret. The approved digital signature algorithms are designed toprevent 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 thatFor EdDSA, the message/data is not hashed before being input into the signature generation and verification
processes.

59FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

they cannot be forged. A number of alternative terms are used in this standard to refer to thesignatory 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, thesignatory is referred to as the claimed signatory until such time as adequate assurance can beobtained of the actual identity of the signatory.
The public key is used in the signature verification process (see Figure 1). The public key neednot 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 bymeans 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 pairused to generate and verify a digital signature. This assurance can only be provided if theowner’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 andobtaining the appropriate assurances. The following are reasons why such assurances are
required:
1. If a verifier does not obtain assurance that a signatory is the actual owner of the key pairwhose public component is used to verify a signature, the problem of forging a signatureis reduced to the problem of falsely claiming an identity. For example, anyone inpossession of a mathematically consistent key pair can sign a message and claim that thesignatory was the President of the United States.
2. If the public key used to verify a signature is not mathematically valid, the arguments
used to establish the cryptographic strength of the signature algorithm may not apply. The
owner may not be the only party who can generate signatures that can be verified withthat public key.
3. If a public key infrastructure cannot provide assurance to a verifier that the owner of a
key pair has demonstrated knowledge of a private key that corresponds to the owner’s
public key, then it may be possible for an unscrupulous entity to have their identity (or anassumed identity) bound to a public key that is (or has been) used by another party. The
unscrupulous entity may then claim to be the source of certain messages signed by that
other party, or it may be possible that an unscrupulous entity has managed to obtainownership of a public key that was chosen with the sole purpose of allowing for theverification of a signature on a specific message.
10

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

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 otherpurpose. 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 theinitial 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.
3.1

Initial Setup

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

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)For the ECDSA and EdDSA algorithms (including HashEdDSA), the intended signatory shallfirst 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] (alsosee 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 forthe 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 tobe 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 theassociated 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 theenvironment 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 amutually 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 arebeyond the scope of this standard. Other means of establishing proof of identity (e.g., byproviding 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 thosemethods meet their security requirements.
3.2

Digital Signature Generation

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 hashfunction.
Depending on the digital signature algorithm to be used, additional information shall beobtained. For example, a random per-message secret number shall be obtained for ECDSA but is
not required for EdDSA and RSA.

12

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

RSA, ECDSA,
and HashEdDSA

EdDSA

Generate a Message Digest

Obtain Additional Information for
the Digital Signature Process

Generate a Digital Signature

Optional

Verify the Digital Signature

Digital Signature Generation Complete

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 signatureshall 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 checkto 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 thesignature, 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 thatgenerates a digital signature).
3.3

Digital Signature Verification and Validation

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 thedomain parameters. The public key and domain parameters may be obtained, for example, from
13

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)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 hashfunction that was used during the digital signature generation process. The received digital
signature is verified in accordance with this standard using the appropriate digital signaturealgorithm, 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 towhether 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 ofthe signatory’s claimed identity, (2) assurance of the validity of the domain parameters (forECDSA 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 togenerate the digital signature at the time that the signature was generated. Methods for theverifier 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 averifier (e.g., the intended recipient of the signed data and associated digital signature). Note thatthe 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 consideredvalid. However, if a verification or assurance process fails, the digital signature shall beconsidered 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 fordetermining the timeliness of digitally signed messages is addressed in SP 800-102,
Recommendation for Digital Signature Timeliness [13].

14FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Actions

Assurances

Get the Claimed
Signatory’s Identifier

Obtain Assurance of the Claimed
Signatory’s Identity

Obtain the Domain
Parameters and Public Key

Obtain Assurance of Domain
Parameter Validity

Generate a Message Digest

Obtain Assurance of the Validityof the Owner’s Public Key

Verify the Digital Signature

Obtain Assurance that the Owner
Possesses the Private Key

Digital Signature Validation Complete

Figure 4: Digital Signature Verification and Validation 6

For EdDSA, the message/data is not hashed into a message digest before being input into the signature generationand verification processes.

615

FIPS 186-5

4

DIGITAL SIGNATURE STANDARD (DSS)The Digital Signature Algorithm (DSA)

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.

5.

The RSA Digital Signature Algorithm

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 areenumerated below (see Section 5.4).
5.1

RSA Key Pair Generation

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 dthat 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 theprivate key exponent d shall be kept secret. Guidance on the protection of these values isprovided in SP 800-57, Part 1. The modulus n and the public key exponent e may be madeknown to anyone.
This standard specifies the use of a modulus whose bit length is an even integer and greater thanor 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 withthe 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 inbits of the hash function output block shall meet or exceed the security strength associated withthe 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 theminimum 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
16

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

functions used during the digital signature process are provided in SP 800-57, Part 1. Both thesecurity 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 ≥ 2048. SP 800-57, Parts 1 and 3 [12, 15], provide further information aboutcomparable 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, thepublic 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 themodulus 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 incompliance 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.
5.2

RSA Key Pair Management

Guidance on the protection of key pairs is provided in SP 800-57, Part 1. The secure use ofdigital signatures depends on the management of an entity’s digital signature key pair as follows:
1. The private key shall be used only for signature generation, as specified in this standard,and shall be kept secret. The public key shall be used only for signature verification, as
specified in this standard, and may be made public.
2. An intended signatory shall have assurance of possession of the private key prior to or
concurrently with using it to generate a digital signature (see Section 3.1).
3. A private key shall be protected from unauthorized access, disclosure, and modification.
4. A public key shall be protected from unauthorized modification (including substitution).
For example, public key certificates that are signed by a CA may provide such protection.
5. A verifier shall be assured of a binding between the public key and the key pair owner(see Section 3).
6. A verifier shall obtain public keys in a trusted manner (e.g., from a certificate signed by a
CA that the entity trusts or directly from the intended or claimed signatory, provided thatthe entity is trusted by the verifier and can be authenticated as the source of the signed
information that is to be verified).
7. Verifiers shall be assured that the claimed signatory is the key pair owner and that the17FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

owner possessed the correct private key at the time the signature was generated (i.e., theprivate key that is associated with the public key used to verify the digital signature) (seeSection 3.3).
8. A signatory and a verifier shall have assurance of the validity of the public key (seeSections 3.1 and 3.3).
5.3

Assurances

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.
5.4

PKCS #1

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.
(a) Implementations that generate RSA key pairs shall use the criteria and methods inAppendix B.3 to generate those key pairs.
(b) For RSASSA-PSS, either an approved hash function or XOF (extendable-output
function) shall be used as the function “Hash” in Sections 9.1.1 and 9.1.2 of RFC 8017.
Approved XOFs are SHAKE128 and SHAKE256, which are specified in FIPS 202.
When SHAKE128 or SHAKE256 is used as the function “Hash,” the output length shallbe 256 or 512 bits, respectively.
(c) For RSASSA-PKCS-v1.5, only approved hash functions shall be used.

(d) Only two prime factors p and q shall be used to form the modulus n = pq.
(e) The exponent e shall be an odd, positive integer such that 216 < 𝑒𝑒 < 2256 .

(f) Random numbers shall be generated using an approved random bit generator, as
specified in SP 800-90A [16].
(g) For RSASSA-PSS, the length (in bytes) of the salt (sLen) shall satisfy 0 ≤ sLen ≤ hLen,
where hLen is the length of the hash function output block (in bytes). This inequality
shall also be checked during the signature verification process, where hLen is determinedby the expected (approved) hash function, and sLen is the actual byte length of the byte
string following the leftmost (most significant) nonzero byte (which should be 0x01) inthe recovered DB.
(h) For RSASSA-PKCS-v1.5, when the hash value is recovered from the encoded message
EM during the verification of the digital signature, 7 the extraction of the ASN.1 value of
the DigestInfo data structure shall be accomplished by either:
7

PKCS #1, v2.2 (Section 8.2.2), provides two methods for comparing the DigestInfo values: 1) comparing the18FIPS 186-5•

DIGITAL SIGNATURE STANDARD (DSS)

Selecting the appropriate number of rightmost (least significant) bits of EM, as
determined by the size of a PKCS #1-defined ASN.1 DER value corresponding to the
expected hash function’s algorithm identifier and output length, regardless of thelength of the padding,
Or (if the DigestInfo is selected by its location with respect to the last byte of
padding),•

Checking that a byte string of the length expected for the ASN.1 DER value ofDigestInfo fills the remaining rightmost (least significant) bytes of EM (i.e., no otherinformation follows the DigestInfo data structure in the encoded message).

Only if the extracted DigestInfo has the appropriate form shall the signature verification processcontinue. Assuming that this is the case, the following two checks shall be performed:
1. The algorithm identifier extracted from DigestInfo shall be examined to verify
that the expected (approved) hash function has been identified.
2. The length of the digest value that is extracted from DigestInfo shall be
determined and verified to be equal to the length of hash values output by the
expected hash function.
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 verificationof 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.
5.4.1 Mask Generation Functions in RSASSA-PSS
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 × (𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 − ℎ𝐿𝐿𝐿𝐿𝐿𝐿 − 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 =SHAKE128�𝐻𝐻, 8 × (𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 − ℎ𝐿𝐿𝐿𝐿𝐿𝐿 − 1)� or 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 = SHAKE256�𝐻𝐻, 8 × (𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 −ℎ𝐿𝐿𝐿𝐿𝐿𝐿 − 1)�. Similarly, for step 7 of Section 9.1.2, instead of dbMask = MGF1(H, emLen – hLen– 1), then dbMask = SHAKE128�𝐻𝐻, 8 × (𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 − ℎ𝐿𝐿𝐿𝐿𝐿𝐿 − 1)� or 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 =SHAKE256�𝐻𝐻, 8 × (𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 − ℎ𝐿𝐿𝐿𝐿𝐿𝐿 − 1)�.

encoded messages EM and EM′ or 2) applying (a not specified) decoding operation. Step (h) above applies to thelatter case.

19

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

6. The Elliptic Curve Digital Signature Algorithm (ECDSA)This standard (FIPS 186-5) specifies (in Section 6.4) methods for digital signature generationand 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 mappingof 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 nothave a good source of quality random numbers.
For signature schemes, secrecy of the private key is critical. This is especially true withdeterministic signature schemes, which return a unique signature computed from the hash of theprivate key and the message. Care must be taken to protect implementations against attacks, suchas side-channel attacks or fault attacks [17, 18, 19, 20, 21, 22]. A cryptographic device may leakcritical 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 toverify the correctness of group arithmetic computations for ECC implementations. These types
of attacks may be of particular concern for hardware implementations of deterministic signatureschemes, as well as embedded or IoT devices and smartcards.
6.1

ECDSA Domain Parameters

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 = (xG, yG)), n is the orderof 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.
6.1.1 Domain Parameter Generation
This standard specifies four ranges for the bit length of n (see Table 1).

20

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Table 1: ECDSA Security Parameters
Bit length of n
( i.e. len(n) )Comparable Security
Strength

224 - 255

approximately len(n)/2;
at least 112 bits

256 - 383

approximately len(n)/2;
at least 128 bits

384 - 511

approximately len(n)/2;
at least 192 bits

≥ 512

approximately len(n)/2;
at least 256 bits

ECDSA and deterministic ECDSA are defined for two arithmetic fields: the finite field GF(p)and the finite field GF(2𝑚𝑚 ). 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 theoutput of the hash function is greater than the bit length of n, then the leftmost len(n) bits of thehash 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 greaterthan 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.
6.1.2 Domain Parameter Management
Each key pair shall be correctly associated with one specific set of domain parameters (e.g., by apublic 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 morethan one purpose (e.g., the same domain parameters may be used for both digital signatures andkey establishment). However, using different domain parameters reduces the risk that key pairs
generated for one purpose could be accidentally used for another purpose.
21

FIPS 186-5

6.2

DIGITAL SIGNATURE STANDARD (DSS)

Private/Public Keys

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 aperiod 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., thepublic 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.
6.2.1 Key Pair Generation
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.
6.2.2 Key Pair Management
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 thatpertain to ECDSA:
1. The validity of the domain parameters shall be assured prior to the generation of the key
pair or the verification and validation of a digital signature (see Section 3).
2. Each key pair shall be associated with the domain parameters under which the key pair
was generated.
3. A key pair shall only be used to generate and verify signatures using the domain
parameters associated with that key pair.
6.3

ECDSA Per-Message Secret Number Generation

A new secret random number k, 0 < 𝑘𝑘 < 𝑛𝑛, shall be generated prior to the generation of each
digital signature for use during the signature generation process. This secret number shall beprotected 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 mod n is the multiplicative inverse of k with respect to multiplication modulon (i.e., 0 < k -1 < n and 1 ≡ (k -1 k) mod n). This inverse is required for the signature generation
process. A technique is provided in Appendix B.1 for deriving k -1 mod n from k.
For (non-deterministic) ECDSA, both k and k -1 may be pre-computed since knowledge of themessage 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.
6.3.1 Generation of Per-Message Secret Number for ECDSA
Methods for randomly generating the per-message secret number are provided in Appendices
22

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

A.3.1 and A.3.2.
6.3.2 Generation of the Per-Message Secret Number for Deterministic ECDSA
Deterministic ECDSA is a variant of ECDSA where the per-message secret number is a functionof 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 withinsufficient 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 inAppendix A.3.3
6.4

ECDSA Digital Signature Generation and Verification

An ECDSA or deterministic ECDSA digital signature (r, s) shall be generated as specified in
Section 6.4.1 using:
1. Domain parameters that are generated in accordance with Section 6.1.1,
2. A private key that is generated as specified in Section 6.2.1,
3. A per-message secret number that is generated as specified in Section 6.3,
4. An approved hash function or XOF (extendable-output function) as discussed below,
and
5. An approved random bit generator (not needed for deterministic ECDSA).
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. WhenSHAKE128 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 theminimum 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 (orXOF) 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 rangesof 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 hashfunction (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 (orXOF) 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 thegeneration or verification of a digital signature. A hash function (or XOF) that provides a lower
23

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

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 alevel no greater than that provided by the hash function (or XOF).
6.4.1 ECDSA Signature Generation Algorithm
Inputs:
1. Bit string M to be signed
2. Private key d in the interval [1, n−1] and domain parameters D
3. Approved hash function or XOF with output length of hashlen bits and a security design
strength that is the same as or greater than the security strength of the key pair
Output:A pair of integers (r, s), each in the interval [1, n−1]

Process:
1. Compute H = Hash(M) using the established hash function or XOF where the bit string H
has hashlen bits.
2. Derive the integer e from H as follows:a. If len(n) ≥ hashlen, set E = H. Otherwise, set E equal to the leftmost log2(n) bits ofH.
b. Convert the bit string E to the integer e as specified in Appendix B.2.1.
3. Generate a per-message secret number k, 0 < 𝑘𝑘 < 𝑛𝑛, for domain parameters D following
one of the procedures in Section 6.3.
4. Compute k -1 mod n using the routine in Appendix B.1.
5. Compute the elliptic curve point R = [k]G.
6. Set 𝑥𝑥𝑅𝑅 to the x-coordinate of the affine representation of the point R = (𝑥𝑥𝑅𝑅 , 𝑦𝑦𝑅𝑅 ).

7. Convert the field element 𝑥𝑥𝑅𝑅 to the integer 𝑟𝑟1 , using the conversion routine in NIST SP
800-186, Appendix F.1.

8. Set r = 𝑟𝑟1 mod n.

9. Compute s = 𝑘𝑘 −1 ⋅ (e + r ⋅ d) mod n.

10. Securely destroy k and 𝑘𝑘 −1 .

11. If r = 0 or if s = 0, and k was generated deterministically (using the procedure in 6.3.2),
then output failure. Otherwise, if r = 0 or if s = 0, then go to Step 3.
12. Output (r, s).
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 𝑘𝑘 −1 shall be protected fromunauthorized disclosure and modification. The per-message secret numbers k and 𝑘𝑘 −1 may be
pre-computed if k is randomly generated. If these numbers are pre-computed, theirconfidentiality and integrity shall be protected in the same manner as the private key.
24

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Note that in the case of deterministic ECDSA, if r = 0 or s = 0, then generating a new permessage 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 andoutputs failure.
6.4.2 ECDSA Signature Verification Algorithm
Inputs:1. Message M
2. A pair of integers (r, s)
3. Purported signature verification key Q and domain parameters D
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 theverification and validation of a digital signature. The validity of the public key Q should also bechecked (see Appendix D.1 of SP 800-186 [5]).
1. Verify that both r and s are integers in the interval [1, n − 1]. Output “reject” ifverification fails.
2. Compute H = Hash(M) using the established hash function or XOF where the bit string H
has hashlen bits.
3. Derive the integer e from H as follows:a. If log 2 (𝑛𝑛) ≥ hashlen, set E = H. Otherwise, set E equal to the leftmost
log 2 (𝑛𝑛) bits of H.

a. Convert the bit string E to the integer e as specified in Appendix B.2.1.
4. Compute s−1 mod n using the routine in Appendix B.1.
5. Compute u = e ⋅ s -1 mod n and v = r ⋅ s -1 mod n.

6. Compute R1 = [u]G + [v]Q. Output “reject” if R1 is the identity element (the point at
infinity).
7. Set xR to the x-coordinate of the affine representation of R1 = (𝑥𝑥𝑅𝑅 , 𝑦𝑦𝑅𝑅 ).

8. Convert the field element 𝑥𝑥𝑅𝑅 to the integer 𝑟𝑟1 , using the conversion routine in SP 800186, Appendix F.1.

6.5

9. Verify that r = 𝑟𝑟1 mod n. Output “reject” if verification fails; output “accept” otherwise.
Assurances

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

25

FIPS 186-5

7.

DIGITAL SIGNATURE STANDARD (DSS)The Edwards-Curve Digital Signature Algorithm (EdDSA)

The Edwards-curve Digital Signature Algorithm (EdDSA) is a digital signature scheme using avariant 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.
7.1

EdDSA Parameters

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 andfault attacks [17, 18, 19, 20, 21, 22]. A cryptographic device may leak critical information withside-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 ofgroup arithmetic computations for ECC implementations. These types of attacks are of particularconcern for hardware implementations of deterministic signature schemes, as well as inembedded 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 =(𝑥𝑥𝐺𝐺 , 𝑦𝑦𝐺𝐺 )), 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 2c. 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 whichcurve is used (per IETF RFC 8032):••

For Ed25519, SHA-512 shall be used.
For Ed448, SHAKE256 (as specified in FIPS 202) shall be used.

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

Encoding

Parameter values used in EdDSA are coded as octet strings, and integers are coded using little8

In this document, some of the notation has been changed from RFC 8032 for consistency with ECDSA notation.

26

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

endian convention (i.e., a 32-octet string h=h[0],...h[31] represents the integer h[0] + 28 × h[1] +... + 2248 × 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 ≤ x, y < p, first encode the y-coordinate asa little-endian string of 32 octets for Ed25519 or 57 octets for Ed448. For Ed25519, the mostsignificant bit of the final octet is always zero, while for Ed448, the most significant octet isalways 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.
7.3

Decoding

For point decoding or “decompression,” square roots modulo p are needed. To decompress an
encoded point for EdDSA:
1. Interpret the octet string as an integer in little-endian representation. The most significant
bit of this integer is the least significant bit of the x-coordinate, denoted as 𝑥𝑥0 . The ycoordinate is recovered simply by clearing this bit. If the resulting value is ≥ p, decoding
fails.
2. To recover the x-coordinate, the curve equation requires x2 = (y2 – 1) / (d y2 – a) mod p.
The denominator is always non-zero mod p. Compute a square root to obtain x. Squareroots can be computed using the Tonelli-Shanks algorithm (see NIST SP 800-186,
Appendix E).
The following routines describe simplified cases to compute square roots for p ≡ 3 mod 4 or p
≡ 5 mod 8. Let u = y2 – 1 and v = d y2 – a.
a) To find a square root of (u/v) if p ≡ 3 mod 4 (as in Ed448), first compute the candidate
root w = (u/v) (p+1)/4 = u3 v (u5v3) (p-3)/4 mod p. If v w2 = u, the square root is x = w.
Otherwise, no square root exists for modulo p, and the decoding fails.
b) To find a square root of (u/v) if p ≡ 5 mod 8 (as in Ed25519), first compute thecandidate root w = (u/v) (p+3)/8 = u v3 (u v7) (p-5)/8 mod p. To find the root, check threecases:• If v w2 = u mod p, the square root is x = w.
• If v w2 = –-u mod p, the square root is x = w × 2((p-1)/4).
• Otherwise, no square root exists for modulo p, and decoding fails.
For both cases, if x = 0 and x0 = 1, point decoding fails. If x mod 2 = x0, then the x-coordinate
is x. Otherwise, the x-coordinate is p – x.
3. Return the decoded point (x,y).

7.4

EdDSA Key Pair Generation

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.
27

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)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 isprovided in Appendix A.2.3.
7.5

Key Pair Management

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 areprovided in Section 6.2.2.
7.6

EdDSA Signature Generation

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:
1. Bit string M to be signed
2. Valid public-private key pair (d, Q) for domain parameters D
3. H: SHA-512 for Ed25519 or SHAKE256 for Ed448
4. For Ed448, a string context set by the signer and verifier with a maximum length of 255
octets; by default, context is the empty string
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 isdefined as the 2b-bit string R || S. The octet strings R and S are derived as follows:
1. Compute the hash of the private key d, H(d) = (h0, h1, ..., h2b-1) using SHA-512 for
Ed25519 and SHAKE256 for Ed448 (H(d)= SHAKE256(d, 912)). H(d) may be precomputed.
2. Using the second half of the digest hdigest2 = hb || ... || h2b-1, define:
2.1

For Ed25519, r = SHA-512(hdigest2 || M); Interpret r as a 64-octet little-endian
integer.

2.2

For Ed448, r = SHAKE256(dom4(0, context) || hdigest2 || M, 912). In IETF RFC
8032, dom4(f, c) is defined to be (“SigEd448” || octet(f) || octet(octetlength(c)) || c).
The string “SigEd448” is in ASCII (8 octets). The value octet(f) is the octet withvalue f, and octetlength(c) is the number of octets in string c. Interpret r as a 114octet little-endian integer.

3. Compute the point [r]G. The octet string R is the encoding of the point [r]G.
4. Derive s from H(d) as in the key pair generation algorithm. Use octet strings R, Q, and M
to define:28

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

4.1 For Ed25519, digest = SHA-512(R || Q || M).
4.2 For Ed448, digest = SHAKE256(dom4(0, context) || R || Q || M, 912).
Interpret digest as a little-endian integer.
5. Compute S = (r + digest × s) mod n. The octet string S is the encoding of the resultant
integer.
6. Form the signature as the concatenation of the octet strings R and S.
7.7

EdDSA Signature Verification

Inputs:1. Message M
2. Signature R || S where R and S are octet strings
3. Purported signature verification key Q that is valid for domain parameters D
4. For Ed448, a string context set by the signer and verifier with a maximum length of 255
octets; by default, context is the empty string
Output: Accept or reject the signature over M as originating from the owner of public key Q.
Process:
1. Decode the first half of the signature as a point R and the second half of the signature as aninteger t. Verify that the integer t is in the range of 0 ≤ t < n. Decode the public key Q into a
point Q’. If any of the decodings fail, output “reject”.
2. Using the established hash function or XOF,
2.1 For Ed25519, compute digest = SHA-512(R || Q || M).
2.2 For Ed448, compute digest = SHAKE256(dom4(0, context) || R || Q || M, 912)
Interpret digest as a little-endian integer u.
3. Check that the verification equation [2ct]G = [2c]R + [2cu]Q’ holds. It’s sufficient, but notrequired, to instead check [t]G = R + [u]Q’. Output “reject” if verification fails; output“accept” otherwise.
7.8

The Prehash Edwards-Curve Digital Signature Algorithm (HashEdDSA)

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 signatureon 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

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

7.8.1 HashEdDSA Signature Generation
Inputs:
1. Bit string M to be signed
2. Valid public-private key pair (d, Q) for domain parameters D
3. H: SHA-512 for Ed25519ph or SHAKE256 for Ed448ph
4. A string context set by the signer and verifier with a maximum length of 255 octets; bydefault, context is the empty string
Output: The signature R || S, where R is an encoding of a point, and S is a little-endian encodedvalue.
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:
1. Compute h(M) = SHA-512(M) for Ed25519ph or h(M) = SHAKE256(M, 512) for
Ed448ph.
2. Compute the hash of the private key d, H(d) = (h0, h1, ..., h2b-1) using SHA-512 for
Ed25519ph and SHAKE256 for Ed448ph (H(d) = SHAKE256(d, 912) ). H(d) may be precomputed.
3. Using the second half of the digest hdigest2 = hb || ... || h2b-1, define:
3.1

For Ed25519ph, r = SHA-512(dom2(1, context ) || hdigest2 || h(M)); r will be 64
octets. In IETF RFC 8032, dom2(f, c) is defined to be the octet string (“SigEd25519
no Ed25519 collisions” || octet(f) || octet(octetlength(c)) || c). The string“SigEd25519 no Ed25519 collisions” is in ASCII (32 octets). The value octet(f) is
the octet with value f, and octetlength(c) is the number of octets in string c. The
string context is set by the signer and verifier (maximum is 255 octets) with theempty string as default.

3.2

For Ed448ph, r = SHAKE256(dom4(1, context) || hdigest2 || h(M), 912), where
context is set by the signer and verifier (maximum is 255 octets) with the empty
string as default. Recall dom4(f,c) is defined in Section 7.6.

In either instance, interpret r as a little-endian integer.
4. Compute the point [r]G. The octet string R is the encoding of the point [r]G.
5. Use octet strings R, Q, and h(M) to define:
5.1 For Ed25519ph, digest = SHA-512(dom2(1, context ) || R || Q || h(M)).
5.2 For Ed448ph, digest = SHAKE256(dom4(1, context ) || R || Q || h(M), 912).
Interpret digest as a little-endian integer.
30

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

6. Compute S = (r + digest × s) mod n. The octet string S is the encoding of the resultant
integer.
7. Form the signature as the concatenation of the octet strings R and S.
7.8.2 HashEdDSA Signature Verification
Inputs:1. Message M
2. Signature R || S where R and S are octet strings
3. Purported signature verification key Q that is valid for domain parameters D
4. A string context set by the signer and verifier with a maximum length of 255 octets; bydefault, context is the empty string
Output: Accept or reject the signature over M as originating from the owner of public key Q.
Process:
1. Decode the first half of the signature as a point R and the second half of the signature as aninteger s. Verify that the integer s is in the range of 0 ≤ s < n. Decode the public key Q into a
point Q’. If any of the decodings fail, output “reject”.
2. Form the bit string HashData as the concatenation of the octet strings R, Q, and h(M) (i.e.,
HashData = R || Q || h(M)) with h(M) = SHA-512(M) for Ed25519ph or h(M) =SHAKE256(M, 512) for Ed448ph.
3. Using SHA-512 or SHAKE256,
3.1 For Ed25519ph, compute digest = SHA-512(dom2(1, context ) || HashData).
3.2 For Ed448ph, compute digest = SHAKE256(dom4(1, context ) || HashData, 912).
Interpret digest as a little-endian integer t.
4. Check that the verification equation [2c s]G = [2c]R + [2ct]Q’ holds. It is sufficient, but notrequired, to instead check [s]G = R + [t]Q’. Output “reject” if verification fails; output“accept” otherwise.
7.8.3 Differences between EdDSA and HashEdDSA
A difference between EdDSA and its prehash version is that HashEdDSA generates a signatureon 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.

31

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)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

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

APPENDIX A: Key Pair Generation
Discrete logarithm cryptography (DLC) is divided into finite field cryptography (FFC) andelliptic 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 instantiateddeterministic random bit generator (DRBG). The DRBG shall have a security strength equal toor greater than the security strength associated with the key pairs and secret numbers to begenerated. 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. Whenrequired by a process in this appendix, the conversion shall be accomplished as specified inAppendix B.2.
A.1

IFC Key Pair Generation

A.1.1 Criteria for IFC Key Pairs
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 andsecrecy of these primes and the private exponent d. The primes p and q shall be generated using
one of the following methods:
A. Both p and q are randomly generated prime numbers (random primes), where p and q
shall both be either:
1. Provable primes (see Appendix A.1.2) or
2. Probable primes (see Appendix A.1.3).
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):•(p–1) has a prime factor p1•(p+1) has a prime factor p2•(q–1) has a prime factor q1•(q+1) has a prime factor q2

where p1, p2, q1 and q2 are called auxiliary primes of p and q.
Using this method, one of the following cases shall apply:
33

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

1. The primes p1, p2, q1, q2, p, and q shall all be provable primes (see Appendix
A.1.4);
2. The primes p1, p2, q1, and q2 shall be provable primes, and the primes p and q
shall be probable primes (see Appendix A.1.5); or
3

The primes p1, p2, q1, q2, p, and q shall all be probable primes (see Appendix
A.1.6).

The minimum lengths for each of the auxiliary primes p1, p2, q1, and q2 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 tothe restrictions in Table A.1. The maximum length is determined by nlen (the sum of thelength 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 p1 and p2, len(p1) + len(p2) shall beless than a value determined by nlen whether p1 and p2 are generated to be probable orprovable primes). 9
Table A.1. Minimum and maximum lengths of p1, p2, q1, and q2
nlen

Min. length of
auxiliary primes
p1, p2, q1, and q2

Max. of len(p1) + len(p2) andlen(q1) + len(q2)p, q Probableprimes 10

p, q Provable primes

2048 ≤ nlen ≤ 3071

> 140 bits

≤ 1007 bits

≤ 494 bits

3072 ≤ nlen ≤ 4095

> 170 bits

≤ 1518 bits

≤ 750 bits

4096 ≤ nlen

> 200 bits

≤ 2030 bits

≤ 1005 bits

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:
1. The public exponent e shall be selected with the following constraints:(a) The public verification exponent e shall be selected prior to generating theprimes, p and q, and the private signature exponent d.

For the probable primes p and q, len(p1) + len(p2) < len(p) – log2(len(p)) – 6, and similarly for len(q1) + len(q2) andlen(q). For the provable primes p and q, len(p1) + len(p2) < len(p)/2 – log2(len(p)) – 7, and similarly for len(q1) +len(q2) and len(q). In each case, len(p) = len(q) = nlen/2.
9

If the constructed probable prime is being chosen to satisfy the (optional) additional c mod 8 requirement, then thesize restriction on the maximum length of len(p1)+len(p2) is slightly less. The corresponding entries of this column
become 1004 bits, 1515 bits, and 2027 bits, respectively. See Appendix B.9.
1034

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)(b) The exponent e shall be an odd positive integer such that:
216 < e < 2256.
Note that the value of e may be any value that meets constraint 1(b) (i.e., e may beeither a fixed value or a random value).
2. The primes p and q shall be selected with the following constraints:(a) (p – 1) and (q – 1) shall be relatively prime to the public exponent e.
(b) The private prime factor p shall be selected randomly and shall satisfy( 2 )(2(nlen / 2) – 1) ≤ p ≤ (2nlen / 2– 1), where nlen is the appropriate length for thedesired security_strength.
(c) The private prime factor q shall be selected randomly and shall satisfy( 2 )(2(nlen / 2) – 1) ≤ q ≤ (2nlen / 2– 1), where nlen is the appropriate length for thedesired security_strength.
(d) |p – q| > 2(nlen / 2) – 100.
3. The private signature exponent d shall be selected with the following constraints after thegeneration of p and q:(a) The exponent d shall be a positive integer value such that
2nlen/ 2 < d < LCM(p – 1, q – 1), and(b) d = e–1 mod (LCM(p – 1, q – 1)).
That is, the inequality in (a) holds, and 1 ≡ (ed) mod LCM(p – 1, q – 1).
In the extremely rare event that d ≤ 2nlen / 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.
A.1.2 Generation of Random Primes that are Provably Prime
An approved method that satisfies the constraints of Appendix A.1.1 shall be used for thegeneration of IFC random primes p and q that are provably prime (see case A.1). One suchmethod is provided in Appendices A.1.2.1 and A.1.2.2. For this method, a random seed isinitially 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.
35

FIPS 186-5

seed

DIGITAL SIGNATURE STANDARD (DSS)

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

Process:
1. If nlen is not valid (see Section 5.1), then Return (FAILURE, 0).
2. Let security_strength be the security strength associated with nlen as specified in SP 80057, Part 1.
3. Obtain a string seed of at least (2 × security_strength) bits from a DRBG that supports
the security_strength.
4. Return (SUCCESS, seed).
A.1.2.2 Construction of the Provable Primes p and q
The following process or its equivalent shall be used to construct the random primes p and q (tobe 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 theother parameters.

p and qThe private prime factors of n.

Process:
1. If nlen < 2048, then return (FAILURE, 0, 0).
2. If ((e ≤ 216) OR (e ≥ 2256) OR (e is not odd)), then return (FAILURE, 0, 0).
3. Set the value of security_strength in accordance with the value of nlen as specified in SP
800-57, Part 1.
4. If (len(seed) < 2 × security_strength), then return (FAILURE, 0, 0).
5. working_seed = seed.
6. Generate p:
6.1

Using L = nlen/2, N1 = 1, N2 = 1, first_seed = working_seed and e, use the provableprime construction method in Appendix B.10 to obtain p and pseed. If FAILURE isreturned, then return (FAILURE, 0, 0).

6.2

working_seed = pseed.

7. Generate q:
7.1

Using L = nlen/2, N1 = 1, N2 = 1, first_seed = working_seed and e, use the provable
36

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

prime construction method in Appendix B.10 to obtain q and qseed. If FAILURE isreturned, then return (FAILURE, 0, 0).
7.2

working_seed = qseed.

8. If ( |p – q| ≤ 2nlen/2 – 100), then go to step 7.
9. Zeroize the internally generated seeds:
9.1

pseed = 0

9.2

qseed = 0

9.3

working_seed = 0

10. Return (SUCCESS, p, q).
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 thegeneration of IFC random primes p and q that are probably prime (see case A.2). In addition, thesecurity 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 ≡ a mod 8, q ≡ b mod 8.

Output:status

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

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

Process:
1. If nlen < 2048, return (FAILURE, 0, 0).
2. If ((e ≤ 216) OR (e ≥ 2256) OR (e is not odd)), then return (FAILURE, 0, 0).
3. Set the value of security_strength in accordance with the value of nlen as specified in SP
800-57, Part 1.
4. Generate p:
37

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

4.1

i = 0.

4.2

Obtain a string p of (nlen/2) bits from a DRBG that supports the security_strength.
4.2.1 (Optional) The two most significant bits in p may be set arbitrarily.

4.3

If p is generated with the p ≡ a mod 8 restriction, then p = p + ((a – p) mod 8),
Else if (p is not odd), then p = p + 1.

4.4

If ((p < ( 2 )(2(nlen / 2) – 1)), then go to step 4.2.

4.5

If (GCD(p − 1, e) = 1), then
4.5.1 Test p for primality as specified in Appendix B.3 using an appropriate
value from Table B-1 in Appendix B.3 as the number of iterations.
4.5.2 If p is PROBABLY PRIME, then go to step 5.

4.6 i= i + 1.
4.7 If (i ≥ 5 × nlen, then return (FAILURE, 0, 0)
Else go to step 4.2.

5. Generate q:
5.1

i = 0.

5.2

Obtain a string q of (nlen/2) bits from a DRBG that supports the security_strength
5.2.1 The two most significant bits in q may be set arbitrarily.

5.3

If q is generated with the q ≡ b mod 8 restriction, then q = q + ((b – q) mod 8),
Else if (q is not odd), then q = q + 1.

5.4

If ((q < ( 2 )(2(nlen / 2) – 1)), then go to step 5.2.

5.5

If (|p – q| ≤ 2nlen/2 – 100), then go to step 5.2.

5.6

If (GCD(q−1, e) = 1) then
5.6.1 Test q for primality as specified in Appendix B.3 using an appropriate
value from Table B-1 in Appendix B.3 as the number of iterations.
5.6.2 If q is PROBABLY PRIME, then return (SUCCESS, p, q).

5.7

i = i + 1.

5.8

If (i ≥ 10 × nlen, then return (FAILURE, 0, 0)

Else go to step 5.2.

A.1.4 Generation of Provable Primes with Conditions Based on Auxiliary
Provable Primes
This section specifies an approved method for the generation of the IFC primes p and q with theadditional conditions specified in Appendix A.1.1, case B.1, where p, p1, p2, q, q1, and q2 are all
38

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

provable primes. For this method, a random seed is initially required (see Appendix A.1.2.1); thelength 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 bitlen1, bitlen2, bitlen3, and bitlen4 be the bit lengths for p1, p2, q1, and q2, respectively, in
accordance with Table A.1. The following process or its equivalent shall be used to generate theprovable primes:
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. If FAILURE is returned, then zeros shall be returned as the values
for p and q.

p and qThe private prime factors of n.

Process:
1. If nlen < 2048, then return (FAILURE, 0, 0).
2. If ((e ≤ 216) OR (e ≥ 2256) OR (e is not odd)), then return (FAILURE, 0, 0).
3. Set the value of security_strength in accordance with the value of nlen as specified in SP
800-57, Part 1.
4. If (len(seed) < 2 × security_strength), then return (FAILURE, 0, 0).
5. working_seed = seed.
6. Generate p:
6.1 Using L = nlen/2, N1 = bitlen1, N2 = bitlen2, firstseed = working_seed, and e, use theprovable prime construction method in Appendix B.10 to obtain p, p1, p2, andpseed. If FAILURE is returned, return (FAILURE, 0, 0).
6.2 working_seed = pseed.
7. Generate q:
7.1

Using L = nlen/2, N1 = bitlen3, N2 = bitlen4 and firstseed = working_seed, and e, use
the provable prime construction method in Appendix B.10 to obtain q, q1, q2, andqseed. If FAILURE is returned, return (FAILURE, 0, 0).

7.2

working_seed = qseed.

8. If ( |p – q| ≤ 2nlen/2 – 100), then go to step 7.
9. Zeroize the internally generated seeds:
9.1

pseed = 0.
39

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

9.2

qseed = 0.

9.3

working_seed = 0.

10. Return (SUCCESS, p, q).
A.1.5 Generation of Probable Primes with Conditions Based on Auxiliary
Provable Primes
This section specifies an approved method for the generation of the IFC primes p and q with theadditional conditions specified in Appendix A.1.1, case B.2, where p1, p2, q1, and q2 are provably
prime, and p and q are probably prime. For this method, a random seed is initially required (seeAppendix A.1.2.1); the length of the seed is equal to twice the security strength associated withthe modulus n. After the first seed is obtained, the primes can be generated.
Let bitlen1, bitlen2, bitlen3, and bitlen4 be the bit lengths for p1, p2, q1, and q2, respectively, in
accordance with Table A.1. The following process or its equivalent shall be used to construct p
and q.
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.

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

Output:status

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

p and qThe private prime factors of n.

Process:
1. If nlen < 2048, then return (FAILURE, 0, 0).
2. If ((e ≤ 216) OR (e ≥ 2256) OR (e is not odd)), then return (FAILURE, 0, 0).
3. Set the value of security_strength in accordance with the value of nlen as specified in
SP 800-57, Part 1.
4. If (len(seed) < 2 × security_strength), then return (FAILURE, 0, 0).
Comment: Generate four primes p1, p2, q1, and q2
that are provably prime (steps 5.1, 5.2, 6.1, and 6.2).
5. Generate p:
40

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

5.1

Using bitlen1 as the length and seed as the input_seed, use the random prime
generation routine in Appendix B.6 to obtain p1 and prime_seed. If FAILURE
is returned, then return (FAILURE, 0, 0) and zeroize all internal variables
generated.

5.2

Using bitlen2 as the length and prime_seed as the input_seed, use the random
prime generation routine in Appendix B.6 to obtain p2 and a new value forprime_seed. If FAILURE is returned, then return (FAILURE, 0, 0) and zeroize
all internal variables generated.

5.3

Generate a prime p using the routine in Appendix B.9 with inputs of p1, p2, nlen,e, security_strength, and, optionally, a, 11 also obtaining Xp. If FAILURE isreturned, then return (FAILURE, 0, 0) and zeroize all internal variables
generated.

6. Generate q:
6.1. Using bitlen3 as the length and prime_seed as the input_seed, use the random
prime generation routine in Appendix B.6 to obtain q1 and a new value forprime_seed. If FAILURE is returned, then return (FAILURE, 0, 0) and zeroize
all internal variables generated.
6.2

Using bitlen4 as the length and prime_seed as the input_seed, use the random
prime generation routine in Appendix B.6 to obtain q2 and a new value forprime_seed. If FAILURE is returned, then return (FAILURE, 0, 0) and zeroize
all internal variables generated.

6.3

Generate a prime q using the routine in Appendix B.9 with inputs of q1, q2, nlen,e, security_strength, and, optionally, b 12, also obtaining Xq. If FAILURE isreturned, then return (FAILURE, 0, 0) and zeroize all internal variables
generated.

7. If ((|p – q| ≤ 2nlen/2 –100) OR (|Xp – Xq| ≤ 2nlen/2 – 100)), then go to step 6.
8. Zeroize the internally generated variables that are not returned:
8.1

Xp = 0.

8.2

Xq = 0.

8.3

prime_seed = 0.

8.4

p1 = 0.

8.5

p2 = 0.

8.6

q1 = 0.

If using the optional parameter a, the upper bounds on the value of len(p1)+len(p2) that are given in Table A.1
shall all be reduced by 3.

11

If using the optional parameter b, the upper bounds on the value of len(q1)+len(q2) that are given in Table A.1
shall all be reduced by 3.

12

41

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

8.7

q2 = 0.

9. Return (SUCCESS, p, q).
A.1.6 Generation of Probable Primes with Conditions Based on Auxiliary
Probable Primes
An approved method that satisfies the constraints of Appendix A.1.1 shall be used for thegeneration of IFC primes p and q that are probably prime and meet the additional constraints ofAppendix A.1.1 (see case B.3). For this case, the prime factors p1, p2, q1, and q2 are also probably
prime.
Four random numbers Xp1, Xp2, Xq1, and Xq2 are generated, from which the prime factors p1, p2,
q1, and q2 are determined. p1, p2, and an additional random number Xp are then used to determinep, and q1, q2, and a random number Xq are used to obtain q. Let bitlen1, bitlen2, bitlen3, andbitlen4 be the bit lengths for p1, p2, q1, and q2, respectively, chosen in accordance with Table A.1.
The following process or its equivalent shall be used to generate p and q:
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 ≡ a mod 8, q ≡ b mod 8.

Output:status

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

p and qThe private prime factors of n.

Process:
1. If nlen < 2048, then return (FAILURE, 0, 0).
2. If ((e ≤ 216) OR (e ≥ 2256) OR (e is not odd)), then return (FAILURE, 0, 0).
3. Set the value of security_strength in accordance with the value of nlen as specified in
SP 800-57, Part 1.
4. Generate p:
4.1

Generate an odd integer Xp1 of length bitlen1 bits and a second odd integer Xp2of length bitlen2 bits using an approved random bit generator that supports the
security_strength.

4.2

Sequentially search successive odd integers, starting at Xp1 until the firstprobable prime p1 is found. Candidate integers shall be tested for primality as
specified in Appendix B.3. Repeat the process to find p2, starting at Xp2. The
42

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

probable primes p1 and p2 shall be the first integers that pass the primality test.
4.3

Generate a prime p using the routine in Appendix B.9 with inputs of p1, p2, nlen,e, security_ strength, and, optionally, a 13, also obtaining Xp. If FAILURE isreturned, return (FAILURE, 0, 0) and zeroize all internal variables generated.

5. Generate q:
5.1

Generate an odd integer Xq1 of length bitlen3 bits and a second odd integer Xq2of length bitlen4 bits using an approved random bit generator that supports the
security_strength.

5.2

Sequentially search successive odd integers, starting at Xq1 until the firstprobable prime q1 is found. Candidate integers shall be tested for primality as
specified in Appendix B.3. Repeat the process to find q2, starting at Xq2. The
probable primes q1 and q2 shall be the first integers that pass the primality test.

5.3

Generate a prime q using the routine in Appendix B.9 with inputs of q1, q2, nlen,e, security_ strength, and, optionally, b, 14 also obtaining Xq. If FAILURE isreturned, return (FAILURE, 0, 0) and zeroize all internal variables generated.

6. If ((|Xp – Xq| ≤ 2nlen/2 –100) OR (|p – q| ≤ 2nlen/2 – 100))), then go to step 5.
7. Zeroize the internally generated values that are not returned:
7.1

Xp = 0.

7.2

Xq = 0.

7.3

Xp1 = 0.

7.4

Xp2 = 0.

7.5

Xq1 = 0.

7.6

Xq2 = 0.

7.7

p1 = 0.

7.8

p2 = 0.

7.9

q1 = 0.

7.10 q2 = 0.
8. Return (SUCCESS, p, q).
A.2

ECC Key Pair Generation

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
If using the optional parameter a, the upper bounds on the value of len(p1)+len(p2) that are given in Table A.1
shall all be reduced by 3.
14
If using the optional parameter b, the upper bounds on the value of len(q1)+len(q2) that are given in Table A.1
shall all be reduced by 3.
13

43

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

key d and public key Q in sections A.2.1 and A.2.2. One of these two methods shall be used togenerate d and Q for both ECDSA and deterministic ECDSA.
Prior to generating ECDSA key pairs, assurance of the validity of the domain parameters (q, FR,a, b {, domain_parameter_seed}, G, n, h) shall have been obtained as specified in Section 3.1.
For both ECDSA and deterministic ECDSA, the valid bit-lengths of n are provided in Table 1 in
Section 6.1.1.
Generation of the public-private key pair (d, Q) for EdDSA shall be done as described by themethod in A.2.3.
A.2.1 ECDSA Key Pair Generation using Extra Random Bits
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:
1. (q, FR, a, b {, domain_parameter_seed}, G, n, h)
The domain parameters that are used for this process. n is a prime number,and G is a point on the elliptic curve.
Output:
1. status

The status returned from the key pair generation procedure. The status will
indicate SUCCESS or an ERROR.

2.

The generated private and public keys. If an error is encountered during
the generation process, invalid values for d and Q should be returned as
represented by Invalid_d and Invalid_Q in the following specification. d isan integer, and Q is an elliptic curve point. The generated private key d isin the interval [1, n–1].

(d, Q)

Process:
1. N = len(n).
Comment: Check that N ≥ 224; see Table 1 (Section 6.1.1).
2. If N is invalid, then return an ERROR indication, Invalid_d, and Invalid_Q.
3. Obtain a string returned_bits of size l from a DRBG with a security strength ofrequested_security_strength (i.e., the security strength associated with N; see SP 80057, Part 1) or more. The output size l should be set to a value that is not less than therecommended output size provided in column 3 of Table A.2, where GF(p) indicatesthe field over which the curve is defined. The output size shall be set to a value that is
not less than the required output size indicated in column 2. Extra bits from the
DRBG are specified to remove the bias produced by the mod function. If an ERROR
indication is returned, then return an ERROR indication, Invalid_d, and Invalid_Q.
4. Convert returned_bits to the (non-negative) integer d using the procedure in
44

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Appendix A.4.1 or an equivalent process with the value of ε set to 2−t, where t is an
integer at least 64. If the procedure outputs INVALID, return an ERROR indication,
Invalid_d, and Invalid_Q.
5. Q = [d]G.
6. Return SUCCESS, d, and Q.
Table A.2: Minimum recommended and required output length l of the DRBG whenused for deriving an ECDSA private key via modular reduction for the recommended
curves over prime fields GF(p).
Prime 15 p

Minimum output-size l(Required)

Minimum output-size l(Recommended)

p224

224

224

p256

288

352

p384

384

384

p521

521

521

p255

252

252

p448

446

446

A.2.2 ECDSA Key Pair Generation by Rejection Sampling
In this method, a random number is obtained and tested to determine that it will produce a valueof 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:
1. (q, FR, a, b {, domain_parameter_seed}, G, n, h)
The domain parameters that are used for this process. n is a prime number,and G is a point on the elliptic curve.
Output:
1. status

The status returned from the key pair generation procedure. The status will
indicate SUCCESS or an ERROR.

2.

The generated private and public keys. If an error is encountered during
the generation process, invalid values for d and Q should be returned, as
represented by Invalid_d and Invalid_Q in the following specification. d is

(d, Q)The primes in this column correspond to the size of the prime fields for the NIST-recommended curves specified
in SP 800-186.
15

45

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

an integer, and Q is an elliptic curve point. The generated private key d isin the interval [1, n–1].
Process:
1. N = len(n).
Comment: Check that N ≥ 224; see Table 1(Section 6.1.1).
2. If N is invalid, then return an ERROR indication, Invalid_d, and Invalid_Q.
3. Obtain a string of N returned_bits from a DRBG with a security strength ofrequested_security_strength (i.e., the security strength associated with N; see SP 80057, Part 1) or more. If an ERROR indication is returned, then return an ERROR
indication, Invalid_d, and Invalid_Q.
4. Convert returned_bits to the (non-negative) integer d using the procedure in Appendix
A.4.2 or an equivalent process. If the procedure outputs INVALID, return an
ERROR indication, Invalid_d, and Invalid_Q.
5. Q = [d]G.
6. Return SUCCESS, d, and Q.
A.2.3 EdDSA Key Pair Generation
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:
1. b: for Ed25519 b = 256, while for Ed448 b = 456.
2. requested_security_strength: 128 bits of security strength for Ed25519 or 224 bits of
security strength for Ed448.
3. H: SHA-512 for Ed25519 or SHAKE256 for Ed448.
Output: Valid public-private key pair (d, Q) for domain parameters D. The private key d is astring of b bits, while the public key Q is the encoding of an elliptic curve point.
Process:
1. Obtain a string of b bits from an approved DRBG (as specified in SP 800-90A [16])with a security strength of requested_security_strength or more. The private key d is thisstring of b bits.
2. Compute the hash of the private key d, H(d) = (h0, h1, ..., h2b-1) using SHA-512 for
Ed25519 and SHAKE256 for Ed448 (H(d)= SHAKE256(d, 912)). H(d) may be precomputed. Note H(d) is also used in the EdDSA signature generation; see Section 7.6.
46

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

3. The first half of H(d), (i.e. hdigest1 = (ℎ0 , ℎ1 , … , ℎ𝑏𝑏−1 )) is used to generate the public
key. Modify hdigest1 as follows:

3.1 For Ed25519, the first three bits of the first octet are set to zero; the last bit of the lastoctet is set to zero; and the second to last bit of the last octet is set to one. That is,ℎ0 = ℎ1 = ℎ2 = 0, ℎ𝑏𝑏−2 = 1, and ℎ𝑏𝑏−1 = 0.
3.2 For Ed448, the first two bits of the first octet are set to zero, all eight bits of the lastoctet are also set to zero, and the last bit of the second to last octet is set to one. Thatis, ℎ0 = ℎ1 = 0, ℎ𝑏𝑏−9 = 1, and ℎ𝑖𝑖 = 0 for 𝑏𝑏 − 8 ≤ 𝑖𝑖 ≤ 𝑏𝑏 − 1.

4. Determine an integer s from hdigest1 using little-endian convention (see Section 7.2).

5. Compute the point [s]G. The corresponding EdDSA public key Q is the encoding (See
Section 7.2) of the point [s]G.
A.3

ECDSA Per-Message Secret Number Generation

ECDSA requires the generation of a new secret number k for each message to be signed. Thissection 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 methodof Section A.3.1 uses additional randomness to ensure that biases introduced during theconversion 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 anotherapproved method shall be used. The cryptographic routine in which these values are used shallknow 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.
A.3.1 Per-Message Secret Number Generation Using Extra Random Bits
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]. Morebits are requested from the DRBG than are needed for k so that statistical bias introduced by themodular reduction step is negligible.
The following procedure or its equivalent may be used to generate a random integer in theinterval [1, n−1].
Inputs:1.

n is a positive integer and a prime number

2. Threshold value t ≥ 64
Outputs:
1. status

The status returned from the secret number generation procedure. The
47

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

status will indicate SUCCESS or FAILURE or an ERROR;
2.

kInteger in the interval [1, n–1]. A value for k shall only be returned if thestatus indicates SUCCESS.

Process:
1. Set N to the bit-length of n. Check that N ≥ 224; see Table 1 (Section 6.1.1).
2. If t < 64, return a FAILURE indication.
3. Obtain a bit string of N+t returned_bits from the established DRBG with requested
security strength (i.e., the security strength associated with N; see SP 800-57, Part 1)
or more. If this procedure returns an ERROR indication, return a FAILURE
indication.
4. Convert returned_bits to the (non-negative) integer k using the procedure in
Appendix A.4.1 or an equivalent process with the value of ε set to 2−t. If theprocedure outputs INVALID, return an ERROR indication.
5. Return a SUCCESS indication and k.
A.3.2 Per-Message Secret Number Generation of Private Keys by Rejection
Sampling
This method uses a cryptographically strong DRBG to produce a random bit string that has thesame bit-size as the requested random integer k in the interval [1, n−1]. The value of k in therequested 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 valueof 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:
1. n is a positive integer and a prime number
Outputs:
1. status

SUCCESS or FAILURE

2. k

Integer in the interval [1, n–1]. A value for k shall only be returned if thestatus indicates SUCCESS.

Process:
1. Set N to the bit-length of n.
Check that N ≥ 224; see Table 1 (Section 6.1.1).
2. Obtain a bit string of N returned_bits from the established DRBG of at least48

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

requested security strength (i.e., the security strength associated with N; see SP 80057, Part 1) or more. If this procedure returns an ERROR indication, return a
FAILURE indication.
3. Convert returned_bits to the (non-negative) integer k using the procedure in
Appendix A.4.2 or an equivalent process. If the procedure outputs INVALID, return
an ERROR indication.
4. Return a SUCCESS indication and k.
A.3.3 Per-Message Secret Number Generation for Deterministic ECDSA
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 shallbe 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 thismethod, the private key d is concatenated with the hash of the message to be signed and used as aseed 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 kdoes not lie in the interval [1, n−1], additional nlen-bit outputs are requested until the candidatefor 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:1. The private key d
2. H, the hash of the message to be signed
3. n, the order of the point G
Output: Secret number k.
Process:
1. Instantiate the per-message secret number generation process
1.1

Convert the private key d to an octet string using the procedure in Appendix
B.2.3.

1.2

Convert the Hash H to an octet string using the procedure in Appendix B.2.4
with modulus n.

1.3

Form seed_material by concatenating the octet string of the private key d withthe octet string of the Hash H.

1.4

Key = 0x00 00...00, where Key is 8 × hashlen / 8 bits in length.
49

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

1.5

V = 0x01 0x01...0x01 where V is 8 × hashlen / 8 bits in length.

1.6

Key = HMAC(Key, V || 0x00 || seed_material).

1.7

V = HMAC(Key, V).

1.8

Key = HMAC(Key, V || 0x01 || seed_material).

1.9

V = HMAC(Key, V).

2. nlen = len(n).
3. k = 0.
4. Generate a candidate value for k by requesting nlen bits from the generation process.
While (k = 0) OR (k ≥ n), do
4.1

temp = Null.

4.2

While (len (temp) < nlen) do:
4.2.1 V = HMAC(Key, V).
4.2.2 temp = temp || V.

4.3

Convert the first nlen bits of the bit string temp into an integer k using theconversion routine in Appendix B.2.1.

4.4

If (0 < k < n), return k 16.

4.5

Key = HMAC(Key, V || 0x00).

4.6

V = HMAC(Key, V).

5. Return k.
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.
A.4

Random Values mod n

Key pair generation and per-message secret number generation for ECDSA require random
values generated in the interval [1, 𝑛𝑛 − 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 inthis 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 ensuringthat any bias introduced during this conversion process is negligible in practice, whereas themethod of Appendix A.4.2 simply checks whether the random output is in the requested interval.

In RFC 6979, before returning k, it is first checked that the resulting value of r in the ECDSA signature will not
equal 0. This will occur with negligible probability and is checked for in step 11 of the ECDSA signature generation
algorithm in Section 6.4.1.

1650

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

A.4.1 Conversion of a Bit String to an Integer mod n via Modular Reduction
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 notdivide 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 ensuresthat outputs are in the interval [1, n−1].
Inputs:
1. Bit string X, of length l.
2. Positive integer 𝑛𝑛, where 2 ≤ 𝑛𝑛 < 2𝑙𝑙 .
3. Threshold value 0 ≤ ε ≤ 2−64 (the upper bound on bias)
Output: Integer x in the interval [1, n−1], or INVALID.
Process:
1. Let l be the length of the bit string X. Set N = 2l, r = N mod (𝑛𝑛 − 1), and 𝜌𝜌 =
2.
3.
4.
5.
6.

𝑟𝑟

. If 𝑁𝑁 <𝑛𝑛−1

𝑛𝑛 then return INVALID.
If 2𝜌𝜌(1 − 𝜌𝜌)(𝑛𝑛 − 1) > 𝜖𝜖 × 𝑁𝑁 or if ε > 2−64, return INVALID.
Convert the bit string X to the integer x using the procedure of Appendix B.2.1.
Set x = x mod (𝑛𝑛 − 1).
Set x = x + 1.
Output x.

A.4.2 Conversion of a Bit String to an Integer mod n via the Discard Method
This method for converting a probability distribution on [0, N−1] into a probability distribution
on the interval [0, n−1] accepts an output in the interval [0, N−1] only if this is also in theinterval [0, n−1] and returns INVALID otherwise. If n is an integer in the interval [N/2, N], thisresults in a distribution that is always close to that of the original distribution. In contrast to themethod in Appendix A.4.1, this method is nondeterministic unless n = N. Note that if n is close
to a power of two, and the input distribution is generated by a strong DRBG with a fixed bitlength output, the probability of returning INVALID is low.
Inputs:
1. Bit string X, of length l.
2. Positive integer n, where 2 ≤ 𝑛𝑛 < 2𝑙𝑙 .

Output: Integer x in the interval [1, n−1], or INVALID.
51

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Process:
1. Set N = 2l, where l is the length of the bit string X.
2. If 𝑛𝑛 ≤ 1, or 𝑛𝑛 ≥ 𝑁𝑁, then output INVALID.
3. Convert the bit string X to the integer x using the procedure of Appendix B.2.1.
4. If x is not an integer in the interval [0, 𝑛𝑛 − 2], output INVALID.
5. Set 𝑥𝑥 = 𝑥𝑥 + 1.
6. Output x.

52

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Appendix B: Generation of Other Quantities
This appendix contains routines for the supplementary processes required for the implementationof this standard. Appendix B.1 is needed to produce the inverse of the per-message secret k (seeSection 6.3 and Appendices A.2.1 and A.2.2) and the inverse of the signature portion s that isused during signature verification (see Section 6.4). The routines in Appendix B.2 are required toconvert between bit strings and integers when implementing this standard. Appendix B.3
contains probabilistic primality tests to be used during the generation of RSA key pairs.
Appendices B.4 and B.5 contain algorithms required during the Lucas probabilistic primality testof Appendix B.3.3 to check for a perfect square and to compute the Jacobi symbol. Appendix
B.6 contains the Shawe-Taylor algorithm for the construction of primes. Appendix B.7 provides
a process to perform trial division as required by the random prime generation routine in
Appendix B.6. The sieve procedure in Appendix C.8 is needed by the trial division routine in
Appendix B.7. The trial division process in Appendix B.7 and the sieve procedure in Appendix
B.8 have been extracted from ANS X9.80 [23], Prime Number Generation, Primality Testing, andPrimality Certificates. Appendix B.9 is required during the generation of RSA key pairs.
Appendix B.10 provides a method for constructing provable primes for RSA (see Appendix
A.1.2.2 and A.1.4).
B.1 Computation of the Inverse Value
Provided that 0 < z < a and 𝐆𝐆𝐆𝐆𝐆𝐆(𝑧𝑧, 𝑎𝑎) = 1, this algorithm is used to compute the multiplicative
inverse z-1 = z–1 mod a, where, 0 < z–1 < a. The algorithm given below is for reference purposes.
Other (constant time) algorithms that produce an equivalent result may be used.
Input:
1. z

The value to be inverted mod a.

2. a

The modulus, a positive integer greater than 1.

Output:
1. status

The status returned from this function, where the status is either
SUCCESS or ERROR.

2. z–1 mod a

The multiplicative inverse of z mod a if it exists.

Process:
1. Verify that a and z are positive integers such that z < a; if not, return an ERROR
indication.
2. Set i = a, j = z, y2 = 0, and y1 = 1.
3. quotient = i/j.
4. remainder = i – ( j × quotient).
5. y = y2 – (y1 × quotient).
6. Set i = j, j = remainder, y2 = y1, and y1 = y.
7. If (j > 0), then go to step 3.
53

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

8. If (i ≠ 1), then return an ERROR indication.
9. Return SUCCESS and z-1 = y2 mod a.
B.2

Conversion between Bit Strings, Integers, and Octet Strings

B.2.1 Conversion of a Bit String to an Integer
An n-long sequence of bits { x1, …, xn } is converted to an integer by the rule
{ x1, … , xn } → (x1 × 2

n–1) + (x2 × 2

n–2) + … + (xn-1 × 2) + xn .

Note that the first bit of a sequence corresponds to the most significant bit of the corresponding
integer, and the last bit corresponds to the least significant bit.
Input:
1. b1, b2, … , bn The bit string to be converted.
Output:
1. C

The requested integer representation of the bit string.

Process:
1. Let (b1, b2, … , bn) be the bits of b from leftmost to rightmost.
2. 𝐶𝐶 = ∑𝑛𝑛𝑖𝑖=1 2(𝑛𝑛−𝑖𝑖) 𝑏𝑏𝑖𝑖
3. Return C.

In this standard, the binary length of an integer C is defined as the smallest integer n satisfying C< 2n .
B.2.2 Conversion of an Integer to a Bit String
An integer x in the range 0 ≤ x < 2n may be converted to an n-long sequence of bits by using its
binary expansion as shown below:
x = (x1 × 2n–1) + (x2 × 2n–2) + … + (xn–1 × 2) + xn → {x1, … , xn}
Note that the first bit of a sequence corresponds to the most significant bit of the corresponding
integer, and the last bit corresponds to the least significant bit.
Input:
1. C

The non-negative integer to be converted.

Output:1. b1, b2, …, bn The bit string representation of the integer C.
Process:54

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

1. Let (b1, b2, …, bn) represent the bit string, where bi = 0 or 1, and b1 is the mostsignificant bit, while bn is the least significant bit.
2. For any integer n that satisfies C < 2n, the bits bi shall satisfy:𝑛𝑛

3. Return b1, b2, …, bn.

𝐶𝐶 = � 2(𝑛𝑛−𝑖𝑖) 𝑏𝑏𝑖𝑖
𝑖𝑖=1

In this standard, the binary length of the integer C is defined as the smallest integer n thatsatisfies C < 2n.
B.2.3

Conversion of an Integer to an Octet String

An integer may be converted to octet strings according to the following procedure:
Inputs:1. Non-negative integers C and L, where C<256L.
Output:
1. Octet-string X of length L.
Process:
1. The integer C can be uniquely written as C=CL−1 256L−1 + CL−2 256L−2 + … + C1 256 +C0, where each coefficient Ci is an integer in the interval [0,255].
2. Set X to the octet string (CL−1, CL-2, …, C1, C0);
3. Output X.
B.2.4

Conversion of a Bit String to an Octet String

An n-long sequence of bits { x1, …, xn } may be converted to an octet string according to thefollowing procedure:
Input:
1. b1, b2, … , bn , the bit string to be converted.
2. N, an integer modulus.
Output:
1. Octet-string X of length L.
Process:55

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

1. Truncate or expand the input bit string to the desired length len(N)a. If n < len(N) then add (len(N)-n) bits (of value zero) to the left of the sequence(i.e., before the input bits in the sequence order).
b. If 𝑛𝑛 ≥ len(N) then the len(N) leftmost bits are kept, and subsequent bits are
discarded.

2. Convert the resulting sequence of bits (b1, b2, … , bk) into an integer value C using the
bit string to integer conversion routine C = ∑ 2(k-i)bi in Appendix B.2.1.
3. If 𝐶𝐶 > 𝑁𝑁, then set C = C mod N.

4. Convert the integer C to a sequence of octets using the routine in Appendix B.2.3, where
C=CL−1 256L−1 + CL−2 256L−2 + … + C1 256 + C0, and each coefficient Ci is an integer in
the interval [0,255].
5. Set X to be the octet string (CL−1, CL-2, …, C1, C0).
6. Output X.
B.3

Probabilistic Primality Tests

A probabilistic primality test may be required during the generation and validation of prime
numbers. An approved robust probabilistic primality test shall be selected and used.
There are several probabilistic algorithms available. The Miller-Rabin probabilistic primality
tests described in Appendices B.3.1 and B.3.2 are versions of a procedure due to M.O. Rabin,based in part on ideas from Gary L. Miller; one of these versions shall be used as the MillerRabin test discussed below. For more information, see [24, p. 395]. For these tests, let the DRBG
be an approved deterministic random bit generator.
There are several Lucas probabilistic primality tests available; the version provided in [25] is
specified in Appendix B.3.3.
Before applying the probabilistic methods for testing primality, an optional trial division test may
be performed (see Appendix B.7). Choose a trial division limit L between 103 and 105 and checkif any of the prime numbers starting with 2 and not exceeding L divide w, where w is the integer
to be tested for primality. This integer may be either p or q, or one of the auxiliary primes p1, p2,
q1, or q2. If this trial division demonstrates that w is a multiple of another prime, then return
COMPOSITE and do not perform any further primality testing for this candidate.
If the trial division was either not performed or it did not find a division factor for the prime
candidate, then further primality testing shall be performed. This standard allows twoalternatives for testing primality: either using several iterations of only the Miller-Rabin test or
using the iterated Miller-Rabin test followed by a single Lucas test. The value of iterations (asused in Appendices B.3.1 and B.3.2) depends on the algorithm being used, the security strength,
the error probability used, the length (in bits) of the candidate prime, and the type of tests to be
performed. Table B.1 lists the minimum number of iterations of the Miller-Rabin tests that shallbe performed. If a prime is used that is not shown in the table, the minimum number of iterations
56

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)of the Miller-Rabin tests needed can be computed using the algorithm given in Appendix C.1.
As stated in Appendix C, if the definition of the error probability that led to the values of thenumber of Miller-Rabin tests for p and q in Table B.1 is not conservative enough, the prescribed
number of Miller-Rabin tests can be followed by a single Lucas test. Since there are no known
non-prime values that pass the two-test combination (i.e., the indicated number of rounds of theMiller-Rabin test with randomly selected bases followed by one round of the Lucas test), thetwo-test combination may provide additional assurance of primality over the use of only theMiller-Rabin test. However, the Lucas test is not required when testing the p1, p2, q1, and q2
values for primality when generating RSA primes. See Appendix C for further information.
Table B.1. Minimum number of rounds of M-R testing when generating primes for use in
RSA Digital Signatures (see Appendix C)
Parameters

M-R Tests Only

M-R Tests Only

p1, p2, q1 and q2 > 140 bits

Error probability = 2-100

Error probability = 2-112

p and q: 1024 bits

For p1, p2, q1 and q2: 32

For p1, p2, q1 and q2: 38

For p and q: 4

For p and q: 5

p1, p2, q1 and q2 > 170 bits

Error probability = 2-100

Error probability = 2 –128

p and q: 1536 bits

For p1, p2, q1 and q2: 27

For p1, p2, q1 and q2: 41

For p and q: 3

For p and q: 4

p1, p2, q1 and q2 > 200 bits

Error probability = 2-100

Error probability = 2 –144

p and q: 2048 bits

For p1, p2, q1 and q2: 22

For p1, p2, q1 and q2: 44

For p and q: 2

For p and q: 4

B.3.1 Miller-Rabin Probabilistic Primality Test
Let DRBG be an approved deterministic random bit generator.
Input:
1. w

The odd integer to be tested for primality. This will be either p or
q, or one of the auxiliary primes p1, p2, q1, or q2.

2. iterations

The number of iterations of the test to be performed; the value
shall be consistent with Table B.1.

Output:
1. status

The status returned from the validation procedure where status iseither PROBABLY PRIME or COMPOSITE.

Process:57

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

1. Let a be the largest integer such that 2a divides w−1.
2. m = (w−1) / 2a.
3. wlen = len (w).
4. For i = 1 to iterations do
4.1

Obtain a string b of wlen bits from a DRBG. Convert b to an integer using thealgorithm in B.2.1.

4.2

If ((b ≤ 1) or (b ≥ w − 1)), then go to step 4.1.

4.3

z = bm mod w.

4.4

If ((z = 1) or (z = w − 1)), then go to step 4.7.

4.5

For j = 1 to a − 1 do.
4.5.1

z = z2 mod w.

4.5.2

If (z = w − 1), then go to step 4.7.

4.5.3

If (z = 1), then go to step 4.6.

4.6 Return COMPOSITE.
4.7 Continue.
5. Return PROBABLY PRIME.
B.3.2 Enhanced Miller-Rabin Probabilistic Primality Test
This method provides additional information when an error is encountered that may be usefulwhen generating or validating RSA moduli. Let DRBG be an approved deterministic random bit
generator.
Input:
1. w

The odd integer to be tested for primality. This will be either p or
q, or one of the auxiliary primes p1, p2, q1, or q2.

2. iterations

The number of iterations of the test to be performed; the value
shall be consistent with Table B.1.

Output:
1. status

The status returned from the validation procedure where status iseither PROBABLY PRIME, PROVABLY COMPOSITEWITH FACTOR (returned with the factor), or PROVABLYCOMPOSITE AND NOT A POWER OF A PRIME.

Process:
1. Let a be the largest integer such that 2a divides w–1.
58

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

2. m = (w – 1) / 2a.
3. wlen = len (w).
4. For i = 1 to iterations do
4.1

Obtain a string b of wlen bits from a DRBG. Convert b to an integer using thealgorithm in B.2.1.

4.2

If ((b ≤ 1) or (b ≥ w – 1)), then go to step 4.1.

4.3

g = GCD(b, w).

4.4

If (g > 1), then return PROVABLY COMPOSITE WITH FACTOR and thevalue of g.

4.5

z = bm mod w.

4.6

If ((z = 1) or (z = w – 1)), then go to step 4.15.

4.7

For j = 1 to a – 1 do.
4.7.1

x = z.

4.7.2

z = x2 mod w.

4.7.3

If (z = w – 1), then go to step 4.15.

4.7.4

If (z = 1), then go to step 4.12.

4.8

x = z.

4.9

z = x2 mod w.

Comment: x = b(w–1)/2 mod w and x ≠ w – 1.

4.10 If (z = 1), then go to step 4.12.
Comment: x = b(w–1) mod w and x ≠ 1.

4.11 x = z.
4.12 g = GCD(x – 1, w).

4.13 If (g > 1), then return PROVABLY COMPOSITE WITH FACTOR and thevalue of g.
4.14 Return PROVABLY COMPOSITE AND NOT A POWER OF A PRIME.
4.15 Continue.
5. Return PROBABLY PRIME.
B.3.3 (General) Lucas Probabilistic Primality Test
The following process or its equivalent shall be used as the Lucas test.
Input:C

The candidate odd integer to be tested for primality.

Output:status Where status is either PROBABLY PRIME or COMPOSITE.
59FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Process:
1. Test whether C is a perfect square (see Appendix B.4). If so, return (COMPOSITE).
2. Find the first D in the sequence {5, –7, 9, –11, 13, –15, 17, …} for which the Jacobi𝐷𝐷symbol � � = −1 and 𝐆𝐆𝐆𝐆𝐆𝐆 �𝐶𝐶,
𝐶𝐶

1−𝐷𝐷
4
𝐷𝐷

� = 1. See Appendix B.5 for an approved method

to compute the Jacobi Symbol. If � � = 0 for any D in the sequence, return
𝐶𝐶(COMPOSITE).

3. K = C + 1.

4. Let Kr Kr – 1 … K0 be the binary expansion of K, with Kr = 1.
5. Set Ur = 1 and Vr = 1.
6. For i = r – 1 to 0, do
6.1 Utemp = Ui+1 Vi+1 mod C.
2
𝑉𝑉 2 +𝐷𝐷𝑈𝑈𝑖𝑖+1

6.2 Vtemp = 𝑖𝑖+1
6.3

2

mod C.

If (Ki = 1), then

𝑈𝑈

6.3.1

Ui = 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡

6.3.2

Vi = 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡

Else

𝑉𝑉

+𝑉𝑉𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡

2+𝐷𝐷𝑈𝑈𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡
2

6.3.3

Ui = Utemp.

6.3.4

Vi = Vtemp.

mod C.
mod C.

7. If (U0 = 0), then return (PROBABLY PRIME). Otherwise, return (COMPOSITE).
Steps 6.2, 6.3.1, and 6.3.2 contain expressions of the form A/2 mod C, where A is an integer, andC is an odd integer. If A/2 is not an integer (i.e., A is odd), then A/2 mod C may be calculated as(A+C)/2 mod C. Alternatively, A/2 mod C = A·(C+1)/2 mod C for any integer A without regard
to A being odd or even.
B.4

Checking for a Perfect Square

The following algorithm may be used to determine whether an n-bit positive integer C is aperfect square. The algorithm is given for reference purposes. Other algorithms that produce anequivalent result may be used.
Input:C The integer to be checked.
Output:status Where status is either PERFECT SQUARE or NOT A PERFECT SQUARE.
60

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Process:
1. Set n, such that 2n > C ≥ 2(n−1).
2. m = n/2.
3. i = 0.
4. Select X0, such that 2m > X0 ≥ 2(m−1).
5. Repeat
5.1

i = i + 1.

5.2

Xi = ((Xi–1)2 + C)/(2Xi–1).

Until (Xi)2 < 2m + C.
6. If C =  Xi  2, thenstatus = PERFECT SQUARE.
Else
status = NOT A PERFECT SQUARE.
7. Return status.
Notes:
1. By starting with X0 > (1/2) Sqrt(C), X0 − Sqrt(C)is guaranteed to be less than X0. Thisinequality is maintained in step 5; i.e., Xi − Sqrt(C)< Xi for all i.
2. For i ≥ 1, 0 ≤ Xi − Sqrt(C) = (Xi–1 − Sqrt(C))2 / (2 Xi–1) < X0/2i.
In particular, 0 ≤ Xm − Sqrt(C) < 1. If Sqrt(C) were an integer, then it would
be equal to the floor of Xm.
3. In general, the inequality Xi − Sqrt(C) < 1 will occur for values of i that are much lessthan m. To detect this, the fact that 2(m−1) ≤ Sqrt(C) < Xi for all i ≥ 1 can be used,Xi − Sqrt(C) = ((Xi)2 − C)/( Xi + Sqrt(C))≤ ((Xi)2 − C)/( 2 Sqrt(C))≤ ((Xi)2 − C)/(2m)Thus, the condition (Xi)2 < 2m + C implies that Xi − Sqrt(C) < 1.
B.5

Jacobi Symbol Algorithm𝑎𝑎This routine computes the Jacobi symbol � �.
Jacobi( ):𝑛𝑛Input:aAny integer. For this standard, the initial value is in the sequence {5, –7, 9, –11,61

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

13, –15, 17, …} as determined by Appendix B.3.3.
Any integer. For this standard, the initial value is the candidate being tested asdetermined by Appendix B.3.3.

nOutput:result The calculated Jacobi symbol.
Process:
1. a = a mod n.
2. If a = 1, or n = 1, then return (1).
3. If a = 0, then return (0).
4. Define e and a1 such that a = 2e a1, where a1 is odd.
5. If e is even, then s = 1.
Else if ((n ≡ 1 mod 8) or (n ≡ 7 mod 8)), then s = 1.
Else if ((n ≡ 3 mod 8) or (n ≡ 5 mod 8), then s = –1.
6. If ((n ≡ 3 mod 4) and (a1 ≡ 3 mod 4)), then s = –s.
7. n1 = n mod a1.
8. Return (s × Jacobi (n1, a1)).
Comment: Call this routine recursively.
Example: Compute the Jacobi symbol for a = 5 and n = 3439601197:
1. n is not 1, and a is not 1, so proceed to Step 2.
2. a is not 0, so proceed to Step 3.
3. 5 = 20 × 5, so e = 0, and a1 = 5.
4. e is even, so s = 1.
5. a1 is not congruent to 3 mod 4, so do not change s.
6. n1 = 2 = n mod 5.
7. Compute and return (1 × Jacobi(2, 5)). This calls Jacobi recursively. Compute the Jacobi
symbol for a = 2 and n = 5:
7.1

n is not 1, and a is not 1, so proceed to Step 7.2.

7.2

a is not 0, so proceed to Step 7.3.

7.3

2 = 21 × 1, so e = 1, and a1 = 1.

7.4 e is odd, and n ≡ 5 mod 8, so set s = –1.
7.5

n is not 3 mod 4, and a1 is not 3 mod 4, so proceed to step 7.6.

7.6

n1 = 0 = n mod 1.
62

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

7.7

Return (–1 × Jacobi(0, 1) = –1). This calls Jacobi recursively. Compute the Jacobi
symbol for a = 0 and n = 1:
7.7.1

n = 1, so return 1.

Thus, Jacobi (0, 1) = 1, so Jacobi (2, 5) = –1×(1) = –1, and Jacobi (5, 3439601197) = 1× (–1) = –1.
B.6

Shawe-Taylor Random_Prime RoutineThis routine is recursive and may be used to construct a provable prime number using a hashfunction.
Let Hash( ) be the selected hash function and let hashlen be the length (in bits) of each output
block of the hash function. The following process or its equivalent shall be used to generate aprime number for this constructive method.
ST_Random_Prime ( ):Input:
1. length

The length of the prime to be generated.

2. input_seed

The seed to be used for the generation of the requested prime.

Output:
1. status

The status returned from the generation routine where status iseither SUCCESS or FAILURE. If FAILURE is returned, thenzeros are returned as the other output values.

2. prime

The requested prime.

3

A seed determined during generation.

prime_seed

4. prime_gen_counter(Optional) A counter determined during the generation of theprime.

Process:
1. If (length < 2), then return (FAILURE, 0, 0 {, 0}).
2. If (length ≥ 33), then go to step 14.
3. prime_seed = input_seed.
4. prime_gen_counter = 0.
Comment: Steps 5 through 7 generate a
pseudorandom integer c of length bits.
5. c = Hash(prime_seed) ⊕ Hash(prime_seed + 1).
6. c = 2length – 1 + (c mod 2length – 1).
7. c = (2 × c / 2 ) + 1.
63

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Comment: The next steps set prime to theleast odd integer greater than or equal to c.
8. prime_gen_counter = prime_gen_counter + 1.
9. prime_seed = prime_seed + 2.
10. Perform a deterministic primality test on c. For example, since c is small, its primality
can be tested by trial division. See Appendix B.7.
11. If (c is a prime number), then
11.1 prime = c.
11.2 Return (SUCCESS, prime, prime_seed {, prime_gen_counter}).
12. If (prime_gen_counter > (4 × length)), then return (FAILURE, 0, 0 {, 0}).
13. Go to step 5.
14. (status, c0, prime_seed, prime_gen_counter) = (ST_Random_Prime (( length / 2 +1), input_seed).
15. If FAILURE is returned, return (FAILURE, 0, 0 {, 0}).
16. iterations = length / hashlen – 1.
17. old_counter = prime_gen_counter.
Comment: Steps 18 through 21 generate a
pseudorandom integer x in the interval[2length – 1, 2length].
18. x = 0.
19. For i = 0 to iterations do
x = x + (Hash(prime_seed + i) × 2i × hashlen).
20. prime_seed = prime_seed + iterations + 1.
21. x = 2length – 1 + (x mod 2length – 1).
Comment: Steps 22 through 25 generate acandidate prime c in the interval [2length – 1,
2length].
22. t = x / (2c0).
23. If (2tc0 + 1 > 2length), then t = 2length – 1 / (2c0).
24. c = 2tc0 + 1.
25. prime_gen_counter = prime_gen_counter + 1.
Comment: The remaining steps test thecandidate prime c for primality.
26. a = 0.
64

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

27. For i = 0 to iterations doa = a + (Hash(prime_seed + i) × 2 i × hashlen).
28. prime_seed = prime_seed + iterations + 1.
29. a = 2 + (a mod (c – 3)).
30. z = a2t mod c.
31. If ((1 = GCD(z – 1, c)) and (1 = 𝑧𝑧 𝑐𝑐0 mod c)), then31.1 prime = c.

31.2 Return (SUCCESS, prime, prime_seed {, prime_gen_counter}).

32. If (prime_gen_counter ≥ ((4 × length) + old_counter)), then return (FAILURE, 0, 0{, 0}).
33. t = t + 1.
34. Go to step 23.
B.7

Trial Division

An integer is proven to be prime by showing that it has no prime factors less than or equal to its
square root. This procedure is not recommended for testing any integers longer than 10 digits.
To prove that c is prime:
1. Prepare a table of primes less than or equal to √𝑐𝑐. This can be done by applying the sieve
procedure in Appendix B.8.

2. Divide c by every prime in the table. If c is divisible by one of the primes, then declare that c
is composite and exit. If convenient, c may be divided by composite numbers. For example,
rather than preparing a table of primes, it might be more convenient to divide by all integers
except those divisible by 3 or 5 (and then check if c is divisible by 3 or 5).
Alternatively, rather than checking if an integer n divides c, computing GCD(n, c) may be
more efficient.
3. Otherwise, declare that c is prime and exit.
B.8

Sieve Procedure

A sieve procedure is described as follows: given a sequence of integers Y0, Y0 + 1, … , Y0 + J, asieve will identify the integers in the sequence that are divisible by primes up to some selected
limit.
Note that the definitions of the mathematical symbols in this process (e.g., h, L, M, p) are internal
to this process only and should not be confused with their use elsewhere in this standard.
Start by selecting a factor base of all the primes pj from 2 up to some selected limit L. The valueof L is arbitrary and may be determined by computer limitations. A good, typical value of L
would be anywhere from 103 to 105.
65

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

1. Compute Sj =Y0 mod pj for all pj in the factor base.
2. Initialize an array of length J + 1 to zero.
3. Starting at Y0 – Sj + pj , let every pjth element of the array be set to 1 (including the firstelement of the array if Sj = 0). Do this for the entire length of the array and for every j.
4. When finished, if the index i of the array is set to 1, then 𝑌𝑌0 + 𝑖𝑖 − 1 is divisible by somesmall prime and is therefore composite.

The array can be either a bit array for compactness when memory is small or a byte array forspeed when memory is readily available. There is no need to sieve the entire sieve interval atonce. The array can be partitioned into suitably small pieces, sieving each piece before going onto the next piece. When finished, every location with the value 0 is a candidate for prime testing.
The amount of work for this procedure is approximately M log log L, where M is the length of
the sieve interval. This is a very efficient procedure for removing composite candidates forprimality testing. If L = 105, the sieve will remove about 96 % of all composites.
In some cases, rather than having a set of consecutive integers to sieve, the set of integers to betested consists of integers lying in an arithmetic progression Y0, Y0 + h, Y0 + 2h, …, Y0 + Jh,
where h is large and not divisible by any primes in the factor base.
1. Select a factor base and initialize an array of length J + 1 to 0.
2. Compute Sj =Y0 mod pj for all pj in the factor base.
3. Compute Tj = h mod pj and r = – Sj Tj – 1 mod pj.
4. Starting at Y0 + r, let every pjth element of the array be set to 1 (including the first elementof the array if Sj = 0). Do this for the entire length of the array and for every j. Note thatthe position Y0 + r in the array actually denotes the number Y0 + rh.
5. When finished, if the index i of the array is set to 1, then 𝑌𝑌0 + (𝑖𝑖 − 1)ℎ is divisible bysome small prime and is therefore composite.

Note: The prime “2” takes the longest amount of time (M/2) to sieve since it touches the most
locations in the sieve array. An easy optimization is to combine the initialization of the sieve
array with the sieving of the prime “2.” It is also possible to sieve the prime “3” duringinitialization. These optimizations can save about 1/3 of the total sieve time.
B.9

Compute a Probable Prime Factor Based on Auxiliary Primes

This routine constructs a probable prime (a candidate for p or q) using two auxiliary prime
numbers and the Chinese Remainder Theorem (CRT).
Input:
r1 and r2

Two odd prime numbers satisfyinglen(r1)+len(r2) ≤ (nlen/2) – log2(nlen/2) – 7.
If the constructed probable prime must satisfy the additional c mod
8 requirement (see below), then the size restriction on r1 and r2
becomes len(r1)+len(r2) ≤ (nlen/2) – log2(nlen/2) – 10.
66

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)nlen

The desired length of n, the RSA modulus.

e

The public verification exponent.

security_strength

The minimum security strength required for random number
generation.

c(An optional parameter) A number from the set {1, 3, 5, 7} that
may be used to add the further requirement that the computed
prime is equal to c mod 8.

Output:status

The status returned from the generation procedure, where status iseither SUCCESS or FAILURE. If FAILURE is returned, thenzeros are returned as the other output values.

private_prime_factor The prime factor of n.
The random number used during the generation of theprivate_prime_factor.

X
Process:

1. If GCD(2r1, r2) ≠ 1, then return (FAILURE, 0, 0).
2. R = ((r2–1 mod 2r1) × r2) – (((2r1)–1 mod r2) × 2r1).
Comment: Apply the CRT so that R ≡ 1 mod2𝑟𝑟1 and R ≡ –1 mod 𝑟𝑟2 .

3. Generate a random number X using an approved random bit generator that supports
the security_ strength, such that √2�2𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛/2−1 � ≤ 𝑋𝑋 ≤ �2𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛/2 − 1�.
4. Y = X + ((R – X) mod 2r1r2).

Comment: Y is the first odd integer ≥ X,
such that r1 is a prime factor of Y–1, and r2
is a prime factor of Y+1.

4.1 If there is an additional requirement that the computed prime is equal to c mod 8,
then set Y to the only element of the following values {Y, Y + 2r1r2, Y + 4r1r2, Y +6r1r2} that is equal to c mod 8.
Comment: The next steps determine therequested prime number by constructing
candidates from a sequence and performing
primality tests.
5. i = 0.
6. If (Y ≥ 2nlen/2), then go to step 3.
7. If (GCD(Y–1, e) = 1), then
7.1 Check the primality of Y as specified in Appendix B.3. If PROBABLY PRIME
is not returned, go to step 8.
67

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

7.2 private_prime_factor = Y.
7.3 Return (SUCCESS, private_prime_factor, X).
8. i = i + 1.
9. If (i ≥ 20(nlen/2)), then return (FAILURE, 0, 0).
10. If the Y ≡ c mod 8 condition is required then Y = Y + (8r1r2),
Else Y = Y + (2r1r2).
11. Go to step 6.
B.10 Construct a Provable Prime (Possibly with Conditions) Based onContemporaneously Constructed Auxiliary Provable Primes
The following process (or its equivalent) shall be used to generate an L-bit provable prime p (acandidate for one of the prime factors of an RSA modulus). Note that the use of p in thisspecification is used generically; both RSA prime factors p and q may be generated using thismethod.
If a so-called “strong prime” is required, this process can generate primes p1 and p2 (of specified
bit-lengths N1 and N2) that divide p − 1 and p + 1, respectively. The resulting prime p will satisfy
the conditions traditionally required of a strong prime, provided that the requested bit-lengths forp1 and p2 have appropriate sizes.
Regardless of the bit-lengths selected for p1 and p2, the quantity p − 1 will have a prime divisor
p0 whose bit-length is slightly more than half that of p. In addition, the quantity p0 −1 will have aprime divisor whose bit-length is slightly more than half that of p0.
This algorithm requires that N1 + N2 ≤ L – L/2 – 4. Values for N1 and N2 should be chosen suchthat N1 + N2 ≤ (L/2) – log2(L) – 7 to ensure that the algorithm can generate as many as 5L distinct
candidates for p.
Let Hash be the selected hash function to be used, and let hashlen be the length (in bits) of each
output block of the hash function.
Provable_Prime_Construction():Input:
1. L

A positive integer equal to the requested bit-length for p. Note that
acceptable values for L = nlen/2 are computed as specified inAppendix B.3.1, criteria 2(b) and (c), with nlen assuming a value
specified in Table B.1.

2. N1

A positive integer equal to the requested bit-length for p1. If N1 ≥2, then p1 is an odd prime of N1 bits; otherwise, p1 = 1. Acceptablevalues for N1 ≥ 2 are provided in Table A.1

3. N2

A positive integer equal to the requested bit-length for p2. If N2 ≥2, then p2 is an odd prime of N2 bits; otherwise, p2 = 1.
Acceptable values for N2 ≥ 2 are provided in Table A.1
68

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

4. firstseed

A bit string equal to the first seed to be used.

5. e

The public verification exponent.

Output:
1. status

The status returned from the generation procedure, where status iseither SUCCESS or FAILURE. If FAILURE is returned, thenzeros are returned as the other output values.

2. p, p1, p2

The required prime p, along with p1 and p2 having the property that
p1 divides p − 1 and p2 divides p + 1.

3. pseed

A seed determined during generation.

Process:
1. If L, N1, and N2 are not acceptable, then return (FAILURE, 0, 0, 0, 0).
Comment: Generate p1 and p2, as well as theprime p0.
2. If N1 = 1, then
2.1

p1 = 1.

2.2

p2seed = firstseed.

3. If N1 ≥ 2, then
3.1

Using N1 as the length and firstseed as the input_seed, use the random prime
generation routine in Appendix B.6 to obtain p1 and p2seed.

3.2

If FAILURE is returned, then return (FAILURE, 0, 0, 0, 0).

4. If N2 = 1, then
4.1

p2 = 1.

4.2

p0seed = p2seed.

5. If N2 ≥ 2, then
5.1

Using N2 as the length and p2seed as the input_seed, use the random prime
generation routine in Appendix B.6 to obtain p2 and p0seed.

5.2

If FAILURE is returned, then return (FAILURE, 0, 0, 0, 0).

6. Using L / 2 + 1 as the length and p0seed as the input_seed, use the random prime
generation routine in Appendix B.6 to obtain p0 and pseed. If FAILURE is returned,
then return (FAILURE, 0, 0, 0, 0).
Comment: Generate a (strong) prime p in
the interval [( 2 )(2L−1), 2L −1].
7. If GCD(p0p1, p2) ≠ 1, then return (FAILURE, 0, 0, 0, 0).
69

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

8. iterations = L / hashlen −1.
9. pgen_counter = 0.
Comment: Generate pseudo-random x in theinterval [( 2 )(2L−1) − 1, 2L − 1].
10. x = 0.
11. For i = 0 to iterations do
x = x + (Hash(pseed + i))× 2 i × hashlen.
12. pseed = pseed + iterations + 1.
13. x = ( 2 )(2L−1) + ( x mod (2L − ( )(2L−1) ) ).
Comment: Generate a candidate for theprime p.
14. Compute y in the interval [1, p2] such that ( y p0 p1 – 1) = 0 mod p2 (the inverse
algorithm of B.1 may be used).
15. t = ((2 y p0 p1) + x)/(2 p0 p1 p2).
16. If ((2(t p2 − y) p0 p1 + 1) > 2L), thent = ( (2 y p0 p1) + ( )(2L−1) ) / (2 p0 p1 p2).
Comment: p satisfies
0 = ( p–1) mod (2p0 p1) and
0 = ( p+1) mod p2.
17. p = 2(t p2 − y) p0 p1 + 1.
18. pgen_counter = pgen_counter + 1.
19. If (GCD(p – 1, e) = 1), thenComment: Choose an integer a in theinterval [2, p – 2].
19.1 a = 0
19.2 For i = 0 to iterations doa = a + (Hash(pseed + i))× 2 i × hashlen.
19.3 pseed = pseed + iterations + 1.
19.4 a = 2 + (a mod (p – 3)).
Comment: Test p for primality:
19.5 z = a2(t p2 − y) p1 mod p.
19.6 If 1 = GCD(z – 1, p) and 1 = z p0 mod p, then return (SUCCESS, p, p1, p2,
pseed).
70

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

20. If pgen_counter ≥ 5L, then return (FAILURE, 0, 0, 0, 0).
21. t = t + 1.
22. Go to step 16.

71

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Appendix C: Calculating the Required Number of Rounds of Testing
Using the Miller-Rabin Probabilistic Primality Test
(Informative)
C.1

The Required Number of Rounds of the Miller-Rabin Primality Tests

The ideas of [26] were applied to estimate pk,t , the probability that an odd k-bit integer thatpasses t rounds of Miller-Rabin (M-R) testing is actually composite. The probability pk,t isunderstood as the ratio of the number of odd composite numbers of a binary length k that can be
expected to pass t rounds of M-R testing (with randomly generated bases) to the sum of thatvalue and the number of odd prime integers of binary length k. This is equivalent to assumingthat candidates selected for testing will be chosen uniformly at random from the entire set of odd
k-bit integers. Following Pomerance et al., pk,t can be (over) estimated by the ratio of the
expected number of odd composite numbers of binary length k that will pass t rounds of M-R
testing (with randomly generated bases) to the total number of odd primes of binary length k.
From the perspective of a party charged with the responsibility of generating a k-bit prime, theobjective is to determine a value of t such that pk,t is no greater than an acceptably small target
value ptarget.
Using [26], it is possible to compute an upper bound for 𝑝𝑝𝑘𝑘,𝑡𝑡 as a function of k and t. From this,an upper bound can be computed for t as a function of k and ptarget, the maximum allowed
probability of accidentally generating a composite number. The following is an algorithm forcomputing t:
1.

For t = 1, 2 … –log2(ptarget)/2
1.1 For M = 3, 4 …�2√𝑘𝑘 − 1 − 1�
1.1.1
1.1.2

(1)

Compute 𝑝𝑝𝑘𝑘,𝑡𝑡 as in (2).
If pk,t ≤ ptarget
1.1.2.1

Accept t.

1.1.2.2

Stop.

In (1), k is the bit length of the candidate primes, and (2) is as follows:
𝑝𝑝𝑘𝑘,𝑡𝑡 = 2.00743 ∙ ln (2) ∙ 𝑘𝑘 ∙ 2−𝑘𝑘 �2𝑘𝑘−2−𝑀𝑀𝑀𝑀 +8(𝜋𝜋2 −6)3

1

𝑚𝑚−(𝑚𝑚−1)𝑡𝑡 ∑𝑚𝑚
2𝑘𝑘−2 ∑𝑀𝑀
𝑚𝑚=3 2
𝑗𝑗=2 (𝑗𝑗+(𝑘𝑘−1)/𝑗𝑗) �. (2)2Using this expression for t, the following methodologies are used for testing the RSA candidate
primes.

WARNING: Care must be taken when using the phrase “error probability” in connection withthe recommended number of rounds of M-R testing. The probability that a composite number
survives t rounds of Miller-Rabin testing is not the same as pk,t , which is the probability that a
number surviving t rounds of Miller-Rabin testing is composite. Ordinarily, the latter probability
is the one that should be of most interest to a party responsible for generating primes, while theformer may be more important to a party responsible for validating the primality of a number
72

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

generated by someone else. However, for sufficiently large k (e.g., k ≥ 51), it can be shown that
pk,t ≤ 4–t under the same assumptions concerning the selection of candidates as those made toobtain formula (2) (see [26]). In such cases, t = –log2(ptarget)/2 rounds of Miller-Rabin testing
can be used to both generate and validate primes with ptarget serving as an upper bound on boththe probability that the generation process yields a composite number and the probability that acomposite number would survive an attempt to validate its primality.
C.2

Generating Primes for RSA Signatures

When generating primes for the RSA signature algorithm, it is still very important to reduce theprobability of errors in the M-R testing procedure. However, since the (probable) primes are used
to generate a user’s key pair, if a composite number survives the testing process, theconsequences of the error may be less dramatic than in the case of generating DSA domain
parameters; only one user’s transactions are affected rather than a domain of users. Furthermore,
if the p or q value generated for some user is composite, the problem will not be undiscovered
for long since it is almost certain that signatures generated by that user will not be verifiable.
Therefore, when generating the RSA primes p and q, it is sufficient to use the number of rounds
derived from (1) and (2) in Appendix C.1 as the minimum number of M-R tests to be performed.
However, if the definition of pk, t is not considered to be sufficiently conservative when testing p
and q, it is recommended that the t rounds of Miller-Rabin tests be followed by a single Lucas
test.
The lengths for p and q that are recommended for use in RSA signature algorithms are at least
1024 bits. Recall that n = pq, so the corresponding lengths for n are the sum of the lengths of pand q. The security strengths for various sizes of n are provided in SP 800-57, Part 1. Hence, it
makes sense to match the number of rounds of Miller-Rabin testing to the target error probability
values of 2–s, where s is the security strength for an n-bit modulus. A probability of 2–100 is
included for all prime lengths since this probability has often been used in the past and may be
acceptable for many applications.
When generating the RSA primes p and q with conditions, it is sufficient to use the value tderived from (1) and (2) as the minimum number of M-R tests to be performed when generating
the auxiliary primes p1, p2, q1, and q2. It is not necessary to use an additional Lucas test on thesenumbers. In the extremely unlikely event that one of the numbers p1, p2, q1, or q2 is composite,
there is still a high probability that the corresponding RSA prime (p or q) will satisfy therequisite conditions.
The sizes of p1, p2, q1, and q2 were chosen to ensure that, for an adversary with significant but
not overwhelming resources, Lenstra’s elliptic curve factoring method [27] (against which there
is no protection beyond choosing large p and q) is a more effective factoring algorithm than the
Pollard P–1 method [27], the Williams P+1 method [28], or various cycling methods [27]. For anadversary with overwhelming resources, the best all-purpose factoring algorithm is assumed tobe the General Number Field Sieve [27].
Table B.1 in Appendix B.3 specifies the minimum number of rounds of M-R testing whengenerating primes to be used in the construction of RSA signature key pairs.

73

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Appendix D: References[1] Moriarty K (ed.), Kaliski B, Jonsson J, Rusch A (2016) PKCS #1: RSA Cryptography
Specifications Version 2.2. (Internet Engineering Task Force (IETF)), IETF Request forComments (RFC) 8017. https://doi.org/10.17487/RFC8017[2] Public Key Cryptography Standard (PKCS) #1, RSA Encryption Standard.
[3] Accredited Standards Committee X9 (2005) Public Key Cryptography for the Financial
Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). (American
National Standards Institute), American National Standard for Financial Services (ANS)
X9.62-2005, Withdrawn.
[4] Pornin T (2013) Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic
Curve Digital Signature Algorithm (ECDSA). (Internet Engineering Task Force (IETF)),
IETF , Request for Comments (RFC) 6979. https://doi.org/10.17487/RFC6979[5] Chen L, Moody D, Regenscheid A, Robinson A, Randall K (2023) Recommendations for
Discrete-Logarithm Based Cryptography: Elliptic Curve Domain Parameters. (National
Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP)
800-186. https://doi.org/10.6028/NIST.SP.800-186[6] Josefsson S, Liusvaara I (2017) Edwards-Curve Digital Signature Algorithm (EdDSA).
(Internet Research Task Force (IRTF)), IRTF Request for Comments (RFC) 8032.
https://doi.org/10.17487/RFC8032[7] National Institute of Standards and Technology (2013) Digital Signature Standard (DSS).
(U.S. Department of Commerce, Washington, DC), Federal Information Processing
Standards Publication (FIPS) 186-4. https://doi.org/10.6028/NIST.FIPS.186-4[8] Barker EB (2006) Recommendation for Obtaining Assurances for Digital Signature
Applications. (National Institute of Standards and Technology, Gaithersburg, MD), NIST
Special Publication (SP) 800-89. http://doi.org/10.6028/NIST.SP.800-89[9] Barker EB, Roginsky AL (2019) Transitioning the Use of Cryptographic Algorithms and
Key Lengths. (National Institute of Standards and Technology, Gaithersburg, MD), NIST
Special Publication (SP) 800-131A, Rev. 2. https://doi.org/10.6028/NIST.SP.800-131Ar2[10] National Institute of Standards and Technology (2015) Secure Hash Standard (SHS). (U.S.
Department of Commerce, Washington, DC), Federal Information Processing Standards
Publication (FIPS) 180-4. https://doi.org/10.6028/NIST.FIPS.180-4[11] National Institute of Standards and Technology (2015) SHA-3 Standard: Permutation-BasedHash and Extendable-Output Functions. (U.S. Department of Commerce, Washington, DC),
Federal Information Processing Standards Publication (FIPS) 202.
https://doi.org/10.6028/NIST.FIPS.202[12] Barker EB (2020) Recommendation for Key Management: Part 1 – General. (National
Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP)
800-57 Part 1, Rev. 5. https://doi.org/10.6028/NIST.SP.800-57pt1r5[13] Barker EB (2009) Recommendation for Digital Signature Timeliness. (National Institute ofStandards and Technology, Gaithersburg, MD), NIST Special Publication (SP) 800-102.
https://doi.org/10.6028/NIST.SP.800-102[14] Barker EB, Chen L, Roginsky AL, Vassilev A, Davis R, Simon S (2019) Recommendation
for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National
74

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP)
800-56B, Rev. 2. https://doi.org/10.6028/NIST.SP.800-56Br2[15] Barker EB, Dang QH (2015) Recommendation for Key Management, Part 3: ApplicationSpecific Key Management Guidance. (National Institute of Standards and Technology,
Gaithersburg, MD), NIST Special Publication (SP) 800-57 Part 3, Rev. 1.
https://doi.org/10.6028/NIST.SP.800-57pt3r1[16] Barker EB, Kelsey JM (2015) Recommendation for Random Number Generation Using
Deterministic Random Bit Generators. (National Institute of Standards and Technology,
Gaithersburg, MD), NIST Special Publication (SP) 800-90A, Rev. 1.
https://doi.org/10.6028/NIST.SP.800-90Ar1[17] Ambrose C, Bos JW, Fay B, Joye M, Lochter M, Murray B (2017) Differential Attacks on
Deterministic Signatures. RSA Conference Cryptographers’ Track, CT-RSA, (Springer, San
Francisco, CA), LCNS, vol. 10808 pp.339-353. https://doi.org/10.1007/978-3-319-769530_18[18] Barenghi A, Pelosi G (2016) A Note on Fault Attacks Against Deterministic Signature
Schemes. 11th International Workshop on Security, IWSEC 2016 (Springer, Tokyo, Japan),
LNCS, vol. pp 182-192. https://doi.org/10.1007/978-3-319-44524-3_11[19] Biehl I, Meyer B, Müller V (2000) Differential Fault Attacks on Elliptic Curve
Cryptosystems. 20th Annual International Cryptology Conference, CRYPTO 2000
(Springer, Santa Barbara, CA), pp 131-146. https://doi.org/10.1007/3-540-44598-6_8[20] Biham E, Shamir A (1997) Differential fault analysis of secret key cryptosystems. 17th
Annual International Cryptology Conference, CRYPTO '97 (Springer, Santa Barbara, CA),
pp 513-525. https://doi.org/10.1007/BFb0052259[21] Boneh D, DeMillo RA, Lipton RJ (2001) On the Importance of Eliminating Errors in
Cryptographic Computations. Journal of Cryptology 14(2):101-119.
https://doi.org/10.1007/s001450010016[22] Poddebniak D, Somorovsky J, Schinzel S, Lochter M, Rösler P (2017) Attacking
Deterministic Signature Schemes Using Fault Attacks. Cryptology ePrint Archive,
2017/1014. https://ia.cr/2017/1014[23] Accredited Standards Committee X9 (2005) Prime Number Generation, Primality Testing
and Primality Certificates. (American National Standards Institute), American National
Standard for Financial Services (ANS) X9.80-2005, R2013. Available athttps://webstore.ansi.org/Standards/ASCX9/ASCX9802005R2013[24] Knuth DE (1997) The Art of Computer Programming, Volume 2: Seminumerical
Algorithms (Addison-Wesley, Boston, MA), 3rd Ed.
[25] Baillie R, Wagstaff SS, Jr. (1980) Lucas Pseudoprimes. Mathematics of Computation
35(152):1391-1417. Available at https://www.ams.org/journals/mcom/1980-35-152/S00255718-1980-0583518-6/S0025-5718-1980-0583518-6.pdf[26] Damgård I, Landrock P, Pomerance C (1993) Average Case Error Estimates for the Strong
Probable Prime Test. Mathematics of Computation 61(203):177-194. Available athttps://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1189518-9/S00255718-1993-1189518-9.pdf[27] Menezes AJ, van Oorschot PC, Vanstone SA (1996) Handbook of Applied Cryptography(CRC Press, Boca Raton, FL). Available at http://cacr.uwaterloo.ca/hac/
75

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)[28] Williams HC (1982) A p+1 Method of Factoring. Mathematics of Computation
39(159):225-234. Available at https://www.ams.org/journals/mcom/1982-39-159/S00255718-1982-0658227-7/S0025-5718-1982-0658227-7.pdf

76

FIPS 186-5

DIGITAL SIGNATURE STANDARD (DSS)

Appendix E: Revisions (Informative)
Below is a summary of the main changes made in revising FIPS 186-4:
•

•
•
•

•
•
•
•
•
•
•
•
•

DSA is no longer approved for digital signature generation. DSA may be used to verify
signatures generated prior to the implementation date of this standard.
o The specifications and algorithms for DSA are no longer included in FIPS 186-5.
They may be found in FIPS 186-4.
ANSI X9.31 was withdrawn, so X9.31 RSA signatures were removed from this standard.
ANSI X9.62 was removed, so new specifications for ECDSA were added to FIPS 186-5.
Note: X9.62 will be replaced by X9.142 (under development).
Many elliptic curve details and algorithms from FIPS 186-4 will now be included in SP
800-186.
o Elliptic curves defined over binary curves (specified in SP 800-186) are now
deprecated.
A new deterministic signature algorithm, EdDSA, is included, as is the prehash version.
A deterministic version of ECDSA is specified.
Larger modulus sizes are allowed for RSA (with updated tables A.1, B.1).
XOFs are allowed for use in ECDSA, RSASSA-PSS.
Constructing primes with congruence conditions mod 8 is allowed.
In B.3.1, the two most significant bits of p and q may be set arbitrarily.
Trial division before checking primality is allowed.
Updated algorithms are included in Appendices B and C to better prevent bias.
The option to generate elliptic curves (besides those specified in SP 800-186) is removed.
Similarly, users are not given the option to generate their own base points on elliptic
curves.

77