Operating SystemsSecurity Fundamentals

Cryptography Basics

LevelIntermediate

Duration90 mins

TopicSecurity Fundamentals

4 / 5

Digital Signatures

The Mathematical Equivalent of Ink on Paper

When you sign a paper document, your signature provides three guarantees: authenticity (the document came from you), integrity (the document hasn't been altered since signing), and non-repudiation (you cannot later deny having signed it). For centuries, legal systems have relied on handwritten signatures despite their weaknesses—they can be forged, documents can be modified after signing, and disputes about authenticity require expensive expert analysis.

Digital signatures provide these same guarantees—but with mathematical certainty rather than ink patterns. A valid digital signature proves:

The message came from the claimed sender (only the private key holder can create the signature)
The message hasn't been modified (any change invalidates the signature)
The sender cannot deny sending it (creating the signature requires the private key only they possess)

Digital signatures are the cryptographic foundation of software security. Every time your operating system verifies a driver, validates a software update, or establishes a secure connection, digital signatures are at work, providing mathematical proof of authenticity.

What You Will Learn

By the end of this page, you will understand how digital signatures work mathematically, distinguish between major signature algorithms (RSA, DSA, ECDSA, Ed25519), comprehend the critical role of hash functions in signature schemes, recognize the difference between signatures and MACs, and see how operating systems use digital signatures for code signing, secure boot, and certificate chains.

How Digital Signatures Work

Digital signatures invert the encryption paradigm. In encryption, the public key encrypts and the private key decrypts. In signatures, the private key signs and the public key verifies.

The Signature Process:

Signing: The signer uses their private key to create a signature over the message
Verifying: Anyone with the signer's public key can verify the signature is valid

Why This Works:

Only the private key holder can create a valid signature (authenticity). Any modification to the message invalidates the signature (integrity). Since only the private key holder could have created the signature, they cannot deny it (non-repudiation).

The Role of Hash Functions:

Digital signature algorithms operate on fixed-size inputs, but messages can be arbitrarily large. We solve this by signing the hash of the message rather than the message itself:

Signature = Sign(PrivateKey, Hash(Message))
Valid = Verify(PublicKey, Message, Signature)

This is efficient (signing a 256-bit hash is fast) and secure (the hash is a unique fingerprint of the message). Changing even one bit of the message completely changes the hash, invalidating the signature.

signature_process.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Digital Signature Process
 
// === SIGNING (Sender with private key) ===
function SIGN_MESSAGE(message, private_key):
    // Step 1: Hash the message (creates fixed-size fingerprint)
    message_hash = SHA256(message)
    
    // Step 2: Create signature using private key
    // (details depend on algorithm: RSA-PSS, ECDSA, Ed25519)
    signature = SIGNATURE_ALGORITHM(private_key, message_hash)
    
    // Step 3: Return message with signature
    // The message itself is NOT encrypted - just authenticated
    return (message, signature)
 
// === VERIFICATION (Anyone with public key) ===
function VERIFY_SIGNATURE(message, signature, public_key):
    // Step 1: Hash the received message
    computed_hash = SHA256(message)
    
    // Step 2: Verify signature against hash
    is_valid = VERIFY_ALGORITHM(public_key, computed_hash, signature)
    
    if is_valid:
        return "Signature valid: message is authentic and unmodified"
    else:
        return "Signature INVALID: message may be tampered or forged"
 
// === CRITICAL PROPERTY ===
// Signing DOES NOT encrypt the message!
// Message content is visible to anyone
// Signature only proves authenticity and integrity
// For confidentiality, encrypt separately (or use authenticated encryption)

Signatures ≠ Encryption

A common misconception: digital signatures do NOT provide confidentiality. The message remains readable by anyone. Signatures only prove WHO sent the message and that it hasn't been MODIFIED. For confidential, authenticated messages, you need both encryption (for confidentiality) and signatures (for authenticity) or an authenticated encryption scheme.

Signatures vs. Message Authentication Codes

Both digital signatures and MACs (Message Authentication Codes) provide authentication and integrity verification. The crucial difference lies in who can verify and non-repudiation.

MACs (HMAC, Poly1305):

Use a shared secret key
Only parties who know the key can create OR verify
No non-repudiation: any key holder could have created the MAC
Fast: symmetric cryptography
Use case: authenticating messages between parties with a shared secret (TLS data transfer)

Digital Signatures (RSA, ECDSA, Ed25519):

Use key pairs: private key signs, public key verifies
Anyone can verify with the public key
Non-repudiation: only private key holder could have signed
Slower: asymmetric cryptography
Use case: code signing, certificates, email signatures, legal documents

MACs vs. Digital Signatures
Property	MAC (HMAC)	Digital Signature
Key type	Shared secret	Key pair (public/private)
Who can create	Anyone with the key	Only private key holder
Who can verify	Anyone with the key	Anyone with public key
Non-repudiation	No (any key holder could create)	Yes (only signer has private key)
Performance	Fast (symmetric)	Slow (asymmetric)
Key distribution	Requires secure channel	Public key can be broadcast
Typical use	Session authentication	Code signing, certificates

When to Use Which

Use MACs when both parties share a secret and non-repudiation isn't needed (e.g., TLS record authentication). Use digital signatures when you need to prove WHO created something to parties who don't share a secret (e.g., software updates—users can verify without knowing any secret). In practice, protocols often use both: signatures for handshake authentication, MACs for data transfer.

RSA Signatures

RSA signatures are conceptually simple: signing uses the same mathematics as decryption, and verification uses encryption mathematics. But as with RSA encryption, raw "textbook" RSA signatures are insecure—practical schemes require padding.

Textbook RSA Signature (INSECURE):

Sign: s = m^d mod n (compute signature using private key d)
Verify: m' = s^e mod n, check if m' = m (recover message using public key e)

Why Textbook RSA is Broken:

Multiplicative property: sign(m₁) × sign(m₂) = sign(m₁ × m₂), allowing signature forgery
Deterministic: Same message always produces same signature
No hash: Attacker can compute signature without knowing corresponding message

RSA-PSS (Probabilistic Signature Scheme):

The modern standard (RFC 8017) adds randomness and structure:

Hash the message with SHA-256
Encode the hash with random salt using the PSS padding function
Apply RSA private key operation to padded value

PSS provides provable security under the RSA assumption and is the recommended RSA signature scheme.

rsa_pss_signing.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// RSA-PSS Signature Scheme (Simplified)
 
function RSA_PSS_SIGN(message, private_key):
    (n, d) = private_key
    
    // Step 1: Hash the message
    m_hash = SHA256(message)  // 32 bytes
    
    // Step 2: Generate random salt
    salt = generate_random_bytes(32)  // Same size as hash
    
    // Step 3: Create encoding
    // M' = 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || m_hash || salt
    M_prime = (8 zero bytes) || m_hash || salt
    H = SHA256(M_prime)
    
    // Step 4: Create data block and mask
    DB = padding || 0x01 || salt
    db_mask = MGF1(H, len(DB))  // Mask Generation Function
    masked_DB = DB XOR db_mask
    
    // Step 5: Construct encoded message
    EM = masked_DB || H || 0xbc
    
    // Step 6: RSA operation
    m_int = bytes_to_integer(EM)
    signature = power(m_int, d, n)
    
    return integer_to_bytes(signature)
 
function RSA_PSS_VERIFY(message, signature, public_key):
    (n, e) = public_key
    
    // Step 1: RSA operation to recover encoded message
    s_int = bytes_to_integer(signature)
    EM_int = power(s_int, e, n)
    EM = integer_to_bytes(EM_int)
    
    // Step 2: Verify structure (0xbc trailer, etc.)
    // Step 3: Unmask and extract salt
    // Step 4: Recompute hash and compare
    // (details in RFC 8017)
    
    return is_valid

RSA Signature Sizes

RSA signatures are the same size as the key modulus: RSA-2048 produces 256-byte signatures, RSA-4096 produces 512-byte signatures. This is quite large compared to ECDSA (64 bytes) or Ed25519 (64 bytes), making RSA less efficient for bandwidth-constrained applications. However, verification is fast (small public exponent), making RSA suitable for scenarios with many verifications.

ECDSA and EdDSA: Elliptic Curve Signatures

Elliptic curve signature algorithms provide the same security as RSA with dramatically smaller keys and signatures, making them ideal for resource-constrained environments and modern protocols.

ECDSA (Elliptic Curve Digital Signature Algorithm):

The elliptic curve variant of DSA, standardized in FIPS 186. Used extensively in TLS, Bitcoin, and code signing.

Signing Process:

Hash the message: e = H(m)
Generate random nonce k (CRITICAL: must be truly random and unique)
Compute point: (x₁, y₁) = k × G
Compute r = x₁ mod n (if r = 0, try new k)
Compute s = k⁻¹(e + r × d) mod n (if s = 0, try new k)
Signature is (r, s)

Verification:

Verify r, s are in valid range
Compute e = H(m)
Compute u₁ = e × s⁻¹ mod n, u₂ = r × s⁻¹ mod n
Compute point (x₁, y₁) = u₁ × G + u₂ × Q
Valid if r ≡ x₁ (mod n)

ECDSA Nonce Disaster

ECDSA's random nonce k must be cryptographically random and NEVER reused. If two signatures use the same k, the private key can be computed from the signatures. This destroyed the PlayStation 3 security (Sony reused k, allowing private key recovery) and has compromised countless wallets and systems. Ed25519 eliminates this risk through deterministic nonce generation.

Ed25519 (EdDSA with Curve25519):

Designed by Daniel Bernstein, Ed25519 is the modern signature algorithm of choice. It addresses ECDSA's weakness through deterministic signing:

Key Properties:

Deterministic: Nonce derived from hash of private key + message, eliminating RNG failures
Fast: Optimized for speed on modern processors (50,000+ signatures/second)
Small signatures: 64 bytes regardless of message size
Small keys: 32-byte private key, 32-byte public key
Constant-time: Designed to resist timing attacks
Collision-resilient: Secure even if SHA-512 has collisions

Signature Algorithm Comparison
Algorithm	Key Size	Signature Size	Security Bits	Special Notes
RSA-2048	2048 bits	256 bytes	~112 bits	Large but widely supported
RSA-4096	4096 bits	512 bytes	~140 bits	Very slow signing
ECDSA P-256	256 bits	64 bytes	~128 bits	Requires secure RNG per signature
ECDSA P-384	384 bits	96 bytes	~192 bits	NSA Suite B
Ed25519	256 bits	64 bytes	~128 bits	Recommended: deterministic, fast
Ed448	456 bits	114 bytes	~224 bits	Higher security Ed variant

ed25519_usage.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Ed25519 Signature (High-Level)
 
// Key Generation
function ED25519_KEYGEN():
    // Private key: 32 random bytes
    private_seed = generate_random_bytes(32)
    
    // Derive scalar and public key
    h = SHA512(private_seed)
    scalar = h[0:32] with bit manipulation (clamp)
    public_key = scalar × BasePoint
    
    return (private_seed, public_key)
 
// Signing - DETERMINISTIC (no RNG needed)
function ED25519_SIGN(message, private_seed):
    h = SHA512(private_seed)
    scalar = h[0:32]  // Clamped
    prefix = h[32:64]  // Used for nonce
    
    // Deterministic nonce from prefix + message
    r = SHA512(prefix || message) mod order
    R = r × BasePoint
    
    // Compute signature
    k = SHA512(R || public_key || message) mod order
    s = (r + k × scalar) mod order
    
    return (R, s)  // 64 bytes total
 
// Verification
function ED25519_VERIFY(message, signature, public_key):
    (R, s) = signature
    
    k = SHA512(R || public_key || message) mod order
    
    // Check: s × BasePoint = R + k × PublicKey
    left = s × BasePoint
    right = R + k × PublicKey
    
    return left == right

Choosing a Signature Algorithm

For new systems: Ed25519 is the default recommendation—deterministic, fast, compact, well-analyzed. Use ECDSA P-256 if Ed25519 isn't available (older TLS, hardware tokens). Use RSA-3072+ only for legacy compatibility or where RSA is mandated. Avoid RSA-2048 for new long-term uses.

Digital Certificates and Certificate Chains

Digital signatures prove that a message came from the holder of a particular private key. But how do you know which private key belongs to which entity? This is the key distribution problem solved by digital certificates and Public Key Infrastructure (PKI).

The Problem:

Alice wants to verify Bob's signature. She has Bob's public key, but how does she know it's really Bob's? An attacker could substitute their own public key, impersonating Bob.

The Solution: Certificates

A digital certificate is a statement: "This public key belongs to this entity," signed by a trusted third party (Certificate Authority or CA).

Certificate Structure (X.509):

Subject: Entity the certificate identifies (e.g., "example.com")
Public Key: The subject's public key
Issuer: CA that signed the certificate
Validity: Valid not before/after dates
Signature: CA's signature over all the above

Certificate Chains:

CAs don't sign end-entity certificates directly with their root keys (too risky). Instead:

Root CA (trusted, embedded in OS)
    └── Intermediate CA 1 (signed by Root)
           └── Intermediate CA 2 (signed by Intermediate 1)
                  └── End-Entity Cert (signed by Intermediate 2)

Verification walks up the chain, verifying each signature, until reaching a trusted root.

certificate_verification.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Certificate Chain Verification
 
function VERIFY_CERTIFICATE_CHAIN(cert, trusted_roots):
    chain = []
    current = cert
    
    while True:
        chain.append(current)
        
        // Check if we've reached a trusted root
        if current.issuer in trusted_roots:
            root = trusted_roots[current.issuer]
            // Verify root signed current
            if not VERIFY_SIGNATURE(current, root.public_key):
                return FAILED("Root signature invalid")
            break
        
        // Check if self-signed (untrusted root)
        if current.issuer == current.subject:
            return FAILED("Untrusted self-signed certificate")
        
        // Find issuer certificate
        issuer_cert = FIND_ISSUER(current.issuer)
        if issuer_cert is None:
            return FAILED("Cannot find issuer certificate")
        
        // Verify issuer signed current certificate
        if not VERIFY_SIGNATURE(current, issuer_cert.public_key):
            return FAILED("Chain signature invalid")
        
        // Move up the chain
        current = issuer_cert
    
    // Verify all certificates in chain
    for cert in chain:
        // Check validity period
        if not (cert.not_before <= now() <= cert.not_after):
            return FAILED("Certificate expired or not yet valid")
        
        // Check revocation status (CRL or OCSP)
        if IS_REVOKED(cert):
            return FAILED("Certificate revoked")
        
        // Check key usage, constraints, etc.
        if not VERIFY_EXTENSIONS(cert):
            return FAILED("Extension constraints violated")
    
    return SUCCESS(chain[0].public_key)

Trust Anchor Security

Security of the entire PKI rests on trusted root certificates bundled with your OS. These are the ultimate trust anchors. Compromise of a root CA's private key would allow impersonation of ANY website/entity. This is why roots are kept in HSMs (Hardware Security Modules) in air-gapped facilities with multiple-person access controls. The 2011 DigiNotar breach (root CA compromised) required emergency OS updates to remove the trust anchor.

Digital Signatures in Operating Systems

Digital signatures are fundamental to operating system security, establishing trust in software at every level from boot firmware to application packages.

Key OS Applications

•Secure Boot — UEFI firmware verifies digital signatures on bootloaders before execution. Only code signed by trusted authorities (Microsoft, distro vendors) can boot. Protects against rootkits that modify the boot chain.
•Kernel Module Signing — Linux requires kernel modules to be signed (CONFIG_MODULE_SIG). The kernel verifies signatures before loading modules, preventing malicious drivers from entering ring 0.
•Driver Signing — Windows requires 64-bit drivers to be signed by Microsoft's cross-signing CA. Unsigned drivers cannot load, preventing malware from installing kernel-level code.
•Code Signing (Applications) — macOS Gatekeeper, Windows SmartScreen verify application signatures. Unsigned or revoked-certificate apps trigger warnings or are blocked entirely.
•Package Management — apt, yum, pacman verify package signatures against distribution keys. This prevents mirror compromise from serving malicious packages.
•Software Updates — OS updates are signed by the vendor. Windows Update, macOS Software Update verify signatures before applying updates, preventing man-in-the-middle attacks on update infrastructure.
•TLS Certificate Verification — The kernel (via TLS implementation) or userspace libraries verify server certificates, walking certificate chains to trusted roots shipped with the OS.

code_signing_examples.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Code Signing Examples
 
# === GPG Signing (Linux packages) ===
# Sign a file
gpg --detach-sign --armor package.tar.gz
# Creates package.tar.gz.asc (detached signature)
 
# Verify signature
gpg --verify package.tar.gz.asc package.tar.gz
 
# === Linux Kernel Module Signing ===
# Check if module is signed
modinfo /lib/modules/$(uname -r)/kernel/drivers/net/e1000e/e1000e.ko
# Look for "sig_id" and "signer" fields
 
# View kernel signing configuration
cat /proc/sys/kernel/module_signature_enforce
 
# === macOS Code Signing ===
# Sign an application
codesign -s "Developer ID Application: Your Name" MyApp.app
 
# Verify signature
codesign -v --verbose MyApp.app
 
# Check signing certificate chain
codesign -d --verbose=4 MyApp.app
 
# === Windows Code Signing ===
# Sign with signtool (Windows SDK)
signtool sign /f certificate.pfx /p password /t http://timestamp.url myapp.exe
 
# Verify signature
signtool verify /pa /v myapp.exe
 
# View signature details
Get-AuthenticodeSignature myapp.exe

The Trust Model

Each OS has its own trust model. Windows trusts Microsoft's root CAs and requires their cross-signature for drivers. macOS trusts Apple's roots and notarization service. Linux distributions trust their own signing keys. All share the same principle: signatures verified against pre-trusted public keys establish software authenticity.

Security Considerations and Attack Vectors

Even secure signature algorithms can be compromised through implementation flaws, operational failures, or attacks on the trust infrastructure.

Common Attack Vectors

•Private Key Compromise — If the signing key is stolen, attackers can forge signatures. Protection: HSMs, key rotation, multi-party signing. Impact: All software signed by that key becomes suspect.
•Nonce Reuse (ECDSA) — Reusing the random nonce k in ECDSA reveals the private key. Protection: Use Ed25519 (deterministic) or RFC 6979 (deterministic nonce). Impact: Complete key recovery from two signatures.
•Hash Collision Attacks — If the hash function has collisions, attackers can create two documents with the same hash—get one signed, substitute the other. Protection: Use SHA-256+, not MD5/SHA-1.
•Time-of-check-to-time-of-use (TOCTOU) — File modified after signature verification but before use. Protection: Verify and use atomically, or verify immediately before use.
•Certificate Authority Compromise — If a CA is compromised, attackers can issue fraudulent certificates. Protection: Certificate Transparency logs, key pinning, short-lived certificates. Impact: DigiNotar (2011) required emergency removal from all browsers.
•Revocation Check Bypass — Attackers block access to revocation servers (CRL/OCSP) to use revoked certificates. Protection: OCSP stapling, must-staple extension, short-lived certificates.

Notable Signature-Related Security Incidents
Incident	Year	Cause	Impact
PlayStation 3 Signing Key	2010	ECDSA nonce reuse	Private key recovered, piracy enabled
DigiNotar CA Breach	2011	CA compromise	Fake Google certificates issued, CA bankrupt
Flame Malware	2012	MD5 collision	Fake Microsoft update certificates created
Bitcoin exchange mtgox	2014	Transaction malleability	Signatures modified, theft enabled
Debian Weak Keys	2008	Poor RNG seeding	Predictable keys for 2 years

Best Practices

Use Ed25519 where possible (deterministic, fast, well-analyzed). Store signing keys in HSMs for high-value signatures. Rotate keys and certificates regularly. Monitor Certificate Transparency for unauthorized certificates. Use SHA-256+ for hashing—never MD5 or SHA-1. Implement proper revocation checking with OCSP stapling.

Summary: Digital Signatures

We've explored digital signatures—the cryptographic mechanism that provides authenticity, integrity, and non-repudiation, forming the trust foundation of modern software security.

Key Takeaways

•Digital signatures provide authenticity, integrity, and non-repudiation — Only the private key holder can sign; anyone can verify with the public key.
•Signatures work on hash of message, not message itself — This is efficient and secure; changing any bit invalidates the signature.
•Signatures differ from MACs — MACs use shared secrets (no non-repudiation); signatures use key pairs (verifiable by anyone).
•RSA-PSS, ECDSA, and Ed25519 are standard algorithms — Ed25519 is recommended for new systems (deterministic, fast, compact).
•ECDSA requires perfect randomness for each signature — Nonce reuse reveals private key. Ed25519 eliminates this risk.
•Certificates bind public keys to identities — Certificate chains establish trust through CAs back to root trust anchors in the OS.
•Operating systems use signatures extensively — Secure boot, driver signing, code signing, package management, TLS certificates.

Looking Ahead:

With symmetric encryption, asymmetric encryption, hash functions, and digital signatures, we have the cryptographic primitives. But how do we manage the secrets (keys) that make these primitives work? The next page explores key management—the operational practices for generating, storing, distributing, rotating, and destroying cryptographic keys securely throughout their lifecycle.

Page Complete

You now understand digital signatures—from RSA-PSS to Ed25519, from signature verification to certificate chains. This knowledge is essential for understanding code signing, secure boot, TLS, and the trust infrastructure that verifies software authenticity throughout operating systems.

4 / 5

Loading learning content...

Operating SystemsSecurity Fundamentals

Cryptography Basics

LevelIntermediate

Duration90 mins

TopicSecurity Fundamentals

4 / 5

Digital Signatures

The Mathematical Equivalent of Ink on Paper

Digital signatures provide these same guarantees—but with mathematical certainty rather than ink patterns. A valid digital signature proves:

The message came from the claimed sender (only the private key holder can create the signature)
The message hasn't been modified (any change invalidates the signature)
The sender cannot deny sending it (creating the signature requires the private key only they possess)

What You Will Learn

How Digital Signatures Work

Digital signatures invert the encryption paradigm. In encryption, the public key encrypts and the private key decrypts. In signatures, the private key signs and the public key verifies.

The Signature Process:

Signing: The signer uses their private key to create a signature over the message
Verifying: Anyone with the signer's public key can verify the signature is valid

Why This Works:

The Role of Hash Functions:

Digital signature algorithms operate on fixed-size inputs, but messages can be arbitrarily large. We solve this by signing the hash of the message rather than the message itself:

Signature = Sign(PrivateKey, Hash(Message))
Valid = Verify(PublicKey, Message, Signature)

signature_process.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Digital Signature Process
 
// === SIGNING (Sender with private key) ===
function SIGN_MESSAGE(message, private_key):
    // Step 1: Hash the message (creates fixed-size fingerprint)
    message_hash = SHA256(message)
    
    // Step 2: Create signature using private key
    // (details depend on algorithm: RSA-PSS, ECDSA, Ed25519)
    signature = SIGNATURE_ALGORITHM(private_key, message_hash)
    
    // Step 3: Return message with signature
    // The message itself is NOT encrypted - just authenticated
    return (message, signature)
 
// === VERIFICATION (Anyone with public key) ===
function VERIFY_SIGNATURE(message, signature, public_key):
    // Step 1: Hash the received message
    computed_hash = SHA256(message)
    
    // Step 2: Verify signature against hash
    is_valid = VERIFY_ALGORITHM(public_key, computed_hash, signature)
    
    if is_valid:
        return "Signature valid: message is authentic and unmodified"
    else:
        return "Signature INVALID: message may be tampered or forged"
 
// === CRITICAL PROPERTY ===
// Signing DOES NOT encrypt the message!
// Message content is visible to anyone
// Signature only proves authenticity and integrity
// For confidentiality, encrypt separately (or use authenticated encryption)

Signatures ≠ Encryption

Signatures vs. Message Authentication Codes

Both digital signatures and MACs (Message Authentication Codes) provide authentication and integrity verification. The crucial difference lies in who can verify and non-repudiation.

MACs (HMAC, Poly1305):

Use a shared secret key
Only parties who know the key can create OR verify
No non-repudiation: any key holder could have created the MAC
Fast: symmetric cryptography
Use case: authenticating messages between parties with a shared secret (TLS data transfer)

Digital Signatures (RSA, ECDSA, Ed25519):

Use key pairs: private key signs, public key verifies
Anyone can verify with the public key
Non-repudiation: only private key holder could have signed
Slower: asymmetric cryptography
Use case: code signing, certificates, email signatures, legal documents

MACs vs. Digital Signatures
Property	MAC (HMAC)	Digital Signature
Key type	Shared secret	Key pair (public/private)
Who can create	Anyone with the key	Only private key holder
Who can verify	Anyone with the key	Anyone with public key
Non-repudiation	No (any key holder could create)	Yes (only signer has private key)
Performance	Fast (symmetric)	Slow (asymmetric)
Key distribution	Requires secure channel	Public key can be broadcast
Typical use	Session authentication	Code signing, certificates

When to Use Which

RSA Signatures

Textbook RSA Signature (INSECURE):

Sign: s = m^d mod n (compute signature using private key d)
Verify: m' = s^e mod n, check if m' = m (recover message using public key e)

Why Textbook RSA is Broken:

Multiplicative property: sign(m₁) × sign(m₂) = sign(m₁ × m₂), allowing signature forgery
Deterministic: Same message always produces same signature
No hash: Attacker can compute signature without knowing corresponding message

RSA-PSS (Probabilistic Signature Scheme):

The modern standard (RFC 8017) adds randomness and structure:

Hash the message with SHA-256
Encode the hash with random salt using the PSS padding function
Apply RSA private key operation to padded value

PSS provides provable security under the RSA assumption and is the recommended RSA signature scheme.

rsa_pss_signing.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// RSA-PSS Signature Scheme (Simplified)
 
function RSA_PSS_SIGN(message, private_key):
    (n, d) = private_key
    
    // Step 1: Hash the message
    m_hash = SHA256(message)  // 32 bytes
    
    // Step 2: Generate random salt
    salt = generate_random_bytes(32)  // Same size as hash
    
    // Step 3: Create encoding
    // M' = 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || 0x00 || m_hash || salt
    M_prime = (8 zero bytes) || m_hash || salt
    H = SHA256(M_prime)
    
    // Step 4: Create data block and mask
    DB = padding || 0x01 || salt
    db_mask = MGF1(H, len(DB))  // Mask Generation Function
    masked_DB = DB XOR db_mask
    
    // Step 5: Construct encoded message
    EM = masked_DB || H || 0xbc
    
    // Step 6: RSA operation
    m_int = bytes_to_integer(EM)
    signature = power(m_int, d, n)
    
    return integer_to_bytes(signature)
 
function RSA_PSS_VERIFY(message, signature, public_key):
    (n, e) = public_key
    
    // Step 1: RSA operation to recover encoded message
    s_int = bytes_to_integer(signature)
    EM_int = power(s_int, e, n)
    EM = integer_to_bytes(EM_int)
    
    // Step 2: Verify structure (0xbc trailer, etc.)
    // Step 3: Unmask and extract salt
    // Step 4: Recompute hash and compare
    // (details in RFC 8017)
    
    return is_valid

RSA Signature Sizes

ECDSA and EdDSA: Elliptic Curve Signatures

Elliptic curve signature algorithms provide the same security as RSA with dramatically smaller keys and signatures, making them ideal for resource-constrained environments and modern protocols.

ECDSA (Elliptic Curve Digital Signature Algorithm):

The elliptic curve variant of DSA, standardized in FIPS 186. Used extensively in TLS, Bitcoin, and code signing.

Signing Process:

Hash the message: e = H(m)
Generate random nonce k (CRITICAL: must be truly random and unique)
Compute point: (x₁, y₁) = k × G
Compute r = x₁ mod n (if r = 0, try new k)
Compute s = k⁻¹(e + r × d) mod n (if s = 0, try new k)
Signature is (r, s)

Verification:

Verify r, s are in valid range
Compute e = H(m)
Compute u₁ = e × s⁻¹ mod n, u₂ = r × s⁻¹ mod n
Compute point (x₁, y₁) = u₁ × G + u₂ × Q
Valid if r ≡ x₁ (mod n)

ECDSA Nonce Disaster

Ed25519 (EdDSA with Curve25519):

Designed by Daniel Bernstein, Ed25519 is the modern signature algorithm of choice. It addresses ECDSA's weakness through deterministic signing:

Key Properties:

Deterministic: Nonce derived from hash of private key + message, eliminating RNG failures
Fast: Optimized for speed on modern processors (50,000+ signatures/second)
Small signatures: 64 bytes regardless of message size
Small keys: 32-byte private key, 32-byte public key
Constant-time: Designed to resist timing attacks
Collision-resilient: Secure even if SHA-512 has collisions

Signature Algorithm Comparison
Algorithm	Key Size	Signature Size	Security Bits	Special Notes
RSA-2048	2048 bits	256 bytes	~112 bits	Large but widely supported
RSA-4096	4096 bits	512 bytes	~140 bits	Very slow signing
ECDSA P-256	256 bits	64 bytes	~128 bits	Requires secure RNG per signature
ECDSA P-384	384 bits	96 bytes	~192 bits	NSA Suite B
Ed25519	256 bits	64 bytes	~128 bits	Recommended: deterministic, fast
Ed448	456 bits	114 bytes	~224 bits	Higher security Ed variant

ed25519_usage.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Ed25519 Signature (High-Level)
 
// Key Generation
function ED25519_KEYGEN():
    // Private key: 32 random bytes
    private_seed = generate_random_bytes(32)
    
    // Derive scalar and public key
    h = SHA512(private_seed)
    scalar = h[0:32] with bit manipulation (clamp)
    public_key = scalar × BasePoint
    
    return (private_seed, public_key)
 
// Signing - DETERMINISTIC (no RNG needed)
function ED25519_SIGN(message, private_seed):
    h = SHA512(private_seed)
    scalar = h[0:32]  // Clamped
    prefix = h[32:64]  // Used for nonce
    
    // Deterministic nonce from prefix + message
    r = SHA512(prefix || message) mod order
    R = r × BasePoint
    
    // Compute signature
    k = SHA512(R || public_key || message) mod order
    s = (r + k × scalar) mod order
    
    return (R, s)  // 64 bytes total
 
// Verification
function ED25519_VERIFY(message, signature, public_key):
    (R, s) = signature
    
    k = SHA512(R || public_key || message) mod order
    
    // Check: s × BasePoint = R + k × PublicKey
    left = s × BasePoint
    right = R + k × PublicKey
    
    return left == right

Choosing a Signature Algorithm

Digital Certificates and Certificate Chains

The Problem:

Alice wants to verify Bob's signature. She has Bob's public key, but how does she know it's really Bob's? An attacker could substitute their own public key, impersonating Bob.

The Solution: Certificates

A digital certificate is a statement: "This public key belongs to this entity," signed by a trusted third party (Certificate Authority or CA).

Certificate Structure (X.509):

Subject: Entity the certificate identifies (e.g., "example.com")
Public Key: The subject's public key
Issuer: CA that signed the certificate
Validity: Valid not before/after dates
Signature: CA's signature over all the above

Certificate Chains:

CAs don't sign end-entity certificates directly with their root keys (too risky). Instead:

Root CA (trusted, embedded in OS)
    └── Intermediate CA 1 (signed by Root)
           └── Intermediate CA 2 (signed by Intermediate 1)
                  └── End-Entity Cert (signed by Intermediate 2)

Verification walks up the chain, verifying each signature, until reaching a trusted root.

certificate_verification.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// Certificate Chain Verification
 
function VERIFY_CERTIFICATE_CHAIN(cert, trusted_roots):
    chain = []
    current = cert
    
    while True:
        chain.append(current)
        
        // Check if we've reached a trusted root
        if current.issuer in trusted_roots:
            root = trusted_roots[current.issuer]
            // Verify root signed current
            if not VERIFY_SIGNATURE(current, root.public_key):
                return FAILED("Root signature invalid")
            break
        
        // Check if self-signed (untrusted root)
        if current.issuer == current.subject:
            return FAILED("Untrusted self-signed certificate")
        
        // Find issuer certificate
        issuer_cert = FIND_ISSUER(current.issuer)
        if issuer_cert is None:
            return FAILED("Cannot find issuer certificate")
        
        // Verify issuer signed current certificate
        if not VERIFY_SIGNATURE(current, issuer_cert.public_key):
            return FAILED("Chain signature invalid")
        
        // Move up the chain
        current = issuer_cert
    
    // Verify all certificates in chain
    for cert in chain:
        // Check validity period
        if not (cert.not_before <= now() <= cert.not_after):
            return FAILED("Certificate expired or not yet valid")
        
        // Check revocation status (CRL or OCSP)
        if IS_REVOKED(cert):
            return FAILED("Certificate revoked")
        
        // Check key usage, constraints, etc.
        if not VERIFY_EXTENSIONS(cert):
            return FAILED("Extension constraints violated")
    
    return SUCCESS(chain[0].public_key)

Trust Anchor Security

Digital Signatures in Operating Systems

Digital signatures are fundamental to operating system security, establishing trust in software at every level from boot firmware to application packages.

Key OS Applications

•Secure Boot — UEFI firmware verifies digital signatures on bootloaders before execution. Only code signed by trusted authorities (Microsoft, distro vendors) can boot. Protects against rootkits that modify the boot chain.
•Kernel Module Signing — Linux requires kernel modules to be signed (CONFIG_MODULE_SIG). The kernel verifies signatures before loading modules, preventing malicious drivers from entering ring 0.
•Driver Signing — Windows requires 64-bit drivers to be signed by Microsoft's cross-signing CA. Unsigned drivers cannot load, preventing malware from installing kernel-level code.
•Code Signing (Applications) — macOS Gatekeeper, Windows SmartScreen verify application signatures. Unsigned or revoked-certificate apps trigger warnings or are blocked entirely.
•Package Management — apt, yum, pacman verify package signatures against distribution keys. This prevents mirror compromise from serving malicious packages.
•Software Updates — OS updates are signed by the vendor. Windows Update, macOS Software Update verify signatures before applying updates, preventing man-in-the-middle attacks on update infrastructure.
•TLS Certificate Verification — The kernel (via TLS implementation) or userspace libraries verify server certificates, walking certificate chains to trusted roots shipped with the OS.

code_signing_examples.sh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Code Signing Examples
 
# === GPG Signing (Linux packages) ===
# Sign a file
gpg --detach-sign --armor package.tar.gz
# Creates package.tar.gz.asc (detached signature)
 
# Verify signature
gpg --verify package.tar.gz.asc package.tar.gz
 
# === Linux Kernel Module Signing ===
# Check if module is signed
modinfo /lib/modules/$(uname -r)/kernel/drivers/net/e1000e/e1000e.ko
# Look for "sig_id" and "signer" fields
 
# View kernel signing configuration
cat /proc/sys/kernel/module_signature_enforce
 
# === macOS Code Signing ===
# Sign an application
codesign -s "Developer ID Application: Your Name" MyApp.app
 
# Verify signature
codesign -v --verbose MyApp.app
 
# Check signing certificate chain
codesign -d --verbose=4 MyApp.app
 
# === Windows Code Signing ===
# Sign with signtool (Windows SDK)
signtool sign /f certificate.pfx /p password /t http://timestamp.url myapp.exe
 
# Verify signature
signtool verify /pa /v myapp.exe
 
# View signature details
Get-AuthenticodeSignature myapp.exe

The Trust Model

Security Considerations and Attack Vectors

Even secure signature algorithms can be compromised through implementation flaws, operational failures, or attacks on the trust infrastructure.

Common Attack Vectors

•Private Key Compromise — If the signing key is stolen, attackers can forge signatures. Protection: HSMs, key rotation, multi-party signing. Impact: All software signed by that key becomes suspect.
•Nonce Reuse (ECDSA) — Reusing the random nonce k in ECDSA reveals the private key. Protection: Use Ed25519 (deterministic) or RFC 6979 (deterministic nonce). Impact: Complete key recovery from two signatures.
•Hash Collision Attacks — If the hash function has collisions, attackers can create two documents with the same hash—get one signed, substitute the other. Protection: Use SHA-256+, not MD5/SHA-1.
•Time-of-check-to-time-of-use (TOCTOU) — File modified after signature verification but before use. Protection: Verify and use atomically, or verify immediately before use.
•Certificate Authority Compromise — If a CA is compromised, attackers can issue fraudulent certificates. Protection: Certificate Transparency logs, key pinning, short-lived certificates. Impact: DigiNotar (2011) required emergency removal from all browsers.
•Revocation Check Bypass — Attackers block access to revocation servers (CRL/OCSP) to use revoked certificates. Protection: OCSP stapling, must-staple extension, short-lived certificates.

Notable Signature-Related Security Incidents
Incident	Year	Cause	Impact
PlayStation 3 Signing Key	2010	ECDSA nonce reuse	Private key recovered, piracy enabled
DigiNotar CA Breach	2011	CA compromise	Fake Google certificates issued, CA bankrupt
Flame Malware	2012	MD5 collision	Fake Microsoft update certificates created
Bitcoin exchange mtgox	2014	Transaction malleability	Signatures modified, theft enabled
Debian Weak Keys	2008	Poor RNG seeding	Predictable keys for 2 years

Best Practices

Summary: Digital Signatures

We've explored digital signatures—the cryptographic mechanism that provides authenticity, integrity, and non-repudiation, forming the trust foundation of modern software security.

Key Takeaways

•Digital signatures provide authenticity, integrity, and non-repudiation — Only the private key holder can sign; anyone can verify with the public key.
•Signatures work on hash of message, not message itself — This is efficient and secure; changing any bit invalidates the signature.
•Signatures differ from MACs — MACs use shared secrets (no non-repudiation); signatures use key pairs (verifiable by anyone).
•RSA-PSS, ECDSA, and Ed25519 are standard algorithms — Ed25519 is recommended for new systems (deterministic, fast, compact).
•ECDSA requires perfect randomness for each signature — Nonce reuse reveals private key. Ed25519 eliminates this risk.
•Certificates bind public keys to identities — Certificate chains establish trust through CAs back to root trust anchors in the OS.
•Operating systems use signatures extensively — Secure boot, driver signing, code signing, package management, TLS certificates.

Looking Ahead:

Page Complete

4 / 5