Research Paper
Research Subject: NIST FIPS 186-5, published February 3, 2023; supersedes FIPS 186-4.
Abstract. This paper examines FIPS PUB 186-5, the NIST standard for RSA, ECDSA, and EdDSA. The central thesis of the paper is that the cryptographic strength of a digital signature is determined not only by the difficulty of factorization or discrete logarithm, but also by the correct generation of secret values: the private key, RSA primes, and the nonce k in ECDSA. Historical incidents involving the Sony PlayStation 3 and Debian OpenSSL demonstrate that an entropy error or nonce repetition can reduce the theoretical strength of a primitive to elementary algebra or brute-force attacks. The paper structures the provisions of FIPS 186-5, provides LaTeX-compatible formulas, and provides practical recommendations for implementation, auditing, and cryptanalysis.
Keywords: FIPS 186-5, DSS, RSA, ECDSA, EdDSA, Ed25519, Ed448, deterministic ECDSA, nonce, per-message secret number, DRBG, entropy, cryptanalysis, key validation, digital signature.
1. Statement of the problem
FIPS 186-5 defines methods for generating and verifying digital signatures to protect binary data. The standard endorses three families: RSA, ECDSA, and EdDSA; DSA is excluded from generating new signatures and reserved only for verifying existing ones. A digital signature is intended to provide authentication of origin, data integrity, and the ability to present cryptographic proof to a third party.
The standard should be read not as proof of the security of the finished product, but as a minimum normative layer. NIST itself explicitly distinguishes between compliance with algorithmic requirements and the security of the entire system: a conforming implementation may remain vulnerable due to errors in key management, the random number generator, side channels, the interface, or the PKI.
2. Security model
2.1 Roles and Trusted Objects
| Essence | Function | Critical requirement |
|---|---|---|
| Signatory | Generates a signature with a private key. | Exclusive ownership and non-disclosure of the private key. |
| Inspector | Verifies the signature with the public key. | Checks not only the signature mathematics, but also the connection between the key and the claimed owner. |
| CA / PKI | Binds the identity of a subject to the public key of a certificate. | Reliable issuance, revocation, and chain of trust verification. |
| Cryptomodule | Stores secrets, generates signatures and random values. | Key protection, correct DRBG, protection against crashes and side channels. |
The public key isn’t secret, but its integrity and ownership are critical: a mathematically valid signature on a substituted key doesn’t confirm the identity of the intended signatory. Therefore, signature verification in an application system involves, at a minimum, checking the algorithm, parameters, the signature itself, the certificate or other authenticated binding of the key to the subject, the revocation status, and the application policy.
2.2. Hashing
For RSA, ECDSA, and HashEdDSA, the original message is digested using an approved hash function; FIPS 186-5 refers to FIPS 180 and FIPS 202. Regular EdDSA, as defined in RFC 8032, incorporates message processing into its own signature generation scheme; HashEdDSA is intended for pre-hash mode and should not mechanically replace regular EdDSA without a protocol context.
% LaTeX h = H(M)
Hash collision resistance is not a cosmetic property. If an attacker receives two different messages with the same signed representation, they can transfer the signature from one message to the other. Therefore, the choice of hash and the encoding of the input are part of the signature’s security.
3. FIPS 186-5 Architecture
| Category | Regulatory status in FIPS 186-5 | The basis of perseverance | Secret meanings |
|---|---|---|---|
| RSA | Approved; uses RFC 8017 / PKCS #1 specifications with additional FIPS requirements. | Complexity of factorization of a module n = pq. | Simple p,q, closed exponential d, intermediate CRT components. |
| ECDSA | Approved; including the deterministic variant per RFC 6979. | Discrete logarithm problem in the elliptic curve group. | Private key d, a unique per-message secret k. |
| EdDSA | Approved; Ed25519 and Ed448 are used, and HashEdDSA is also defined. | Discrete logarithm on Edwards curves. | Secret seed and derived scalar/nonce material. |
| DSA | Not approved for new generation; only verification of old signatures is allowed. | Discrete logarithm in a finite field. | Historically: private key and one-time k. |
An important change in the 2023 edition is the transfer of a significant portion of the elliptic curve parameter issues to SP 800-186, the addition of EdDSA, and the standardization of deterministic ECDSA. NIST thereby eliminates two historically significant classes of risks: ECDSA’s reliance on an external source of randomness for each signature and the lack of a modern, standardized Edwards curve algorithm in the previous DSS.
4. RSA: Requirements and Risks
4.1 Mathematical scheme
An RSA key is constructed from two secret distinct prime numbers p and q. The modulus n is published, a public exponent is chosen ethat is relatively prime to the Carmichael function or the corresponding order, and the private exponent satisfies the congruence below.
% LaTeX n = pq \lambda(n) = \operatorname{lcm}(p-1,q-1) ed \equiv 1 \pmod{\lambda(n)}
FIPS 186-5 defines requirements for RSA key pair generation, key management, and guarantees; Appendix A contains prime number generation procedures, and Appendix B contains the Miller–Rabin, enhanced Miller–Rabin, and Lucas probabilistic primality tests, as well as the Shawe–Taylor procedure for provably prime numbers. Formally, a “probably prime” number is acceptable if the probability of misclassification is negligible, but an implementation must adhere to the specified checks and number of testing rounds.
4.2 Generating Prime Numbers
For RSA, simply invoking the primality test once is not enough. A cryptographically strong source of randomness, candidate selection of the required length, verification of conditions for the pair p,q, probabilistic or provable primality tests, and secure destruction of intermediate secrets are required. FIPS allows several approaches: random provably prime, random probabilistically prime, and variants with auxiliary primes and specified conditions.
% LaTeX p \ne q, \qquad n = pq, \qquad \gcd(e,\lambda(n))=1
A cryptanalytic example is Debian OpenSSL (CVE-2008-0166, 2006–2008). A bug in the Debian branch of OpenSSL made the random number generator predictable; SSH, OpenVPN, DNSSEC keys, X.509 certificates, and other keying material were affected. The attack did not factorize a correctly formed RSA modulus; it reduced the space of possible secrets sufficiently that keys could be enumerated and compared with known public keys. This demonstrates that the requirement for randomness in generation p is q part of RSA’s security, not an operational detail.
4.3. Signature and Encoding
FIPS 186-5 endorses RSA signatures within RFC 8017 / PKCS #1 and emphasizes the role of correct encoding and masking functions in RSASSA-PSS. A signature cannot be implemented as a raw modular power operator over a hash: security is ensured by a specific encoding scheme, the choice of hash, the salt, and strict verification of the representation structure.
% LaTeX s = \operatorname{RSASP1}(K_{\mathrm{priv}}, EM), \qquad EM = \operatorname{EMSA\!\!\!-PSS-ENCODE}(H(M),\mathrm{salt})
In practice, this means: use the high-level library API for RSASSA-PSS or RSASSA-PKCS1-v1_5, fix the allowed algorithms in the protocol policy, avoid algorithmic confusion, and check all bytes of the encoded message during verification.
5. ECDSA: The Criticality of the One-Time Secret
5.1 Parameters and keys
ECDSA operates on a subgroup of the order n of an elliptic curve with a base point G. The private key is chosen as a scalar in the allowed range, and the public key is obtained by scalar multiplication. The domain parameters must be approved and valid; for federal use, recommended curves are listed in SP 800-186.
% LaTeX 1 \le d \le n-1, \qquad Q = [d]G
Public key verification should not be a formality: the point must be correctly decodable, lie on the expected curve, not be a point at infinity, and belong to the correct subgroup according to the parameters used. Ignoring these conditions creates the basis for attacks with invalid points and interprotocol errors.
5.2. Signature generation
For each message, a secret number k from the range is selected [1,n-1]. The dot is calculated [k]G = (x_1,y_1), then the signature components (r,s). If r=0 or s=0, the value k is discarded and a new one is selected.
% LaTeX [k]G=(x_1,y_1), \qquad r=x_1 \bmod ns = k^{-1}\bigl(h + dr\bigr) \bmod n \sigma=(r,s), \qquad h=\operatorname{bits2int}(H(M))
This is precisely k the most dangerous secret of ECDSA. It must remain unknown, be unique for each signature, and be generated without statistical bias. FIPS 186-5 requires generation with extra random bits, rejection sampling, and deterministic ECDSA; Appendix A specifically describes the conversion of random strings to absolute values n and addresses the problem of distribution bias.
5.3. Repeating the nonce: Full key output
Let two signatures of different messages be created with the same k component and therefore have the same value r. For the hash representations, h_1,h_2 we obtain:
% LaTeX s_1 = k^{-1}(h_1 + dr) \bmod n s_2 = k^{-1}(h_2 + dr) \bmod nk = (h_1-h_2)(s_1-s_2)^{-1} \bmod nd = r^{-1}(s_1 k-h_1) \bmod n
This is not approximate cryptanalysis or an ECDLP solution: given two known signatures with a duplicate, k the private key is extracted using exact modulo arithmetic n. In practical auditing, a match r for a single public key is a high-priority indicator of compromise, although the match must be analyzed taking into account the signature encoding and the curve.
# Учебный псевдокод аудита повторного nonce в ECDSA
# Вход: набор записей (pubkey_id, message_hash, r, s), порядок n
for pubkey_id, signatures in group_by_public_key(records):
for sig1, sig2 in all_pairs(signatures):
if sig1.r == sig2.r and sig1.hash != sig2.hash:
k = ((sig1.hash - sig2.hash) * inverse(sig1.s - sig2.s, n)) % n
d = ((sig1.s * k - sig1.hash) * inverse(sig1.r, n)) % n
assert public_key(d) == pubkey_id
report_compromise(pubkey_id)
A historical example is the Sony PlayStation 3 in 2010. The research group fail0verflow demonstrated that Sony’s ECDSA signatures used a repeating per-message secret number. After extracting the private key, it became possible to generate signatures for arbitrary code, thus breaking the code-signing core trust model. The incident became a canonical example of why “a random number for every signature” is a strict cryptographic requirement.
5.4 Deterministic ECDSA
FIPS 186-5 endorses deterministic ECDSA per RFC 6979. Instead of directly accessing a random number generator for each signing, a random number generator k is deterministically derived from the private key and the message hash using an HMAC-DRBG-like process. The same key and the same message yield the same hash k, but different messages yield different values with the correct hash function.
% LaTeX (schematic; the exact procedure is RFC 6979) k = \operatorname{NonceGen}(d, H(M))
Determinism eliminates dependence on the quality of online entropy at the time of signature and prevents random replay k due to RNG failure. It does not protect against leakage d, hash compromise, fault attacks, coding errors, or implementations with variable timing; therefore, it should be combined with key protection and cryptomodule testing.
5.5 ECDSA Verification
% LaTeX w=s^{-1}\bmod n, \qquad u_1=hw\bmod n, \qquad u_2=rw\bmod n (X,Y)=[u_1]G+[u_2]Q, \qquad \text{accept iff } r \equiv X \pmod n
The verifier must reject signatures within r or s outside the interval [1,n-1], as well as decoding errors and invalid parameters. In network protocols, it is safer to use strict, canonical signature serialization: ambiguous encoding creates risks of malleability, cache bypass, log inconsistency, and incompatibility between implementations.
6. EdDSA and HashEdDSA
6.1. Motivation for inclusion
FIPS 186-5 includes EdDSA in DSS for the first time and allows variants Ed25519 and Ed448 on Edwards curves; HashEdDSA is also defined for signing prehashed messages. The EdDSA architecture reduces the risk of operator error when generating nonces: the nonce scalar is deterministically derived from the secret material and the message, rather than being selected by an external random generator for each signature.
6.2 Schematic Mathematics
a The secret scalar and prefix are hashed from the secret seed prefix; the public key is . The nonce scalar , the period , and the scalar part of the signature are formed A=[a]Bfor the message .MrRS
% LaTeX (EdDSA scheme) a,\mathrm{prefix} \leftarrow \operatorname{Expand}(\mathrm{seed}), \qquad A=[a]B r = H(\mathrm{prefix}\parallel M) \bmod L, \qquad R=[r]B k = H(\operatorname{enc}(R)\parallel \operatorname{enc}(A)\parallel M) \bmod LS=(r+ka)\bmod L \sigma=(\operatorname{enc}(R),\operatorname{enc}(S))
Deterministic nonce computation reduces the replay risk kknown from ECDSA/DSA, but places particular emphasis on seed confidentiality, hashing correctness, domain separation, constant-time operations with scalars, and resistance to error injection. If an attacker, under the influence of a fault, obtains associated erroneous signatures, determinism alone does not prevent leaks.
6.3. HashEdDSA
HashEdDSA signs the message hash, not the original stream directly, which is convenient for big data, stream processing, and hardware interfaces where the original message cannot be retransmitted to the module. However, the EdDSA and HashEdDSA modes are semantically different: the protocol must explicitly specify the mode, pre-hash algorithm, and context to prevent the same logical object from being signed in incompatible representations.
7. Generating secret values
7.1 Categories of Secrets
| Secret | Where it is applied | Properties | Consequence of violation |
|---|---|---|---|
p,q | RSA | Various, correctly tested simple; unpredictable; destroyed after the required components are output if the policy does not require CRT. | Factorization or key recovery from a small/predictable candidate space. |
d | RSA, ECDSA, EdDSA | Uniformly formed within the acceptable range, confidential throughout the entire life cycle. | Complete possibility of signature forgery. |
k | ECDSA | Secret, unique to the message, unbiased; generated randomly by a valid method or deterministically. | In case of repetition – algebraic recovery d; in case of partial leaks – lattice cryptanalysis. |
seed | EdDSA | High-entropy, confidential, protected from copying and leaks. | Restore scalar and ability to generate all owner signatures. |
| DRBG status | Key generation and random ECDSA | Secret, correctly initialized with entropy, protected from state rollback. | Predictable keys, repetition or nonce correlation. |
7.2. Shift in modulo reduction
The naive operation x mod n for a x fixed-length uniform space creates a bias if the size of the original space is not a multiple of n. FIPS 186-5 specifically addresses this: Appendix A proposes extra random bits and rejection sampling methods, and describes the modular reduction and discard methods for values modulo n.
% LaTeX \Pr[x \bmod n = a] \neq \frac{1}{n}\quad\text{in general, if}\quad n \nmid 2^t
Rejection sampling is practically preferable: obtain a sufficient number of random bits, interpret them as , c and accept only if 1 \le c \le n-1. This ensures uniformity of the accepted value at the cost of rare resampling.
# Псевдокод равномерного выбора скаляра для порядка n
while True:
c = OS_CSPRNG(ceil(log2(n)) bits)
if 1 <= c < n:
return c
For production modules, the randomness source and DRBG must comply with the adopted cryptographic policy, including FIPS 140-3 and SP 800-90A requirements. Replacing the CSPRNG with rand()a timestamp, PID, counter, or hash of publicly available data is prohibited.
7.3 Partial nonce leak
Replay k is an extreme case. If an attacker learns several bits of the nonce in a series of ECDSA signatures, obtains biased values, or observes correlated errors, the comparison system s_i k_i - r_i d ≡ h_i (mod n) can be attacked using hidden number and lattice methods. Therefore, the FIPS requirement for unbiased generation protects not only against obvious nonce replay but also against more sophisticated statistical cryptanalysis.
% LaTeX s_i k_i-r_i d \equiv h_i \pmod n
A practical example from cryptanalysis. In 2013, there were reports of the theft of Bitcoin funds from Android devices due to insufficiently correct random number generation during ECDSA signing: repeatable or predictable nonces allowed the recovery of wallet private keys. The principle is the same as in the PS3: the implementation of the secret source is compromised, not the discrete logarithm problem secp256k1.
8. Cryptanalytic Lessons
| Implementation failure | Violated requirement | Observed artifact | Attack method | Consequence |
|---|---|---|---|---|
One k in two ECDSA signatures | Uniqueness per-message secret. | The same r for one key. | Direct solution of two linear congruences. | Full disclosure d. |
| Predictable RNG | Cryptographic unpredictability of the key material. | Small seed/key space. | Enumeration, precomputation, public key matching. | Compromise of key pairs. |
| Displaced nonce | Uniformity of distribution k. | Statistical dependence of signatures. | Hidden Number Problem, LLL and related lattice methods. | Recovering the key given a sufficient number of observations. |
| No key/point validation | Assurance of public key validity. | Invalid or foreign parameter/key. | Attacks of incorrect point, small subgroup, protocol substitution. | Leaks or false authentication. |
| Unstable implementation of the operation | Protecting secrets during computation. | Dependence of time, consumption or errors on a secret scalar. | Timing, power analysis, fault analysis. | Partial or complete extraction of secretion. |
This analysis explains the engineering value of FIPS 186-5: the document specifies not only signature equations but also key generation modes, requirements for domain parameters, validation procedures, random bit transformation, and primality tests. Cryptanalysis of real-world systems primarily exploits deviations from these requirements.
9. Implementation practice
9.1 Minimum profile
- Select only permitted algorithms and parameters: RSA with a secure modulus length and modern padding, ECDSA on an approved curve, or Ed25519/Ed448 in accordance with the system profile.
- For ECDSA, use deterministic RFC 6979 or a verified CSPRNG/DRBG with rejection sampling; do not export or log
k. - Generate keys using a certified library or hardware module; do not write your own simple RSA or scalar key generation without proper and thorough auditing.
- Separate keys by purpose: the signature key should not be used as an exchange or encryption key.
- Verify the format, ranges, algorithm identifiers, parameters, and origin of the public key before accepting the signature.
- Implement constant-time operations with secrets, protect against fault injection, erase temporary buffers, and control backup copies of keys.
- Introduce tests: NIST vector tests, negative decoding tests, nonce replay tests, and continuous RNG quality monitoring.
9.2. ECDSA archive audit
For a historical set of signatures, passive scanning is useful: normalize signatures, group them by public key, search for duplicates r, check ranges r,s, and record used hashes and library versions. Such analysis is safe as a protective procedure if performed by the infrastructure owner or within the scope of an explicitly authorized audit; detection of a duplicate r should be treated as an incident, with immediate key rotation, certificate revocation, and an evaluation of all previously created signatures.
10. Restrictions and migration
FIPS 186-5 explicitly states that the algorithms discussed are not designed to withstand a large-scale quantum computer. RSA, ECDSA, and EdDSA remain classical schemes with different mathematical foundations, but all require a cryptographic migration plan toward post-quantum NIST standards, particularly for long-lived signatures, archives, root CAs, and software updates.
The transition from FIPS 186-4 was accompanied by a one-year cool-down period; DSA should not be selected for new systems. Modern protocols should be designed for crypto-agility: explicit algorithm negotiation, format versioning, separation of signature contexts, and the ability to change the algorithm without changing the business semantics of the document.
Conclusion
FIPS 186-5 formalizes the modern DSS core triplet: RSA, ECDSA, and EdDSA. Its most important practical implication is that secret values are not an implementation side-effect: the quality of the generation of the p,q, d, seed, and especially the ECDSA value k directly determines whether the computational difficulty of the problem underlying the signature is preserved.
The PS3 and Debian OpenSSL incidents illustrate two sides of the same principle. A strong algorithm cannot compensate for nonce repetition, predictable DRBG, biased distribution, or insecure key management. Therefore, a FIPS 186-5-compliant system must combine rigorous mathematics, secure secret generation, parameter and key verification, a robust PKI, and implementation engineering that protects against observation and failure.
Sources used
NIST FIPS PUB 186-5 (2023): Requirements for Digital Signatures and Secret Value Generation: https://dynet.ru/nist-fips-pub-186-5-2023-requirements-for-digital-signatures-and-secret-value-generation/
- National Institute of Standards and Technology. Digital Signature Standard (DSS) . NIST FIPS 186-5, 2023. DOI: 10.6028/NIST.FIPS.186-5 .
- NIST. SP 800-186: Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters , 2023.
- Krawczyk, H.; Pornin, T. RFC 6979: Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) , IETF, 2013.
- Josefsson, S.; Liusvaara, I. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA) , IETF, 2017.
- Moriarty, K. et al. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 , IETF, 2016.
- US-CERT. VU#925211: Debian and Ubuntu OpenSSL packages contain a predictable random number generator , CVE-2008-0166, 2008.
- Sanatinia, A.; Noubir, G. On the Security of ECDSA and the Sony PlayStation 3 ; a historical case of nonce replay is also documented in the works and materials of the fail0verflow community.