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³ + 5 mod 97, which has 79 points (a prime, so cofactor 1); generator G = (1, 43), order n = 79. Real ECDSA uses 256-bit primes.

Python: Ed25519 Signing

# Ed25519 via the pyca 'cryptography' package (pip install cryptography;
# not the standard library). public_bytes_raw() needs version 40 or later.
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey

# 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

# Key generation on NIST P-256
private_key = ec.generate_private_key(ec.SECP256R1())
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: OpenSSL draws a random nonce k. For RFC 6979 use
# ec.ECDSA(hashes.SHA256(), deterministic_signing=True)  (v43+)
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")  # usually 70-72

# 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 (1/3)

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
    // Right-to-left square-and-multiply, one exponent bit per cycle

    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;

SystemVerilog: Modular Inverse (2/3)

    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

SystemVerilog: Modular Inverse (3/3)

    assign k_inv = result;

    // Behavioural modular multiply (simulation model). A real core uses a
    // Montgomery multiplier here: see Presentation 01 and deck 05.
    function automatic logic [WIDTH-1:0] mont_mul(
        input logic [WIDTH-1:0] a, b, m
    );
        logic [2*WIDTH-1:0] p;
        p = {{WIDTH{1'b0}}, a} * {{WIDTH{1'b0}}, b};  // full 2W-bit product
        return WIDTH'(p % {{WIDTH{1'b0}}, m});
    endfunction
endmodule
  

SystemVerilog: ECDSA Sign Top-Level (1/2)

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_n, mont_mul, mont_add: config register / modular ALU (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

SystemVerilog: ECDSA Sign Top-Level (2/2)

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

Performance Comparison

Notable Attacks & Failures

Key Takeaways

References