Digital Signatures

Roadmap

Why Digital Signatures?

A digital signature binds a message to a signer's identity with three guarantees:

Anatomy: Hash-then-Sign

All modern signature schemes follow the hash-then-sign paradigm:

The DSA Family Tree

ECDSA: Key Generation

Given agreed-upon domain parameters (CURVE, G, n):

ECDSA: Signing Algorithm

To sign message m with private key d:

ECDSA: Verification Algorithm

Given message m, signature (r, s), and public key Q:

Deterministic ECDSA — RFC 6979

Eliminates the random nonce k entirely, making signatures reproducible and safe from RNG failures.

Schnorr Signatures

Proposed by Claus-Peter Schnorr in 1989. Simpler, provably secure under the Random Oracle Model, and crucially — linear.

EdDSA — Ed25519 & Ed448

A Schnorr variant on twisted Edwards curves, designed by Bernstein et al. (2011). Deterministic nonce, constant-time, misuse-resistant.

Scheme Comparison

Multi-Signatures & Threshold Signing

Schnorr's linearity enables n-of-n and t-of-n signing protocols that produce a single standard signature.

Standards Landscape

Where Signatures Live

Hardware: ECDSA/EdDSA Accelerators

Digital signature operations are bottlenecks in TLS handshakes, blockchain validation, and IoT authentication. Hardware acceleration is essential.

Side-Channel Attacks & Countermeasures

Signature implementations leak secrets through timing, power, and electromagnetic emanations.

Post-Quantum: ML-DSA & SLH-DSA

Shor's algorithm breaks ECDSA/EdDSA/Schnorr on a cryptographically relevant quantum computer. NIST has standardized replacements.

Interactive: ECDSA Signing Simulator

Simplified ECDSA over a tiny curve for educational purposes. Uses a toy prime field.

Toy curve: y² = x³ + 2x + 3 mod 97, Generator G = (3, 6), order n = 5 (very small for demonstration). Real ECDSA uses 256-bit primes.

Python: Ed25519 Signing

import hashlib, os

# --- Ed25519 via Python's standard library (3.6+) ---
from cryptography.hazmat.primitives.asymmetric.ed25519 import (
    Ed25519PrivateKey, Ed25519PublicKey
)
from cryptography.hazmat.primitives import serialization

# Key generation
private_key = Ed25519PrivateKey.generate()
public_key  = private_key.public_key()

# Sign
message   = b"Digital signatures are provably secure"
signature = private_key.sign(message)  # 64 bytes, deterministic

print(f"Public key : {public_key.public_bytes_raw().hex()}")
print(f"Signature  : {signature.hex()}")
print(f"Sig length : {len(signature)} bytes")

# Verify
try:
    public_key.verify(signature, message)
    print("✓ Signature valid")
except Exception:
    print("✗ Signature INVALID")

# Tamper test
try:
    public_key.verify(signature, b"Tampered message!")
    print("✓ Signature valid")       # Should NOT reach here
except Exception:
    print("✗ Tampered message detected — signature invalid")
  

Python: ECDSA (P-256) Low-Level

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.backends import default_backend

# Key generation on NIST P-256
private_key = ec.generate_private_key(ec.SECP256R1(), default_backend())
public_key  = private_key.public_key()

# Extract private scalar d
d = private_key.private_numbers().private_value
print(f"Private key d: {d:#066x}")

# Sign (uses RFC 6979 deterministic nonce internally)
message   = b"ECDSA on NIST P-256"
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

print(f"Signature (DER): {signature.hex()}")
print(f"DER length: {len(signature)} bytes")  # 70-72 bytes

# Decode (r, s) from DER
from cryptography.hazmat.primitives.asymmetric.utils import decode_dss_signature
r, s = decode_dss_signature(signature)
print(f"r = {r:#066x}")
print(f"s = {s:#066x}")

# Verify
public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
print("✓ ECDSA signature verified")
  

SystemVerilog: Modular Inverse

The modular inverse k⁻¹ mod n is the most expensive non-EC operation in ECDSA signing. Fermat's little theorem: k⁻¹ = kⁿ⁻² mod n.

