John Napier’s “Signature” in 12 lines of Python

John Napier’s “Signature” in 12 lines of Python

My university campus is in the home of John Napier, and my city (Edinburgh) and university thus have a strong linkage to logarithms. One of the great things about logs is that they are now used in computer security — in the form of discrete logs. For this we have the difficulty of finding the inverse log when we use large numbers. For example — if we use very large numbers — it is extremely difficult to find x, even if we know g and v:

v=g^x

In order to make the maths work for other operations, we add in the modulo — the remainder of an integer divide — of a prime number (mod p):

v=g^x (mod p)

So, let’s see if we can sign for some data, and where we create a value which checks that we have signing it with a secret, and where we should a public value for verification. This is know as public key signing, and where we sign our data with a private key (a secret value) and everyone else proves it with our public key. In the following we will create a simple ElGamal signer for a message, and try to do it in just 12 lines of Python code.

With ElGamal signing, we create a secret signing exponent (s) and then a signing exponent of:

To sign a document (D), we create an ephemeral key (e) — note that this value will not be needed to be sent, but will change the output of the signatures each time. Next we calculate two signature values:

We then check that these values are the same:

The public verification part of the signature is g,v,p and the signature is S1,S2. The secret is s. This works because:

Notice that e is not required for the checking.

Coding

The coding is here:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import gmpy2
import sys
from random import randint

bits=60
msg="Hello"

if (len(sys.argv)>1):
        msg=str(sys.argv[1])
if (len(sys.argv)>2):
        bits=int(sys.argv[2])

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
g=2

s= randint(0, p-1)
v = pow(g,s,p)

e= Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
e_1=(gmpy2.invert(e, p-1))

D=  bytes_to_long(msg.encode('utf-8'))

S_1=pow(g,e, p)
S_2=((D-s*S_1)*e_1) % (p-1)

v_1 = (pow(v,S_1,p)*pow(S_1,S_2,p))%p
v_2 = pow(g,D,p)

print ("Message: %s " % msg)
print ("g: %s" % g)
print ("p: %s" % p)
print ("\nv: %s" % v)
print ("e: %s" % e)
print ("\ns: %s" % s)

print ("\nS_1= %s" % S_1)
print ("S_2=%s" % S_2)
print ("\nV_1=%s" % v_1)
print ("v_2=%s" % v_2)

A sample run [here]:

Message: hello 
g: 2
p: 962407025293790003

v: 612300875982281884
e: 732907246215819091

s: 121873416674282055

S_1= 3576004450321573
S_2=84330426223295484

V_1=735588321791033494
v_2=735588321791033494

Conclusions

And there you go … isn’t Python wonderful for making things come alive. John Napier left a legacy on this world, and that legacy is now making the Internet a safer place.