Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What Is Asymmetric Encryption?
3.
Why is Cryptography a Smart Solution?
4.
What Are Digital Signatures?
4.1.
Key
4.1.1.
Public Key 
4.1.2.
Private Key
4.2.
Encryption
4.2.1.
Symmetric Encryption
4.2.2.
Asymmetric Encryption
5.
Block Diagram of Digital Signature
6.
Importance of Digital Signature
7.
Role of Digital Signatures
8.
Digital Signature Algorithm Explanation
9.
Steps in DSA Algorithm
10.
Correctness of the Algorithm
11.
How Does DSA Work?
12.
How Does the Algorithm Authenticate Sender?
13.
Advantages of DSA
14.
Disadvantages of DSA
15.
Example of a DSA Signing by Alice
16.
Example of DSA Verification by Bob
17.
Difference Between RSA Algorithm and DSA
18.
Authenticate the Data Source With DSA
19.
Global Public key Components
19.1.
Signature Functions
19.2.
Verifying Functions
20.
Frequently Asked Questions
20.1.
What is the algorithm for a digital signature?
20.2.
Why is the DSA algorithm used?
20.3.
Describe DSA and RSA.
20.4.
Is RSA an algorithm for digital signatures?
21.
Conclusion
Last Updated: Apr 29, 2024
Easy

Digital Signature Algorithm (DSA) in Cryptography

Author Vaibhav Mani
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Hello Ninjas!

Nowadays, while filling out job applications, many of you definitely would have read the term digital signature. So yes, we are going to talk about that only today, emphasizing more on its algorithm names as Digital Signature Algorithm.

Introduction

The term DSA(digital signature algorithm) here refers to a standard for digital signatures. As a more effective way to create digital signatures, the National Institute of Standards and Technology (NIST) introduced it in 1991. It is one of the most preferred digital signature algorithms in use today, along with RSA

What Is Asymmetric Encryption?

Asymmetric encryption, or public-key cryptography, uses a pair of keys (public and private) to encrypt and decrypt data. Public key encrypts, private key decrypts, ensuring secure communication.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Why is Cryptography a Smart Solution?

Cryptography ensures secure communication by converting data into a format unreadable to unauthorized users. It protects sensitive information from interception, tampering, and unauthorized access, fostering trust in digital transactions and communications.

What Are Digital Signatures?

In asymmetric encryption, we have a private and a public key; the public key is shareable to all users, but the private key is non-shareable. If the message encryption is done using a sender's private key, the process is known as digital signatures.

Before diving deep into Digital Signature Algorithm, let’s understand some terms.

Key

It is the most vital and important information as far as security is concerned because if some plaintext gets known to an attacker or hacker, no problem, but if the gets known to the attacker/hacker, then it means the whole information is leaked. Once the key is revealed, no information remains hidden. So the key must be kept secret.

Public Key 

It is a large numeric value used to encrypt data, sometimes, the key is obtained through software processes, but usually, it is provided by the authority and is accessible by all people or the whole public.

Private Key

It is also called a secret key. It is a changeable value that is used to encrypt and decrypt data. Unlike public keys, they are not shared with all people. Instead only shared with the authorized person who is going to decrypt data.

Encryption

The process of converting plain text or information into cypher text, or text that the receiver can only decode, is known as encryption in the field of cryptography. Moreover, It assists in securing communication networks and stopping illegal permits to critical data such as emails and customer information. Has mainly two types: Symmetric encryption and Asymmetric encryption.

Symmetric Encryption

The sender's and receiver’s messages are encrypted using the same key in symmetric encryption. Here, there is less focus on data or message security. 

Asymmetric Encryption

On the other hand, private and public keys are used in asymmetric encryption. The public key is for data encryption, and the private key is for data decryption.

Block Diagram of Digital Signature

A digital signature consists of four main components:

  1. Message: The original message or data that needs to be signed.
  2. Hash Function: Converts the message into a fixed-size hash value.
  3. Private Key: Used by the sender to encrypt the hash value.
  4. Digital Signature: The encrypted hash value, which is attached to the message.
Block Diagram of Digital Signature

Importance of Digital Signature

Digital signatures ensure:

  • Data integrity
  • Authentication
  • Non-repudiation
  • Confidentiality
  • Legal compliance

Role of Digital Signatures

  • Ensures the integrity of electronic documents.
  • Provides authentication of the sender's identity.
  • Prevents tampering with digital documents.
  • Facilitates secure electronic transactions.
  • Enables legal compliance and regulatory requirements.

Digital Signature Algorithm Explanation

To implement the concept of digital signature, we have two primary algorithms, namely:

We will be focussing on DSA. The NIST(National Institute of Standards and Technology) accepted the Digital Signature Algorithm as a standard in 1994. The digital signature algorithm is similar to asymmetric encryption in many ways but departs from it slightly. 

In contrast to asymmetric encryption, the Digital Signature Algorithm generates a digital signature from two 160-bit values using mathematical functions.

Digital Signature Algorithm Explanation

Let us understand the algorithm in brief:

  • Consider a simple text message.
     
  • Apply the hash function to this simple text message then our hash code is generated.
     
  • Hash code, along with the random variable k, is given input to the signature algorithm.
     
  •  For this signature, we use the global public key PUA. Along with this, we will use the private key of the sender PRA.
     
  • Now we get the signature appended to the simple text.
     
  • Along with the simple text, we will get two components named s and r.
     
  • These s and r are known as signature components.
     
  • Now reverse functions are applied.
     
  • The hash function is applied along with the s and r components to a verifying function.
     
  • The verifying function uses the global public key and the sender's public key. 
     
  • The resultant of verifying function is compared with signature component r.

