View source for Energy level

The '''Digital Signature Algorithm''' ('''DSA''') is a [[Federal Information Processing Standard]] for [[digital signature]]s. It was proposed by the [[National Institute of Standards and Technology]] (NIST) in August 1991 for use in their '''Digital Signature Standard''' ('''DSS''') and adopted as FIPS 186 in 1993.<ref name="FIPS-186">[http://www.itl.nist.gov/fipspubs/fip186.htm FIPS PUB 186]: Digital Signature Standard (DSS), 1994-05-19</ref> Four revisions to the initial specification have been released: FIPS 186-1 in 1996,<ref name="FIPS-186-1">[http://csrc.nist.gov/publications/fips/fips1861.pdf FIPS PUB 186-1]: Digital Signature Standard (DSS), 1998-12-15</ref> FIPS 186-2 in 2000,<ref name="FIPS-186-2">[http://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2.pdf FIPS PUB 186-2]: Digital Signature Standard (DSS), 2000-01-27</ref> FIPS 186-3 in 2009,<ref name="FIPS-186-3">[http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf FIPS PUB 186-3]: Digital Signature Standard (DSS), June 2009</ref> and FIPS 186-4 in 2013.<ref name="FIPS-186-4">[http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf FIPS PUB 186-4]: Digital Signature Standard (DSS), July 2013</ref>

DSA is covered by {{US patent|5231668}}, filed July 26, 1991 and attributed to David W. Kravitz,<ref>[http://www.certicom.com/index.php/dr-david-kravitz Dr. David W. Kravitz]</ref> a former [[National Security Agency|NSA]] employee. This patent was given to "The United States of America as represented by the Secretary of Commerce, Washington, D.C.", and NIST has made this patent available worldwide [[royalty-free]].<ref>Werner Koch. [http://lists.gnupg.org/pipermail/gnupg-devel/1997-December/014123.html DSA and patents]</ref> [[Claus P. Schnorr]] claims that his {{US patent|4995082}} (expired) covered DSA; this claim is disputed.<ref>[http://csrc.nist.gov/groups/SMA/ispab/documents/94-rpt.txt Minutes of the Sept. 94 meeting of the Computer System Security and Privacy Advisory Board]</ref> DSA is a variant of the [[ElGamal signature scheme|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.<ref name="FIPS-186-4" /><ref name="FIPS-180-4">[http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf FIPS PUB 180-4]: Secure Hash Standard (SHS), March 2012</ref> 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''.<ref>[http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf NIST Special Publication 800-57]</ref> FIPS 186-3 specifies ''L'' and ''N'' length pairs of (1024,160), (2048,224), (2048,256), and (3072,256).<ref name="FIPS-186-3" />
* 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''<sup>(''p''–1)/''q''</sup> mod ''p'' for some arbitrary ''h'' (1 &lt; ''h'' &lt; ''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 &lt; ''x''&nbsp;<&nbsp;''q''.
* Calculate ''y'' = ''g<sup>x</sup>'' mod ''p''.
* Public key is (''p'', ''q'', ''g'', ''y''). Private key is ''x''.

There exist efficient algorithms for computing the [[modular exponentiation]]s  ''h''<sup>(''p''–1)/''q''</sup> mod ''p'' and ''g<sup>x</sup>'' mod ''p'', such as [[exponentiation by squaring]].

==Signing==

Let <math>H</math> be the hashing function and <math>m</math> the message:
* Generate a random per-message value <math>k</math> where <math>0 < k < q</math>
* Calculate <math>r=\left(g^{k}\bmod\,p\right)\bmod\,q</math>
* In the unlikely case that <math>r=0</math>, start again with a different random <math>k</math>
* Calculate <math>s=k^{-1}\left(H\left(m\right)+xr\right)\bmod\,q</math>
* In the unlikely case that <math>s=0</math>, start again with a different random <math>k</math>
* The signature is <math>\left(r,s\right)</math>

The first two steps amount to creating a new per-message 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 <math>k^{-1}\bmod\,q</math> 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 <math>k^{q-2}\bmod\,q</math>.

==Verifying==
* Reject the signature if <math>0<r<q</math> or <math>0<s<q</math> is not satisfied.
* Calculate <math>w=s^{-1}\bmod\,q</math>
* Calculate <math>u_{1}=H\left(m\right)\cdot w\,\bmod\,q</math>
* Calculate <math>u_{2}=r\cdot w\,\bmod\,q</math>
* Calculate <math>v=\left(\left(g^{u_{1}}y^{u_{2}}\right)\bmod\,p\right)\bmod\,q</math>
* The signature is valid if <math>v=r</math>

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<sup>(''p''&nbsp;&minus;&nbsp;1)/''q''</sup>'' mod ''p'' it follows that
''g<sup>q</sup>'' ≡ ''h''<sup>''p''&nbsp;&minus;&nbsp;1</sup> ≡ 1 (mod&nbsp;''p'') by
[[Fermat's little theorem]]. Since ''g''&nbsp;>&nbsp;1 and ''q'' is prime, ''g'' must have order&nbsp;''q''.

The signer computes

:<math>s=k^{-1}(H(m)+xr)\bmod\,q</math>

Thus 

:<math>
\begin{align}
k & \equiv H(m)s^{-1}+xrs^{-1}\\
  & \equiv H(m)w + xrw \pmod{q}
\end{align}
</math>

Since ''g'' has order ''q'' (mod p) we have

:<math>
\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}
</math>

Finally, the correctness of DSA follows from

:<math>\begin{align}
 r &= (g^k \bmod\,p) \bmod\,q\\
   &= (g^{u1}y^{u2} \bmod\,p) \bmod\,q\\
   &= v
\end{align}</math>

==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 the entire private key to an attacker.<ref>[http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-that-almost-was/ The Debian PGP disaster that almost was]</ref>  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.<ref>[http://rdist.root.org/2010/11/19/dsa-requirements-for-random-k-value/ DSA ''k''-value Requirements]</ref>

In December 2010, a group calling itself ''fail0verflow'' announced recovery of the [[ECDSA]] private key used by [[Sony]] to sign software for the [[PlayStation 3]] game console. The attack was made possible because Sony failed to generate a new random ''k'' for each signature.<ref>{{Cite news|last=Bendel|first=Mike|title=Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access|publisher=Exophase.com|date=2010-12-29|url=http://exophase.com/20540/hackers-describe-ps3-security-as-epic-fail-gain-unrestricted-access/|accessdate=2011-01-05}}</ref>

This issue can be prevented by deriving ''k'' deterministically from the private key and the message hash, as described by RFC 6979. This ensures that ''k'' is different for each ''H(m)'' and unpredictable for attackers who do not know ''x''.

==See also==
* [[Elliptic Curve DSA]]
* [[Modular arithmetic]]

==References==
{{reflist|2}}

==External links==
* [http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf FIPS PUB 186-4: Digital Signature Standard (DSS)], the fourth (and current) revision of the official DSA specification.
* [http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf Recommendation for Key Management -- Part 1: general], NIST Special Publication 800-57, p.&nbsp;62&ndash;63

{{Cryptography navbox | public-key}}

[[Category:Digital signature schemes]]