Digital signature algorithm

The Digital Signature Algorithm (DSA) is a cryptographic algorithm used to verify the authenticity of digital messages and digital documents by ensuring that the information haven’t been tampered during transmission. DSA is based on mathematical principles involving modular exponentiation and discrete logarithms, making it highly secure when implemented correctly.

• Digital signatures verify authenticity; they don’t ensure confidential communication.
• To achieve confidentiality, both the message and the signature should be encrypted.
• Encryption can be done using either a secret key or a public key cryptosystem.
• Incorporating this extra security layer enhances a basic digital signature scheme.

Working Principle of DSA

The Digital Signature Algorithm operates through a three-part process: key generation, signature creation, and signature verification.

1. Key Generation: DSA involves generating a pair of keys – a private key and a corresponding public key. The private key is kept secret, while the public key is shared openly.
2. Signature Generation: To sign a message, the sender uses their private key to perform calculations on the message hash, generating a digital signature.
3. Signature Verification: The recipient uses the sender’s public key to verify the signature. If the calculated signature matches the received signature, the message is considered authentic.

Key Generation Phase

1. Choose Domain Parameters:
   • Select prime numbers p and q, where q is a prime divisor of (p-1).
   • Choose a generator g, where 𝑔^𝑥 mod 𝑝 generates a unique value for each x in the range [1, p-1].
   • The domain parameters are chosen to create a secure group.
2. Generate Private Key:
   • Choose a random private key 𝑥 in the range [1, q-1].
   • The private key is randomly generated.
3. Compute Public Key:
   • Compute the corresponding public key 𝑦=𝑔^𝑥 mod 𝑝.
   • Here, public key is computed based on the private key and domain parameters.

Verification Phase

1. Obtain Parameters and Signature:
   • Obtain the domain parameters (p, q, g), the sender’s public key (y), the message M, and the digital signature (r, s).
2. Calculate Intermediate Values:
   • Compute 𝑤=𝑠^-1 mod 𝑞 (modular multiplicative inverse of s modulo q).
   • Compute 𝑢1=(𝐻(𝑀)⋅𝑤) mod 𝑞 and 𝑢2=(𝑟⋅𝑤) mod 𝑞 where H(M) is the hash value of the message.
   • Here, Intermediate values are calculated to prepare for signature verification.
3. Calculate Verification Value:
   • Compute 𝑣=((𝑔^𝑢1⋅𝑦^𝑢2) mod 𝑝) mod 𝑞
   • The verification value (v) is computed using the sender’s public key, hash value of the message, and signature components.
4. Verify Signature:
   • If 𝑣=𝑟 the signature is valid; otherwise, signature is invalid.
   • If the computed v matches the received r (signature component), the signature is considered valid, ensuring the authenticity and integrity of the message.

Digital signature algorithm example

Let’s use a simplified example with small numbers for illustration:

• Let us choose the domain parameters: 𝑝=283, 𝑞=47, 𝑔=60
• Private Key: 𝑥=24
• Public Key: 𝑦=158
• Message: 𝑀 with hash 𝐻(𝑀)=41
• Signature: 𝑟=19, 𝑠=30

1. Verify that 0<𝑟=19<47 and 0<𝑠=30<47 indicating a valid signature.
2. Calculate intermediate values:
   • 𝑤=30^−1 mod 47=11
   • 𝑢1 = (41⋅11) mod 47=28
   • 𝑢2 = (19⋅11) mod 47=21
3. Compute 𝑣= ((60^28 ⋅ 158^21) mod 283) mod 47=19
4. As 𝑣=𝑟, the signature is accepted as valid.

This example demonstrates the step-by-step process of key generation and verification using DSA algorithm, ensuring the authenticity and integrity of digitally signed messages.

Advantages of DSA

1. Security: DSA provides robust security against forgery and tampering, ensuring the integrity and authenticity of digital documents.
2. Efficiency: DSA offers efficient signature generation and verification processes, making it suitable for real-time applications.
3. Standardization: DSA is a standardized algorithm, ensuring interoperability and compatibility across different systems and platforms.

Disadvantages of DSA

1. Key Length: DSA typically requires longer key lengths compared to some other algorithms like RSA for equivalent security levels.
2. Limited Use Cases: DSA is primarily used for digital signatures and may not be suitable for encryption or key exchange purposes.
3. Implementation Complexity: Implementing DSA correctly requires understanding complex mathematical concepts, which can be challenging for some developers.

Comparison of DSA Digital Signature with RSA Digital Signature

The below table compare and contrast the Digital Signature Algorithm (DSA) with the RSA digital signature scheme in terms of key length, computational complexity, and suitability for different applications.

Aspect	DSA	RSA
Key Length	Typically shorter (e.g., 1024 bits)	Longer for equivalent security levels (e.g., 2048 bits)
Computational Complexity	Faster computations	Slower computations
Suitability	Primarily used for digital signatures	Versatile (encryption, signatures, key exchange)
Security	Vulnerable to nonce reuse if RNG flawed.	Resistant to certain attacks if key length is sufficient
Advantages	Shorter key lengths, faster operations	Versatility, robust security with long keys.
Disadvantages	Vulnerability to specific attacks.	Longer key lengths, slower operations compared to DSA for same security.

This table provides a concise overview of the key differences between DSA and RSA in terms of key length, computational complexity, suitability for different applications, security considerations, and their respective advantages and disadvantages.