Subject: Cryptography & Network Security

Topic: Module 4

Difficulty: Medium/High

${\underline{\textbf{Digital Signature Schemes and Authentication Protocols }}}$

Digital Signatures:

An electronic signature that prove the authenticity of a sender of the message is called ‘Digital Signature

Process of Digital Signature:

• The sender uses a signing algorithm to sign the message

• The message and signature are sent to the receiver

• The receiver receives the message and the signature and applies verifying algorithm to the combination

• If the result is true, the message is accepted or else rejected.

Need for key:

• In digital signature, the signer uses his private key applied to a signing algorithm to sign the document

• The verifier on the other hand uses the public key at the signer, applied to the verifying alogorithm to verify the document

Difference between Key generations is Crypto system and digital signature

• Digital signature needs a public key system. The signer signs with his private key, the verifier verifies the signers public key.

• A cryptosystem uses the private and public key of the receiver whereas a digital signature uses the private and public key of the sender.

RSA digital signature scheme

• RSA idea is also used for signing and verifying a message it is called RSA digital signature shceme.

• Digital signature scheme changes the role of the private and public keys

• Private and public keys of only the sender are used not the receiver

• Sender uses her own private key to sign the document and the receiver uses the sender’s public key to verify it.

  

• The signing and verifying sets use the same function, but with different parameters. The verifier compares the message and the output of the function for congruence. If the result is two true the message is accepted.

Key generation in RSA

Key generation in RSA digital signature scheme is exactly the same as key generation in RSA cryptosystem.

Working of RSA digital signature scheme:

• Sender A wants to send a message to the receiver B along with the digital signature S calculated ours the message M

• Step1: The sender A uses the message digest algorithm to calculate the message digest $MD_1$ our the original message M

  

• Step 2: The sender A now encrypts the message digest with her private key. The output of this process is called the digital signature.

  

• Step 3: Now the sender A sends the original message M along with digital signature DS to receiver B

  

• Step 4: After the receiver B receives the original message M and the sender A’s digital signature, B uses the same message digest algorithm which was used by A and calculate its own message digest $MD_2$ as shown below.

  

• Step 5: The receiver B now uses the sender’s A’s public key to decrypt the digital signature. Note that A had used his private key to decrypt the message digest $MD_1$ to form the digital signature. Therefore only A’s public key can be used to decrypt it. The output of this process is the original message digest which was calculated by A ($MD_1$) in step 1.

  

Step 6: B now compare the following two message digests.

1. $MD_2$, which it had calculated in step 4

2. $MD_1$, which is retrieved from A’s digital signature in step 5

         If $MD_1$ = $MD_2$ the following facts are established:
   

a. B accepts the original message (M) as the correct, unaltered message from A

b. B is also assured that the message came from A and not from someone else attached, posing as A

Thus, the principle of digital signature is quite strong, secure and reliable.

El-gamal digital signature scheme:

• This scheme used the same keys but a different algorithm

• The algorithm creates two digital signatures, these two signatures, are used in verification phase.

• The key generation process is the same as that of EI-gamal algorithms

• The public key remains ($E_1, E_2, P$) and the private key continues to be D

Signature

• This process works as follows

1. The sender selects a random number R

2. The sender computes the first signature $S_1$ using $S_1 = E_1^Rmodp$

3. The sender computes the second signature $S_2$ using the equation

$S_2$ =$(M-D XS_1) X R^{-1}mod (P-1)$

Where P= large prime number

M= original message that needs to be signed

1. The sender sends $M, S_1, S_2$ to the receiver.

For eg. Let $E_1$ = 10, $E_2$ = 4, P=19, M=14, D=16 & R=5

Then, $S_1 = E_1^Rmodp$= 10^5mod19= 3

$S_2 =(M-D XS_1) X R^{-1}mod (P-1) = (14-16 X3) X 5^{-1}mod (18) $= 4

Then these signatures $S_1 and S_2$ are sent to the receiver.

Verification:

This process works as follows.

1. The receiver performs the 1st part of verification called $V_1$ using the equation

$V-1 = E_1^M mod P$

1. The receiver performs the 2nd part of verification called as $V_2$ using the equation

$V_2 = E_2^{S_1} S_1^(S_2)mod P$

Eg $V_1 = E_1^M mod P$

$V_2 = E_2^{S_1} S_1^(S_2)mod P = 4^3 X 3^4mod P$ = 5184 mod 19 = 16

Since $V_1$=$V_2$, the signature is valid.

Schnarr digital signature scheme:

• The problem with EI-gamal digital signature is that P needs to be very large to guarantee that the discrete log problem is interactive. The recommendation is a p of at least 1024 bits. This could make this signature as large as 2048 bits to reduce the size of the signature schnorr proposed a new scheme based on EI-gamal, but with a reduced size.

  

