The ESIGN (Efficient digital SIGNature) method involves the generation of two random prime numbers (\(p\) and \(q\)), and generates a value of \(n=p^2 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.
ESIGN (Efficient digital SIGNature) |
Theory
In this method, we generate two prime numbers \(p\) and \(q\) and then compute:
\(n=p^2 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:
\(v=h(M)\)
Next we generate a random number \(x\) and which is between zero and \(pq\). Next we compute:
\(w= \lceil ((v-x^k) \pmod n/(pq) \rceil \)
\(y=w \cdot {(k x^{k-1})}^{-1} \pmod p \)
\(s=x+ypq \pmod n\)
The signature is then \(s\).
Check signature
Now Bob must check Alice's signature, and so he uses her public key (\(n,k\)). First, Bob will compute:
\(u=s^k \pmod n\)
\(z=h(M)\)
Bob checks that \(u\) is within these limit:
\(z \leq u \leq z+ 2^{\frac{2}{3} \textit{log} (n)}\)
If it is, the signature is valid.
Coding
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
References
[1] Fujioka, A., Okamoto, T., & Miyaguchi, S. (1991, April). ESIGN: An efficient digital signature implementation for smart cards. In Workshop on the Theory and Application of of Cryptographic Techniques (pp. 446-457). Springer, Berlin, Heidelberg [here].