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 SHA-1 and SHA-256).
Digital Signature Algorithm (DSA) with C# |
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 C#. With this, we can create a key pair with:
var dsa = System.Security.Cryptography.DSA.Create(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 message and then generates a signature:
var hash1 = System.Security.Cryptography.HashAlgorithm.Create("SHA1").ComputeHash(System.Text.Encoding.UTF8.GetBytes(message)); var SignedHash = dsa.CreateSignature(hash1);
The full code is:
pnamespace GCM { class Program { static void Main(string[] args) { var message="Test"; var size="512"; var mode="SHA1"; if (args.Length >0) message=args[0]; if (args.Length >1) size=args[1]; if (args.Length >2) mode=args[2]; try { int bits = Convert.ToInt32(size); var dsa = System.Security.Cryptography.DSA.Create(bits); var e = dsa.ExportParameters(true); string str1 = "Message: : " + message; str1 = str1 + "\nHash message: " + mode; str1 = str1 + "\nBits: " + size; str1 = str1+"\n=== Private key ===\nx: " + BitConverter.ToString(e.Seed).Replace("-", string.Empty); str1 = str1+"\n\n=== Public key ===\nP: " + BitConverter.ToString(e.P).Replace("-", string.Empty); str1 = str1 + "\nQ: " + BitConverter.ToString(e.Q).Replace("-", string.Empty); str1 = str1 + "\nG: " + BitConverter.ToString(e.G).Replace("-", string.Empty); str1 = str1 + "\nY: " + BitConverter.ToString(e.Y).Replace("-", string.Empty); var hash1 = System.Security.Cryptography.HashAlgorithm.Create(mode).ComputeHash(System.Text.Encoding.UTF8.GetBytes(message)); var SignedHash = dsa.CreateSignature(hash1); str1 = str1 + "\nSignature: " + BitConverter.ToString(SignedHash).Replace("-", string.Empty); str1 = str1 + "\nSignature: " + Convert.ToBase64String(SignedHash); var rtn = dsa.VerifySignature(hash1,SignedHash); str1 = str1 + "\n\nSignature Verified: " + rtn; Console.WriteLine("{0}",str1); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
and a sample test for an MD5 hash and for a 512-bit signature:
Message: : HelloHash message: sha1Bits: 512 === Private key === x: BD1194E4927924AA1C200ABCDC37B5ED0CD224B8 === Public key === P: F7335A7DF8E0DD06B5235CFD93E1E81ECDBCD9E7F248B4B625FF32DFD410358F580764D01DE1AEFE4010C714D6EB11A32F7963161655170AAE40BC313CA3544F Q: B1F065CFD2CD1BDBE9FF2BECF795268E0A5C1313 G: E569819C61898C75EC2C5B41F0C26D970C3E08580A5A59FCA34EDAF5D61CE6D664329122B308EDED92E97359FE83FE462E0181B0A85F7CC7D3BDA12D209EA6BE Y: 8F8616A72CC088B8ACB0A03DF58412793F5DF7796DF45D8ECA096A5084C704E784B437078212A7F35D2A142A66F3F67BB7642DFF47D2FED80993848C39C52BCC Signature: 8731AC8C2A411EE085473537184B854C6688372934E3937921FD02280B83CF995B96F82CB2F52B27 Signature: hzGsjCpBHuCFRzU3GEuFTGaINyk045N5If0CKAuDz5lblvgssvUrJw== 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\)