With ECDSA (Elliptic Curve Digital Signature) we use an elliptic curve to produce a digital signature. Overall, we take a hash of a message, and then create a signature using a private key. The public key can then be used to verify the signature. In this case we will take a standard ECDSA signature with SHA-1, SHA-256, SHA-384 and SHA-512 hashing, and using the secp256r1 curve.
ECDSA for Different Hashing Methods and C# |
Method
With Elliptic Curve Cryptography (ECC) we can use a Weierstrass curve form of the form of \(y^2=x^3+ax+b \pmod p\). Bitcoin and Ethereum use secp256k1 and which has the form of \(y^2=x^3 + 7 \pmod p\). In most cases, though, we use the NIST defined curves. These are SECP256R1, SECP384R1, and SECP521R1, but an also use SECP224R1 and SECP192R1. SECP256R1 has 256-bit (x,y) points, and where the private key is a 256-bit scalar value (\(a\)) and which gives a public key point of:
\(a.G\)
Creating the signature
An outline of ECDSA is:
Alice signs the message with the following:
- Create a hash of the message \(e=\textrm{HASH}(m)\).
- Let \(h\) be the \(L_{n}\) be the leftmost bits of \(e\), \(L_{n}\) has a bit length of the group order \(N\).
- Create a random number \(k\) which is between 1 and \(N-1\).
- Calculate a point on the curve as \((x_{1},y_{1})=k\times G\).
- Calculate \( r=x_{1} \pmod N \). If \(r=0\), go back to Step 3.
- Calculate \(s=k^{-1}(h+rd_{A}) \pmod N\). If \(s=0\), go back to Step 3.
- The signature is the pair \((r,s)\).
Bob will check with:
- Create a hash of the message \(e=\textrm{HASH}(m)\).
- Let \(h\) be the \(L_{n}\) leftmost bits of \(e\).
- Calculate \(c=s^{-1} \pmod N\)
- Calculate \(u_{1}=h \cdot c \pmod N\) and \(u_{2}=r \cdot c \pmod N\).
- Calculate the curve point (\(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}\). If \((x_{1},y_{1})=O\) then the signature is invalid.
- The signature is valid if \(r\equiv x_{1}{\pmod {n}}\), invalid otherwise.
Coding
The coding is:
namespace Cmce { using Org.BouncyCastle.Crypto; using Org.BouncyCastle.Security; using Org.BouncyCastle.Crypto.EC; using Org.BouncyCastle.Crypto.Parameters; using System.Security.Cryptography.X509Certificates; class Program { static void Main(string[] args) { try { var msg="Hello"; var method="SHA-1withECDSA"; if (args.Length >0) msg=args[0]; if (args.Length >1) method=args[1]; var gen = new Org.BouncyCastle.Crypto.Generators.ECKeyPairGenerator("ECDSA"); var secureRandom = new SecureRandom(); var keyGenParam = new KeyGenerationParameters(secureRandom, 256); gen.Init(keyGenParam); var keyPair = gen.GenerateKeyPair(); ECPrivateKeyParameters privateKeyParam = (ECPrivateKeyParameters)keyPair.Private; ECPublicKeyParameters publicKeyParam = (ECPublicKeyParameters)keyPair.Public; var signer = SignerUtilities.GetSigner(method); signer.Init(true,keyPair.Private); signer.BlockUpdate(System.Text.Encoding.UTF8.GetBytes(msg), 0,System.Text.Encoding.UTF8.GetBytes(msg).Length); byte[] signature = signer.GenerateSignature(); signer = SignerUtilities.GetSigner(method); signer.Init(false,keyPair.Public); signer.BlockUpdate(System.Text.Encoding.UTF8.GetBytes(msg), 0,System.Text.Encoding.UTF8.GetBytes(msg).Length); var rtn=signer.VerifySignature(signature); Console.WriteLine("Message: {0}",msg); Console.WriteLine("\n=== Private key ==="); Console.WriteLine("D={0}",privateKeyParam.D.ToString()); Console.WriteLine("Method={0}",method); Console.WriteLine("\n=== Public key ==="); Console.WriteLine("Gy={0}",publicKeyParam.Parameters.G.YCoord.ToString()); Console.WriteLine("Gx={0}",publicKeyParam.Parameters.G.XCoord.ToString()); Console.WriteLine("Curve={0}",publicKeyParam.Parameters.Curve.ToString()); Console.WriteLine("Order={0}",publicKeyParam.Parameters.N.ToString()); Console.WriteLine("Qx={0}",publicKeyParam.Q.XCoord.ToString()); Console.WriteLine("Qy={0}",publicKeyParam.Q.YCoord.ToString()); Console.WriteLine("\n=== Signature ==="); Console.WriteLine("\nSignature={0}",Convert.ToHexString(signature)); Console.WriteLine("\nVerified={0}",rtn); } catch (Exception e) { Console.WriteLine("Error: {0}",e.Message); } } } }
and a sample test for secp256k1:
Message: Post Quantum Crypto === Private key === D=121419095404849764515855012415047775391541554722394902556065690372269803511 Method=SHA-1withECDSA === Public key === Gy=4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5 Gx=6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 Curve=Org.BouncyCastle.Math.EC.Custom.Sec.SecP256R1Curve Order=115792089210356248762697446949407573529996955224135760342422259061068512044369 Qx=eb3472338fbfbb1510870bb820ad05f30b9d1330197cd8abf30e6de98abf9b64 Qy=4375cdefe245958f3a0358a723f7dbe2dc8847f7df180c1f2bc6ce691b2cbfb2 === Signature === Signature=304502206DE460A0E46515B578A838CA71961E51FF3B6A76257E07744912EDC48F72AEF802210088753A7A3294DCD9808B87CDA1A7E668833FB57F79DBD696F6DABAB98771B18A Verified=True
The signature is in a DER form, and we can then parse with [here] to get the \(r\) and \(s\) values:
DER: 304502206DE460A0E46515B578A838CA71961E51FF3B6A76257E07744912EDC48F72AEF802210088753A7A3294DCD9808B87CDA1A7E668833FB57F79DBD696F6DABAB98771B18A [U] SEQUENCE (30) [U] INTEGER (02): 49705608531639052973379532627260569791942375067203030641079606654887303229176 [U] INTEGER (02): 61721672109631760174112530506626131835392659902044938154054687780295991734666 -----BEGIN PUBLIC KEY----- MEUCIG3kYKDkZRW1eKg4ynGWHlH/O2p2JX4HdEkS7cSPcq74AiEAiHU6ejKU3NmAi4fNoafmaIM/tX9529aW9tq6uYdxsYo= -----END PUBLIC KEY-----