Digital Signature

Digital Signature is an authentication mechanism tha enable the creator of a message to attach a code that act as a signature.
Digital Signature is formed by taking the hash of the message and encrypting the message with the creator’s private key.
Digital Signature grantees the source and integrity of the message.
Digital Signature is a public key technique but it cannot be used for encryption or key exchange.

1- It must verify the author and the time and the date of the signature.
2- It must authenticate the contents at the time of the signature.
3- It must be verifiable by third-parties to solve disputes.

1- The signature must be a bit pattern that depends on the message being singed.
2- The signature must use some information unique to the sender to prevent both forgery and denial.
3- It must be relatively easy to produce the digital signature.
4- It must be relatively easy to recognize and verify the digital signature.
5- It must be computationally infeasible to forge a digital signature.
6- It must be practical to retain a copy of the digital signature in storage.

Elgamal Digital Signature uses the private key for encryption and public key for decryption.
The global elements of ELgamal Digital Signature are prime number q and primitive root of q is alpha , User A generates a private key as follows:
1- Generate a random integer \({X}_{a}\) such that 1 < \({X}_{a}\) < q-1.
2- Compute \({Y}_{a} = {a}^{{X}_{a}}\) mod(q).
A’s private key is \({X}_{a}\) and public key is {q,a,\({Y}_{a}\)}.
To sign a message M, User A first compute the hash value m of the message m = H(M) such that m is an integer 0 <= m <= q-1.
Then user A forms the digital signature as follows:
1- Choose a random integer k such that 1<= k <=q-1 and gcd (k,q-1)=1.
2- Compute \({S}_{1} = {a}^{k} mod(q)\)
3- Compute \({k}^{-1} mod(q-1)\)
4- Compute \({S}_{2} = {K}^{-1} * (m-{X}_{a}-{S}_{1}) mod(q-1)\)
5- The signature consists of (\({S}_{1},{S}_{2})\)

User B can verify the signature as follows:
1- Compute \({V}_{1} = {a}^{m} mod(q)\)
2- Compute \({V}_{2} = {Y}_{a}^{{S}_{1}} * {S}_{1}^{S2} mod(q)\)
If \({V}_{1}={V}_{2}\) then the signature is valid.

Example:
In GF(19) q = 19 has primitive roots {2,3,10,13,14,15} and we choose a = 10
User A generates public/private key as follows:
1- \({X}_{a}\) = 16
2- \({Y}_{a} = {a}^{{X}_{a}} mod(q) = 4\)
Then User A private key = 16 and public key={19,10,4}
Suppose User A wants to sign a message with a hash value =14
1- choose k =5
2- \({S}_{1} = {a}^{k} mod(q) {10}^{5} mod(19) = 3\)
3- \({k}^{-1} mod(q-1) = {5}^{-1} mod(18) = 11\)
4- \({S}_{2} = {K}^{-1} * (m-{X}_{a}-{S}_{1}) mod(q-1) = 11(14-16-3)mod(18) = 4\)

User B can verify the signature as follows:
1- \({V}_{1} = {a}^{m} mod(q) = {10}^{14} mod(19) = 16\)
2- \({V}_{2} = {Y}_{a}^{{S}_{1}} * {S}_{1}^{{S}_{2}} mod(q) = {4}^{3} * {3}^{4} mod 19 = 16\)
\({V}_{1} = {V}_{2}\) Then the signature is valid.

Schnorr scheme is also based on discrete logarithms and this scheme is based on using a prime number p with p-1 having a prime factor q.
To generate public/private key
1- Choose p and q such that q is a prime factor of p-1.
2- Choose integer b such that \({a}^{b}\) = 1 mod(q)
The values b,p,q comprise a global public key that can be common to a group of users
3- Choose random integer S 0 < S < q , this is user’s private key
4- Calculate \(V={b}^{-S} mod(p)\) , this is user’s public key
User’s public key is V and User’s private key is S can generates a signature as follows:
1- Choose a random integer r 0 < r < q and compute \(X = {b}^{r} mod(p)\)
2- Concatenate the message with X and hash the result to compute value e which e=H(M||X)
3- Compute \(Y= (r+{S}_{e}) mod(q)\) the signature consists of (e,Y)
Other users can verify the signature as follows:
1- Compute \(X` = {b}^{Y} * {V}^{e} mod(p)\)
2- Verify e = H(M||X`)
If H(M||X)= H(M||X`) Then the signature is valid.

DSA is also based on discrete logarithms and based on ELgamal and Schnorr schemes, DSA consists of Three public parameters that can be common to a group of users
1- 160 bit prime number q is chosen
2- prime number p with length from 512 to 1024 bits such that q divides (p-1)
3- g is chosen to be in the form of \({h}^{(p-1)/1}\) mod(p) which h is an integer between 1 and (p-1) and g > 1.
With these three parameters each user can generate his public/private key.

• The private key X must be random number from 1 to (q-1)
• The public key can be calculated \(y = {g}^{X}\)

To create a signature, users calculate two parameters r and s that are function of the public key components (p,q,g) and user’s private key (x) and the hash code of the message H(M) and a random integer k and unique for each signature
\(r= ({g}^{k} mod(p))mod(q)\)
\(s= [ {K}^{-1} * H(M) + X] mod(q)\)
The signature is (r,s)

At the receiving end verification can be done as follows
1- \(W= {s`}^{-1} mod(q)\)
2- \({U}_{1}= (H(M`)*W) mod(q)\)
3- \({U}_{3}= (r`*w) mod(q)\)
4- \(V= [({g}^{U1} * {Y}^{{U}_{2}} mod(p))] mod(q)\)
If V = r` then the signature is valid.

Note: It is computationally infeasible to recover k from r or recover X from S.