# ESIGN

Oct 23 · 3 min read

As a researcher, you should never dismiss a method, even though it isn’t currently used. There are often opportunities to bring back methods, as has been shown with post-quantum cryptography (PQC) and lightweight cryptography. So let’s look at a smart little signature scheme called ESIGN (Efficient digital SIGNature). The method involves the generation of two random prime numbers (p and q), and generates a value of n=p²q. It was created by Fujioka et al [1], and is defined as a fast method of creating signatures, and where the difficulty relates to the factorization of integers [here]:

In this method, we generate two prime numbers p and q and then compute:

n=p²q

Next, we select a positive integer (k) and which must be greater than or equal to four. Alice’s public key is then (n,k) and her private key is (p,q).

First, we take a message (M) and compute its hash:

Next, we generate a random number x and which is between zero and pq, and then we compute:

The signature is then s.

Now Bob must check Alice’s signature for a given message, and so he uses her public key (n,k). First, Bob will compute:

Bob checks that u is within these limit:

If it is, the signature is valid. Here is a demo:

The coding is here:

import randomimport libnumimport mathfrom Crypto.Util.number import getPrimefrom Crypto.Random import get_random_bytesimport hashlibimport sysprimebits=32m="Hello"if (len(sys.argv)>1):  primebits=int(sys.argv[1])if (len(sys.argv)>2):  m=(sys.argv[2])print (f"m={m}")if primebits>128: primebits=128p = getPrime(primebits, randfunc=get_random_bytes)q = getPrime(primebits, randfunc=get_random_bytes)n=p*p*qk=4v=random.randint(1,2**32)a = hashlib.md5(m.encode())b = a.hexdigest()v= int(b, 16) % nprint (f"v={v}")x=random.randint(1,p*q)## inv_pq = libnum.invmod(p*q,n)w=math.ceil(((v-x**k) % n) /(p*q))y=(w*libnum.invmod(k*pow(x,k-1,p),p) % p)print (f"y={y}")s = (x + y*p*q) % nprint (f"w={w}")print (f"s={s}")u=pow(s,k,n)z=vprint (f"n={n}")upper = z+pow(2,math.ceil(2*math.log(n)/math.log(2)/3),n)print (f"\nlower={z}")print (f"u={u}")print (f"upper={upper}")if (u>z and u<upper): print("Success")

A sample run is:

m=Hellok=4p=2484630793q=4089168911n=25244035189403130107637493439v=18963166676425126233166851417y=2075976933w=2477046937s=21092081332359487493973173022lower=18963166676425126233166851417u=18963166677469736202375777899upper=18963166685648498270021627225Success

And code here:

Written by

Written by