A fail-stop signature allows Alice to prove that a signature that looks like she has signed, has not actually been signed by her, and is a forgery. In this case we will use the van Heijst-Pedersen method [1]. With this method, the generation of the keys is split between the TTP (trusted third party) and Alice. The TTP generates two prime numbers \(q\) and \(p\), and where \(q\) divides into \(p-1\). Next the TTP selects a generator value (\(g\)) and computes \(\alpha\) such that \(\alpha=g^{(p-1)/q} \pmod p\). Next select a random value of \(a\) from 0 to \(q-1\) and computes: \(\beta=\alpha^a \pmod p\). The TTP sends \((p,q,\alpha,\beta)\) to Alice for her public key, and Alice creates her private key as (\(x_1,x_2,y_1,y_2\)). In the following, the 8-bit prime version generates a forgery, and which should be detected. The value of \(a\) is used to detect a forgery. Overall it is a one-time signature method, and where Alice will sign a message, and then reveal the related private key [article].
Fail-stop signature - Proving a forgery |
Theory
With this method, the generation of the keys is split between the TTP (trusted third party) and Alice. The TTP generates two prime numbers \(q\) and \(p\), and where \(q\) divides into \(p-1\). Next the TTP selects a generator value (\(g\)) and computes \(\alpha\) such that:
\(\alpha=g^{(p-1)/q} \pmod p\)
Next select a random value of \(a\) from 0 to \(q-1\) and computes:
\(\beta=\alpha^a \pmod p\)
The TTP sends \((p,q,\alpha,\beta)\) to Alice as her public key, and the value of \(a\) is the associated private key. For the signature, Alice now selects four random values \((x_1, x_2, y_1, y_2)\), and which because her private key. She then computes:
\(\beta_1=\alpha^{x_1} \beta^{x_2} \pmod p\)
\(\beta_2=\alpha^{y_1} \beta^{y_2} \pmod p\)
Alice's public key becauses (\(\beta_1,\beta_2, p,q,\alpha,\beta\)).
Alice creates a signature for message (\(M\)) with:
\(sig_1=x_1 + m y_1 \pmod q\)
\(sig_2=x_2 + m y_2 \pmod q\)
The signatures is then (\(sig_1,sig_2\)). Bob verifies with:
\(v_1=\beta_1 \beta_2^m \pmod p\)
\(v_2=\alpha^{sig_1} \beta^{sig_2} \pmod p\)
If \(v_1\) is equal to \(v_2\) is signature is correct. The signature proof is:
\(v_1 \equiv \beta_1 \beta_2^m \equiv (\alpha^{x_1} \beta^{x_2}) {(\alpha^{y_1} \beta^{y_2})}^m \equiv \alpha^{x_1 + m y_1} \beta^{x_2+ m y_2} \equiv \alpha^{sig_1} \beta^{sig_2} \equiv v_2 \)
This method is a one time signing scheme.
Detecting the forgery
Now for the elements of the public key (\(\beta_1, \beta_2\)), we can have other possible values for \(x'_1, x'_2, y'_1, y'_2\). A forger will try to generate the values of \(\beta_1\) and \(\beta_2\) with \(x'_1, x'_2, y'_1, y'_2\). In the following the forger can discover the alternative values:
try: for x1 in range(1,q-1): for x2 in range(1,q-1): for y1 in range(1,q-1): for y2 in range(1,q-1): beta1fake = (pow(alpha,x1,p)*pow(beta,x2,p)) % p beta2fake = (pow(alpha,y1,p)*pow(beta,y2,p)) % p if (beta1==beta1fake and beta2==beta2fake): raise StopIteration except StopIteration: pass sig1fake = (x1+ m*y1) % q sig2fake = (x2+m*y2) % q print (f"\nx1={x1}, x2={x2}") print (f"y1={y1}, y2={y2}") print (f"\nSig1={sig1fake}, Sig2={sig2fake}")
The forger can then publish \(x'_1, x'_2, y'_1, y'_2\) and \(signfake_1\)(\(s'_1\)) and \(signfake_2\)(\(s'_2\)) and it will appear valid. The fake is detected by computing:
\(a=(s_1 - s'_1) \times {(s'_2-s_2)}^{-1} \pmod q\)
If the value of \(a\) is the same as the value generated by the TTP, the signature is a forgery, as the forger is unlikely to have used the correct private key \((x_1, x_2, y_1, y_2)\).
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=8 if (len(sys.argv)>1): primebits=int(sys.argv[1]) if primebits>128: primebits=128 isprime=False # For q, search for a prime q that is a factor of p-1 while (isprime==False): p = getPrime(primebits, randfunc=get_random_bytes) q = p//2 if (sympy.isprime(q) and sympy.gcd(q,p-1)>1): isprime=True alpha=1 while (alpha==1): g=3 alpha = pow(g,(p-1)//q,p) a=random.randint(1,q-1) beta=pow(alpha,a,p) m=10 x1 = random.randint(1,q-1) x2 = random.randint(1,q-1) y1 = random.randint(1,q-1) y2 = random.randint(1,q-1) print("\nAlice's private key:") print (f"x1={x1}, x2={x2}, y1={y1}, y2={x2} ") beta1 = (pow(alpha,x1,p)*pow(beta,x2,p)) % p beta2 = (pow(alpha,y1,p)*pow(beta,y2,p)) % p print("\nAlice's public key:") print (f"p={p}, q={q}, alpha={alpha}, beta={beta}, beta1={beta1}, beta2={beta2}") sig1 = (x1+ m*y1) % q sig2 = (x2+m*y2) % q print (f"\nx1={x1}, x2={x2}") print (f"y1={y1}, y2={y2}") print (f"\nSig1={sig1}, Sig2={sig2}") v1=(beta1*pow(beta2,m,p)) % p v2=(pow(alpha,sig1,p)*pow(beta,sig2,p)) % p print (f"v1={v1}, v2={v2}") if (v1==v2): print("Signature checks okay") else: print("Bad signature") if (primebits>8): sys.exit() # ===== Fake print ("\n\nNow let's generate a fake...") try: for x1 in range(1,q-1): for y1 in range(1,q-1): for x1 in range(1,q-1): for y2 in range(1,q-1): beta1fake = (pow(alpha,x1,p)*pow(beta,x2,p)) % p beta2fake = (pow(alpha,y1,p)*pow(beta,y2,p)) % p if (beta1==beta1fake and beta2==beta2fake): raise StopIteration except StopIteration: pass sig1fake = (x1+ m*y1) % q sig2fake = (x2+m*y2) % q v1=(beta1*pow(beta2,m,p)) % p v2=(pow(alpha,sig1fake,p)*pow(beta,sig2fake,p)) % p print (f"v1={v1}, v2={v2}") if (v1==v2): print("Fake Signature checks okay") else: print("Bad fake signature") print (f"\nx1={x1}, x2={x2}") print (f"y1={y1}, y2={y2}") print (f"\nBeta1fake={beta1fake}, Beta2fake={beta2fake}") print (f"\nSig1={sig1fake}, Sig2={sig2fake}") s1diff= (sig1-sig1fake) % q s2diff= libnum.invmod(sig2fake-sig2,q) aval=(s1diff * s2diff) % q print (f"aval={aval}, a={a}") if (aval==a): print ("Proven fake!!!!!") else: print ("Not a fake")
A sample run is:
Alice's private key: x1=637721427, x2=423754701, y1=1577013578, y2=423754701 Alice's public key: p=3417835067, q=1708917533, alpha=9, beta=1479338844, beta1=2087698532, beta2=270213486 x1=637721427, x2=423754701 y1=1577013578, y2=942102927 Sig1=1027599410, Sig2=1300196306 v1=805573460, v2=805573460 Signature checks okay
If we use 8-bit primes, the program searches for a fake value of the private key. Here is a run:
Alice's private key: x1=62, x2=25, y1=70, y2=25 Alice's public key: p=167, q=83, alpha=9, beta=47, beta1=144, beta2=49 x1=62, x2=25 y1=70, y2=53 Sig1=15, Sig2=57 v1=137, v2=137 Signature checks okay Now let's generate a fake... v1=137, v2=137 Fake Signature checks okay x1=1, x2=49 y1=1, y2=23 Beta1fake=144, Beta2fake=49 Sig1=11, Sig2=30 aval=6, a=6 Proven fake!!!!!
References
van Heijst, E., Pedersen, T. P., & Pfitzmann, B. (1992, August). New constructions of fail-stop signatures and lower bounds. In Annual International Cryptology Conference (pp. 15-30). Springer, Berlin, Heidelberg [here].