The Roots of ECDSA … Meet DSA

The Digital Signature Algorithm (DSA) is a standard defined in the Federal Information Processing Standard (FIPS 186) for digital…

The Roots of ECDSA … Meet DSA

The Digital Signature Algorithm (DSA) is a standard defined in the Federal Information Processing Standard (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 royalty-free:

Initally, we created a private key of x and a prime number of p with a generator of g. The public key is then:

and where g is a generator value and p is a large prime number. The public key is then Y,g,p, and the private key is x.

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.

To create a signature for a message (M), he creates a random value (k) and then computes two values for the signature:

When Alice receives this signature, she takes Bob’s public key (p,q,g,Y) and the message can computes:

She then checks that v is equal to r. If so, the signature checks out. This works because:

Code

First we install the Bouncy Castle library:

dotnet add package BouncyCastle.Cryptography

We can generate the DSA parameters with a given size (s) with (and where the 100 value defines the certainty of the resultant values):

DsaParametersGenerator paramgen = new DsaParametersGenerator();
paramgen.Init(s, 100, new SecureRandom());
DsaKeyGenerationParameters param = new DsaKeyGenerationParameters(new SecureRandom(), paramgen.GenerateParameters());

Next we can generate the keypair (x) for the secret key and Y for the public key):

DsaKeyPairGenerator pGen = new DsaKeyPairGenerator();
pGen.Init(param);
AsymmetricCipherKeyPair pair = pGen.GenerateKeyPair();

To sign, we use the private key (pair.Private):

var signEng = new DsaSigner ();
signEng.Init(true, pair.Private);
var sig = signEng.GenerateSignature(data);

This produces (r,s). We can then verify with:

signEng.Init(false, pair.Public);
var rtn = signEng.VerifySignature(data,sig[0],sig[1]);

The full code is [here]:

namespace DSA
{
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Crypto.Generators;
using System.Text;
    using Org.BouncyCastle.Crypto.Signers;
    using Microsoft.VisualBasic;
class Program
    {
        static void Main(string[] args)
        {
            string str="Hwello";
            string size="512";
            if (args.Length >0) str=args[0];
            if (args.Length >1) size=args[1]; 
           byte[] data = Encoding.ASCII.GetBytes(str);
            int s = Convert.ToInt32(size);
     
     DsaParametersGenerator paramgen = new DsaParametersGenerator();
     paramgen.Init(s, 100, new SecureRandom());
DsaKeyGenerationParameters param = new DsaKeyGenerationParameters(new SecureRandom(), paramgen.GenerateParameters());

            DsaKeyPairGenerator pGen = new DsaKeyPairGenerator();
            pGen.Init(param);
            AsymmetricCipherKeyPair pair = pGen.GenerateKeyPair();

            var signEng = new DsaSigner ();

            signEng.Init(true, pair.Private);
             var sig = signEng.GenerateSignature(data);
            signEng.Init(false, pair.Public);
            
            var rtn = signEng.VerifySignature(data,sig[0],sig[1]);
            var priv =(DsaPrivateKeyParameters)pair.Private;
         var pub =(DsaPublicKeyParameters)pair.Public;
           Console.WriteLine ("Message: {0}",str);
           Console.WriteLine ("Size: {0}",size);
           Console.WriteLine ("=== DSA Parameters ==");
           Console.WriteLine ("G: {0}",paramgen.GenerateParameters().G);
           Console.WriteLine ("P: {0}",paramgen.GenerateParameters().P);
        Console.WriteLine ("Q: {0}",paramgen.GenerateParameters().Q);
  
   Console.WriteLine ("\n=== DSA Key ==");
            Console.WriteLine ("Private key: {0}",priv.X);
            Console.WriteLine ("Public key: {0}",pub.Y);
   Console.WriteLine ("\n=== Signature ==");
            Console.WriteLine ("r={0}, s={1}",sig[0],sig[1]);
            Console.WriteLine ("Verified: {0}",rtn);
        }
    }
}

A sample run for a 512-bit key pair is [here]:

Message: Hello
Size: 512
=== DSA Parameters ==
G: 6315842408883679050998228401955118004993094283460362010779226355726078790656463978919373615485671781301356414782239730353228017702878713789477363238784403
P: 11353218387712052453117439443682630415798922734473176956047513195091786833827766620859385636721218505238590524193035284455826686923346331259180022601640757
Q: 1373765573482805921388414353412640419898614573109
=== DSA Key ==
Private key: 710326233066814254114014694915918827184995480103
Public key: 6095234537857694657110769308386369450576615299858886769549486708558552348498611824280953912423272275560451472263092468849483756968813503366996094419896100
=== Signature ==
r=743728676722615404160262679297179828344611846610, s=787917565937143904762833006247843705012979337866
Verified: True

and for 1,024 bit [here]:

Message: Hello
Size: 1024
=== DSA Parameters ==
G: 77206347644771834045071124620982021380393327677680300105823068688397424514968861704555270645719169090311049553343491759469778000474520473846737025516648206640178069664020395740018339555088758764769408603401681756865277334818734903129926741845434823416914862034779289174907495105334751869952884745186779567137
P: 170927963540436973395578809226686003183353635653717452296090863760744506271219320961278876466941173077884934426852763153107212587200885214893238270817377633713075147566773932311781366606505358222438416501231760815032995651129879366645762883026284990021852801406055445637262156450343075980153005948058003644489
Q: 774311712032489155573934037160135026445670537081
=== DSA Key ==
Private key: 726131351827193716889706360163813656414755951208
Public key: 154651483748804619492273082417278447006394502135509962924879290455166141805694006027750079129964115889417244813718933071871517629758591373116764814210028695468173260194559384179838061963125773438511461820792490544019889819756099781773559794176197122819594711125375120736618901249222277666845179553700511972029
=== Signature ==
r=1053154942009016635742137506046300845552663873995, s=727871508603029109375498112153249652725572609450
Verified: True

Conclusions

NIST has now deprecated the DSA signature for new signatures, and it is still worthwhile to learn the basic method, as it can help in reading research papers in cryptography.