module mod_inverse #(
    parameter int WIDTH = 256
)(
    input  logic                clk,
    input  logic                rst_n,
    input  logic                start,
    input  logic [WIDTH-1:0]    k,        // value to invert
    input  logic [WIDTH-1:0]    n,        // modulus (curve order)
    output logic [WIDTH-1:0]    k_inv,    // k^{-1} mod n
    output logic                done
);
    // Fermat's little theorem: k^{-1} = k^{n-2} mod n
    // Uses Montgomery modular exponentiation (square-and-multiply)

    logic [WIDTH-1:0] exp;       // exponent = n - 2
    logic [WIDTH-1:0] base_reg;  // current base (squared each cycle)
    logic [WIDTH-1:0] result;    // accumulator
    logic [$clog2(WIDTH)-1:0] bit_idx;
    logic running;

    assign exp = n - 2;

    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n) begin
            done    <= 1'b0;
            running <= 1'b0;
        end else if (start) begin
            base_reg <= k;
            result   <= {{(WIDTH-1){1'b0}}, 1'b1};  // 1
            bit_idx  <= '0;
            running  <= 1'b1;
            done     <= 1'b0;
        end else if (running) begin
            // Square-and-multiply: check bit_idx of exponent
            if (exp[bit_idx])
                result <= mont_mul(result, base_reg, n);
            base_reg <= mont_mul(base_reg, base_reg, n);
            if (bit_idx == WIDTH - 1) begin
                running <= 1'b0;
                done    <= 1'b1;
            end
            bit_idx <= bit_idx + 1;
        end
    end

    assign k_inv = result;

    // Montgomery multiplication (simplified — see Presentation 01)
    function automatic logic [WIDTH-1:0] mont_mul(
        input logic [WIDTH-1:0] a, b, m
    );
        // ... full Montgomery reduction pipeline ...
        return (a * b) % m;  // placeholder for synthesis
    endfunction
endmodule
  

SystemVerilog: ECDSA Sign Top-Level

module ecdsa_sign_top #(
    parameter int N = 256  // Curve order bit-width
)(
    input  logic             clk, rst_n, start,
    input  logic [N-1:0]     msg_hash,    // e = H(m), pre-computed
    input  logic [N-1:0]     priv_key,    // d
    input  logic [N-1:0]     nonce_k,     // k (from TRNG or RFC 6979)
    // Curve parameters loaded via config registers (omitted)
    output logic [N-1:0]     sig_r,
    output logic [N-1:0]     sig_s,
    output logic             valid
);
    typedef enum logic [2:0] {
        IDLE, SCALAR_MUL, CALC_R, MOD_INV, CALC_S, DONE
    } state_t;

    state_t state;
    logic [N-1:0] kG_x;       // x-coord of k·G
    logic [N-1:0] k_inv;      // k^{-1} mod n
    logic ec_done, inv_done;

    // Sub-modules (instantiation ports abbreviated)
    ec_point_mul   #(.N(N)) u_pmul  (.*);  // k·G → (kG_x, kG_y)
    mod_inverse    #(.WIDTH(N)) u_inv(.*);  // k^{-1} mod n

    always_ff @(posedge clk or negedge rst_n) begin
        if (!rst_n) state <= IDLE;
        else case (state)
            IDLE:       if (start) state <= SCALAR_MUL;
            SCALAR_MUL: if (ec_done)  state <= CALC_R;
            CALC_R: begin
                sig_r <= kG_x % curve_n;  // r = x₁ mod n
                state <= (sig_r == 0) ? IDLE : MOD_INV;
            end
            MOD_INV:    if (inv_done) state <= CALC_S;
            CALC_S: begin
                // s = k⁻¹ · (e + r·d) mod n
                sig_s <= mont_mul(k_inv,
                    mont_add(msg_hash, mont_mul(sig_r, priv_key)));
                state <= (sig_s == 0) ? IDLE : DONE;
            end
            DONE: begin valid <= 1'b1; state <= IDLE; end
        endcase
    end
endmodule
  

Performance Comparison

Notable Attacks & Failures

Key Takeaways

References