The Beauty and Power of Elliptic Curves: Message Recovery From a Digital Signature

The Beauty and Power of Elliptic Curves: Message Recovery From a Digital Signature

I posted an article on ECRN (Elliptic Curve Nyberg and Rueppel), and how you could recover a message from a digital signature, and someone asked how it worked, so I will document here. The related article is:

and where we can recover a message from a signature (r,s).

Introduction

There’s one simple little equation that protects your online security like no other equation:

y²=x³+ax+b (mod p)

This is the equation of an elliptic curve, and it is beautiful in its simplicity and in its power to protect us when we are online. With this, we define a base point on the curve as G, and then define a scalar value of x. We then multiply G by x, and determine a point:

P=x.G

This is the scalar multiplication of points, and, along with point addition, is the basic operation that we conduct when processing with elliptic curves.

ECRN Signature

First we convert the message to an integer value:

e=Int(M)

we first we create a temporary key pair:

Key=(V_pub,V_priv)

Next we take the x-co-ordinate of V_pub to generate the value of r, and where n is the order of the curve:

r=V_x+e (mod n)

x=D

u=priv

And then compute s:

s=u−r.x (modn)

The signature is then (r,s).

ECRN Verification

We get the base point of the curve G, and use the public key W to get:

P=s.G+r.W

and then:

t=r−P_x (modn)

We verify the signature if t is equal to e. This works because:

t=r−Px=V_x+e−(s.G+r.W)_x=pub_x+e−s.G_x−r.W_x (mod n)

Thus:

t=pub_x+e−(u−r.x).G−r.W_x=pub_x+e−u.G_x−r.x.G_x−r.W_x (mod n)

t=pub_x+e−priv.G_x−r.x.G_x−r.W_x (mod n)

t=e

We have proven the signature, and also that the message is recovered from t. Obviously, we would have to convert this integer value back into our message format. The integer value that represents the message, but thus be less than the order of the curve (n).

Coding breakdown

First we can convert out message into a byte array with:

var message= System.Text.Encoding.ASCII.GetBytes(msg)

