To Be Or To Be (Deterministic). That Is The Question

To Be Or To Be (Deterministic). That Is The Question

OpenSSL now supports deterministic ECDSA signatures

Just imagine I had a wet signature, and every time I signed my name, it would give me a different version of it. This would be a non-deterministic signature, but someone could still tell it was me who had signed it. I suppose it’s a bit like using DocuSign, and where the output is not my signature, but DocuSign can tell that it was my email address and location that was used. Of course, my signature — if I could remember how I actually do my wet signature — should be deterministic and should always be a good match to my previous signatures.

But what about a digital signature? With this, Bob has a key pair: a private key and a public key. He then uses his private key to sign a hash of a message, and then Alice proves this signature with his public key:

So, should the signature (r,s) be ever-changing, or have the same output for the same private key and message? Well, with the ever-changing version, we use a random nonce value (k) to make sure it will always change the actual signature. But this brings in weaknesses, such as when we reuse the nonce value or leak the value. To overcome this, there is a move towards using deterministic signatures, and which will produce the same signature for the same private key and message, while still keeping compatibility with existing systems. We thus have to do something with the k value, so that it does not affect the output.

And, so, OpenSSL has just released Version 3.2.0, and one of the key features is a deterministic version of OpenSSL [here], and which complies with RFC 6979:

ECDSA

The ECDSA signature has become the fundamental building block of blockchain applications and in applications which require a light-weight signature method. But it has weaknesses, especially where we do not create a random nonce and when we reuse a nonce value. This type of signature is defined as non-deterministic, as it is not possible to determine the output for a given input. A hash value, for example, is deterministic and where we always get the same hash output for the same input. However, many blockchain applications now use deterministic ECDSA signatures which comply with RFC 6879 [here]:

There are several benefits of this, of which a key advantage is that it is easier to test for a given input and output. Along with this, there has been a general weakness around the randomness of the nonce with a non-deterministic signature. The deterministic version does not need a random source.

The magic of producing a deterministic signature is to create a random nonce (k) that is a mixture of the message and the private key.

Computation

With our curve, we have a generator point of G and an order n. We start by generating a private key (d) and then generate the public key of:

Q=d.G

The public key is a point on the curve, and where it is derived from adding the point G, d times. With a message (m), we aim to apply the private key, and then create a signature (r,s). First, we create a random nonce value (k) and then determine the point:

P=k.G

Next we compute the x-axis point of this point:

r=P_x (mod n)

This gives us the r value of the signature. Next, we take the hash value of the message:

e=H(m)

And then compute the s value as:

s=k^{−1}.(e+d.r)(modn)

The signature is (r,s).

We can verify by taking the message (m), the signature (r,s) and the public key (Q):

e=H(m)

Next we compute:

w=s^{−1}(modn)

u1=e.w

u2=r.w

We then compute the point:

X=u1.G+u2.Q

And then take the x-coordinate of X:

x=X_x (mod n)

If x is equal to r , the signature has been verified.

With a non-deterministic ECDSA, we generate the per-message secret value (k) using a random process. With a deterministic ECDSA, as with EdDSA, the per-message secret value (k) is determined in a fully deterministic way and using a mixture of the message and the private key. When we verify, it does not matter if we are using a deterministic or a non-deterministic signature.

Coding

First, we create a folder named “bc_ecdsa_d” and then go into that folder. We can create a .NET console project for .NET 8.0 with:

dotnet new console --framework net8.0

Next, we can install the Bouncy Castle library with:

dotnet add package BouncyCastle.Crypto.dll --version 1.8.1

Next some code:

