Digital Signature Algorithm (DSA) in Cryptography: How It Works & More

What Is Asymmetric Encryption?

You utilize two distinct keys in asymmetric encryption methods, one for encryption and the other for decryption. You use the public key for encryption; meanwhile, you use the private key for decryption. However, you must generate both keys from the receiver’s end.

Using separate keys for encryption and decryption, as seen in the figure above, has helped eliminate key exchange, as seen in the case of symmetric encryption.

For example, if Alice needs to send a message to Bob, both the private and public keys must belong to Bob.

The process for the above image is as follows:

• Step 1: Alice first uses Bob’s public key to encrypt the message

• Step 2: The encrypted message reaches Bob

• Step 3: Bob decrypts the message with his secret key

This eliminates the requirement for the sender and recipient to exchange any secret keys, minimizing the window of opportunity for exploitation.

Now that you learned how asymmetric encryption happens, you will look at how the digital signature architecture is set up. 

Become a Certified Ethical Hacker!

CEH v12 - Certified Ethical Hacking CourseExplore Program

Why is Cryptography a Smart Solution?

Cryptography involves using codes and ciphers to protect sensitive information from unauthorized access. Cryptography protects data in many applications, including banking, military communications, and secure emails.

Cryptography is a smart solution because it provides an efficient and secure way to protect sensitive data and communications. Cryptography uses advanced mathematical algorithms to encrypt data so only authorized parties can access it, and it also prevents third parties from intercepting communications or manipulating data. 

It enables secure transmission over the internet, protecting data from unauthorized access and potential tampering. Cryptography also allows for data authentication, which can be used to verify the integrity of data and the sender's identity, meaning that data cannot be tampered with or changed without authorization. Finally, cryptography can authenticate users and ensure that only the intended recipient can access the data.

What Are Digital Signatures?

The objective of digital signatures is to authenticate and verify documents and data. This is necessary to avoid tampering and digital modification or forgery during the transmission of official documents.

With one exception, they work on the public key cryptography architecture. Typically, an asymmetric key system encrypts using a public key and decrypts with a private key. For digital signatures, however, the reverse is true. The signature is encrypted using the private key and decrypted with the public key. Because the keys are linked, decoding it with the public key verifies that the proper private key was used to sign the document, thereby verifying the signature's provenance.

Read more: What is Cryptography And How Does It Protect Data?

M - Plaintext

H - Hash function

h - Hash digest 

‘+’ - Bundle both plaintext and digest   

E - Encryption

D - Decryption

The image above shows the entire process, from the signing of the key to its verification. So, go through each step to understand the procedure thoroughly.

