The Covid-19  pandemic has given a new life to the work-from-home initiative, taking the corporate world into an untapped phase. Without a doubt, most of the users reading this have had to digitally sign some official documents over the past couple of years because of the lack of face-to-face interaction and standard distance constraints. To maintain the authenticity and integrity of such documents holding critical information, the DSA Algorithm was proposed and passed as a global standard for verifying digital signatures.

Before moving forward with the algorithm, you will get a refresher on asymmetric encryption, since it verifies digital signatures according to asymmetric cryptography architecture, also known as public-key cryptography architecture.

PGP in Cyber Security With Modules From MIT SCC

Your Cyber Security Career Success Starts Here!View Course
PGP  in Cyber Security With Modules From MIT SCC

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.

process.

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.

alice.

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. 

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?

ds_process-DSA_Algorithm.

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.

Cybersecurity Bootcamp

Certificate and Masterclasses From UCI DCEExplore Now
Cybersecurity Bootcamp

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.

dsa-DSA_Algorithm

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.

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.

    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. 

    Advanced Executive Program in Cybersecurity

    In Partnership with IIIT Bangalore and NPCIEnroll Now
    Advanced Executive Program in Cybersecurity

    Advantages of DSA

    advantages.

    • 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.

    This sums up our lesson on the DSA Algorithm.

    Equip yourself with the latest skills and expertise in the fastest growing field of cybersecurity. Enroll today in the Best PGP in Cyber Security and stay abreast with the latest trends.

    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 CEH (v10) - Certified Ethical Hacking Course or the Cyber-Security Expert Master’s Program.

    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.

    About the Author

    Baivab Kumar JenaBaivab Kumar Jena

    Baivab Kumar Jena is a computer science engineering graduate, he is well versed in multiple coding languages such as C/C++, Java, and Python.

    View More
    • Disclaimer
    • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.
    • *According to Simplilearn survey conducted and subject to terms & conditions with Ernst & Young LLP (EY) as Process Advisors