# Digital Signature Algorithm

﻿
Digital Signature Algorithm

The Digital Signature Algorithm (DSA) is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS), specified in FIPS 186,[1] adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1.[2] The standard was expanded further in 2000 as FIPS 186-2 and again in 2009 as FIPS 186-3.[3]

DSA is covered by U.S. Patent 5,231,668, filed July 26, 1991, and attributed to David W. Kravitz,[4] a former NSA employee. This patent was given to "The United States of America as represented by the Secretary of Commerce, Washington, D.C." and the NIST has made this patent available worldwide royalty-free.[5] Dr. Claus P. Schnorr claims that his U.S. Patent 4,995,082 (expired) covered DSA; this claim is disputed.[6] DSA is a variant of the ElGamal Signature Scheme.

## Key generation

Key generation has two phases. The first phase is a choice of algorithm parameters which may be shared between different users of the system, while the second phase computes public and private keys for a single user.

### Parameter generation

• Choose an approved cryptographic hash function H. In the original DSS, H was always SHA-1, but the stronger SHA-2 hash functions are approved for use in the current DSS. The hash output may be truncated to the size of a key pair.
• Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The original DSS constrained L to be a multiple of 64 between 512 and 1024 (inclusive). NIST 800-57[7] recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030), using correspondingly longer N. FIPS 186-3[3] specifies L and N length pairs of (1024,160), (2048,224), (2048,256), and (3072,256).
• Choose an N-bit prime q. N must be less than or equal to the hash output length.
• Choose an L-bit prime modulus p such that p–1 is a multiple of q.
• Choose g, a number whose multiplicative order modulo p is q. This may be done by setting g = h(p–1)/q mod p for some arbitrary h (1 < h < p−1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h=2 is used.

The algorithm parameters (p, q, g) may be shared between different users of the system.

### Per-user keys

Given a set of parameters, the second phase computes private and public keys for a single user:

• Choose x by some random method, where 0 < x < q.
• Calculate y = gx mod p.
• Public key is (p, q, g, y). Private key is x.

There exist efficient algorithms for computing the modular exponentiations h(p–1)/q mod p and gx mod p, such as exponentiation by squaring.

## Signing

Let H be the hashing function and m the message:

• Generate a random per-message value k where 0 < k < q
• Calculate r = (gk mod p) mod q
• In the unlikely case that r = 0, start again with a different random k
• Calculate s = (k−1(H(m) + x·r)) mod q
• In the unlikely case that s = 0, start again with a different random k
• The signature is (rs)

The first two steps amount to creating a new per-user key. The modular exponentiation here is the most computationally expensive part of the signing operation, and it may be computed before the message hash is known. The modular inverse k−1 mod q is the second most expensive part, and it may also be computed before the message hash is known. It may be computed using the extended Euclidean algorithm or using Fermat's little theorem as kq−2 mod q.

## Verifying

• Reject the signature if 0 < r < q or 0 < s < q is not satisfied.
• Calculate w = s−1 mod q
• Calculate u1 = H(mw mod q
• Calculate u2 = r·w mod q
• Calculate v = ((gu1·yu2) mod p) mod q
• The signature is valid if v = r

DSA is similar to the ElGamal signature scheme.

## Correctness of the algorithm

The signature scheme is correct in the sense that the verifier will always accept genuine signatures. This can be shown as follows:

First, if g = h(p − 1)/q mod p it follows that gqhp − 1 ≡ 1 (mod p) by Fermat's little theorem. Since g > 1 and q is prime, g must have order q.

The signer computes

$s=k^{-1}(H(m)+xr) \mod{q}. \,$

Thus

\begin{align} k & \equiv H(m)s^{-1}+xrs^{-1}\\ & \equiv H(m)w + xrw \pmod{q}. \end{align}

Since g has order q (mod p) we have

\begin{align} g^k & \equiv g^{H(m)w}g^{xrw}\\ & \equiv g^{H(m)w}y^{rw}\\ & \equiv g^{u1}y^{u2} \pmod{p}. \end{align}

Finally, the correctness of DSA follows from

$r=(g^k \mod p) \mod q = (g^{u1}y^{u2} \mod p) \mod q = v.\,$

## Sensitivity

With DSA, the entropy, secrecy and uniqueness of the random signature value k is critical. It is so critical that violating any one of those three requirements can reveal your entire private key to an attacker.[8] Using the same value twice (even while keeping k secret), using a predictable value, or leaking even a few bits of k in each of several signatures, is enough to break DSA.[9]

## References

1. ^ FIPS-186, the first version of the official DSA specification.
2. ^ FIPS-186-1, the first revision to the official DSA specification.
3. ^ a b FIPS-186-3, the third and current revision to the official DSA specification.
4. ^ Dr. David W. Kravitz
5. ^ Werner Koch. DSA and patents
6. ^ Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board
7. ^ NIST 800-57
8. ^ The Debian PGP disaster that almost was.
9. ^ DSA k-value Requirements

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Digital Signature Algorithm — Le Digital Signature Algorithm, plus connu sous le sigle DSA, est un algorithme de signature numérique standardisé par le NIST aux États Unis, du temps où le RSA était encore breveté. Cet algorithme fait partie de la spécification DSS pour… …   Wikipédia en Français

• Digital Signature Algorithm — Der Digital Signature Algorithm (DSA) ist ein Standard der US Regierung für Digitale Signaturen. Er wurde vom National Institute of Standards and Technology (NIST) im August 1991 für die Verwendung in deren Digital Signature Standard (DSS)… …   Deutsch Wikipedia

• DIGITAL SIGNATURE ALGORITHM — (DSA) схема цифровой подписи, разработанная NIST на основе алгоритма Эль Гамаля (также известна как Digital Signature Standard, DSS). Использует тот же тип ключей, что и алгоритм Диффи Хельмана, работает быстрее RSA …   Словарь электронного бизнеса

• Digital Signature Algorithm — …   Википедия

• Elliptic Curve Digital Signature Algorithm — (ECDSA) est un algorithme de signature numérique. C est une variante du standard DSA qui à la différence de l algorithme d origine utilise la cryptographie sur les courbes elliptiques. Les avantages de ECDSA sur DSA et RSA sont des longueurs de… …   Wikipédia en Français

• Elliptic curve digital signature algorithm — (ECDSA) est un algorithme de signature numérique à clé publique, variante de DSA il fait appel à la cryptographie sur les courbes elliptiques. Sommaire 1 Introduction 2 Algorithme 2.1 Préparation des clé …   Wikipédia en Français

• Digital Signature Standard — Der Digital Signature Algorithm (DSA) ist ein Standard der US Regierung für Digitale Signaturen. Er wurde vom National Institute of Standards and Technology (NIST) im August 1991 für die Verwendung in deren Digital Signature Standard (DSS)… …   Deutsch Wikipedia

• Digital Signature Standard — DSS, Digital Signature Standard Создатель: NIST Создан: август 1991 Опубликован: 19 мая 1994 Размер ключа: 512 1024 бит Размер подписи: два числа по 160 бит DSS (Digital Signature Standard)  американский стандарт, описывающий Digital Si …   Википедия

• Digital signature — This article is about secure cryptographic signatures. For simple signatures in digital form, see Electronic signature. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital… …   Wikipedia

• Digital signature forgery — In a cryptographic digital signature or MAC system, digital signature forgery is the ability to create a pair consisting of a message m and a signature (or MAC) σ that is valid for m, where m has not been signed in the past by the legitimate… …   Wikipedia