Implementing RSA for Digital Signature from Scratch

This article dives deep into RSA algortihm, offering a step-by-step guide to the implementation specifically for digital signatures in Python without relying on external libraries. By constructing RSA from scratch, we can truly appreciate the genius behind its simple yet robust architecture while gaining practical insights into its theoretical background.

Let’s break down the implementation into three parts:

1. Key Generation: Generating the public and private keys needed for RSA.
2. Signing the Message: Creating a digital signature for a given message using the private key.
3. Verifying the Signature: Checking the validity of the signature with the public key to ensure it corresponds to the original message.

Key Generation

Generate two large prime numbers, p and q.

Compute n = p × q

Compute the totient 𝜙(𝑛)=(𝑝−1)×(𝑞−1)

Choose an integer e such that 1<𝑒<𝜙(𝑛) and gcd(𝑒, 𝜙(𝑛))=1 which becomes the public key.

Lastly, we need to calculate the private key d. This is achieved by finding the modular inverse of e mod 𝜙(𝑛). The modular inverse d is a number such that (d × e) % 𝜙(𝑛) = 1. The public key is the pair (e, n), and the private key is the pair (d, n).

# RSA Key Generation
p, q = generate_prime(3, 5000), generate_prime(3, 5000)
while p == q:
    q = generate_prime(3, 47)

n = p * q
totient_n = (p - 1) * (q - 1)

# Find a number "e" that is coprime to the "totient_n"
e = randint(3, totient_n - 1)

while math.gcd(e, totient_n) != 1:
    e = randint(3, totient_n - 1)

d = mod_inverse(e, totient_n)

Signing the Message

To initiate the digital signature process, we start by capturing the message that needs to be signed.

message = input("Enter the message: ")

Before signing the message, we need to divide it into manageable pieces called blocks. The split_into_blocks function does precisely that. It takes the full message and divides it into a series of substrings, each of which is no longer than block_size. This ensures that each block is small enough to be encrypted using our RSA algorithm.

def split_into_blocks(message, block_size):
    return [message[i : i + block_size] for i in range(0, len(message), block_size)]

Once we have our message blocks, we can encrypt each one to generate the signature. The encrypt_block function converts the block from a string into a large integer (by encoding it in UTF-8 and using big-endian byte order). It then uses the RSA encryption formula c = m^d mod n where m is the block converted to an integer, d is the private key exponent, and n is the modulus.

def encrypt_block(block, d, n):
    block_int = int.from_bytes(block.encode("utf-8"), byteorder="big")
    encrypted_block_int = pow(block_int, d, n)
    return encrypted_block_int

The sign brings everything together. It determines the correct block size based on the bit-length of our modulus n. If the entire message fits into one block, it encrypts it directly. Otherwise, it encrypts each block separately. The output is a tuple consisting of the original message blocks and their corresponding encrypted versions, constituting the digital signature.

def sign(message, d, n):
    block_size = ((n.bit_length() - 1) // 8)
    if len(message) <= block_size:
        return [encrypt_block(message, d, n)]
    else:
        blocks = split_into_blocks(message, block_size)
        signed_blocks = [encrypt_block(block, d, n) for block in blocks]
        return blocks, signed_blocks

blocks, signed_blocks = sign(message, d, n)

This step concludes the signing process by producing the digital signature for the message that was entered by the user.

Verifying the Digital Signature

Once a message has been signed and the digital signature has been created, the last step is the verification. This process confirms whether the signed message is valid and ensures that it was indeed created with the signer’s private key.

To begin verification, we take the signed blocks and attempt to decrypt them using the public key:

verification_result = verify(signed_blocks, e, n, message)

This line calls the verify function, which performs the following actions:

1. Decrypting Each Signed Block

The verify function iterates over each encrypted block (the digital signature) and applies the decryption process using the public key.

def verify(signed_blocks, e, n, original_message):
    decrypted_blocks = [
        decrypt_block(signed_block, e, n) for signed_block in signed_blocks
    ]
    decrypted_message = "".join(decrypted_blocks)
    return decrypted_message == original_message

Each block is decrypted by reversing the RSA signing process, using the public exponent e and the modulus n. The result is a series of blocks that should match the original message when concatenated.

2. Decrypting a Single Block

Inside the verification process, each block of the digital signature is decrypted individually by the decrypt_block function:

def decrypt_block(encrypted_block_int, e, n):
    decrypted_block_int = pow(encrypted_block_int, e, n)
    decrypted_block_bytes = decrypted_block_int.to_bytes(
        (decrypted_block_int.bit_length() + 7) // 8, byteorder="big"
    )
    return decrypted_block_bytes.decode("utf-8")

This function converts the encrypted integer back into bytes, then into a string, using the RSA decryption formula m = c^e mod n. The process ensures that if the signature is valid, the output string will be identical to the original message block.

3. Comparing the Decrypted Message with the Original

After decrypting all the signed blocks, the verify function concatenates them into a full message and compares it with the original message that was signed. If they match, the function returns True, confirming the signature is valid.

print(
    f"\nPublic Key:{e}\nPrivate Key:{d}\nn:{n}\nPhi of n:{totient_n}\np:{p}\nq:{q}\n\n"
)

message = input("Enter the message: ")
blocks, signed_blocks = sign(message, d, n)
verification_result = verify(signed_blocks, e, n, message)

blocks_str = "".join(blocks)
signed_blocks_str = " ".join(map(str, signed_blocks))
signed_message = blocks_str + " | " + signed_blocks_str


print("\nSeperated message:", blocks)
print("Signed blocks:", signed_blocks)
print("Signed message:", signed_message)
print("Verification result:", verification_result)

In essence, the verification_result will be True if the decrypted message matches the original message exactly, proving that the signature is indeed authentic. This is the cornerstone of trust in digital communications, ensuring that messages remain untampered and genuine from sender to receiver.

The implementation described above outlines the foundational steps of creating and verifying digital signatures with the RSA algorithm in Python.

Below is an example output of the signing and verification process:

This output demonstrates a successful encryption and subsequent verification of the message, proving the signature’s validity.

To delve deeper and explore the full implementation, including additional utility functions, visit my GitHub repository. The repository provides comprehensive insights and the complete source code that can be used as a starting point for your projects or for further experimentation with RSA digital signatures.

Thank you for reading!