Where, $S_1, S_2$: signatures

D: alices private key

R: random secret

M: message

($e_1, e_2, p, q$): Alices public key

In signing process, two functions create two signatures, in the verifying process the output of one function is compared to the 1st signature for verification.

Here two modules: p & q are used

Function 1 & 3 use p,

Function 2 uses q

Key generation:

Before signing a message, Alice needs to generate keys and announce the public keys to the public.

a. Alice selects a prime ‘P’ which is usually 1024 bits in length

b. Alice selects another prime of which is the same size as the digest created by the cryptographic hash function (currently 160 b) beat it may change in future. The prime of needs to divide (p-1) i.e (p-1)= 0 mod 9

c. Alice chooses $e_1$ to be the qth root of 1 module p, for the allice chooses a primiture element $e_0$ and calculate $e_1 = e_1^{(p-1)/q}mod p$

d. Alice chooses an integer, d as her private key

e. Alice calculate $e_2 = e_1^dmodp$

f. Alice’s public key is $(e_1, e_2, p, q)$; & private key is d.

Where,

M: message, r: Random secret, I: concentration

$S_1, S_2$: Signature, d: Alice’s Private key, n(…) hash algorithm.

V: verification $(e_1, e_2, p, q)$ : Alices public key

Signing:

• Alice chooses a random number r. note that although public & private keys can be used to sign multiple messages, Alice needs to change and each time she sends a new message. Note also that and needs to be between 1 and q

• Alice calculates the first signature $S_1 = h(M/e_1^Rmodp)$. The message is pretended to the value of $e_1^Rmodp$; then the hash function is applied to create a digest. Net that the hash function is not directly applied to the message, but instead is applied to the concatenation of M and $e_1^Rmodp$

• Alice calculates the second signature $S_2 = r + d X S_1 modq$. Note that part of the calculation of $S_2$ is done in module of arithmetic.

• Alice sends M, $S_1$ & $S_2$

Verifying Message

• The receiver Bob, assume receives M, $S_1 & S_2$

• Bob calculates v= H(M/$e_1^{S_2}e_2^{S_1}mod p)4$

• if $S_1$ is longluent to V modulo p, the message is accepted other rejected.

Digital signature standard (DSS)

• DSS uses a digital signature algorithm (DSA) based on the EI gamal scheme with some ideas the schnorr sheme

  

Where, $S_1, S_2$: signatures

D: alices private key

R: random secret

M: message

($e_1, e_2, p, q$): Alices public key

• In signing process, two functions create two signature, in the verifying process, the output of one function is compared to the first signature for verification. This is similar to schnorr, but the input are different. Another difference is that this scheme uses the message digest (not message) as part of inputs to functions 1 & 3.

• This scheme uses two moduli p and q function 1 and 3 use both p and q function 2 uses only q.

Key generation:

Before siging a message to any entity, alice needs to generate keys and announce the public ones to the public.

1. Alice chooses a prime no P, between 512 and 1024 bits in lenth the numbers bits in p must be a multiple of 64

2. Alice chooses a 160 bit prime module q in such a way that q divides (p-1)

3. Alice uses two multiplications groups <$Z_p, X\gt and \ltZ_q, X\gt$ the second is a subgroup of the first.

4. Alice creates e, to be the qth root of 1 modulo p ($e^p = 1 mod p$). to do so, alice chooses a primulas element in $Z-p, C-o$ and calculates $e_1 = e_0^(C, P_2,p,q)$ and his private key

   Signing:

   

Following steps to sign the message

• Alice chooses a random number r $(1 \le r \le q)$. Note that although public and private keys can be chosen once and used to sign many messages, Alice needs to select a new and each time she needs to sign a new message.

• Alice calculates the first signature $S_1 = (e_1^Rmodp)modq$. Note that the value of the first signature does not depend on M, the message.

• Alice creates a digest of message h(M)

• Alice calculates the second signature $S_2 =(h(M) + DS_1) X R^{-1}mod q$ Note that the calculation of $S_2$ is done in module q arithmetic.

• Alice sends M, S, & $S_2$ to bob.

Verifying Message:

Following are the steps used to verify the message which M, $S_1$, & $S_2$ are received.

a. Bob checks to sec if 0<$S_1$<q</p>

b. Bob checks to sec if 0<$S_2$<q</p>

c. Bob calculates a digest of M using the same hash algorithms used by Alice

d. Bob calculates V = [ $(e_1^{h(M)S_2^{(-1)}} e_2^{S_1S_2^{-1}})modp) modq$ ]

e. If $S_1$ is Longmont to V, the message is a accepted, otherwise it is rejected.