Overcoming the Weaknesses of ECDSA — Deterministic Signatures
Overcoming the Weaknesses of ECDSA — Deterministic Signatures
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.
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 (modn)
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-co-ordinate of X:
x=X_x(modn)
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 Dotnet console project for .NET 8.0 with:
dotnet new console --framework net8.0Next we can install the Bouncy Castle library with:
dotnet add package BouncyCastle.Crypto.dll --version 1.8.1Next 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=256And 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