ESIGN

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 math

from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
import hashlib
import sys

primebits=32

m="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=4

v=random.randint(1,2**32)

a = hashlib.md5(m.encode())
b = a.hexdigest()
v= int(b, 16) % n

print (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) % n

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

v=18963166676425126233166851417
y=2075976933
w=2477046937
s=21092081332359487493973173022

lower=18963166676425126233166851417
u=18963166677469736202375777899
upper=18963166685648498270021627225
Success

And code here: