Similar questions

Explain the digital signatures and how are they used?

Requirements:

i. Message authentication protects 2 parties who exchange messages from any third party. However, it does not protect the 2 parties against each other. Several forms of dispute between the two are possible. Example: Suppose that John sends an authenticated message to Mary. Consider the following disputes that could arise:

1. Mary may forge a different message and claim that it came from John. Mary would simply have to create a message and append an authentication code using the key that John and Mary share.

2. John can deny sending the message, because it is possible for Mary to forge a message, there is no way to prove that John did in fact send the message.

ii. Both scenarios are of legitimate concern. Here are examples of above scenarios:

• First Scenario: An electronic fund transfer takes place and the receiver increases the amounts of funds transferred and claims that the larger amount had arrived from the sender.

• Second Scenario: It is that an electronic mail message contains instructions to a stockbroker for a transaction that subsequently turns out badly. The sender pretends that the message was never sent.

iii. In situations where there is not complete trust between sender and receiver, something more than authentication is needed. The most attractive solution to this problem is the digital signature. The digital signature is analogous to the handwritten signature. It must have the following properties:

• It must verify the author and the date and time of the signature.
• It must to authenticate the contents at the time of the signature.
• It must be verifiable by third parties to resolve disputes.

iv. Thus, the digital signature function includes the authentication function on the basis of these properties, we can formulate the following requirements for a digital signature :

• The signature must be a bit pattern that depends on the message being signed.
• The signature must use some information unique to the sender, to prevent both forgery and denial.
• It must be relatively easy to produce the digital signature.
• It must be relatively easy to recognize and verify the digital signature.
• It must be computationally infeasible to forge a digital signature, either by constructing a new message for an existing digital signature or by constructing a fraudulent digital signature for a given message.
• It must be practical to retain a copy of the digital signature in storage.

v. The Digital Signature Standard (DSS) Approach

• The DSS uses an algorithm that is assigned to provide only the digital signature function. Unlike RSA, it can’t be used for encryption or key exchange. Nevertheless, it is a public key technique.
• The DSS approach for generating digital signatures to that used with RSA. In the RSA approach, the message to be signed is input to a hash function that produces a secure hash code of fixed length.
• This hash code is then encrypted using the sender’s private key to form the signature. Both the message and the signature are then transmitted.
• The recipient takes the message and produces a hash code. The recipient also decrypts the signature using the sender’s public key.
• If the calculated hash code matches the decrypted signature. The signature is accepted as valid. Because only the sender knows the private key, only the sender could have produced a valid signature.

• The DSS approach also makes use of a hash function. The hash code is provided as input to a signature function along

  H (x) = h (h is known) -> one way property

• It is computationally infeasible to find any pair (x, y) such that

  H (x) = H (y) -> strong collision resistance

vi. The Digital Signature Algorithm (DSA):

The DSA is based on the difficulty of computing discrete algorithms. There are 3 parameters that are public and can be common to group of users. The algorithm consists of 3 steps:

1. Key Generation
2. Signing

3. Verifying

   1. Key Genration :

      Algorithm

• Global Public-key components

  1. p: Prime number where 2L-1

  2. q : Prime divisor of (p-1) , where 2159 < q < 2160 ; bit length of 64 bits
  3. g =h (p-1) /q mod p , where h is any integer with 1< h < (p-1) such that h (p-1) /q mod p >1

• User’s Private Key
  

  1. x : Random or Pseudorandom integer with 0 <x &lt;="" q<="" li="">

• User’s Public Key
  

  1. y : gx mod p

  • User’s per-message secret number
    

    1. k : random or pseudorandom integer with 0 < k <q< p="">

    2. Signing:
       

$$\text{Figure 5.7 Signing}$$

• r = $(g^k mod p )$ mod q
• s = $[k^{-1} (H (M) + xr )]$ mod q

• signature : (r, s)

  3.Verifying:

  • w= $(s^| )^{-1}$ % mod q
  • U1 = [H ($M^|$ ) w ] mod q
  • U2 = ($r^|$) w mod q
  • V = [($g^{u1} \ y_{u2}$) mod p ] mod q
  • TEST : v = $r^|$

  M : Message to be signed

  H (M) : Hash of M using SHA-1

  $M^|, r^|, s^|$ : received versions of M, r , s.

  • Test at the end is on the value r, which does not depend on the message at all r is a function of k and the 3 global public key components. Receiver can recover ‘r’ using the incoming message and signature, the public key of the user and the global public key.
  • Because of the difficulty of discrete logarithms, it is feasible for an opponent to recover k from r or to recover x from s. The demanding task is signature generation is the exponential $g^k$ mod p and $k^{-1}$.