satoshi.ke

peer to peer systems


Digital Signatures

Intro

In the previous article, we introduced asymmetric encryption, and particularly the use of public key encryption for transmitting secrets. In this article, we shall take a look at digital signatures, another application of asymmetric encryption.

In public key encryption, we used the recipient’s public key to encrypt the message in transit so that only the recipient could decrypt it using their private key.

In a digital signature system, the sender encrypts the message with their private key producing a signature. The signature is attached to the message and sent to the recipient. The recipient can then use the sender’s public key to verify the signature.

The goal is not to hide the message from eavesdroppers, but to prove to the to the recipient that the message was not tampered with in transit.

Signing

“Illustration of signing”

The sender will first generate a hash of the message to get a fixed-size representation of it (we discussed hashing in this article).

The hash will then be encrypted using the senders private key producing a signature. This signature will be attached to the original message and sent to the recipient.

Signature Verification

“Illustration of verification”

On receiving the signed message, the recipient will decrypt the signature with sender’s public key to recover the original hash of the message.

Additionally, the sender also independently generates another hash of the received message on their side. If the two hashes match, this confirms to the sender that the message they received is the same as the one sent by the sender.

This confirms to the recipient that the message wasn’t tampered with in transit, because only the sender’s private key could been used to create a signature that can be verified with their public key.

Uses

Some uses of digital signatures:

  • Software developers can sign the software packages and binaries they produce, which users (manually, or through their operating system) can check to not have been tampered with by verifying against the developers’ published public keys.

  • In blockchain systems, transactions sent by an account are sent along with a signature which can be used to verify all valid transactions from the account.

Examples in code

We take a look at signing and verifying in Python and JavaScript.

Python

import base64

from cryptography.hazmat.primitives.asymmetric import rsa, padding, utils
from cryptography.hazmat.primitives import hashes

private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

message = "The quick brown fox jumps over the lazy dog"
hash_algorithm = hashes.SHA256()


def hash_function(msg_bytes):
    hasher = hashes.Hash(hash_algorithm)
    hasher.update(msg_bytes)
    return hasher.finalize()


sender_side_hash = hash_function(bytes(message, "utf-8"))


def sign(message_hash, private_key):
    return private_key.sign(
        message_hash,
        padding.PSS(
            mgf=padding.MGF1(hash_algorithm), salt_length=padding.PSS.MAX_LENGTH
        ),
        utils.Prehashed(hash_algorithm),
    )


signature = sign(sender_side_hash, private_key)

# At this point, the signature is sent to the recipient along with
# the message. The signature can be base64 encoded like below
# so that it can be safely transmitted across the network:
b64_signature = base64.b64encode(signature)

# and decoded like this:
signature = base64.b64decode(b64_signature)

recipient_side_hash = hash_function(bytes(message, "utf-8"))


def verify(public_key, signature, message_hash):
    public_key.verify(
        signature,
        message_hash,
        padding.PSS(
            mgf=padding.MGF1(hash_algorithm), salt_length=padding.PSS.MAX_LENGTH
        ),
        utils.Prehashed(hash_algorithm),
    )


# would raise an exception if verification fails
verify(public_key, signature, recipient_side_hash)

[source file]

In python, we use the third party library cryptography that can be installed via:

pip install cryptography

We start by generating a sender public/private key pair to be used for signing and verifying. On the sender’s side, the hash of the plaintext message is generated then encrypted using the sender’s private key producing the signature.

The signature would then be attached to the message and sent to the recipient. We’ve assumed that part and don’t show it here.

When the receiver gets the signed message, they independently generate a hash of the received message using the same algorithm that was used on the sender’s side. This, along with the signature will be passed to the public key’s verify method. Under the hood, the verify method will decrypt the signature and compare the resultant hash with the one provided to it.

If they match, the signature is considered verified, otherwise the verify method throws an exception.

JavaScript

const { generateKeyPairSync, createSign, createVerify } = await import("node:crypto");

const { publicKey, privateKey } = generateKeyPairSync('rsa', {
    publicExponent: 65537,
    modulusLength: 2048,
});

const message = "The quick brown fox jumps over the lazy dog";

const sign = (messageBytes, privateKey) => {
    const signer = createSign("SHA256");
    signer.update(messageBytes);
    signer.end();
    return signer.sign(privateKey);
};

let signature = sign(Buffer.from(message), privateKey);

// At this point, the signature is sent to the recipient along with
// the message. The signature can be base64 encoded like below
// so that it can be safely transmitted across the network:
let b64Signature = signature.toString("base64");

// and decoded like this:
signature = Buffer.from(b64Signature, "base64");

const verify = (publicKey, signature, messageBytes) => {
    const verifier = createVerify("SHA256");
    verifier.update(messageBytes);
    verifier.end();
    return verifier.verify(publicKey, signature);
};

let isVerified = verify(publicKey, signature, Buffer.from(message));

console.assert(isVerified == true); // should pass

[source file]

In JavaScript, we use utilizes provided by NodeJS’s built-in crypto module.

We generate a sender’s public/private key pair and use the private key to sign the message. The signer object takes care of hashing under the hood using the hashing algorithm argument passed to it.

On the receiver’s side, the sender’s public key is likewise used to verify the signature by the verifier object. The verify method returns a boolean value indicating whether the signature successfully passes verification.

Conclusion

In this article, we discussed the variant of asymmetric encryption used to implement a digital signature system. We described how it works at a high level, mentioned some uses and showed some code examples on Python and JavaScript.

For a more in-depth exploration, checkout the CRYPTO101 course and the Cryptopals challenge.