Digital Signatures: RSA and ECDSA

CS 463/480 Lecture, Dr. Lawlor

RSA Signatures

To set up RSA, you compute secret primes p and q, and publish their product n.  Your public exponent e (normally 65537) is used to compute a secret key d that has the property:
    med = m mod n

This lets you use your private key d to decrypt messages sent by anyone as me mod n.  You can also sign a message using your private key d, with the signature md mod n.  Anyone can verify this signature by raising this to the public exponent, as is used by SSL certificates.

This all works because you computed your private key d as:
   d = e-1 mod φ(n) = (p-1)*(q-1)

The trick is that multiplication modulo n wraps around with period φ(n) = (p-1)*(q-1).  Since only you know the secret primes, only you know the multiplication wraparound period.

Most signature algorithms listed below rely on a similar feature of the multiplication wraparound period.

Multiplication Wraparound on Elliptic Curves

Below, we'll use the fact that good elliptic curves have "prime order n": points wrap around to the identity element O every n additions (This n is smaller than the curve field prime P, but they're both big known primes).  For example, we can start at the generator point G, do a scalar multiplication by n, and we will get back to the identity O:
    O = n × G

If we first add G to itself a few times, such as d times (for a secret key d), we get some non-identity point Q (our public key):
    Q = d × G

If anybody wants to check my public key, they can add Q to itself n times, and it should reach the identity:
    n × Q = n × (d × G) = d × (n × G) = d × O = O

(If it were feasible to compute n × Q by repeatedly adding Q, we would actually reach the identity d times on the way there, but any efficient multiplication algorithm is likely to skip over all these intermediate identity values.)

Schnorr Signatures

A beautifully simple signature scheme, the Schnorr signature, had its US patent expire in 2008 and is now free for use.

We start by creating a secret key d, an integer; and a public key Q, a curve point (Q=d × G).

To sign a message M:
  1. Create a private message nonce k, a random integer from 0 to n.
  2. R=k × G;       Compute a public nonce R, a curve point.
  3. e=H(M,R);      Hash the message and public nonce.  This is the first half of the signature.
  4. s=(k-e*d)%n;     The second half of the signature is computed by modular arithmetic, mod the curve wraparound.
The signature is the integers (e,s).

To validate a signature:
  1. Rv=s × G + e × Q;    Add the curve generator to itself s times, and add this to e times your public key Q.
  2. ev=H(M,Rv);    Recompute the hash in step 2.  If e==ev, the signatures match.
The signature validates because R == R3
  Rv=s × G + e × Q           verification step 1
  Rv=s × G + e × d × G     definition of public key
  Rv=(s+e*d) × G               elliptic curve is a group, so associative
  Rv=(k-e*d+e*d) × G        signature step 4
  Rv=k × G=R                    cancel terms

Here's the python3 Schnorr signature code.  I'm using the bitcoin elliptic curve, but all the cool kids are using Ed25519: the Schorr-style EdDSA over the elliptic curve Curve25519.  

# Hash the message M and the curve point R
#  (this isn't any offical scheme, but a simple ASCII concatenation)
def hashThis(M,C):
	hash=sha256();
	hash.update(M.encode());
	hash.update(str(R).encode());
	return int(hash.hexdigest(),16); # part 1 of signature

# Make signing key
G=curve.G; # generator of curve
n=curve.n; # order of curve
d=rand.getrandbits(256)%n # secret key
Q=G.mul(d); # move down curve by x to make public key

# Schnorr signature process: 
#   uses message and secret key x
M="I am a fish"; # message
k=rand.getrandbits(256)%n; # message nonce
R=G.mul(k); # used to encode
e=hashThis(M,R); # part 1 of signature
s=(k-e*d)%n; # part 2 of signature

print("Signature (e,s)=",e,",",s);

# Verification procss: 
#   uses message, public key Y, signature e, s
Rv=G.mul(s).add(Q.mul(e));
ev=hashThis(M,Rv); # check signature 

if (e==ev):
	print("Signature valid!");
else:
	print("Signature invalid: R=",R," and Rv=",Rv);

(Try this in NetRun now!)

This Python implementation takes about 18 milliseconds.

Elliptic Curve DSA: ECDSA

In ECDSA, to sign a message m using our private key d, we compute:
  1. z = low bits of hash of message.  We keep enough bits that z<n
  2. k = random integer from 1 to n-1.  We can't ever repeat k values for different messages, or let people guess our k value (due to a weak generator).  Some argue you should compute a deterministic k=hash(z,d)
  3. (x,y) = k × G.  That is, we move down the curve by a distance of k.
  4. r = x mod n.  That is, we take the curve point's x coordinate mod the group order.
  5. s = (z+r d) / k mod n.  We do "division" here by modular inverse, using the EGCD.
  6. Return the signature (r,s)
To verify a signature (r,s), we compute:
  1. z = low bits of hash of message.
  2. u1 = z/s mod n.  Again, the division is modular inverse.
  3. u2 = r/s mod n.  Usually you compute the modular inverse of s once, and apply it again here.
  4. (x,y) = u1 × G + u2 × Q.  This is two curve point multiplications by scalars, and one curve point addition.
  5. The signature is valid if and only if r==x mod n.
Why does this work?  You can expand that last curve point computation to see why:
   C = u1 × G + u2 × Q            verification step 4
   C = u1 × G + u2 × d × G      creation of public key
   C = (u1 + u2 d) × G               elliptic curve distributes over addition
   C = (z/s + r/s d) × G               verification steps 2 and 3
   C = (z + r d)/s × G                  factor out division by s
   C = (z + r d)/((z+r d)/k) × G   expand s from signature step 5
   C = k × G                                cancel terms
This last step is exactly how we computed r in signature step 4.

ECDSA is used to verify transactions in BitCoin: a BitCoin address is an encoded hash of an ECDSA public key.

Here's some simple Python3 code that implements ECDSA for the BitCoin elliptic curve:
# Make signing key
G=curve.G; # generator of curve
n=curve.n; # order of curve
d=rand.getrandbits(256)%n # secret key
Q=G.mul(d); # move down curve by d (public key)

# Signature process: 
#   uses message and secret key d
# hashing phase
hash=sha256();
hash.update("I am a fish".encode());
z=int(hash.hexdigest(),16); # SHA-256 matches 256-bit curve size
print("Message digest z=",z);
# signing
k=rand.getrandbits(256)%n; # message nonce
C=G.mul(k); # move down curve by k
r=C.get_x()%n; # part 1 of signature
s=(((z+r*d)%n)*modular_inverse(k,n))%n; # part 2 of signature

print("Signature (r,s)=",r,",",s);

# Verification procss: 
#   uses message z, public key Q, signature r, s
si=modular_inverse(s,n) # =1/s
u1=(z*si)%n  # u1=z/s mod n
u2=(r*si)%n  # u2=r/s mod n
C=G.mul(u1).add(Q.mul(u2)); # C = u1 G + u2 Q
if (r%n==C.get_x()%n):
	print("Signature valid!");
else:
	print("Signature invalid: C.x =",C.get_x()%n);


print("ECDSA elapsed=",time()-start," seconds")

(Try this in NetRun now!)

This takes about 20 milliseconds.  I actually prefer the Schnorr, myself--both signing and verifying are much simpler.