namespace ECIES
{
using Org.BouncyCastle.Crypto;
using Org.BouncyCastle.Crypto.Engines;
using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Security;
using Org.BouncyCastle.Crypto.Generators;
using System.Text;
using Org.BouncyCastle.Asn1.Pkcs;
    using Org.BouncyCastle.Pkcs;
    using Org.BouncyCastle.X509;
    using Org.BouncyCastle.Asn1.X9;
    using Org.BouncyCastle.Crypto.EC;
    using Org.BouncyCastle.Crypto.Agreement;
    using Org.BouncyCastle.Crypto.Digests;
    using Org.BouncyCastle.Crypto.Macs;
    using Org.BouncyCastle.Math;
    using Org.BouncyCastle.Crypto.Signers;
    using System.Security.Cryptography.X509Certificates;
    class Program
    {
        static void Main(string[] args)
        {
            string str="Hello";
             var curvename="secp256k1";
            
            if (args.Length >0) str=args[0];
            if (args.Length >1) curvename=args[1]; 
try { 
                var h13 = new Sha256Digest();
                h13.BlockUpdate(System.Text.Encoding.UTF8.GetBytes(str), 0, str.Length);
                var messageHash=new byte[h13.GetDigestSize()];
                h13.DoFinal(messageHash, 0);
            X9ECParameters ecParams = ECNamedCurveTable.GetByName(curvename);
            var curveparam = new ECDomainParameters(ecParams.Curve, ecParams.G, ecParams.N, ecParams.H, ecParams.GetSeed());
  
            Org.BouncyCastle.Crypto.Parameters.ECKeyGenerationParameters keygenParams = new Org.BouncyCastle.Crypto.Parameters.ECKeyGenerationParameters (curveparam, new SecureRandom());
            Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator generator = new  Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator("ECDSA");
            generator.Init(keygenParams);
            var keyPair = generator.GenerateKeyPair();
ECDsaSigner signer = new ECDsaSigner(new HMacDsaKCalculator(new Sha256Digest()));
signer.Init(true,keyPair.Private );
var signature = signer.GenerateSignature(messageHash);
Console.WriteLine("R: {0}",signature[0].ToString(16).ToUpper()); 
Console.WriteLine("S: {0}",signature[1].ToString(16).ToUpper()); 
signer.Init(false,keyPair.Public );
var res = signer.VerifySignature(messageHash,signature[0],signature[1]);
Console.WriteLine("Verified: {0}",res);
            Console.WriteLine("Plain: {0} ",str);
         
            Console.WriteLine("\n== Curve: {0} ",curvename);
            Console.WriteLine("\n==Alice keys == ");
            var privateKey = (ECPrivateKeyParameters) keyPair.Private;
            var publicKey = (ECPublicKeyParameters) keyPair.Public;
            Console.WriteLine("\n  == Private key === ");
            Console.WriteLine("  == D ==={0} ",privateKey.D.ToString()); 
            Console.WriteLine("  == Public key === ");
            Console.WriteLine("  == Q_x ==={0} ",publicKey.Q.XCoord);
            Console.WriteLine("  == Q_t ==={0} ",publicKey.Q.YCoord);
            Console.WriteLine("\n\nCurve details: G={0}, N={1}, H={2}", curveparam.G, curveparam.N, curveparam.H);
            Console.WriteLine("A={0}\nB={1}\nField size={2}",curveparam.Curve.A,curveparam.Curve.B,curveparam.Curve.FieldSize);
            
              } catch (Exception e) {
                Console.WriteLine("Error: {0}",e.Message);
            }
        }
    }
}

A sample run for secp2561 with SHA256 ECDSA gives:

Message: Hello 123
R: D7D35767D66DEAA33D5882A32DA5BBA47E113DD51BD38ED6DFBBB9CB414560CD
S: B870767CC01D917ACFCEBEA169A77E0B25BD16D38D0CCAFE719D89FB1830E798
Verified: True
Plain: Hello 123 
== Curve: secp256k1 
==Alice keys == 
  == Private key === 
  == D ===23044095599826657146353542612152967565900797004069510060578218970272405543165 
  == Public key === 
  == Q_x ===6f816ca06eb427398f5eb44e501a32291b46f514145aa94698df5c29240f86dd 
  == Q_t ===a069aecb3d38308fcaf80da1b60bc44774f79da5208316b23425daee925de6fc 
Curve details: G=(79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,1,0), N=115792089237316195423570985008687907852837564279074904382605163141518161494337, H=1
A=0
B=7
Field size=256

And for NIST (FIPS) with SHA256 ECDSA with P-256:

Message: Hello 123
R: 390FC91644CEF3D011DBDC4056BBE2F78D58EBCBD30AB0717225DCA85FC0D5F8
S: 428453D64E4F463394038885464CD2565C6CDF37B44B709FD9D30ED93CE956D0
Verified: True
Plain: Hello 123 

== Curve: P-256 

==Alice keys == 
  == Private key === 
  == D ===69313545009895186027070593671631970332419607009905382443028721939453033465971 
  == Public key === 
  == Q_x ===dbf9cff5f9d2ffa4e402cc4a28ec1bd292687f527997434e9f01619096776f87 
  == Q_t ===a37d4db03c3155a7ddaab7206438472ae5e017c3ecba179c6b0a1a5cb32d584 
Curve details: G=(6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5,1,ffffffff00000001000000000000000000000000fffffffffffffffffffffffc), N=115792089210356248762697446949407573529996955224135760342422259061068512044369, H=1
A=ffffffff00000001000000000000000000000000fffffffffffffffffffffffc
B=5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Field size=256

Conclusions

If you need to use ECDSA, then use it, and then consider whether you want the signature to be deterministic or not. But, also consider EdDSA, and which has a deterministic signature, and just as efficient as ECDSA. It also scales better in a distributed environment.