With DSA (Digital Signature Algorithm) we use discrete logarithms to produce a digital signature. Overall, we take a hash of a message, and then create a signature using a private (secret) key and a random nonce value (\(k\)). The public key and a hash of the message is then be used to verify the signature. In this case, we will create the signature using a range of key sizes (512-bit, 1,024 bits and 2,048 bits), and a range of hashing methods (such as MD5, SHA-1 and SHA-256).
Digital Signature Algorithm (DSA) with PowerShell |
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
Now, let's implement using PowerShell. With this, we can create a key pair with:
$dsa = [System.Security.Cryptography.DSA]::Create([int]$bits)
and where $$bits is the number of bits we need. Normally this will start at 512 bits, but we need at least 1,024 bits to be secure. To create a signature, we take a hash of the message and then generate the signature. The following generates an SHA-1 hash, for a word ($word) and then generates a signature:
$hash1=[System.Security.Cryptography.HashAlgorithm]::Create("SHA1').ComputeHash([System.Text.Encoding]::UTF8.GetBytes($word)) $SignedHash = $dsa.CreateSignature($hash1);
The full code is:
$word=$Args[0] $hashmethod=$Args[1] $bits=$Args[2] "Input word: "+$word "Hash method: "+$hashmethod "Bits: "+$bits $dsa = [System.Security.Cryptography.DSA]::Create([int]$bits) $KeyInfo = $dsa.ExportParameters($true) "`n==== DSA Key (Secret) ====" "x: "+[System.Convert]::ToHexString($KeyInfo.Seed) "`n==== DSA Key (Public) ====" "P: "+[System.Convert]::ToHexString($KeyInfo.P) "Q: "+[System.Convert]::ToHexString($KeyInfo.Q) "g: "+[System.Convert]::ToHexString($KeyInfo.P) "Y: "+[System.Convert]::ToHexString($KeyInfo.Y) "`n==== Signature ====" $hash1=[System.Security.Cryptography.HashAlgorithm]::Create($hashmethod).ComputeHash([System.Text.Encoding]::UTF8.GetBytes($word)) $SignedHash = $dsa.CreateSignature($hash1); "Hash (Hex): "+[System.Convert]::ToHexString($hash1) "Signature (Hex): "+[System.Convert]::ToHexString($SignedHash) "Signature (Base64): "+[System.Convert]::ToBase64String($SignedHash) $rtn = $dsa.VerifySignature($hash1,$SignedHash); "`nSignature Verified: "+$rtn
and a sample test for MD5 and 512-bit signature:
Input word: qwerty Hash method: md5 Bits: 512 ==== DSA Key (Secret) ==== x: 0786A628C5FDA280868984120D71EAB6AEDB2215 ==== DSA Key (Public) ==== P: 865C0A9855AA1B307C26EF28DD40478F85B0E04E4A4B9AD5CC0D549D2548FAA420AE42332DC0ED0EB92064586C96293F9F2EC26D542AE221D4E3DD6F17018FC5 Q: C76DFDB11B04A4D675CF1EB3B84D3E526ED96491 g: 865C0A9855AA1B307C26EF28DD40478F85B0E04E4A4B9AD5CC0D549D2548FAA420AE42332DC0ED0EB92064586C96293F9F2EC26D542AE221D4E3DD6F17018FC5 Y: 79247303CC8F3E3A2102C05291D33137F7845C2B9F3A8BB43D6CF2E64CB1DA661E59D92295A3F82F14115CC333A2E225BA53BBACCBC0C67884CEE7E8FE950366 ==== Signature ==== Hash (Hex): D8578EDF8458CE06FBC5BB76A58C5CA4 Signature (Hex): 5C54CCC5EF8A15024BFF04AF98C879A4DBC4308818E74A5F659E7B7849D29DEDDBB37FBA91028A6A Signature (Base64): XFTMxe+KFQJL/wSvmMh5pNvEMIgY50pfZZ57eEnSne3bs3+6kQKKag== Signature Verified: True
For a 1,024 bit key with MD5 hashing, we get:
Input word: qwerty Hash method: md5 Bits: 1024 ==== DSA Key (Secret) ==== x: 3AE737444D8E21FE9FD06FAE1918381945F11128 ==== DSA Key (Public) ==== P: FF69798C1D3F517216EA1D6AC5AD4E649B2E20BB210DD6F3A8812B0EBA879AC0F1A062A2C17C7932E3B01C7B99CB2F9748DA2D57E63EFDB372BDDA8141C12B1CDFFF9A98A9225FEC1F4400BA59EE41924C7BCC7E1F5C32F389B234DBC12D61585AEBB34FAE5ABE56699A44B43AD3FD28873FED55E44DDD383E98A2F51C13E6D5 Q: 8D70B8E6B282F960EEE6B73E007E3033DC1BDB77 g: FF69798C1D3F517216EA1D6AC5AD4E649B2E20BB210DD6F3A8812B0EBA879AC0F1A062A2C17C7932E3B01C7B99CB2F9748DA2D57E63EFDB372BDDA8141C12B1CDFFF9A98A9225FEC1F4400BA59EE41924C7BCC7E1F5C32F389B234DBC12D61585AEBB34FAE5ABE56699A44B43AD3FD28873FED55E44DDD383E98A2F51C13E6D5 Y: 93E45854F6A715B96DE91113796BFE60519AEA291DF4FB9A9C6EC1D9FB970969A0F8594C0E3116A914031480A15A414EBD245AD349D86CA5C567656197FDF7F294E1CECEC8A5F74F3767D0076BFB23CCF6A5E60C608559FD9233E75C4887E7516B4BDDF7C33E17E3162894D2BF9B774C1DDE53214AF98CB26BF7E17250AF5E91 ==== Signature ==== Hash (Hex): D8578EDF8458CE06FBC5BB76A58C5CA4 Signature (Hex): 600D734694911926080C26FFAA71978E65F20F103A59A06369B74B0B754FC51BC7E36B6B5DFAEDE9 Signature (Base64): YA1zRpSRGSYIDCb/qnGXjmXyDxA6WaBjabdLC3VPxRvH42trXfrt6Q== Signature Verified: True
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\)