Steps in DSA Algorithm

  1. Key Generation: Generate public and private keys.
  2. Parameter Generation: Select prime numbers and compute parameters.
  3. Signature Generation: Hash message, generate signature.
  4. Signature Verification: Verify signature using public key.

Correctness of the Algorithm

  • DSA relies on the difficulty of solving the discrete logarithm problem.
  • The security of DSA rests on the proper generation of keys and parameters.

How Does DSA Work?

DSA works by generating a pair of keys (public and private), hashing the message, generating a signature using the private key, and verifying the signature using the public key.

How Does the Algorithm Authenticate Sender?

  • Sender generates a signature using their private key.
  • Receiver verifies the signature using the sender's public key.

Advantages of DSA

  • Offers digital signature capabilities.
  • Provides non-repudiation.
  • Offers key generation and authentication.

Disadvantages of DSA

  • Requires secure key management.
  • Can be slower compared to RSA.
  • Limited to digital signature applications.

Example of a DSA Signing by Alice

  • Alice hashes the message.
  • Alice generates a signature using her private key.

Example of DSA Verification by Bob

  • Bob receives the message and signature.
  • Bob hashes the message and verifies the signature using Alice's public key.

Difference Between RSA Algorithm and DSA

CriteriaRSADSA
Key TypeUses both public and private keys.Uses separate keys for signing and verification.
UsageEncryption and digital signatures.Primarily for digital signatures.
Key SizeGenerally larger key sizes are used.Smaller key sizes compared to RSA.
PerformanceEncryption/decryption can be slower.Generally faster for signing operations.
SecurityVulnerable to attacks if keys are not properly managed.Security relies on discrete logarithm problem.

Authenticate the Data Source With DSA

  • Data source hashes the message.
  • Data source generates a signature using its private key.
  • Recipient verifies the signature using the data source's public key.

Global Public key Components

In Digital Signature Algorithm, global public key components are used on both the receiver and sender sides.

Follow the steps one after the other:

  • P: prime number: (2n-1 < P < 2n)
    n: length of bits multiple of 64.
     
  • Q: prime divisor of P-1.
    {Eg: P =13 , Q : P-1, ie: 12, so prime divisor of 12 will be 3}.
     
  • G: h(P-1)/Q mod P
     
  • h: any integer {1 < h < P-1}.  
     

IMPORTANT:  h is not a hash function. It is an integer between 1 to P-1.

There are all called global public key components. Now we have to fetch the user's private key.

  • Let us assume it is x.
    x: Random number 0 < x < Q.
     
  • Now fetch the user public key.
     
  • Let's assume it is y, y: Gx mod P.       
     
  • G is the global public key.
     
  • P is the prime number.
     
  • K is an integer(a secret number) {0 < K < Q}


We have talked about the signature components, i.e. r and s. Now here we are, going to see how r and s are calculated.

Signature Functions

Let us see how ‘r’ and ‘s’ are calculated.

r: (GK mod P)mod Q

s: [K-1(H(M)+x.r)]mod Q
 

  • G: global public key
     
  • P: Prime number
     
  • Q: prime divisor of P-1
     
  • K: the secret number
     
  • H(M): applied hash function on M(initial sender’s message)
     
  • x: user private key
     
  • r: signature component


They both collectively are called signature functions. This signature function is used on the sender's side.

Verifying Functions

At the receiver side, V is calculated using verifying functions. Here we are going to calculate the V value:

V= [(Gu1 yu2)mod P] mod Q

where,

  • u1= [H(M’)w]mod Q
     
  • w= (s')-1mod Q
     
  • u2= (r')w mod Q
     
  • H(M'): hash function applied to the message received at the receiver side.
     
  •  r', s' are the signature components received at the receiver side.
     
  • M' is the message received at the receiver side.
     
  • r', s' are the signature components received at the receiver side.
     
  • r,s are signature components generated at the sender side.


To verify the overall result at the end, we compare r' and V values (r’==V)

Also Read - Kadanes Algorithm

Frequently Asked Questions

What is the algorithm for a digital signature?

A person who electronically signs a document uses their private key, which they keep safe at all times, to create the signature. The mathematical approach creates data that matches the signed document, known as a hash, and encrypts that data, acting as a cipher.

Why is the DSA algorithm used?

Digital Signature Algorithm is what DSA stands for. It serves as a means of verifying digital signatures. It is based on the discrete logarithm and modular exponentiation mathematical concepts. In 1991, the National Institute of Standards and Technology (NIST) developed it.

Describe DSA and RSA.

A specific kind of cryptosystem algorithm is RSA. A particular kind of digital signature algorithm is DSA. Use. Data information can be protected using the RSA algorithm. The digital signatures and their verification can be done using the DSA algorithm.

Is RSA an algorithm for digital signatures?

The most general asymmetric cryptographic algorithm is called RSA. Although it is generally used for message encryption, it may also be used to perform digital signatures over a message.

Conclusion

In this blog, we have gone through the Digital signature algorithm and also got familiar with Symmetric and Asymmetric encryption. We can say at the sender side, signature algorithms functions are used. And at the receiver side, verification algorithm functions are used. Also, r is the major signature component along with s.

We use the private key on the sender side and the public key on the receiver side. Apart from this, we have used public global key components. They are called global components because they are used on both the sender and receiver sides. Hash functions are used at both sender and receiver sides.

To learn more about DSA(Digital Signature Algorithm), refer to the following:

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Previous article
The Schnorr Signature Scheme
Next article
The Elliptic Curve DSA
Live masterclass