Digital Signature Algorithm (DSA)

The Digital Signature Algorithm (DSA) is a method for creating and checking digital signatures, published as a United States federal standard by the National Institute of Standards and Technology (NIST). A signer uses a secret private key to produce a signature on a message, and anyone holding the matching public key can confirm that the signature is genuine and that the message has not been altered. DSA was proposed in 1991 and adopted in the Digital Signature Standard, FIPS 186, in 1994.

DSA belongs to the family of public-key methods studied in cryptography. Its security rests on the discrete logarithm problem: calculating powers of a number modulo a large prime is easy, but reversing the calculation is believed to be infeasible for well-chosen sizes. It is used for authentication and integrity checks rather than secrecy: DSA only signs; unlike RSA, it is not designed for encryption. Its elliptic-curve version, ECDSA, uses the same structure with shorter keys and is the signature scheme behind the Bitcoin blockchain and the Ethereum blockchain.

A handwritten signature is easy to copy and says nothing about whether the page above it was changed. A digital signature fixes both problems. The signer has a private stamp that only they hold, and everyone else has a public magnifying glass that can check the stamp. The stamp's mark depends on the exact words of the document, so changing a single letter makes the check fail.

DSA is one recipe for making such stamps, and it is one of the technical methods that can sit behind a legally recognized e-signature. The maths ensures that seeing many stamped documents does not reveal the private stamp itself. The method relies on a fresh random number for every signature, and if that number is reused or predictable, the private key can be worked out, which has caused real losses.

The system uses public parameters: a large prime $p$, a smaller prime $q$ that divides $p - 1$, and a generator $g$. The signer chooses a private key $x$ and publishes the public key $y = g^{x} \bmod p$. To sign a message $m$, the signer computes its hash $H(m)$ with a cryptographic hash function, picks a secret random number $k$ and calculates the two parts of the signature:

• $k^{-1}$ is the number that multiplied by $k$ gives 1, working modulo $q$.
• $x$ is the private key and $H(m)$ the message hash.
• The pair $(r, s)$ is the signature.

A verifier computes $w = s^{-1} \bmod q$, $u_1 = H(m) w \bmod q$ and $u_2 = r w \bmod q$, then checks whether $\left( g^{u_1} y^{u_2} \bmod p \right) \bmod q$ equals $r$.

A toy example with tiny numbers shows the steps. Take $p = 23$, $q = 11$, $g = 4$, private key $x = 3$, so $y = 4^{3} \bmod 23 = 18$. Let $H(m) = 5$ and $k = 7$. Then $4^{7} \bmod 23 = 8$, so $r = 8$. The inverse of 7 modulo 11 is 8, so $s = 8 \times (5 + 3 \times 8) \bmod 11 = 232 \bmod 11 = 1$. To verify, $w = 1$, $u_1 = 5$, $u_2 = 8$, and $4^{5} \times 18^{8} \bmod 23 = 12 \times 16 \bmod 23 = 8$, which matches $r$. Real systems use primes thousands of bits long.

The Elliptic Curve Digital Signature Algorithm replaces calculations with large primes by operations on points of an elliptic curve. It offers similar security with much smaller keys and signatures, which saves space on a blockchain. Bitcoin and Ethereum use ECDSA over a curve called secp256k1: transactions are hashed with functions such as SHA-256, and every transaction carries a signature proving that the owner of the address authorized it, and nodes verify it before accepting the transaction. Bitcoin added Schnorr signatures as an alternative with the Taproot upgrade in 2021, and many newer blockchains use the Ed25519 scheme.

The random value $k$, often called a nonce, is the scheme's weak point. If the same $k$ is used for two signatures with one key, anyone can calculate the private key from the two signatures. This flaw exposed the signing key of a major games console in 2010, and in 2013 a faulty random-number generator on Android devices led to thefts from Bitcoin wallets that reused values. Modern implementations derive $k$ deterministically from the key and message to avoid this problem. Keys are often protected in a hardware security module in banking.

NIST's 2023 revision of the standard, FIPS 186-5, withdrew approval for creating new signatures with classic DSA, leaving it only for verifying existing ones, while keeping ECDSA and adding EdDSA. A large quantum computer running Shor's algorithm could break DSA, ECDSA and RSA alike, so NIST published post-quantum signature standards in 2024, including ML-DSA in FIPS 204. Banks, certificate authorities and blockchain developers are planning migrations, a slow process for blockchains whose old addresses expose public keys.

• NIST: FIPS 186-5, Digital Signature Standard