Digital Signature Algorithm (DSA) — generation and verification using Python

In the digital age, ensuring the authenticity and integrity of digital messages is crucial. One of the most widely used techniques for achieving this is the Digital Signature Algorithm (DSA). In this article, we will understand DSA algorithm and implement DSA generation and verification process using Python.

What is a Digital Signature?

A digital signature is a mathematical scheme that uses cryptography to validate the authenticity and integrity of a digital message. It’s like a physical signature, but instead of using a pen and paper, it uses complex algorithms and keys to ensure that the message has not been tampered with or altered during transmission.

History of the Digital Signature Algorithm

The concept of digital signatures dates back to the 1970s, when cryptographers like Whitfield Diffie and Martin Hellman proposed the idea of using public-key cryptography for digital signatures. However, it wasn’t until the 1990s that the Digital Signature Algorithm (DSA).

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 break using brute-force system.

How the Digital Signature Algorithm Works

The DSA is based on the principles of public-key cryptography, which uses a pair of keys: a private key and a public key. In DSA, the private key is used to create the digital signature, while the public key is used to verify it.

DSA Process

Here’s a step-by-step explanation of the DSA Process:

1. Key Generation

The first step is to generate a pair of keys: a private key and a public key. The private key is used to create the digital signature, while the public key is used to verify it.

2. Hash Function

The next step is to hash the digital message using a cryptographic hash function, such as SHA-256. This creates a fixed-length digest of the message.

3. Signature Generation

The private key is used to sign the hash digest, creating a digital signature. This is done using a complex algorithm that involves modular exponentiation and multiplication.

4. Signature Verification

The recipient uses the public key to verify the digital signature. This involves decrypting the signature using the public key and comparing it with the original hash digest. If the two match, the signature is valid, and the message has not been tampered with.

Security of the Digital Signature Algorithm

The security of the DSA relies on the difficulty of computing discrete logarithms in a finite field. This means that it’s computationally infeasible to compute the private key from the public key, or to forge a digital signature without knowing the private key.

Major benefits of DSA Algorithm

• Message Authentication: Origin of the sender can be verified using the right key combination.
• Integrity Verification: The message cannot be tampered since it will prevent the bundle from being decrypted altogether.
• Non-repudiation: The sender cannot claim they never sent the message if the message is verified by the signature.

Python implementation

We will create two python files one for DSA generation/signing and another one for verification. We are using PyCryptodome to implement DSA, more information can be found here. Please install the library using following command in the the command line as follows:

C:\DSA>pip install pycryptodome

DSA_Generation_Signing.py — (detailed comments are provided)

# Filename: DSA_Generation_Signing.py

# use following command to install PyCryptodome if not present
# pip install PyCryptodome

from Crypto.PublicKey import DSA
from Crypto.Hash import SHA256
from Crypto.Signature import DSS


# this function will create a private and publice key -> save both keys in separate files and retuen the generated file names
def generate_DSA_Keypair(key_filename, passphrase):
    key = DSA.generate(2048) # private_key
    public_key = key.publickey() # public_key
    
    public_key_filename = key_filename + "_public_key_dsa.pem"
    private_key_filename = key_filename + "_private_key_dsa.pem"
    
    # save/export the public key
    with open(public_key_filename, "wb") as file:
        # PEM is default value as well, refer: https://pycryptodome.readthedocs.io/en/latest/src/public_key/dsa.html
        file.write(public_key.exportKey('PEM'))
        file.close()

    # save/export the private key
    with open(private_key_filename, "wb") as file:
        file.write(key.exportKey('PEM', True, passphrase))
        file.close()
    
    # return the generated public and private key file names
    return public_key_filename, private_key_filename



# this function will encode the message -> create the digital signature using sender private key -> sign the encoded message using the generated signature
def create_signature(message, private_key_filename, signature_filename_prefix, passphrase):
    # read/import the private key 
    with open(private_key_filename, "rb") as private_key_file:
        private_key = DSA.importKey(private_key_file.read(), passphrase)

    # encode message using SHA256
    message_hash = SHA256.new(message.encode())

    # create digital signer using private key
    signer = DSS.new(private_key, 'fips-186-3')
    # sign the message and generate a digital signature
    DSA_signature = signer.sign(message_hash)

    signature_key_filename = signature_filename_prefix + "_signature_dsa.dsa"

    # save/export the generated Digital Signature
    with open(signature_key_filename, "wb") as file:
        file.write(DSA_signature)
        file.close()
    
    # return the generated Digital Signature file name
    return signature_key_filename



# prefix helps in identifying the keys
DSA_key_filename_prefix = "kbp" 

# generate the public and private keys, we have also used a passphrase for extra protection
public_key_filename, private_key_filename = generate_DSA_Keypair(DSA_key_filename_prefix, 'MyPassphrase')
print("Public key filename: ", public_key_filename)
print("Private key filename: ", private_key_filename)

# This is the message which needs to be signed using a Digital Signature - and then verified in next step
text = "Secret Message"

# Create the Digital Signature, same passphrase needs to be provided which was used for key pair generation
signature_key_filename = create_signature(text, private_key_filename, DSA_key_filename_prefix, 'MyPassphrase')
print("Digital Signature filename: ",signature_key_filename)

# The message is sent to the receiver alongwith the Digital Signature file and sender's Public Key
# Private key of the sender is never shared 

Output — DSA_Generation_Signing.py

Following files will be generated in the same folder where code is located.

Generated files — DSA_Generation_Signing.py

DSA_Verification.py— (detailed comments are provided)

# Filename: DSA_Verification.py

from Crypto.PublicKey import DSA
from Crypto.Hash import SHA256
from Crypto.Signature import DSS

# this function will verify the message using Digital Signature file and Public Key of the sender
def verify_signature(public_key_filename, message, signature_key_filename):
    # read/import the public key of the sender
    with open(public_key_filename, "rb") as public_key_file:
        public_key = DSA.importKey(public_key_file.read())
        
    # read/import the Digital Signature File    
    with open(signature_key_filename, "rb") as signature_key_file:
        DSA_signature = signature_key_file.read()

    # encode the plain message
    message_hash = SHA256.new(message.encode())

    # create a DSA verifier
    verifier = DSS.new(public_key, 'fips-186-3')

    try:
        # verify the messsage using the Digital Signature and verifier created using sender's public key
        verifier.verify(message_hash, DSA_signature)
        print("Verification is successful")
    except ValueError:
        print("Verification failed")


# Sender sends three infomation points to the receiver
    # 1. public key of sender
    # 2. Digital Signature for the sent message
    # 3. the message itself
public_key_filename = "kbp_public_key_dsa.pem"
signature_key_filename = "kbp_signature_dsa.dsa"
text = "Secret Message"

# Verify if the digital signature is valid i.e. was signed using sender's private key
verify_signature(public_key_filename, text, signature_key_filename)

Output — DSA_Verification.py

Note: Refer the comments in above python files to understand the code/process.

To summarize:

1. Public/Private key pair is generated for sender
2. Message is encoded and Private key of sender is used to generate the Digital signature
3. Message, Digital Signature and Sender’s Public key is sent to the receiver
4. Receiver uses Digital Signature and Sender’s Public key to verify that the message was signed using sender’s Private Key

Congratulations, you have successfully implemented DSA using Python!