Can I Recover A Message From My Signature?

Can I Recover A Message From My Signature?

Wouldn’t it be amazing if I could sign my name on a message, and where my signature contains the details of the message? Someone could then examine my signature and find out the message. For this, in 1993, Nyberg and Rueppel published a classic paper that allowed a message to be extracted from a digital signature [1]:

All we needed was to take the message and sign with our private key (D), and then create a digital signature (r,s). The values of r and s will thus have the contents of the message. We can then prove the signature with our public key (W), and also extract the message. When implemented in elliptic curves, the method is defined as ECRN (Elliptic Curve Nyberg and Rueppel).

In this case we have a private key of D and which will sign a message (M). A public key (W) will then prove the signature.

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).

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−Px(modn)

We verify the signature if t is equal to e.

This works because:

t=r−Px=Vx+e−(s.G+r.W)x=pubx+e−s.Gx−r.Wx(modn)

Thus:

t=pubx+e−(u−r.x).G−r.W=pubx+e−u.Gx−r.x.Gx−r.Wx(modn)

t=pubx+e−priv.Gx−r.x.Gx−r.Wx (modn)

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).

Code

First we create a folder named “bc_ecrn”, and then go into that folder.We can create a Dotnet 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 [here]:

namespace ECCurves
{
    using Org.BouncyCastle.Asn1.X9;
    using Org.BouncyCastle.Security;
    using Org.BouncyCastle.Crypto.Parameters;
using Org.BouncyCastle.Crypto.Signers;
    class Program
    {
        
        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();
// Create signature
        var signer = new ECNRSigner()  ;     
            var privateKey = (ECPrivateKeyParameters) keyPair.Private;
            var publicKey = (ECPublicKeyParameters) keyPair.Public;      
        signer.Init(true, privateKey);
        var sig=signer.GenerateSignature(System.Text.Encoding.ASCII.GetBytes(msg));
 
 
 // Verify signature
         var signer2 =  new ECNRSigner()  ;
        signer2.Init(false, publicKey);
        var rtn=signer2.VerifySignature(System.Text.Encoding.ASCII.GetBytes(msg),sig[0],sig[1]);

            Console.WriteLine("== Curve: {0} ",curvename);
            Console.WriteLine("== Algol: {0} ",signer.AlgorithmName);
            Console.WriteLine("== Message: {0} ",msg);
            Console.WriteLine("\n== Signature === ");
 Console.WriteLine("== r={0}, s={1} ",sig[0],sig[1]);
Console.WriteLine("== Verified: {0} ",rtn);
            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 for secp2561 [here]:

== Curve: secp256k1 
== Algol: ECNR 
== Message: Hello 
== Signature === 
== r=68713335814914116005996791438516321633183124382225581798639034901780193915383, s=64471947377690057185195810404413639708477135492177494991177556775099422258446 
== Verified: True 
== Private key === 
== D ===80640791308386035477115769340457987686650233533202879957006150723649639290657 
== Public key === 
== Q_x ===8b64b16271d0e380e00af8f0183ae95a2b119fecd3f8530d457b5fbef27e3400 
== Q_t ===b8dbe263cba10554410b144aff475adaa57847936228265f11ceb95dbf31a935 

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

And for P-256 [here]:

== Curve: P-256 
== Algol: ECNR 
== Message: Hello 
== Signature === 
== r=53825644542839693570202641386287847751014815063390885848538830493772945823310, s=73158031570208988019238906980840742546040172827266903437455102732164155234648 
== Verified: True 
== Private key === 
== D ===48978035178548283970560120414494558939516024466453698286377439643686958795274 
== Public key === 
== Q_x ===849ca9e27616035079876ab9ad46ffd1e73a6157e6f41039257fd1cb7a5165d6 
== Q_t ===91fff008c7071b0852d9c88851d7691a10e18ac42d96c80c9dedf168acdd6c52 

Curve details: G=(6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5,1,ffffffff00000001000000000000000000000000fffffffffffffffffffffffc), N=115792089210356248762697446949407573529996955224135760342422259061068512044369, H=1
A=ffffffff00000001000000000000000000000000fffffffffffffffffffffffc
B=5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
Field size=256
Field size=256

Conclusions

Isn’t that cool? A signature that contains a message. Go try it here:

https://asecuritysite.com/bouncy/bc_ecrn

References

[1] Nyberg, K., & Rueppel, R. A. (1993, December). A new signature scheme based on the DSA giving message recovery. In Proceedings of the 1st ACM Conference on Computer and Communications Security (pp. 58–61).