# Proving a Forged Signature — The Fail-stop Signature Method

I did a pre-interview with the mighty Torben P Pedersen (famous for the Pedersen Commitment) [here], and will be following up with a full interview, soon. Torben has contributed so much to cryptography of the decades, so let’s take a look at his work on fail-stop signatures:

At the time, Torben was at Aarhus University in Denmark, and Engene at CWI in Amsterdam [here]. With the fail-stop signature, a forgery can be detected, and then the signing mechanism no longer used. We have various properties for this:

• If Alice has signed a message, Bob should be able to accept it.
• Eve cannot forge the signature, without going costly work.
• If Eve manages to create a forgery, Alice can prove with a proof-of-sorgery.
• Alice cannot produce a signature which at a future time will be marked as a forgery.

So, how do you detect a forger? Well, get them to do something that is valid, but to become valid, there’s a few different options that the forger could use to make the fake. If there are lots of options to select from, the forger is unlikely to pick the right one, and we’ll be able to detect a forger a work.

With the van Heijst-Pedersen meethod , the generation of the keys is split between the TTP (trusted third partner) 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 α) such that:

Next select a random value of a from 0 to q−1 and computes:

The TTP sends (p,q,α,β) to Alice. Alice now selects four random values (x1,x2,y1,y2) . She then computes:

Alice creates a signature for message (M) with:

The signatures is then (sig1,sig2). Bob verifiers with:

If v1 is equal to v2 is signature is correct. The signature proof is:

This method is a one time signing scheme.

# Detecting the forgery

Now for the elements of the public key (β1,β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 β1 and β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 StopIterationexcept StopIteration: pass        sig1fake = (x1+ m*y1) % qsig2fake = (x2+m*y2)  % qprint (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 signfake1(s′1) and signfake2(s′2) and it will appear valid. The fake is detected by computing:

The coding is here:

`import randomimport libnumimport sympyfrom Crypto.Util.number import getPrimefrom Crypto.Random import get_random_bytesimport sysprimebits=8if (len(sys.argv)>1):  primebits=int(sys.argv)if primebits>128: primebits=128isprime=False# For q, search for a prime q that is a factor of p-1while (isprime==False):  p = getPrime(primebits, randfunc=get_random_bytes)  q = p//2  if (sympy.isprime(q) and sympy.gcd(q,p-1)>1): isprime=Truealpha=1while (alpha==1):  g=3  alpha = pow(g,(p-1)//q,p)a=random.randint(1,q-1)beta=pow(alpha,a,p)m=10x1 = 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)) % pbeta2 = (pow(alpha,y1,p)*pow(beta,y2,p)) % pprint("\nAlice's public key:")print (f"p={p}, q={q}, alpha={alpha}, beta={beta}, beta1={beta1}, beta2={beta2}")sig1 = (x1+ m*y1) % qsig2 = (x2+m*y2)  % qprint (f"\nx1={x1}, x2={x2}")print (f"y1={y1}, y2={y2}")print (f"\nSig1={sig1}, Sig2={sig2}")v1=(beta1*pow(beta2,m,p)) % pv2=(pow(alpha,sig1,p)*pow(beta,sig2,p)) % pprint (f"v1={v1}, v2={v2}")if (v1==v2): print("Signature checks okay")else: print("Bad signature")# ===== Fakeif (primebits>8): sys.exit()print ("\n\nNow let's generate a fake...")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 StopIterationexcept StopIteration: pass        sig1fake = (x1+ m*y1) % qsig2fake = (x2+m*y2)  % qprint (f"\nx1={x1}, x2={x2}")print (f"y1={y1}, y2={y2}")print (f"\nSig1={sig1fake}, Sig2={sig2fake}")s1diff= (sig1-sig1fake)%qs2diff= libnum.invmod(sig2-sig2fake,q)aval=(s1diff * s2diff) % qprint (f"aval={aval}, a={a}")`

A sample run is:

`Alice's public key:172416440120879 86208220060439 9 3Alice's private key:a:  32435590251523Sigs  57589080246324 79290697369458v1= 74539090295259 v2= 74539090295259`

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=47, x2=74, y1=69, y2=74 Alice's public key:p=179, q=89, alpha=9, beta=147, beta1=173, beta2=146x1=47, x2=74y1=69, y2=52Sig1=25, Sig2=60v1=16, v2=16Signature checks okayNow let's generate a fake...x1=1, x2=32y1=1, y2=17Sig1=11, Sig2=24aval=35, a=54`

Here is a demo:

and the code:

## 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].

Written by

Written by

## Prof Bill Buchanan OBE

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