Image for post
Image for post
Photo by Kelly Sikkema on Unsplash

ESIGN

Prof Bill Buchanan OBE
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]:

Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

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:

Image for post
Image for post
Image for post
Image for post

Bob checks that u is within these limit:

Image for post
Image for post

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=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=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) % 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=25244035189403130107637493439
v=18963166676425126233166851417
y=2075976933
w=2477046937
s=21092081332359487493973173022
lower=18963166676425126233166851417
u=18963166677469736202375777899
upper=18963166685648498270021627225
Success

And code here:

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store