• Step 1: M, the original message is first passed to a hash function denoted by H# to create a digest.
• Step 2: Next, it bundles the message together with the hash digest h and encrypts it using the sender’s private key.
• Step 3: It sends the encrypted bundle to the receiver, who can decrypt it using the sender’s public key.
• Step 4: Once it decrypts the message, it is passed through the same hash function (H#), to generate a similar digest.
• Step 5: It compares the newly generated hash with the bundled hash value received along with the message. If they match, it verifies data integrity.

There are two industry-standard ways to implement the above methodology. They are:

1. RSA Algorithm
2. DSA Algorithm

Both the algorithms serve the same purpose, but the encryption and decryption functions differ quite a bit. So, now that you understand how it is supposed to function while verifying the signature, let’s deep dive into our focus for today, the DSA Algorithm.

Block Diagram of Digital Signature

A digital signature is a type of electronic signature based on cryptography and used to authenticate the identity of the sender of a message or the signer of a document and to ensure that the original content of the message or document is unchanged. 

The block diagram of the digital signature process is as follows:

• Message or Document: This is the data or document that needs to be signed.
• Hashing: The document or message is converted into a fixed-length hash using a cryptographic hash function.
• Encryption: The hash is then encrypted using the sender's private key.
• Signature: The encrypted hash is the document's digital signature.
• Verification: The signature is then verified using the sender's public key to ensure the signature's validity and the document's authenticity.

Become a Certified Ethical Hacker!

CEH v12 - Certified Ethical Hacking CourseExplore Program

Explanation of the Block Diagram

The digital signature block diagram outlines the process of creating and verifying digital signatures. 

• The process begins with a message being sent from one party to another. This message is then run through a cryptographic hashing algorithm, which produces a hash of the message. 
• Then, the hash is encrypted using the sender's private key. The encrypted hash is then attached to the original message, forming the digital signature. 
• After that, the recipient verifies the digital signature by decrypting the hash with the sender's public key and then comparing it to a new hash generated from the original message. This decrypting process assures that the message has not been altered in transit and can be trusted as coming from the sender. Once again, the digital signature proves that the data is from a trusted source and has not been changed.

Importance of Digital Signature 

The importance of digital signatures is not negligible in this digital world, and there are some,

1. Ensures Authenticity: Digital signatures ensure the authenticity of a message or transaction by proving that the message or signature was created using the private key associated with the digital signature.
2. Offers Non-repudiation: A digital signature provides an entire record that a specific individual signed the document or transaction at a particular time. This feature prevents the individual from denying that they signed it.
3. Provides Security: Digital signatures use encryption algorithms to protect the data from unauthorized access and tampering. The cryptographic techniques used by digital signatures also protect the data from being changed or manipulated during transmission.
4. Improves Efficiency: Digital signatures can reduce the time and money spent on paperwork, printing, scanning, and mailing documents. 
5. Enhances Compliance: Digital signatures help organizations to meet regulatory and legal compliance requirements by providing an audit trail of signed documents.

Role of Digital Signatures

• Digital signatures are used for authentication or verification. They are used to verify the authenticity and integrity of a digital document or message. 
• The prominent role of a digital signature is to ensure the integrity and authenticity of a digital document or message. A digital signature is essentially a type of electronic signature which provides non-repudiation and authentication between two parties. It serves as proof that the two parties have agreed to specific terms and conditions and have mutually verified the contents of a document or message.
• Digital signatures can also protect confidential information, ensuring that only authorized persons can access the data. 
• Furthermore, digital signatures can also be used to track a digital transaction's source and ensure that it has not been modified.

Encryption With Digital Signature

Encryption is transforming information (referred to as plaintext) using an algorithm (called cipher) to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The process's result is encrypted information. In cryptography, this encrypted information is referred to as ciphertext. 

What Is the DSA Algorithm?

Digital Signatures Algorithm is a FIPS (Federal Information Processing Standard) for digital signatures. It was proposed in 1991 and globally standardized in 1994 by the National Institute of Standards and Technology (NIST). It functions on the framework of modular exponentiation and discrete logarithmic problems, which are difficult to compute as a force-brute system.

DSA Algorithm provides three benefits, which are as follows:

• Message Authentication: You can verify the origin of the sender using the right key combination.
• Integrity Verification: You cannot tamper with the message since it will prevent the bundle from being decrypted altogether.
• Non-repudiation: The sender cannot claim they never sent the message if verifies the signature.

The image above shows the entire procedure of the DSA algorithm. You will use two different functions here, a signing function and a verification function. The difference between the image of a typical digital signature verification process and the one above is the encryption and decryption part. They have distinct parameters, which you will look into in the next section of this lesson on the DSA Algorithm.

Become a Certified Ethical Hacker!

CEH v12 - Certified Ethical Hacking CourseExplore Program

Steps in DSA Algorithm

Keeping the image above in mind, go ahead and see how the entire process works, starting from creating the key pair to verifying the signature at the end.

1. Key Generation

There are two steps in the key generation process: parameter generation and per-user keys. 

Parameter Generation

• Initially a user needs to choose a cryptographic hash function (H) along with output length in bits |H|. Modulus length N is used in when output length |H| is greater. 
• Then choose a key length L where it should be multiple of 64 and lie in between 512 and 1024 as per Original DSS length. However, lengths 2048 or 3072 are recommended by NIST for lifetime key security. 
• The values of L and N need to be chosen in between (1024, 60), (2048, 224), (2048, 256), or (3072, 256) according to FIPS 186-4. Also, a user should chose modulus length N in such a way that modulus length N should be less than key length (N<L) and less than and equal to output length (N<=|H|). 
• Later a user can choose a prime number q of N bit and another prime number as p of L bit in such a way that p-1 is multiple of q. And then choose h as an integer from the list ( 2……..p-2). 
• Once you get p and q values, find out 

g = h^(p-1)/q*mod(p). If you get g = 1, please try another value for h and compute again for g except 1. 

p, q and g are the algorithm parameters that are shared amongst different users of the systems.

Per-user Keys

To compute the key parameters for a single user, first choose an integer x (private key) from the list (1…….q-1), then compute the public key, y=g^(x)*mod(p). 

2. Signature Generation

• It passes the original message (M) through the hash function (H#) to get our hash digest(h).
• It passes the digest as input to a signing function, whose purpose is to give two variables as output, s, and r.
• Apart from the digest, you also use a random integer k such that 0 < k < q.
• To calculate the value of r, you use the formula r = (gk mod p) mod q.
• To calculate the value of s, you use the formula s = [K-1(h+x . R)mod q].
• It then packages the signature as {r,s}.
• The entire bundle of the message and signature {M,r,s} are sent to the receiver.

3. Key Distribution

While distributing keys, a signer should keep the private key (x) secret and publish the public key (y) and send the public key (y) to the receiver without any secret mechanism. 

Signing

Signing of message m should be done as follows: 

• first choose an integer k from (1……q-1) 
• compute 

r = g^(k)*mod(p)*mod(q). If you get r = 0, please try another random value of k and compute again for r except 0. 

• Calculate 

s=(k^(-1)*(H(m)+xr))*mod(q). If you get s = 0, please try another random value of k and compute again for s except 0. 

• The signature is defined by two key elements (r,s). Also, key elements k and r are used to create a new message. Nevertheless, computing r with modular exponential process is a very expensive process and computed before the message is known. Computation is done with the help of the Euclidean algorithm and Fermat's little theorem. 

4. Signature Verification 

• You use the same hash function (H#) to generate the digest h.
• You then pass this digest off to the verification function, which needs other variables as parameters too.
• Compute the value of w such that: s*w mod q = 1
• Calculate the value of u1 from the formula, u1 = h*w mod q
• Calculate the value of u2 from the formula, u2 = r*w mod q
• The final verification component v is calculated as v = [((gu1 . yu2) mod p) mod q].
• It compares the value of v to the value of r received in the bundle.
• If it matches, the signature verification is complete.

Having understood the functionality of the DSA Algorithm, you must know the advantages this algorithm offers over alternative standards like the RSA algorithm.

Become a Certified Ethical Hacker!

CEH v12 - Certified Ethical Hacking CourseExplore Program

Correctness of the Algorithm

The correctness of the algorithm can be computed using following signature schemes. 

s=(k^(-1)*(H(m)+xr))*mod(q)

k=H(m)*s^(-1)+x*r*s^(-1) 

  = H(m)*w+x*r*w*mod(q)

g^k=[g^(H(m)*w)]×[g^(xrw)] 

     =[g^(H(m)*w)]×[y^(rw)]

     =g^(u1)*y^(u2)*mod(p)

Thus, the correctness of algorithm for DSA is 

r=(g^(k)*mod(p))mod(q) =[g^(u1)*y^(u2)*mod(p)]*[mod(q)] 

r =v 

Sensitivity

1. In DSA, the random values of signature key element k are critical that violating it may reveal the entire privacy to the attackers. Sometimes, using the same value for the signature key element and losing a few bits of k might be enough to reveal the private key x to attackers. 
2. An attack can be prevented only if a new random value of k is calculated for every different signature value. Thus, it is necessary to have the different value of k for every different H(m) and unpredictable in order to keep the private key x secret from attackers. 

How Does DSA Work?

DSA stands for Digital Signature Algorithm. It is a cryptographic algorithm used to generate digital signatures, authenticate the sender of a digital message, and prevent message tampering.

DSA works by having two keys: a private key owned by the sender and a public key held by the receiver. 

• The sender uses their private key to generate a signature for the message, which is then sent along with it. 
• Then, the message receiver uses the sender's public key to verify that the signature is valid and that the message has not been tampered with. 
• The verification process is done using unique algorithms that allow the receiver to validate the signature without having access to the sender's private key.

How Does the Algorithm Authenticate Sender?

The algorithm authenticates the sender by verifying the digital signature of the message. 

• The digital signature is created using the sender's private key, which is known only to the sender. 
• Then, the receiver uses the sender's public key to verify the digital signature. 

If the digital signature is valid, the receiver understands the sender sent the message.

Advantages of DSA

• Highly Robust: DSA is highly robust in the security and stability aspect compared to alternative signature verification algorithms.
• Better Speed: The key generation is much faster compared to the RSA algorithm and such.
• Less Storage: DSA requires less storage space to work its entire cycle.
• Patent Free: When NIST released it, it was patent-free to enable its global use free of cost.

Cons of Using Digital Signature Algorithm

DSA is one of the most popular algorithms for creating digital signatures. However, DSA has some potential drawbacks.

1. Limited Key Length: DSA has limited key lengths, which limit its use in specific applications.
2. Rigid Key Management: Key management is rigid and requires specific key lengths.
3. Limited Digital Certificate Support: DSA does not support certificates, which limits its use in specific applications.
4. Incremental signature algorithm: DSA is not an incremental signature algorithm, meaning it cannot be updated or changed once a signature is generated.
5. Relatively new: DSA is a relatively new algorithm and has not been extensively studied or vetted like some of the more established algorithms.
6. Impact on storage and transmission: DSA signatures can be larger than signatures created with other algorithms, which can impact storage and transmission efficiency.

Become a Certified Ethical Hacker!

CEH v12 - Certified Ethical Hacking CourseExplore Program

Example of a DSA Signing by Alice

Alice creates a message, M, that she wants to send to Bob. She also creates a digital signature, S, for the message using her private key. Then she sends the message and digital signature to Bob. Then act follows,

• Alice Generated an M message she would like to send to Bob.
• Then Alice Generates a random number, k, and computer = (g^k mod p) mod q.
• After that, compute, s = (k^-1 * (H(M) + x*r)) mod q, where H is a cryptographic hash function, and x is Alice's private key.
• Alice's digital signature, S, is the pair (r, s).
• Alice sends the message M and her digital signature S to Bob.

Example of DSA Verification by Bob

Bob receives Alice's message, M, and the digital signature S. He then applies the verification algorithm using the public key (p, q, g, y) Alice has shared with him to verify the signature.

Bob uses the public key to verify that Alice's digital signature is valid and corresponds to the message M. He does this by calculating the following values:

Where H(M) is the hash of Alice's message, s is Alice's signature, r is the first part of Alice's signature, g is the generator, y is Alice's public key, p is the modulus, and q is the prime number.

To verify a message, M, that Alice has signed, Bob first computes

r = (g^x mod p) mod q.

Bob then computes:

s = (y^r * r^x mod p) mod q.

If s = M, then the message is verified.

DSA VS RSA (Rivest-Shamir-Adleman) 

DSA and RSA are both cryptographic algorithms used for digital signatures and encryption.

DSA (Digital Signature Algorithm)

• DSA is a signature-only algorithm and requires a private key for signing and a public key for verifying.
• DSA is a faster algorithm and is simpler to implement than RSA.
• DSA is more secure than RSA as it provides message integrity and non-repudiation.

RSA (Rivest-Shamir-Adleman)

• RSA is a signature and encryption algorithm that can be used for both digital signatures and encryption.
• RSA is a slower algorithm and is more challenging to implement than DSA.
• RSA is less secure than DSA, which is vulnerable to chosen-ciphertext attacks and requires more computing power.

Authenticate the Data Source With DSA

To authenticate a data source with DSA; the following steps should be followed:

1. Create a Data Source Name (DSN).
2. Configure the DSN with the data source credentials, including a username, password, and database name.
3. Test the connection to the data source.
4. Enable DSA authentication in the data source configuration.
5. Create a DSA user account with the same name as the user account used in the data source configuration.
6. Assign a password to the DSA user account.
7. Assign the same database name to the DSA user account configured in the data source.
8. Test the connection to the data source using the DSA user credentials.
9. Enable DSA authentication for the data source application.
10. Restart the data source application to enable DSA authentication.

This sums up our lesson on the DSA Algorithm.

How Can Simplilearn Help You?

Hope this article has helped you understand how vital digital signatures are in this digital age and the impact of cryptography in shaping the threat model of our corporate sector. This is, however, a small drop in the vast ocean that is cybersecurity, which is an industry that has a growing demand for trained professionals.

Simplilearn provides a "Cybersecurity Expert" course that will teach you all you need to know to get started in a cybersecurity profession or improve in one. The course is jam-packed with industry-leading learning topics to help you understand all you need to know before moving ahead in this field.

Conclusion

With this, you have understood the importance of asymmetric cryptography, the working of digital signatures, the functionality of DSA, the steps involved in the signature verification, and its advantages over similar counterparts. Hope this tutorial helped you understand the DSA algorithm.

Take your cybersecurity knowledge to the next level by checking out one of our many other exciting and useful offerings, such as the Advanced Executive Program In Cyber Security and Professional Certificate Program in Ethical Hacking and Penetration Testing.

Do you have any questions or queries regarding this article on the DSA algorithm? Please do let us know in the comment section of this tutorial, and we’d be happy to have our experts answer them for you.