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.
$MD_2$, which it had calculated in step 4
$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
The sender selects a random number R
The sender computes the first signature $S_1$ using $S_1 = E_1^Rmodp$
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
- 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.
- The receiver performs the 1st part of verification called $V_1$ using the equation
$V-1 = E_1^M mod P$
- 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)
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.
Alice chooses a prime no P, between 512 and 1024 bits in lenth the numbers bits in p must be a multiple of 64
Alice chooses a 160 bit prime module q in such a way that q divides (p-1)
Alice uses two multiplications groups <$Z_p, X\gt and \ltZ_q, X\gt$ the second is a subgroup of the first.
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.
and 2 others joined a min ago.
teamques10
★ 69k
pedsangini276
• 4.8k
