The Digital Signature Algorithm (DSA) is a standard defined in Federal Information Processing Standard (as FIPS 186) for digital signatures, and is based on discrete logarithms. It was outlined by NIST is 1991, and proposed within the Digital Signature Standard (DSS). This was then standardized with FIPS 186 in 1994, and FIPS 186-4 in 2013. Within FIPS 186-5, it is defined that DSA should not be used for the generation of signatures, but can be used for signature verification. Although DSA has a patent (Patent 5,231,668 by David W. Kravitz, who had previously worked for the NSA), NIST published the standard as a royality-free. The ECDSA method is an extension of DSA, but implemented with elliptic curve (EC) methods. As with most public key signing methods, we take a hash of a message, and then apply a private key to create a signature (\(r,s\)). This is done by creating a random value (\(k\)) to produce the signature. The signature is then verified using the associated public key. This then verifies the creator of the signature and that the message has not been changed.
DSA parameters with OpenSSL |
Method
With a discrete logarithm method, we typically have a base generator (\(g\)) and a prime number (\(p\)). We can then perform operations such as:
\(v=g^x. g^y \pmod p = g^{x+y} \pmod p\)
and:
\(v={(g^x)}^y \pmod p = g^{x.y} \pmod p\)
The Digital Signature Algorithm (DSA) is a standard defined in Federal Information Processing Standard (as FIPS 186) for digital signatures, and is based on discrete logarithms. It was outlined by NIST is 1991, and proposed within the Digital Signature Standard (DSS). This was then standardized with FIPS 186 in 1994, and FIPS 186-4 in 2013. Within FIPS 186-5, it is defined that DSA should not be used for the generation of signatures, but can be used for signature verification. Although DSA has a patent (Patent 5,231,668 by David W. Kravitz, who had previously worked for the NSA), NIST published the standard as a royality-free. The ECDSA method is an extension of DSA, but implemented with elliptic curve (EC) methods. As with most public key signing methods, we take a hash of a message, and then apply a private key to create a signature (\(r,s\)). This is done by creating a random value (k) to produce the signature. The signature is then verified using the associated public key. This then verifies the creator of the signature and that the message has not been changed.
Initially, Bob creates two prime numbers (\(p\) and \(q\)) and generates a generator value of \(g\). Next, he generates his secret key (\(x\)) and then computes his public key:
\(Y=g^{x} \pmod p\)
To create a signature for a message (\(M\)), he creates a random value (\(k\)) and then computes two values for the signature:
\(r = g^{k} \pmod{p} \pmod{q}\)
\(s=(k^{-1}.(H(m)+x.r)) \pmod {q}\)
When Alice receives this signature, she takes Bob's public key \((p,q,g,Y)\) and the message can computes:
\(w = s^{-1} \pmod q\)
\(u_1 = H(M).w \pmod q\)
\(u_2 = r.w \pmod q\)
\(v = (g^{u_1} . y^{u_2}) \pmod {p} \pmod {q}\)
She then checks that \(v\) is equal to \(r\). If so, the signature checks out. This works because:
\(v = g^{h.w}.y^{r.w} = g^{h.w}.g^{x.r.w} = g^{h.w+x.r.w} = g^{h/s+x.r/s} = g^{(H+x.r)/(k^{-1}(H+x.r))} = g^k = r\)
Coding
As we do with the Diffie-Hellman method, we generate DSA parameters:
openssl dsaparam -out dsaparam.pem 1024 type dsaparam.pem openssl gendsa -out 1.pem dsaparam.pem openssl dsa -in 1.pem -text
and a sample test:
-----BEGIN DSA PARAMETERS----- MIIBJgKBgQDb0iZNO05qBkl0qyRjjMq4FxCv31LGvMjk2v+Z5QQRmsvemJIMcjbT q+/j+ZxVIlG6CCKyQSsZ4zvN2nIvSDfwfyo8OOQYKRH+dktMs8FgHd2UBDMyoK84 hcsb3G2ci0ZgU/9PxNtDRz4TJRYpKZAiZ5phLhNQAd1DKSDBL/HEhQIdAMng+Agv AvP6juCUZ/0R7FkLjpxP7k3yKsZoyXsCgYASwir8gZ+8OWdcSIee+SHlrOZ8g61h Cd0PL6r5K5NRwsGNdaW0A/aAbpliVhz3ZEMykpYZD3kXUHrkPyaRLSRMmIQ0HdDa NxJ5VSC5uQf1xNhmsxaUvfNqEX1zWK+5A5DyhJPzZCBpQrGbELnsaLKKFMTywJkC dFYrYPn7lUt/NA== -----END DSA PARAMETERS----- Private-Key: (1024 bit) priv: 00:97:24:4b:e0:ba:17:32:a2:1b:f7:79:26:3c:8b: 91:3e:ea:b7:b9:07:eb:46:77:55:87:06:dd:5c pub: 00:91:0e:02:a0:34:3c:31:6f:c1:49:e8:e7:ef:6b: dd:ef:91:8f:d4:49:93:8c:2f:7b:c6:77:9c:07:de: b3:62:1c:8e:95:00:ba:4b:61:f9:57:b0:91:b4:3a: a8:f6:4c:f4:28:a9:dd:a3:6b:a7:2f:23:4b:dc:af: df:ea:b8:59:c6:a3:1a:95:03:ec:17:eb:6d:66:6c: d9:3b:9f:8c:45:4a:fa:2f:79:c1:6e:ba:77:b4:97: 9d:91:0c:9c:a3:0d:51:23:48:03:94:a8:52:f2:27: da:7c:87:03:3a:d5:1d:3d:70:30:c2:43:84:55:5c: 71:0d:de:23:12:34:8d:fd:3e P: 00:db:d2:26:4d:3b:4e:6a:06:49:74:ab:24:63:8c: ca:b8:17:10:af:df:52:c6:bc:c8:e4:da:ff:99:e5: 04:11:9a:cb:de:98:92:0c:72:36:d3:ab:ef:e3:f9: 9c:55:22:51:ba:08:22:b2:41:2b:19:e3:3b:cd:da: 72:2f:48:37:f0:7f:2a:3c:38:e4:18:29:11:fe:76: 4b:4c:b3:c1:60:1d:dd:94:04:33:32:a0:af:38:85: cb:1b:dc:6d:9c:8b:46:60:53:ff:4f:c4:db:43:47: 3e:13:25:16:29:29:90:22:67:9a:61:2e:13:50:01: dd:43:29:20:c1:2f:f1:c4:85 Q: 00:c9:e0:f8:08:2f:02:f3:fa:8e:e0:94:67:fd:11: ec:59:0b:8e:9c:4f:ee:4d:f2:2a:c6:68:c9:7b G: 12:c2:2a:fc:81:9f:bc:39:67:5c:48:87:9e:f9:21: e5:ac:e6:7c:83:ad:61:09:dd:0f:2f:aa:f9:2b:93: 51:c2:c1:8d:75:a5:b4:03:f6:80:6e:99:62:56:1c: f7:64:43:32:92:96:19:0f:79:17:50:7a:e4:3f:26: 91:2d:24:4c:98:84:34:1d:d0:da:37:12:79:55:20: b9:b9:07:f5:c4:d8:66:b3:16:94:bd:f3:6a:11:7d: 73:58:af:b9:03:90:f2:84:93:f3:64:20:69:42:b1: 9b:10:b9:ec:68:b2:8a:14:c4:f2:c0:99:02:74:56: 2b:60:f9:fb:95:4b:7f:34 -----BEGIN DSA PRIVATE KEY----- MIIBzAIBAAKBgQDb0iZNO05qBkl0qyRjjMq4FxCv31LGvMjk2v+Z5QQRmsvemJIM cjbTq+/j+ZxVIlG6CCKyQSsZ4zvN2nIvSDfwfyo8OOQYKRH+dktMs8FgHd2UBDMy oK84hcsb3G2ci0ZgU/9PxNtDRz4TJRYpKZAiZ5phLhNQAd1DKSDBL/HEhQIdAMng +AgvAvP6juCUZ/0R7FkLjpxP7k3yKsZoyXsCgYASwir8gZ+8OWdcSIee+SHlrOZ8 g61hCd0PL6r5K5NRwsGNdaW0A/aAbpliVhz3ZEMykpYZD3kXUHrkPyaRLSRMmIQ0 HdDaNxJ5VSC5uQf1xNhmsxaUvfNqEX1zWK+5A5DyhJPzZCBpQrGbELnsaLKKFMTy wJkCdFYrYPn7lUt/NAKBgQCRDgKgNDwxb8FJ6Ofva93vkY/USZOML3vGd5wH3rNi HI6VALpLYflXsJG0Oqj2TPQoqd2ja6cvI0vcr9/quFnGoxqVA+wX621mbNk7n4xF SvovecFuune0l52RDJyjDVEjSAOUqFLyJ9p8hwM61R09cDDCQ4RVXHEN3iMSNI39 PgIdAJckS+C6FzKiG/d5JjyLkT7qt7kH60Z3VYcG3Vw= -----END DSA PRIVATE KEY-----
We can see that the private key (priv) has 28 bytes (224 bits), while the public key (\(pub=G^{priv} \pmod P\)) and prime number \(P\) has 128 bytes (1,024 bits). Notice that the \(Q\) value is smaller that the other prime (\(P\)). In a signature, Bob will sign with \(priv\), and then send his public key (\(pub, P, Q and G\)) to Alice. She can then check Bob's signature with his public key.
Additional
DSA is similar to Schnorr signatures. With this, Bob generates a secret value of \(x\), and a prime number of \(p\). He then produces a public key of:
\(Y=g^x \pmod p\)
Bob then creates a random number of \(k\) and computes:
\(r = g^{k} \pmod{p}\)
Next, with a message (m), she computes a challenge (\(e\)) with a hash function of:
\(e=H(r || M)\)
Next, Peggy computes:
\(s = k - x.e\)
Peggy then sends e,s to Victor (the verifier). Victor then determines if:
\(r_v = g^s. Y^e\)
\(e_v = H(r_v || M) \)
These should equal each other. This works because:
\(r_v = g^s. g^{x.e} = g^{k-x.e}. g^{x.e}=g^{k-x.e+x.e} = g^k = r\)