The
Digital Signature Algorithm (DSA) is a
United States Federal GovernmentThe federal government of the United States is the central government entity established by the United States Constitution, which shares sovereignty over the United States with the governments of the individual U.S. states. The federal government has three branches: the legislative, executive, and...
standardFederal Information Processing Standards are publicly announced standards developed by the United States Federal government for use by all non-military government agencies and by government contractors...
or
FIPSFederal Information Processing Standards are publicly announced standards developed by the United States Federal government for use by all non-military government agencies and by government contractors...
for
digital signatureA digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
s. It was proposed by the
National Institute of Standards and TechnologyThe National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory which is a non-regulatory agency of the United States Department of Commerce...
(NIST) in August 1991 for use in their
Digital Signature Standard (DSS), specified in
FIPSFederal Information Processing Standards are publicly announced standards developed by the United States Federal government for use by all non-military government agencies and by government contractors...
186
http://www.itl.nist.gov/fipspubs/fip186.htm, adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1
http://www.mozilla.org/projects/security/pki/nss/fips1861.pdf.
The
Digital Signature Algorithm (DSA) is a
United States Federal GovernmentThe federal government of the United States is the central government entity established by the United States Constitution, which shares sovereignty over the United States with the governments of the individual U.S. states. The federal government has three branches: the legislative, executive, and...
standardFederal Information Processing Standards are publicly announced standards developed by the United States Federal government for use by all non-military government agencies and by government contractors...
or
FIPSFederal Information Processing Standards are publicly announced standards developed by the United States Federal government for use by all non-military government agencies and by government contractors...
for
digital signatureA digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
s. It was proposed by the
National Institute of Standards and TechnologyThe National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory which is a non-regulatory agency of the United States Department of Commerce...
(NIST) in August 1991 for use in their
Digital Signature Standard (DSS), specified in
FIPSFederal Information Processing Standards are publicly announced standards developed by the United States Federal government for use by all non-military government agencies and by government contractors...
186
http://www.itl.nist.gov/fipspubs/fip186.htm, adopted in 1993. A minor revision was issued in 1996 as FIPS 186-1
http://www.mozilla.org/projects/security/pki/nss/fips1861.pdf. The standard was expanded further in 2000 as FIPS 186-2 and again in 2009 as FIPS 186-3
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf.
DSA is covered by , filed July 26, 1991, and attributed to
David W. Kravitz, a former
NSAThe National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States government, administered as part of the United States Department of Defense. Created on November 4, 1952 by President Harry S...
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
royaltyRoyalties are usage-based payments made by one party to another for ongoing use of an asset, sometimes an intellectual property right. Royalties are typically a percentage of gross or net sales derived from use of an asset or a fixed price per unit sold of an item...
-free.
http://lists.gnupg.org/pipermail/gnupg-devel/1997-December/014123.html Dr. Claus P. SchnorrClaus-Peter Schnorr is a distinguished German mathematician and cryptographer. He received his Ph.D. from the University of Saarbrücken in 1966, and his habilitation in 1970. Schnorr's contributions to cryptography include his study of Schnorr groups, which are used in the digital signature...
claims that his covers DSA; this claim is disputed (see
minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board).
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:
- Choose an approved cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
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 recommends lengths of 2048 (or 3072) for keys with security lifetimes extending beyond 2010 (or 2030), using correspondingly longer N. FIPS 186-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.
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 exponentiationModular exponentiation is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography....
s
ha mod
p and
gx mod
p, such as
exponentiation by squaringExponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. In additive groups the appropriate name is double-and-add algorithm. It implicitly uses the binary expansion...
.
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
- Calculate s = (k-1(H(m) + x*r)) mod q
- Recalculate the signature in the unlikely case that r=0 or s=0
- The signature is (r,s)
The
extended Euclidean algorithmThe extended Euclidean algorithm is an extension to the Euclidean algorithm for finding the greatest common divisor of integers a and b: it also finds the integers x and y in Bézout's identity....
can be used to compute the modular inverse
k-1 mod q.
Verifying
- Reject the signature if either 0< r
s
- Calculate w = (s)-1 mod q
- Calculate u1 = (H(m)*w) 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 schemeThe ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It was described by Taher ElGamal in 1984 The ElGamal signature scheme is a digital signature scheme which is based on the difficulty of computing discrete logarithms. It...
.
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
gq ≡
hp-1 ≡ 1 (mod p) by
Fermat's little theoremFermat's little theorem states that if p is a prime number, then for any integer a, a p − a will be evenly divisible by p...
. Since
g>1 and
q is prime,
g must have order
q.
The signer computes
Thus
Since
g has order
q we have
Finally, the correctness of DSA follows from
External links