This lets you use your private key

This all works because you computed your private key

The trick is that multiplication modulo

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

O = n × G

If we first add G to itself a few times, such as

Q = d × G

If anybody wants to check my public key, they can add Q to itself

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

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:

- C
reate a private message nonce k, a random integer from 0 to

*n*.

R=k × G; Compute a public nonce R, a curve point

.

- e=H(M,R); Hash the message and
public nonce. This is the first half of the signature.

- s=(k-e*d)%n; The second half of the signature is computed by modular arithmetic, mod the curve wraparound.

To validate a signature:

- Rv=s × G + e × Q; Add the curve generator to
itself
*s*times, and add this to*e*times your public key Q.

- ev=H(M,Rv); Recompute the hash in step 2. If e==ev, the signatures match.

Rv=s × G + e × Q

Rv=s × G + e × d × G

Rv=(s+e*d) × G

Rv=(k-e*d+e*d) × G

Rv=k × G=R

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

This Python implementation takes about 18 milliseconds.

- z = low bits of hash of message. We keep enough bits
that z<n

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

- (x,y) = k × G. That is, we move down the curve by a
distance of
*k*. - r = x mod n. That is, we take the curve point's x
coordinate mod the group order.

- s = (z+r d) / k mod n. We do "division" here by modular inverse, using the EGCD.
- Return the signature (r,s)

- z = low bits of hash of message.
- u1 = z/s mod n. Again, the division is modular inverse.
- u2 = r/s mod n. Usually you compute the modular
inverse of s once, and apply it again here.

- (x,y) = u1 × G + u2 × Q. This is two curve point
multiplications by scalars, and one curve point addition.

- The signature is valid if and only if r==x mod n.

C = u1 × G + u2 × Q

C = u1 × G + u2 × d × G

C = (u1 + u2 d) × G

C = (z/s + r/s d) × G

C = (z + r d)/s × G

C = (z + r d)/((z+r d)/k) × G

C = k × G

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.