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). This break breaks down the maths involved in the method, and the associated C# code - and recover the message from the signature.
Message Recovery for ECRN and Bouncy Castle (with C#) ECRN using Bouncy Castle and C# |
Method
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)\)
If we have message defined as a byte array, we can convert this to a Big Integer with:
BigInteger e = new BigInteger(1, message);
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\):
\(r=V_x+e \pmod n\)
\(x=D\)
\(u=priv\)
And then compute \(s\):
\(s=u-r.x \pmod n\)
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-P_x \pmod n\)
We verify the signature if \(t\) is equal to \(e\).
This works because:
\(t=r-P_x = V_x+e - (s.G + r.W)_x = pub_x +e - s.G_x - r.W_x \pmod n\)
Thus:
\(t= pub_x + e - (u - r.x).G - r.W = pub_x + e - u.G_x -r.x.G_x - r.W_x \pmod n\)
\(t= pub_x + e - priv.G_x -r.x.G_x - r.W_x \pmod 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\)).
Code break down
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:
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(""); }
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.
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
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).