Unit 5: Digital Signature and Key management

I. Foundations of Digital Signatures and Key Management

Digital signatures and key-management mechanisms provide trust in network communication. A digital signature uses asymmetric cryptography to bind a signer to data, while key management controls the generation, distribution, agreement, storage, replacement, and revocation of cryptographic keys.

• Security objectives:
  • Authentication: Confirms the claimed origin of a message.
  • Integrity: Detects unauthorized modification of signed data.
  • Non-repudiation: Provides evidence that the private-key holder signed the data, subject to secure key custody and valid certificates.
  • Confidentiality: Is not provided by signatures; encryption is required separately.
• Core convention: A private key creates a signature, while the corresponding public key verifies it.
• Hashing convention: Practical schemes sign a fixed-length digest (h=H(M)), not an arbitrarily long message (M).
• Key-management assumption: Security depends on authentic key ownership, strong randomness, protected storage, controlled key lifetimes, and prompt revocation.
• Threat model: Attackers may observe messages, request signatures, replace public keys, replay data, or attempt to recover secret keys.

II. Digital Signature Fundamentals — Properties, Operation, and Threats

A. Comparison of digital signatures

Digital signatures differ from handwritten signatures, message authentication codes, and encryption in their construction and security properties.

• Digital versus handwritten signatures:
  • A handwritten signature is generally constant and attached physically to a document.
  • A digital signature depends on the exact message; changing one bit should cause verification failure.
  • Digital signatures can be checked algorithmically using a public key.
• Digital signature versus MAC:
  1. Digital signature: Uses a private/public key pair; any holder of the authentic public key can verify.
  2. Message authentication code: Uses one shared secret (K), such as (t=\operatorname{HMAC}_K(M)); both parties can generate the tag, so it normally cannot prove which party created it.
• Signature versus encryption:
  1. Signature: The signer applies a private-key operation to support origin authentication and integrity.
  2. Encryption: The sender encrypts for a recipient, commonly using the recipient’s public key, to provide confidentiality.
• Direct and arbitrated signatures:
  • Direct: Signer and verifier operate without a trusted intermediary during each transaction.
  • Arbitrated: A trusted third party validates or records signatures, reducing disputes but creating dependency on the arbiter.
• Operational comparison: RSA signatures rely on integer factorization, ElGamal and Schnorr on discrete logarithms, and ECDSA/EdDSA on elliptic-curve discrete logarithms.

B. Process of digital signatures

The digital-signature process hashes a message, signs the digest with a private key, and verifies the result with the corresponding authenticated public key.

• Key generation: Produce private key (SK) and public key (PK); (SK) remains confidential while (PK) is distributed authentically.
• Signing:

h = H(M)
S = Sign(SK, h)
send (M, S, certificate)

• (M): message.
• (H): collision-resistant hash function.
• (h): message digest.
• (S): signature.
  • Verification:

h = H(M)
valid = Verify(PK, h, S)
accept only if valid and the key is trusted

• Certificate validation: The verifier checks the certificate chain, identity, validity period, intended key usage, and revocation status before trusting (PK).
• Context binding: Protocol identifiers, sender identity, timestamps, or sequence numbers should be included in signed data to prevent reuse in another context.
• Important distinction: Verification proves mathematical consistency with (PK); it proves identity only when (PK) has been reliably bound to its owner.

C. Attacks on digital signatures

Attacks target the mathematical scheme, hash function, nonce generation, private-key implementation, or public-key binding.

• Attack models:
  • Key-only attack: The attacker knows only the public key.
  • Known-message attack: The attacker has valid message-signature pairs.
  • Chosen-message attack: The attacker obtains signatures for selected messages, possibly adaptively.
• Forgery goals:
  • Existential forgery: Produce one new valid message-signature pair.
  • Selective forgery: Forge a signature for a chosen target message.
  • Universal forgery: Sign arbitrary messages without the private key.
  • Key recovery: Recover the private key, enabling complete impersonation.
• Hash attacks: A collision (H(M_1)=H(M_2)) may let a signature intended for (M_1) validate (M_2); collision-resistant hashes such as SHA-256 are therefore required.
• Nonce attacks: Reusing or biasing the secret nonce in DSA, ECDSA, ElGamal, or Schnorr can reveal the private key.
• Implementation attacks: Timing, power analysis, fault injection, and cache leakage can expose secret computations; constant-time code and hardware protection reduce risk.
• Protocol attacks: Replay, certificate substitution, and algorithm downgrade are controlled through freshness data, authenticated certificates, and strict algorithm policies.

III. Digital Signature Schemes — Number-Theoretic Constructions

A. RSA Digital signature scheme

RSA signatures use modular exponentiation, with security based on the difficulty of factoring a large composite modulus.

• Keys: Choose primes (p,q), compute (n=pq), select (e), and calculate (d) such that (ed\equiv1\pmod{\lambda(n)}).
• Signature principle:

S = Encode(H(M))^d mod n
Verify that S^e mod n = Encode(H(M))

• (n): RSA modulus.
• (e): public exponent.
• (d): private exponent.
• (\operatorname{Encode}): secure padding and digest encoding.
  • Required encoding: Textbook RSA is deterministic and algebraically malleable. RSA-PSS adds randomized padding and is the preferred modern RSA signature encoding.
  • Security controls: Use sufficiently large keys, protected private exponentiation, validated padding, and blinding against timing attacks.
  • Limitation: RSA keys and signatures are relatively large compared with elliptic-curve schemes offering comparable security.

B. ElGamal Digital signature scheme

