DSA parameters with ASN.1 parsing and 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. In this case, we will parse the parameters and key using ASN1 parsing.
|
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
First, we need to generate the DSA parameters (\(g\), \(q\) and \(p\)):
openssl dsaparam -out dsaparam.pem 1024 cat dsaparam.pem | openssl asn1parse 0:d=0 hl=4 l= 294 cons: SEQUENCE 4:d=1 hl=3 l= 129 prim: INTEGER :F32D65E67DAEEA3BFD27F8E111EC8839AF1DF699ED1EB77F56AE8712F8DDB7047177DC08FC352F1F3AFD491C0FCB6558FFFA884C59BF131C8F2B83B52BDE7398D3DE305D75A8673DA256555C7212633356C0F54D50A595FDBE8DA1DB02A19F93C111B96E89F290D1B0693FA74B77074F20C485258644D2E9E5673A0B86559931 136:d=1 hl=2 l= 29 prim: INTEGER :A9E0490B4326857C1B6ACE962D30125BFE3BC2954D354F7FFEF11BA5 167:d=1 hl=3 l= 128 prim: INTEGER :6F54C58630BD46CAA0ECF31FD9471389E4F2056C1D1EE9A4A088180804BC327138EC4A26989884971ECEB4F159935D72DE654B3AFF329D61588AAC29CB8F2D7DEDC05A5912CC089E8F8E043019EAC944D2D1CBA1225AD17827BAA7AC1F11FCC82D9B9D632D4716A4D758EED8D84DCA7C4C07DE49AE861DA4A9025C6987EFA790 -----BEGIN DSA PARAMETERS----- MIIBJgKBgQDzLWXmfa7qO/0n+OER7Ig5rx32me0et39WrocS+N23BHF33Aj8NS8f Ov1JHA/LZVj/+ohMWb8THI8rg7Ur3nOY094wXXWoZz2iVlVcchJjM1bA9U1QpZX9 vo2h2wKhn5PBEbluifKQ0bBpP6dLdwdPIMSFJYZE0unlZzoLhlWZMQIdAKngSQtD JoV8G2rOli0wElv+O8KVTTVPf/7xG6UCgYBvVMWGML1GyqDs8x/ZRxOJ5PIFbB0e 6aSgiBgIBLwycTjsSiaYmISXHs608VmTXXLeZUs6/zKdYViKrCnLjy197cBaWRLM CJ6PjgQwGerJRNLRy6EiWtF4J7qnrB8R/Mgtm51jLUcWpNdY7tjYTcp8TAfeSa6G HaSpAlxph++nkA== -----END DSA PARAMETERS-----
In the case, we have \(p\)= F32D65E67DAEEA3BFD ... 59931, \(q\)= A9E0490B4326857C1B6 ... C2954D354F7FFEF11BA5, and \(g\) = 6F54C58630 ... FA790. Thus \(g\) and \(p\) have 256 hex characters, and which is 1,024 bits, and \(q\) has 56 hex characters, and represents 224 bits (the size of the private key).
First, we need to generate the DSA key (\(g\), \(q\), \(p\), \(pub\) and \(priv\)):
0:d=0 hl=4 l= 458 cons: SEQUENCE 4:d=1 hl=2 l= 1 prim: INTEGER :00 7:d=1 hl=3 l= 129 prim: INTEGER :F32D65E67DAEEA3BFD27F8E111EC8839AF1DF699ED1EB77F56AE8712F8DDB7047177DC08FC352F1F3AFD491C0FCB6558FFFA884C59BF131C8F2B83B52BDE7398D3DE305D75A8673DA256555C7212633356C0F54D50A595FDBE8DA1DB02A19F93C111B96E89F290D1B0693FA74B77074F20C485258644D2E9E5673A0B86559931 139:d=1 hl=2 l= 29 prim: INTEGER :A9E0490B4326857C1B6ACE962D30125BFE3BC2954D354F7FFEF11BA5 170:d=1 hl=3 l= 128 prim: INTEGER :6F54C58630BD46CAA0ECF31FD9471389E4F2056C1D1EE9A4A088180804BC327138EC4A26989884971ECEB4F159935D72DE654B3AFF329D61588AAC29CB8F2D7DEDC05A5912CC089E8F8E043019EAC944D2D1CBA1225AD17827BAA7AC1F11FCC82D9B9D632D4716A4D758EED8D84DCA7C4C07DE49AE861DA4A9025C6987EFA790 301:d=1 hl=3 l= 128 prim: INTEGER :3B8B165B513C634ECF18EE25F9E9822EBCC093AD9CA7B178E6BB7505590558EA22D5D66A04ACC5290E80241250FB3DBAD9C417E6EF689561F7718B982035F94C5E8715604EB0866F068B17064006841D055C66DB5F0EBFD471DA542FD3A2B496B9D1B299F3A01EE845E1E7EEB8E6A219651EDBF903D9DBC0836FFCE3E5789C7B 432:d=1 hl=2 l= 28 prim: INTEGER :4131BA6870D09314D3E645D9B3C682FC5791917C4EF52C67D3B76A11 -----BEGIN PRIVATE KEY----- MIIBWgIBADCCATMGByqGSM44BAEwggEmAoGBAPMtZeZ9ruo7/Sf44RHsiDmvHfaZ 7R63f1auhxL43bcEcXfcCPw1Lx86/UkcD8tlWP/6iExZvxMcjyuDtSvec5jT3jBd dahnPaJWVVxyEmMzVsD1TVCllf2+jaHbAqGfk8ERuW6J8pDRsGk/p0t3B08gxIUl hkTS6eVnOguGVZkxAh0AqeBJC0MmhXwbas6WLTASW/47wpVNNU9//vEbpQKBgG9U xYYwvUbKoOzzH9lHE4nk8gVsHR7ppKCIGAgEvDJxOOxKJpiYhJcezrTxWZNdct5l Szr/Mp1hWIqsKcuPLX3twFpZEswIno+OBDAZ6slE0tHLoSJa0XgnuqesHxH8yC2b nWMtRxak11ju2NhNynxMB95JroYdpKkCXGmH76eQBB4CHEExumhw0JMU0+ZF2bPG gvxXkZF8TvUsZ9O3ahE= -----END PRIVATE KEY-----
We have taken \(g\), \(q\) and \(p\) from the parameters, and now generated a private key of 4131BA6870D09314D3 ... 4EF52C67D3B76A11, and a public key of 3B8B165B513C634ECF18EE25 ... A542FD3A2B496B9D1B299F3A01EE845E1E7EEB8E6A219651EDBF903D9DBC0836FFCE3E5789C7B.
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.
Now let's try to compute this with Python. Let's take the private key (\(x\)), the generator (\(g\)) and the prime number (\(p\)), and compute the public key (\(Y\)):
>>> g=0x6F54C58630BD46CAA0ECF31FD9471389E4F2056C1D1EE9A4A088180804BC327138EC4A26989884971ECEB4F159935D72DE654B3AFF329D61588AAC29CB8F2D7DEDC05A5912CC089E8F8E043019EAC944D2D1CBA1225AD17827BAA7AC1F11FCC82D9B9D632D4716A4D758EED8D84DCA7C4C07DE49AE861DA4A9025C6987EFA790 >>> x=0x4131BA6870D09314D3E645D9B3C682FC5791917C4EF52C67D3B76A11 >>> p=0xF32D65E67DAEEA3BFD27F8E111EC8839AF1DF699ED1EB77F56AE8712F8DDB7047177DC08FC352F1F3AFD491C0FCB6558FFFA884C59BF131C8F2B83B52BDE7398D3DE305D75A8673DA256555C7212633356C0F54D50A595FDBE8DA1DB02A19F93C111B96E89F290D1B0693FA74B77074F20C485258644D2E9E5673A0B86559931 >>> Y=pow(g,x,p) >>> print (hex(Y)) 0x3b8b165b513c634ecf18ee25f9e9822ebcc093ad9ca7b178e6bb7505590558ea22d5d66a04acc5290e80241250fb3dbad9c417e6ef689561f7718b982035f94c5e8715604eb0866f068b17064006841d055c66db5f0ebfd471da542fd3a2b496b9d1b299f3a01ee845e1e7eeb8e6a219651edbf903d9dbc0836ffce3e5789c7b
and we see that the public key (\(Y\)) matches the generated value from ASN.1. This matches:
301:d=1 hl=3 l= 128 prim: INTEGER :3B8B165B513C634ECF18EE25F9E9822EBCC093AD9CA7B178E6BB7505590558EA22D5D66A04ACC5290E80241250FB3DBAD9C417E6EF689561F7718B982035F94C5E8715604EB0866F068B17064006841D055C66DB5F0EBFD471DA542FD3A2B496B9D1B299F3A01EE845E1E7EEB8E6A219651EDBF903D9DBC0836FFCE3E5789C7B
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\)