Overview
DSA computes signatures from a private key, a message digest, and a fresh nonce in a finite subgroup. Verification checks a modular equation using the public key and signature pair.
CoreSource checked
DSA
Signs message digests with modular arithmetic over a subgroup and a per-signature nonce.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Cryptography
- Difficulty
- Intermediate
- Family
- Digital Signatures
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Digital Signature Algorithm
Core Concepts
digital signature generationdigital signaturesmodular arithmeticcryptography
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(k)
Average
O(k^2)
Worst
O(k^3)
Space
O(k)
When to Use
- Use only when a protocol or legacy compatibility requirement calls for DSA.
- Use through libraries that enforce parameter and nonce requirements.
When Not to Use
- Avoid custom implementations or weak parameter sets.
- Avoid if high-quality unique nonces cannot be guaranteed.
What It Does
- Derives signature values from a message digest and private key
- Uses a fresh per-message nonce
- Verifies signatures with public subgroup parameters
Use Cases
- Understanding classic discrete-log signature schemes
- Interoperating with systems that still require DSA
- Comparing nonce-sensitive signature constructions
Inputs
- Message, key, modulus, seed, or public parameters
- Security parameter or nonce when required
Outputs
- Cryptographic value such as signature, random bits, proof, or modular result
Pseudocode
- 1.Validate domain parameters and key ranges
- 2.Hash and encode the message digest
- 3.Generate a fresh nonce k
- 4.Compute signature values r and s modulo the subgroup order
- 5.Verify by checking the public modular relation
Canonical Example
- Input
- digest h, private key x, nonce k, and subgroup parameters
- Output
- signature pair (r, s)
- Explanation
- The signer combines h, x, and k modulo the subgroup order; the verifier recomputes the public equation.
Implementation Notes
- Use vetted libraries and approved parameter sizes.
- Generate nonces deterministically or from a strong random source according to the protocol.
- Validate public parameters, public keys, and signature ranges.
Common Pitfalls
- Reusing or leaking the nonce can reveal the private key.
- Accepting invalid subgroup parameters can break the security assumptions.
- Signing unhashed or inconsistently encoded messages creates interoperability and security bugs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow signing with modular arithmetic over a subgroup and per-message nonce on a small digital signature generation example.
Step 1 of 5: Validate domain parameters and key ranges
cryptography-mechanismNotes
Nonce handling is the most common catastrophic DSA implementation failure.
Sources (1)
What each reference supports for this entry.
FIPS 186-5
DocumentationNIST Digital Signature Standard reference for DSA legacy verification and digital signature algorithm requirements.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborSchnorr Signature
DSA and Schnorr signatures are discrete-log signature schemes with different signing equations.
DSA signing and verification rely on modular exponentiation.
Related Algorithms
Tags
Cryptography