With an undeniable signatures, Alice requires an interaction with Bob to prove Bob's signature. In this case we will implement the Chaum-van Antwepen undeniable signature scheme [1]. For this, Bob interacts with Alice to prove that he was the one who signed a message.
Undeniable signatures (Chaum-van Antwepen) |
Theory
With an undeniable signatures, Alice requires an interaction with Bob to prove Bob's signature. In this case we will implement the Chaum-van Antwepen undeniable signature scheme. For this, Bob interacts with Alice to prove that he was the one who signed a message
Key generation
Bob generates two prime numbers (\(p\) and \(q\)) and where:
\(p=2q+1\)
Next Bob selects a random value \(\beta\)) and then selects:
\(\alpha=\beta^{(p-1)/q} \pmod p\)
Next Bob selects a random value of (\(a\) from 0 to \(q-1\):
\(a \in \{1,2, .... q-1\}\)
and computes:
\(y=\alpha^a \pmod p\)
Bob's public key is \((p,\alpha,y)\) and his private key is \(a\).
Signature generation
Bob now computes a signature value (\(s\)) for a message (\(m\)) with:
\(s=m^a \pmod p\)
The value of \(s\) is now the signature for message (\(m\)).
Checking signature
Now Alice must verify the signature, and for Bob to interact for there to be undeniable proof of the signature. First Alice generates two random values:
\(x_1 \in \{1,2, .... q-1\}\)
\(x_2 \in \{1,2, .... q-1\}\)
Alice then computes:
\(z=s^{x_1} y^{x_2} \pmod p\)
and sends this value to Bob.
Bob computes:
\(w={(z)}^{a^{-1}} \pmod p\)
and where \(a a^{-1} = 1 \pmod q\). Bob sends this value to Alice. Alice then computes:
\(w'=m^{x_1} \alpha^{x_2} \pmod p\)
If \(w\) is equal to \(w'\), the signature is accepted. This works because:
\(w \equiv {(z)}^{a^{-1}} \equiv { (s^{x_1} y^{x_2} ) }^{a^{-1}} \equiv { (m^{a x_1} \alpha^{a x_2} ) }^{a^{-1}} \equiv m^{x_1} \alpha^{x_2} \equiv w' \pmod p\)
Coding
The coding is here:
import random # import libnum import sympy from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes import sys primebits=32 if (len(sys.argv)>1): primebits=int(sys.argv[1]) if (primebits>128): primebits=128 isprime=False # For q, search for a prime p that is p=2q+1 while (isprime==False): q = getPrime(primebits, randfunc=get_random_bytes) p =2*q+1 if (sympy.isprime(p)): isprime=True # res=list(libnum.factorize(p).values()) # if (res[0]==1 and len(res)==1): isprime=True alpha=1 while (alpha==1): beta=random.randint(1,p) alpha = pow(beta,(p-1)//q,p) a=random.randint(1,q-1) y=pow(alpha,a,p) m=10 s=pow(m,a,p) print ("q: ",q) print("\nBob's public key:") print ("p: ",p) print ("alpha: ",alpha) print ("y: ",y) print ("\nBob's private key:") print ("a: ",a) print ("\nSignature for message:") print ("s: ",s) x1=random.randint(1,q-1) x2=random.randint(1,q-1) print ("\nx1 and x2:",x1,x2) z=pow(s,x1,p)*pow(y,x2,p) % p a_inv=pow(a,-1,q) print ("\na inv",a_inv) w = pow(z,a_inv,p) w_dash=(pow(m,x1,p)*pow(alpha,x2,p)) %p print ("\nw=",w) print ("w'=",w_dash)
References
[1] Chaum, D., & Van Antwerpen, H. (1989, August). Undeniable signatures. In Conference on the Theory and Application of Cryptology (pp. 212–216). Springer, New York, NY.