#Key Generation steps
- Choose a L-bit prime p, such that it satifies the following
- 512 <= L <= 1024
- 64 divides L
- p-1 has a 160-bit prime factor, eg. q.
- Choose a g that belongs to group Zp* such that order of g is q.
- Choose a number uniformly at random from set {2,3,...,q-1}.
- Compute h = g^a mod p. (using square and multiply)
- Verification Key = (p,q,g,h)
- Signing key = a
#Signing process The input to this algorithm is a message-file F, verification key and signing key. The output is the signature on file in signature.txt.
- Choose a random element r in 1 <= r <= q-1
- Compute C1 = ( g^r mod p) mod q. (using square and multiply)
- Compute C2 = (int(SHA1(F)) + aC1)r^-1 mod q. (r^-1 using extended Euclidean algorithm)
- If C1=0 or C2=0, a new random value of r should be chosen and C1, C2 to be recomputed.
- Output (C1, C2) as signature on the file F.
#Verification process The input to this algorithm is a message-signature pair (F, (C1, C2)) and the VerKey (p, q, g, h).
- Compute t1 = int(SHA1(F))C2^-1 mod q. (C2^-1 using extended Euclidean algorithm)
- Compute t1 = C1C2^-1 mod q.
- if (g^t1 * h^t2 mod p) mod q = C1 then output "valid signature" else output "invalid signature".
python version : 3.4.3