Understanding & Creating RSA Digital Signatures
In this article, I am going to show you what to learn from the first articles to turn it into real world, production safe usage. This article is going to cover one last major concept before we get into the real world usage of RSA: create unforgeable digital signatures.
The Authentication Game
You can think of a digital signature as a cryptographic fingerprint. It is like your own handwritten signature that proves a document came from you – a digital signature proves a message, text, or object came from the holder of a specific private key for this example.
The Mathematical Foundation
The following is the reason why I personally love RSA. The signatures are very elegant in design. Do you remember the encryption formulas? If you look at the two following examples, the mathematics are 100% identical. All we managed to do is swap which key does what. This symmetry is what makes RSA s powerful for encrypting secrets and signatures.
Standard RSA Encryption:
Encrypt: c = m^e mod n (using public key)
Decrypt: m = c^d mod n (using private key)RSA Digital Signatures:
Sign: s = m^d mod n (using private key)
Verify: m = s^e mod n (using public key)Building the Signature System
Since by now, we should have a decent understanding of the mathematics that makes RSA encryption work, I am going to extend the RSA implementation with signature capabilities in the following code block.
import hashlib
from typing import Union, Tuple
class RSADigitalSignature:
def __init__(self, rsa_instance):
self.rsa = rsa_instance
self.n = rsa_instance.n
self.e = rsa_instance.e
self.d = rsa_instance.d
def _hash_message(self, message: Union[str, bytes]) -> int:
if isinstance(message, str):
message = message.encode('utf-8')
hash_digest = hashlib.sha256(message).digest()
hash_int = int.from_bytes(hash_digest, byteorder='big')
if hash_int >= self.n:
raise ValueError(f"Hash too large for key size. Hash: {hash_int}, n: {self.n}")
return hash_int
def sign_message(self, message: Union[str, bytes]) -> int:
print(f"Signing message: {message}")
message_hash = self._hash_message(message)
print(f"Message hash: {message_hash}")
signature = pow(message_hash, self.d, self.n)
print(f"Generated signature: {signature}")
return signature
def verify_signature(self, message: Union[str, bytes], signature: int) -> bool:
try:
print(f"Verifying signature for: {message}")
expected_hash = self._hash_message(message)
decrypted_hash = pow(signature, self.e, self.n)
is_valid = expected_hash == decrypted_hash
print(f"Expected hash: {expected_hash}")
print(f"Decrypted hash: {decrypted_hash}")
print(f"Signature valid: {is_valid}")
return is_valid
except Exception as e:
print(f"Verification failed: {e}")
return FalseYou may be asking why are we hashing before we are signing. Well, hashing is not optional – it is actually critical for the following reasons.
- RSA can only handle numbers smaller than
n. Larger messages will exceed this limit. - Hashing is actually quite fast which is
O(n). RSA operations are usually slow which isO(log³n). - The raw message signing has vulnerabilities. The hash will act as a fixed sized fingerprint for us.
- Industry standard and real-world practices expect to have signatures on the hashes – this is following standards such as the PKCS#1.
Complete Code Example
def demonstrate_rsa_signatures():
print("Generating RSA keys...")
rsa = RSA(key_size=1024)
signature_system = RSADigitalSignature(rsa)
message = "Transfer $1000 from Alice to Bob"
print(f"\nOriginal message: '{message}'")
print("\n" + "="*50)
print("SIGNING PROCESS")
print("="*50)
signature = signature_system.sign_message(message)
print("\n" + "="*50)
print("VERIFICATION PROCESS")
print("="*50)
is_valid = signature_system.verify_signature(message, signature)
print("\n" + "="*50)
print("TAMPERING DETECTION TEST")
print("="*50)
tampered_message = "Transfer $10000 from Alice to Bob"
is_tampered_valid = signature_system.verify_signature(tampered_message, signature)
return signature, is_valid, is_tampered_valid
signature, valid, tampered = demonstrate_rsa_signatures()In case you want to use the code for shorter messages, I will give an implementation for a more sophisticated signature scheme that allows us to do message recovery if we choose to do so.
def sign_with_recovery(self, message: Union[str, bytes]) -> int:
if isinstance(message, str):
message = message.encode('utf-8')
message_int = int.from_bytes(message, byteorder='big')
if message_int >= self.n:
raise ValueError("Message too large for recovery signature")
signature = pow(message_int, self.d, self.n)
return signature
def verify_with_recovery(self, signature: int) -> Union[bytes, None]:
try:
recovered_int = pow(signature, self.e, self.n)
byte_length = (recovered_int.bit_length() + 7) // 8
recovered_message = recovered_int.to_bytes(byte_length, byteorder='big')
return recovered_message
except Exception:
return NoneDon't Forget about the Security
While the implementations and source code which I provided demonstrates the core concepts of how to do message signatures and encryption, for the production environments, we would need additional security layers. This would be using PKCS#1, adding salt and randomization, and key size requirements.
If there is going to be a Part 5, I will most likely cover the real-world usage and application of writing RSA encryption in your Python code.
The Conclusion
The use of digital signatures represent RSA's dual nature – the same mathematical foundation serves secrecy and authentication. For us to understand how to flip the key usage, you now understand how to use one of cryptography's most powerful tools.
Please remember that RSA signatures aren't just about providing an identity, they are for creating unforgeable digital trust on the internet. Every time you download a file, go to buy something on Amazon or eBay, or verify a digital document, RSA signatures are working behind the scenes to keep the trust between two parties.