The Feige-Fiat-Shamir signature uses two random prime values (\(p\) and \(q\)) and create a modulus (\(n\)). From this Bob creates a public key and a private key, and uses the private key to sign a message, and this is proven with the public key.
Fiege-Fait Shamir signature |
Theory
The Feige-Fiat-Shamir signature uses two random prime values (\(p\) and \(q\)) and create a modulus (\(n\)). From this Bob creates a public key and a private key, and uses the private key to sign a message, and this is proven with the public key.
Key generation
Initially we generate two prime numbers (\(p\) and \(q\)). We then generate:
\(n=p \times q\)
\(\phi=(p-1) \times (q-1)\)
We then select \(k\) random numbers (\(s_1, s_2 ... s_k\)) and compute:
\(v_j={s_j}^{-2} \pmod n\)
The public key becomes \((v_1, v_2 ... v_k)\) and the modulus (\(n\)) and the private key becomes \((s_1, s_2 ... s_k)\).
Signature generation
Now Bob wants to sign a message (\(M\)). First he selects a random number:
\(r = \textrm{rand}(n-1)\)
Bob then computes \(u\):
\(u=r^2 \pmod n\)
We can then compute the hash of the message and the value of \(u\):
\(e = H(M || u)\)
This gives us a bit array value of \(e_1, e_2, ... e_k\). Next we compute the signature value:
\(s = r \cdot \prod_{j=1}^{k} {s_j}^{e_j} \pmod n \)
Bob's signature related to \(M\) is \((e,s)\).
Verifying the signature
Alice computes:
\(w = s^2 \cdot \prod_{j=1}^{k} {v_j}^{e_j} \pmod n \)
The value of \(w\) should be the same as the value of \(u\) that Bob used. Alice can then easily compute the same hash as Bob with:
\(e' = H(M || w)\)
If the bit values of \(e\) and \(e'\) match, the signature is valid. This works because:
\(w = s^2 \cdot \prod_{j=1}^{k} {v_j}^{e_j} = r^2 \cdot \prod_{j=1}^{k} {s_j}^{2 e_j} \prod_{j=1}^{k} {v_j}^{e_j} = r^2 \cdot \prod_{j=1}^{k} {{s_j}^{2}{v_j}}^{e_j}=r^2 = u \pmod n \)
And so \(u\) is equal to \(w\), and thus \(e\) is equal to \(e'\).
Coding
The coding is here:
import random from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes import sys primebits=64 bitsize=128 if (len(sys.argv)>1): primebits=int(sys.argv[1]) if (len(sys.argv)>2): bitsize=int(sys.argv[2]) if (primebits>512): primebits=512 p = getPrime(primebits, randfunc=get_random_bytes) q = getPrime(primebits,randfunc=get_random_bytes) n = p*q PHI=(p-1)*(q-1) k=10 s=[0,0,0,0,0] v=[0,0,0,0,0] for i in range(0,5): s[i]=random.randint(1,n) v[i]=pow(s[i],-2,n) print ("Public key:",s) print ("\nPrivate key:",v) r=random.randint(1,n) u=r**2 % n e=[1,1,0,1,1] sval = r for i in range(0,len(s)): sval =sval * pow(s[i],e[i],n) % n print ("\nSignature (s): ",sval) print ("\nSignature (e): ",e) print ("\nu: ",u) sval = sval**2 for i in range(0,len(v)): sval =sval * pow(v[i],e[i],n) % n print ("\nw: ",sval%n)
A sample run:
p: 13712523228440659687 q: 10017526842032596031 n: 137365569512899780050952290278817902297 Public key: [4064536337132086758839069526980367908, 52071107145609921714058724715596339606, 113591091472084402236994532333505438048, 49481846708542151105993955483852745876, 80249538234822658921994248906469830031] Private key: [72892744806449264939331779486956624262, 35228535408821668557042379959688569825, 126159995474413719146475524493010860118, 51058326997865865633908852980198695234, 107402681516744704268098824869838373344] Signature (s): 56364307577771206607213622830305045984 Signature (e): [1, 1, 0, 1, 1] u: 67677044543658103203961296936471239051 w: 67677044543658103203961296936471239051