The ElGamal signature scheme operates in a finite cyclic group and depends on the hardness of the discrete logarithm problem.

• Keys: Choose prime (p), generator (g), private key (x), and public key (y=g^x\bmod p).
• Signing: Select fresh random (k) with (\gcd(k,p-1)=1), then compute:

r = g^k mod p
s = k^(-1)(H(M) - xr) mod (p - 1)

• Verification:

g^H(M) ≡ y^r · r^s (mod p)

• (k^{-1}): inverse of (k) modulo (p-1).
• ((r,s)): signature pair.
  • Nonce requirement: If the same (k) signs two messages, their equations can expose (k) and then private key (x).
  • Limitation: The signature contains two group elements or integers and is generally larger than a comparable Schnorr-style signature.

C. Schnoor Digital signature scheme

The Schnoor scheme, conventionally spelled Schnorr, is a compact discrete-logarithm signature built from a commitment and a hash challenge.

• Parameters: Use a cyclic group of prime order (q) with generator (g); choose private key (x) and public key (Y=g^x).
• Signing:

choose nonce k
R = g^k
e = H(R || M)
s = k + ex mod q
signature = (e, s)

• Verification: Under the stated public-key convention, compute (R'=g^sY^{-e}), then accept if (e=H(R'\parallel M)).
• Concrete roles:
  • (R): temporary commitment.
  • (e): message-dependent challenge.
  • (s): response combining nonce (k) and secret (x).
• Advantages: Offers simple security proofs, compact signatures, efficient verification, and useful multisignature constructions.
• Critical condition: A unique unpredictable nonce is essential; deterministic nonce generation can reduce random-number-generator failures.

IV. Standardized Signature Systems — Interoperability and Assurance

A. Digital signature standards

Digital signature standards specify approved algorithms, parameter sizes, encodings, hashing rules, and validation procedures.

• DSS: The U.S. Digital Signature Standard is published as FIPS 186; FIPS 186-5 approves RSA, ECDSA, and EdDSA for digital signatures while retaining DSA only for verifying existing signatures.
• DSA structure: For subgroup order (q), private key (x), nonce (k), and public key (y=g^x\bmod p):

r = (g^k mod p) mod q
s = k^(-1)(H(M) + xr) mod q

• ECDSA: Transfers DSA-style equations to elliptic-curve points, providing smaller keys and signatures than traditional finite-field systems.
• EdDSA: Uses Edwards curves and deterministic signing, with Ed25519 as a widely deployed instance; implementations must still resist side channels and validate inputs.
• Encoding standards: Specifications define whether signatures use structured encodings such as ASN.1 DER or fixed-width byte strings; mismatched encoding causes interoperability or validation failures.
• Validation requirements: Implementations must reject invalid parameters, malformed signatures, unsupported hashes, and out-of-range signature components.

V. Cryptographic Key Management — Establishing Shared and Public Keys

A. Symmetric key distribution

Symmetric key distribution securely delivers the same secret key to communicating parties.

• Manual distribution: Keys are transferred physically or through a protected administrative channel; this is practical only for small, controlled systems.
• Existing-key transport: A new session key (K_s) is encrypted under a long-term key (K_m):

C = E(K_m, K_s || identities || lifetime)

• (K_m): master key.
• (K_s): temporary session key.
  • Key Distribution Center: A KDC shares a long-term key with each user and issues session-key material, as in Kerberos.
  • Scalability: Direct pairwise keys for (n) users require (n(n-1)/2) keys; a KDC reduces each user’s long-term storage but becomes a high-value trusted service.
  • Controls: Key wrapping, authenticated encryption, expiry times, key separation, rotation, and destruction limit exposure.

B. Symmetric key agreement

Symmetric key agreement lets parties jointly derive a shared secret rather than having one party directly transport the final key.

• Pre-shared-key derivation: Parties combine a shared secret with fresh nonces and context using a key-derivation function:

K_session = KDF(K_shared, nonce_A || nonce_B || context)

• Distinction from transport: Distribution sends a selected key; agreement derives a key from contributions or shared secret material.
• Hybrid agreement: Authenticated Diffie–Hellman produces a shared secret, after which a KDF derives symmetric encryption and MAC keys.
• Forward secrecy: Ephemeral Diffie–Hellman protects past session keys even if a long-term authentication key is later compromised.
• Authentication requirement: Unauthenticated agreement permits a man-in-the-middle attack; signatures, certificates, or pre-shared authentication keys must bind the exchange.
• Freshness: Nonces, ephemeral values, and transcript binding prevent replay and ensure different sessions obtain different keys.

C. Public-key Distribution

Public-key distribution makes a user’s authentic public key available while preventing attackers from substituting their own key.

• Public announcement: Publishing a key is simple but permits forged announcements and impersonation.
• Public directory: A trusted directory stores identity-key records; authenticated updates and protected queries are necessary.
• Public-key authority: An online authority returns signed, fresh key information, improving control but adding latency and availability dependence.
• Certificates: A certification authority signs a binding among subject identity, public key, validity period, serial number, and usage constraints.
• PKI validation: A verifier builds a chain to a trusted root, checks signatures and names, enforces policy, and examines revocation through CRLs or OCSP.
• Alternative trust models: Certificate pinning, trust-on-first-use, and decentralized webs of trust reduce or redistribute CA dependence but introduce different recovery and scaling problems.
• Key lifecycle: Secure generation, enrollment, renewal, rotation, revocation, archival, and destruction are necessary because correct distribution alone does not protect an expired or compromised key.