# ESIGN

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

## Signature generation

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.*

## Checking signature

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 random

import libnum

import mathfrom Crypto.Util.number import getPrime

from Crypto.Random import get_random_bytes

import hashlib

import 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=128

p = getPrime(primebits, randfunc=get_random_bytes)

q = getPrime(primebits, randfunc=get_random_bytes)n=p*p*q

k=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=v

print (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=Hello

k=4

p=2484630793

q=4089168911

n=25244035189403130107637493439v=18963166676425126233166851417

y=2075976933

w=2477046937

s=21092081332359487493973173022lower=18963166676425126233166851417

u=18963166677469736202375777899

upper=18963166685648498270021627225

Success

And code here: