Digital Signature Algorithm

The Digital Signature Algorithm ( DSA ; German  " Digital Signature Algorithm " ) is a standard of the US government for Digital Signatures . It was recommended by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS) . In addition to the DSA (originally the only algorithm defined in the DSS ), the DSS contains the RSA signature and ECDSA as further algorithms . The DSS was first in FIPS released and -PUB 186 most recently amended in FIPS PUB 186-4.

It was designed by the NSA as part of an attempt by the US government to bring high-security encryption under control. Part of this strategy was also the export ban on strong encryption algorithms, disregard of which was prosecuted. The DSA is based on the discrete logarithm in finite fields. It is based on the Elgamal signature process and is related to the Schnorr signature . The transfer of the DSA to elliptical curves is called ECDSA ( Elliptic Curve Digital Signature Algorithm ) and is standardized in ANSI X9.62.

As part of the IEEE P1363 standardization, Schnorr accused NIST of infringing its patent with the Digital Signature Algorithm that it had developed . This was in effect until 2008. Before the development of the DSA, negotiations with Schnorr had failed to use his signature scheme. The company RSA , which holds an exclusive license to Schnorr's signature process, could have made it difficult to use a discrete logarithm process instead of its RSA system as a standard with patent disputes, but probably shied away from an open confrontation with the US government.

functionality

A hash process and a math group are required for DSA . As Hashing was originally only SHA-1 allowed in newer versions of the standard also was SHA-2 admitted. The choice of the group depends on two parameters , and from that determine the safety of the procedure. In the original standard and is required, whereby a multiple of 64 must be. The current standard allows the following combinations of and : (1024, 160), (2048, 224), (2048, 256), (3072, 256). may be at most as large as the output length of the hash algorithm. ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle N}$ ${\displaystyle 512\leq L\leq 1024}$ ${\displaystyle N=160}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle N}$ ${\displaystyle N}$

Generate parameters

1. Choose a prime number of length bit. ${\displaystyle q\,}$ ${\displaystyle N\,}$
2. Choose a prime number of length bits such that is a multiple of . ${\displaystyle p\,}$ ${\displaystyle L\,}$ ${\displaystyle p-1}$ ${\displaystyle q\,}$
3. Choose one that has the order in the unit group . A simple way to ensure this is to first find a group element with and and then put it. The desired property then follows from Lagrange's theorem (Because is coprime to the prime number , must be according to Fermat's Little Theorem - the order of can therefore be at most . Since is prime, the order of can not be a divisor of .) ${\displaystyle g}$ ${\displaystyle q}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle h\,}$ ${\displaystyle 1<h<p-1\,}$ ${\displaystyle h^{\frac {p-1}{q}}\mod p\neq 1}$ ${\displaystyle g=h^{\frac {p-1}{q}}\mod p}$ ${\displaystyle h}$ ${\displaystyle p}$ ${\displaystyle g^{q}=h^{p-1}=1\mod p}$ ${\displaystyle g}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle g}$ ${\displaystyle q}$

The parameters are public and can be used by multiple users. ${\displaystyle (p,q,g)}$

Generate key

1. Pick a random one for which: ${\displaystyle x\,}$ ${\displaystyle 1<x<q\,}$
2. Calculate ${\displaystyle y=g^{x}\mod p}$

The verification key is published ( public key ), the signature key must remain secret as it is the secret key . ${\displaystyle y\,}$ ${\displaystyle x\,}$

Sign

To sign the message , it is also sufficient to sign its hash value . ${\displaystyle m\,}$ ${\displaystyle H(m)}$

1. For each message to be signed, choose a random one with ${\displaystyle k\,}$ ${\displaystyle 1<k<q\,}$
2. Compute ; is so a new one must be chosen. ${\displaystyle r=(g^{k}\mod p)\mod q}$ ${\displaystyle r=0}$ ${\displaystyle k}$
3. Compute ; If so, you have to start again with step 1 ${\displaystyle s=k^{-1}\cdot (H(m)+r\cdot x)\mod q}$ ${\displaystyle s=0}$

The signature of the message is the tuple . The value must be kept secret, must not be easy to guess and must not be reused, otherwise the secret signature key can be calculated (see section Security). ${\displaystyle (r,s)\,}$ ${\displaystyle k}$ ${\displaystyle x}$

Verification

A signature and the message are given . ${\displaystyle (r,s)}$ ${\displaystyle m\,}$

1. Check if and . If this is not the case, reject the signature as invalid. ${\displaystyle 0<r<q}$ ${\displaystyle 0<s<q}$
2. Calculate ${\displaystyle w=s^{-1}\mod q}$
3. Calculate ${\displaystyle u_{1}=H(m)\cdot w\mod q}$
4. Calculate ${\displaystyle u_{2}=r\cdot w\mod q}$
5. Calculate ${\displaystyle v=(g^{u_{1}}\cdot y^{u_{2}}\mod p)\mod q}$
6. If so, the signature is valid, otherwise it is invalid. ${\displaystyle v=r\,}$

safety

Random value requirements

As with all signature methods that are based on the discrete logarithm , in particular for methods that are based on elliptic curves , the security depends to a large extent on the properties of the calculated random values.

A random value must be generated for each signature . This must have sufficient entropy , be kept secret and may only be used once. These requirements are critical: If the value is unknown, the secret signature key can be calculated from the signature: . This is also possible if the same value is used twice. It is possible to calculate from two messages with signatures signed with the same . It is then calculated as before . If the entropy is low, an attacker can calculate a secret key for each possible one and then use the public verification key to test which of these is the correct one. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x=(k\cdot s-H(m))\cdot r^{-1}\mod q}$ ${\displaystyle k}$ ${\displaystyle m_{1},m_{2}}$ ${\displaystyle (r,s_{1}),(r,s_{2})}$ ${\displaystyle k=(H(m_{1})-H(m_{2}))/(s_{1}-s_{2})}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle k}$

Concealed channels

Gustavus Simmons discovered several covert channels in DSA. This allows an implementer to inject a message into a signature that only someone who knows the key of the covert channel can read. If the recipient of the message knows the secret signature key, the channel is broadband. If the sender and recipient share a common secret without the recipient knowing the secret signature key, the channel is narrow-band. According to Simmons, it is a “remarkable coincidence” that the obvious disadvantages of the El Gamal process in DSS can all be overcome and that DSS offers “the most favorable conditions for covert communication that have been discovered to date”. Neither NIST nor the NSA commented on the allegation. Since a malicious DSS developer can send parts of the secret key over the hidden channel with any signature, one can only trust DSS implementations whose developers are completely trusted.

Individual evidence

1. ↑ FIPS-186 ( Memento of the original from April 7, 2012 on WebCite ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. , the first version of the standard. 
2. ↑ FIPS-186-4 (PDF; 776 kB), the fourth and current revision.
3. ^ GJ Simmons, "The Subliminal Channels in the US Digital Signature Algorithm (DSA)." Proceedings of the Third Symposium on: State and Progress of Research in Cryptography, Rome: Fondazione Ugo Bordoni, 1993, pp. 35-54.