DSA signature generation with OpenSSL[OpenSSL Home][Home]
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. The file used in this case contains the text of "This is a test."
|
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
We can create a keypair and signature for a file named test.txt. In this case, the file contains "This is a test.":
openssl dsaparam -out dsaparam.pem 1024 openssl gendsa -out 1.pem dsaparam.pem openssl dgst -sha256 -sign 1.pem -out 1.sig -hex test.txt type 1.sig type 1.sig | openssl enc -base64 openssl dsa -in 1.pem - text
and a sample test:
SA-SHA2-256(test.txt)= 303c021c41f04a15af85a5215f181ccd1999931db8051cd6c77c71d9dfa9b079021c17be382511cd4313fb24bec6618390638a1b652600a68d633bf9b23e RFNBLVNIQTItMjU2KHRlc3QudHh0KT0gMzAzYzAyMWM0MWYwNGExNWFmODVhNTIx NWYxODFjY2QxOTk5OTMxZGI4MDUxY2Q2Yzc3YzcxZDlkZmE5YjA3OTAyMWMxN2Jl MzgyNTExY2Q0MzEzZmIyNGJlYzY2MTgzOTA2MzhhMWI2NTI2MDBhNjhkNjMzYmY5 YjIzZQ0K Private-Key: (1024 bit) priv: 76:44:c6:a7:37:71:ba:6d:b2:ac:73:b4:e1:14:4f: 69:32:cf:d5:9f:e3:9b:cb:af:ef:fb:38:ac pub: 00:c5:80:e0:ac:15:4c:17:63:7e:c1:52:50:19:54: 6c:1f:3b:6b:00:a4:5f:9f:e6:82:51:59:d2:9d:fb: c1:53:cf:c7:03:60:ce:64:6b:b2:7d:31:3f:84:ae: bb:9e:54:25:cd:eb:19:aa:e3:69:82:e1:22:e4:25: 0a:93:bf:7b:61:1a:22:50:2c:61:72:ce:9d:33:dc: 77:b2:c7:e8:6e:b7:20:21:84:50:83:78:9a:6c:13: af:74:2c:41:c3:48:b7:a0:ec:07:99:36:4b:f3:c3: c8:22:e8:62:ff:ac:b8:fa:f5:bb:c5:31:57:f0:0f: 45:3d:21:36:dd:2f:b7:5a:45 P: 00:f7:52:0b:82:62:03:34:97:82:ac:7f:91:07:cb: 6c:bb:d1:5a:2c:a5:d5:b2:28:f3:05:ec:70:80:be: 65:c3:40:dd:47:16:1b:31:21:c1:49:91:6d:50:b3: 4d:4d:54:96:5e:9f:4e:1b:66:cc:fb:ee:df:f1:ba: 86:58:66:fd:e0:16:2e:ad:d6:5e:7e:ea:ac:1d:60: 2c:98:a8:ac:c6:75:5c:ab:d0:6a:f7:6a:e1:d8:20: 86:68:aa:75:a0:bf:c3:43:9b:55:03:46:9b:0c:73: 33:0c:5d:bf:db:0a:1d:a9:29:07:b4:e6:63:30:dc: 5d:5d:0d:83:7c:86:b2:07:b5 Q: 00:aa:c1:56:61:8d:80:7c:b1:e5:7a:24:27:5e:40: 67:88:88:47:cd:ac:fd:63:64:cc:8d:88:82:49 G: 00:a3:f8:a3:80:62:cf:a5:1a:0f:90:d3:41:26:ef: c2:09:ed:09:84:5c:87:ff:9e:7f:de:c6:2b:23:98: f2:0e:26:9b:59:99:43:0d:0c:61:a5:de:39:1e:16: 6c:3d:dd:d1:02:11:57:da:c4:f5:e2:48:2c:91:5d: 56:11:28:8b:5d:e2:fb:b5:94:e5:db:50:32:c5:f2: cd:8e:bb:eb:3a:40:e1:c1:0a:09:ef:40:84:48:d0: e6:24:11:13:5a:ff:74:f2:06:de:2a:df:14:a6:f2: 0c:34:db:8b:ae:71:b2:a3:67:4a:fc:51:31:46:06: d2:27:29:c3:60:41:4c:82:dd -----BEGIN DSA PRIVATE KEY----- MIIBzAIBAAKBgQD3UguCYgM0l4Ksf5EHy2y70VospdWyKPMF7HCAvmXDQN1HFhsx IcFJkW1Qs01NVJZen04bZsz77t/xuoZYZv3gFi6t1l5+6qwdYCyYqKzGdVyr0Gr3 auHYIIZoqnWgv8NDm1UDRpsMczMMXb/bCh2pKQe05mMw3F1dDYN8hrIHtQIdAKrB VmGNgHyx5XokJ15AZ4iIR82s/WNkzI2IgkkCgYEAo/ijgGLPpRoPkNNBJu/CCe0J hFyH/55/3sYrI5jyDiabWZlDDQxhpd45HhZsPd3RAhFX2sT14kgskV1WESiLXeL7 tZTl21AyxfLNjrvrOkDhwQoJ70CESNDmJBETWv908gbeKt8UpvIMNNuLrnGyo2dK /FExRgbSJynDYEFMgt0CgYEAxYDgrBVMF2N+wVJQGVRsHztrAKRfn+aCUVnSnfvB U8/HA2DOZGuyfTE/hK67nlQlzesZquNpguEi5CUKk797YRoiUCxhcs6dM9x3ssfo brcgIYRQg3iabBOvdCxBw0i3oOwHmTZL88PIIuhi/6y4+vW7xTFX8A9FPSE23S+3 WkUCHHZExqc3cbptsqxztOEUT2kyz9Wf45vLr+/7OKw= -----END DSA PRIVATE KEY----- -----BEGIN DSA PARAMETERS----- MIIBJwKBgQD3UguCYgM0l4Ksf5EHy2y70VospdWyKPMF7HCAvmXDQN1HFhsxIcFJ kW1Qs01NVJZen04bZsz77t/xuoZYZv3gFi6t1l5+6qwdYCyYqKzGdVyr0Gr3auHY IIZoqnWgv8NDm1UDRpsMczMMXb/bCh2pKQe05mMw3F1dDYN8hrIHtQIdAKrBVmGN gHyx5XokJ15AZ4iIR82s/WNkzI2IgkkCgYEAo/ijgGLPpRoPkNNBJu/CCe0JhFyH /55/3sYrI5jyDiabWZlDDQxhpd45HhZsPd3RAhFX2sT14kgskV1WESiLXeL7tZTl 21AyxfLNjrvrOkDhwQoJ70CESNDmJBETWv908gbeKt8UpvIMNNuLrnGyo2dK/FEx RgbSJynDYEFMgt0= -----END DSA PARAMETERS-----
The signature in this case is "303c021c41f04a15af85a5215f181ccd1999931db8051cd6c77c71d9dfa9b079021c17be382511cd4313fb24bec6618390638a1b652600a68d633bf9b23e".
This is in the DER format, and we can interpret with [here]:
DER string: 303c021c41f04a15af85a5215f181ccd1999931db8051cd6c77c71d9dfa9b079021c17be382511cd4313fb24bec6618390638a1b652600a68d633bf9b23e ==Sequence== Integer (02): 0x41f04a15af85a5215f181ccd1999931db8051cd6c77c71d9dfa9b079 Integer (02): 0x17be382511cd4313fb24bec6618390638a1b652600a68d633bf9b23e
In this case, we have an \(r\) value of "0x41f04a15af85a5215f181ccd1999931db8051cd6c77c71d9dfa9b079", and an \(s\) value of "0x17be382511cd4313fb24bec6618390638a1b652600a68d633bf9b23e".