Ref [here]

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

Prof Bill Buchanan OBE

--

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=ur.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=rP_x (modn)

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

--

--

Prof Bill Buchanan OBE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.