From this we can produce the signature. First, we convert our message (and which is the in the form of a byte array (message) to a Big Integer:

            BigInteger e = new Org.BouncyCastle.Math.BigInteger(message);
            var eBitLength = e.BitLength;

The r value is computed by taking a temporate key, and then computing V_x+e (mod n):

do 
            {
                // Temp key
                ECKeyPairGenerator keyGen = new ECKeyPairGenerator();

                keyGen.Init(new ECKeyGenerationParameters(privKey.Parameters, new SecureRandom()));

                tempPair = keyGen.GenerateKeyPair();

                //    Get V_x
                ECPublicKeyParameters V = (ECPublicKeyParameters) tempPair.Public; 
                var Vx = V.Q.AffineXCoord.ToBigInteger(); 

                // r=V_x+e (mod n)
                r = Vx.Add(e).Mod(n);
            }
            while (r.SignValue == 0);

With this V_x is the x-coordinate of a temporary public key, e is the message converted to an integer value, and n is the order of the curve (and which is the number of points on the curve). We can now compute s, but using the user’s private key, the r value, and the temporary private key:

            // Compute s
            BigInteger x = privKey.D;                // User's private key to sign messae
            BigInteger u = ((ECPrivateKeyParameters)tempPair.Private).D; // Use temp private key

            // s=u-rx (mod n)
            s = u.Subtract(r.Multiply(x)).Mod(n);

We now have (r,s), and can then verify the signature against a message, and using the associated public key. First we product P of P=s.G+r.W:

            // compute P = sG + rW

            var G = pubKey.Parameters.G;
            var W = pubKey.Q;

            var P = G.Multiply(s).Add(W.Multiply(r)).Normalize();

Next compute t, which is t=r-x (mod n):

            BigInteger x = P.AffineXCoord.ToBigInteger();

            // t=r-x (mod n)
            BigInteger t = r.Subtract(x).Mod(n);

The value of t is now the recovered value, and so we can test if t is equal to e (the Big Integer version of the message):

            // Return "" if the signature is not verified
            if (t.Equals(e)) return(t);
            else return new BigInteger("");`

And, finally, we just need to covert the Big Integer value (t) back to an ASCII message:

        var mess=t.ToByteArray();
        var recovered_message= System.Text.Encoding.ASCII.GetString(mess);

Here is the full code [here]:

namespace ECCurves
{
    using Org.BouncyCastle.Asn1.X9;
    using Org.BouncyCastle.Security;
    using Org.BouncyCastle.Crypto.Parameters;

    using Org.BouncyCastle.Crypto.Signers;
    
   using Org.BouncyCastle.Math.EC;
    using Org.BouncyCastle.Crypto.Generators;
    using Org.BouncyCastle.Crypto;
    using  Org.BouncyCastle.Math;

    class Program
    {
        
        static public BigInteger[] GenerateSignature(BigInteger n, ECPrivateKeyParameters privKey, byte[] message)
        {


            var nBitLength = n.BitLength;

            BigInteger e = new Org.BouncyCastle.Math.BigInteger(message);
            var eBitLength = e.BitLength;

            var r = new Org.BouncyCastle.Math.BigInteger("1");
            var s = new Org.BouncyCastle.Math.BigInteger("1");

            AsymmetricCipherKeyPair tempPair;
            // First generate r
            do 
            {
                // Temp key
                ECKeyPairGenerator keyGen = new ECKeyPairGenerator();

                keyGen.Init(new ECKeyGenerationParameters(privKey.Parameters, new SecureRandom()));

                tempPair = keyGen.GenerateKeyPair();

                //    Get V_x
                ECPublicKeyParameters V = (ECPublicKeyParameters) tempPair.Public; 
                var Vx = V.Q.AffineXCoord.ToBigInteger(); 

                // r=V_x+e (mod n)
                r = Vx.Add(e).Mod(n);
            }
            while (r.SignValue == 0);

            // Compute s
            BigInteger x = privKey.D;                // User's private key to sign messae
            BigInteger u = ((ECPrivateKeyParameters)tempPair.Private).D; // Use temp private key

            // s=u-rx (mod n)
            s = u.Subtract(r.Multiply(x)).Mod(n);

            return new BigInteger[]{ r, s };
        }
        static public BigInteger VerifySignature(ECPublicKeyParameters pubKey, byte[] message, BigInteger r, BigInteger s)
        {
 
 
            BigInteger n = pubKey.Parameters.N;
            int nBitLength = n.BitLength;

            BigInteger e = new BigInteger(1, message);
            int eBitLength = e.BitLength;


            // compute P = sG + rW

            var G = pubKey.Parameters.G;
            var W = pubKey.Q;

            var P = G.Multiply(s).Add(W.Multiply(r)).Normalize();

            BigInteger x = P.AffineXCoord.ToBigInteger();

            // t=r-x (mod n)
            BigInteger t = r.Subtract(x).Mod(n);

            // Return "" if the signature is not verified
            if (t.Equals(e)) return(t);
            else return new BigInteger("");
        }
        static void Main(string[] args)
        {
            
            
          
            var curvename="secp256k1";
            var msg="Hello";


            if (args.Length >0) msg=args[0];
            if (args.Length >1) curvename=args[1];



             
            try {


            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();



            var privateKey = (ECPrivateKeyParameters) keyPair.Private;
            var publicKey = (ECPublicKeyParameters) keyPair.Public;      


        var sig= GenerateSignature( ecParams.N, privateKey,System.Text.Encoding.ASCII.GetBytes(msg));

        var rtn= VerifySignature(publicKey, System.Text.Encoding.ASCII.GetBytes(msg),sig[0],sig[1]);
        var mess=rtn.ToByteArray();
        var recovered_message= System.Text.Encoding.ASCII.GetString(mess);


            Console.WriteLine("== Curve: {0} ",curvename);
            Console.WriteLine("== Message value: {0} ",msg);

            Console.WriteLine("\n== Signature === ");
            Console.WriteLine("== r={0}, s={1} ",sig[0],sig[1]);
            Console.WriteLine("\n== Recovered value (t): {0} ",rtn);
                Console.WriteLine("== Recovered string: {0} ",recovered_message);


            Console.WriteLine("\n\n\n== Additional information === ");
            Console.WriteLine("\n== Private key === ");
            Console.WriteLine("== D ==={0} ",privateKey.D.ToString()); 
            Console.WriteLine("\n== 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}", ecParams.G, ecParams.N, ecParams.H);

            Console.WriteLine("A={0}\nB={1}\nField size={2}",ecParams.Curve.A,ecParams.Curve.B,ecParams.Curve.FieldSize);




    } catch (Exception e) {
    Console.WriteLine("Error: {0}",e.Message);
    }
    }
    }



}

A sample run is [here]:

A sample run is:

== Curve: secp256k1 
== Message value: Hello 

== Signature === 
== r=56258093035193924605893768055363523414376214869995886419518049532816721288808, s=55950376245422583689902803410240675760102692452339378815507453953374937128606 
== Recovered value: 310939249775 
== Recovered string: Hello 



== Private key === 
== D ===37283788335607829401650757553565046746977748236557448780505781328800305968150 

== Public key === 
== Q_x ===f1158fa7a8147503836a6bf82f513d4dbccfe08c09c98332c2c451bc3ef712f3 
== Q_t ===5b5828e2c57675b75afbd96bdcf05da5b141ba37715bedc93c5229a04262418e 


Curve details: G=(79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,1,0), N=115792089237316195423570985008687907852837564279074904382605163141518161494337, H=1
A=0
B=7
Field size=256

One of the limitations is that the Big Integer value for the message must be less than the order of the curve. For secp256k1, the order of the curve has around 32 bytes, and so our message must be less than 32 ASCII characters.

Conclusions

Sometimes the simplest things are the most beautiful and the most powerful.