4. Asymmetric Cryptography, Digital Signatures and Key Agreement

Introduction and Context

Symmetric cryptography is efficient, but it creates a fundamental distribution problem: communicating parties must already share a secret key. In a large network, securely establishing and managing those shared keys can become difficult. Asymmetric cryptography addresses this problem by using a mathematically related pair of keys: a public key that may be distributed openly and a private key that must remain secret.

Public-key techniques support three closely related security functions. They enable encryption for confidentiality, digital signatures for authentication and integrity, and key-agreement protocols for establishing shared session secrets. These functions are often combined in practical systems such as TLS, secure email, virtual private networks, software-update infrastructures, and digital identity systems.

Asymmetric cryptography does not replace symmetric cryptography. Public-key operations are comparatively expensive and are therefore normally used to authenticate parties or establish a short-lived symmetric key. The resulting architecture is called hybrid cryptography. Understanding this division of labour, the assumptions on which it rests, and the ways implementations fail is central to advanced network security.

Learning Objectives

By the end of this chapter, a student should be able to:

• explain the mathematical and operational foundations of asymmetric cryptography;
• distinguish RSA encryption, RSA signatures, Diffie–Hellman key exchange, and elliptic-curve methods;
• describe how digital signatures provide authentication, integrity, and non-repudiation-related evidence;
• analyse hybrid encryption and the relationship between authentication and confidentiality;
• explain forward secrecy and compare static and ephemeral key-agreement designs;
• identify major security assumptions, implementation vulnerabilities, and governance concerns; and
• select appropriate mechanisms for realistic network-security requirements.

The Public-Key Model

In a public-key system, each entity has a key pair. The public key is distributed through a certificate, directory, or trusted channel. The private key is retained by its owner. Security depends not merely on the secrecy of the public key—it is intended to be public—but on the infeasibility of deriving the private key from the public key or manipulating the underlying mathematical problem.

For encryption, a sender uses the recipient’s public key and the recipient uses the corresponding private key to decrypt. For signatures, the private key is used to create a signature and the public key is used to verify it. These operations are related mathematically but are not interchangeable in a simplistic sense. A secure signature scheme is not automatically an encryption scheme, and a raw encryption operation should never be treated as a signature.

Public-key systems require a trust model. A public key is useful only when the user can determine whose key it is and whether it remains valid. Public Key Infrastructure (PKI) addresses this through certificates, certification authorities, certificate policies, validation procedures, revocation mechanisms, and trust stores. In some applications, such as secure messaging, trust may instead be established through key fingerprints, transparency mechanisms, or direct verification.

RSA: Integer-Factorization Cryptography

RSA is based on arithmetic involving large composite integers. Two large primes are selected and multiplied to form a modulus. The public key contains the modulus and a public exponent; the private key contains a mathematically related private exponent. The difficulty of factoring the modulus is the principal security assumption behind conventional RSA, although the exact security of a deployed scheme also depends on padding and parameter choices.

The textbook RSA transformation is deterministic and algebraically structured. It is therefore insecure when used directly. Modern RSA encryption uses RSA-OAEP, which introduces randomized encoding and is designed to resist chosen-ciphertext attacks under appropriate assumptions. RSA signatures use a different encoding method, such as RSA-PSS. An implementation must not confuse OAEP and PSS, nor use raw modular exponentiation for either purpose.

RSA has historically been important because it supports both encryption and signatures and is widely implemented. Its disadvantages include relatively large keys, expensive computation compared with elliptic-curve operations, and vulnerability to implementation errors involving padding, random number generation, or decryption behaviour. RSA encryption is increasingly used less often for new protocol designs, while RSA signatures remain present in many infrastructures.

A secure RSA deployment requires a suitable modulus size, a carefully selected public exponent, strong prime generation, constant-time private-key operations where appropriate, and standardized padding. Private keys should be protected in hardware security modules (HSMs), trusted platform modules, or carefully managed keystores when their compromise would affect many users.

Diffie–Hellman Key Agreement

Diffie–Hellman (DH) enables two parties to establish a shared secret over an untrusted network without transmitting that secret directly. In a simplified finite-field version, the parties agree on a group and generator. One party selects a private value and publishes a corresponding group element; the other does the same. Each party combines its private value with the other party’s public value and obtains the same shared result.

The security intuition is that computing the shared secret from public values requires solving a difficult discrete-logarithm-related problem. The protocol itself, however, does not authenticate the participants. An active attacker can establish one shared secret with each endpoint and relay or alter traffic. This is the classic man-in-the-middle attack. Consequently, DH must be combined with certificates, digital signatures, pre-shared keys, or another authenticated channel.

Finite-field DH requires careful parameter selection. Small or weak groups, unsafe subgroup handling, and failure to validate public values can create attacks. Modern protocols commonly prefer elliptic-curve Diffie–Hellman (ECDH), which offers comparable security with smaller public keys and often better performance.

Ephemeral Diffie–Hellman generates fresh private values for individual sessions. When ephemeral keys are deleted after use and long-term authentication keys are not used to derive the session secret directly, compromise of a long-term private key does not ordinarily reveal recorded past sessions. This property is known as forward secrecy.

Elliptic-Curve Cryptography

Elliptic-curve cryptography (ECC) uses the algebraic structure of points on an elliptic curve over a finite field. The central hard problem is the elliptic-curve discrete logarithm problem: given a point and a multiple of that point, recovering the multiplier should be computationally infeasible.

ECC includes several families of mechanisms. ECDH and its variants provide key agreement; elliptic-curve signature systems such as ECDSA and EdDSA provide authentication and integrity. Curve selection is a security decision, not merely a performance decision. Standardized, well-reviewed curves and libraries should be preferred over custom curves or unfamiliar parameter sets.

ECC offers smaller keys than RSA for comparable classical security levels. This reduces certificate size, bandwidth, and storage requirements, which is valuable for mobile, embedded, and high-volume systems. Nevertheless, ECC is highly sensitive to implementation quality. Invalid-curve attacks, nonce reuse, poor randomness, side-channel leakage, and incorrect point validation can compromise security.

Signature algorithms also differ in operational requirements. ECDSA requires a fresh, secret, uniformly generated nonce for every signature. Reusing or predicting that nonce can reveal the private key. Deterministic nonce-generation methods reduce dependence on external randomness, but they still require correct implementation. EdDSA designs simplify certain choices and are often less fragile, although interoperability and regulatory requirements may influence selection.

Digital Signatures as Security Evidence

A digital signature is a cryptographic value produced using a private key over a message or, more commonly, a cryptographic hash of the message. Verification uses the public key. A valid signature demonstrates that the message corresponds to the private key associated with that public key and that the signed content has not changed since signing, assuming the key remains uncompromised and the verification process is correct.

Signatures provide authentication of the signing key, integrity, and evidence supporting accountability. The term non-repudiation should be used carefully. Cryptography alone cannot prevent a person from claiming that a key was stolen, misused, or operated by an automated system. Legal non-repudiation depends on identity proofing, key custody, audit records, applicable law, organizational controls, and evidentiary procedures.

A sound signature workflow includes canonical representation of the data, domain separation, algorithm identification, certificate validation, and protection against replay. A signature on a transaction should normally include context such as the transaction type, intended recipient, protocol version, expiry time, and unique identifier. Signing an ambiguous or incomplete representation can allow a valid signature to be transferred to a different meaning.

Hash functions are central to signatures. A collision-resistant hash is needed so that an attacker cannot produce two different messages with the same digest in a way that defeats the signature’s purpose. Deprecated hash algorithms and insecure signature schemes must not be retained merely for compatibility without risk assessment and compensating controls.

Hybrid Encryption and Authenticated Key Establishment

A practical secure connection usually combines asymmetric and symmetric cryptography. The asymmetric mechanism authenticates endpoints and establishes a session key; a symmetric authenticated-encryption algorithm then protects application data. This design is efficient because symmetric encryption handles large volumes of traffic while public-key operations occur only during setup or key rotation.

Authenticated encryption with associated data (AEAD) provides confidentiality and integrity for ciphertext and can authenticate unencrypted metadata such as sequence numbers or protocol labels. Examples include AES-GCM and ChaCha20-Poly1305. Correct nonce management is essential: accidental nonce reuse can seriously undermine some AEAD modes.

A typical authenticated hybrid exchange has the following logical stages:

1. The parties negotiate supported protocol versions and cryptographic algorithms.

2. The server presents an identity credential, commonly a certificate.

3. The client validates the certificate chain, name, validity period, key usage, and revocation or status information as required by policy.

4. The parties perform an authenticated ephemeral key agreement.

5. A key derivation function expands the shared secret into separate encryption, authentication, and traffic-direction keys.

6. Application data is protected with an AEAD scheme, with rekeying or termination governed by protocol policy.

The key derivation step matters because a raw DH value should not be used directly as an encryption key. A modern KDF incorporates context, transcript information, and labels so that keys used for different purposes cannot be confused. Transcript binding also helps prevent downgrade and negotiation-manipulation attacks.

Security Assumptions and Failure Boundaries

Cryptographic security is conditional. RSA depends on assumptions related to factoring and secure encoding; DH and ECDH depend on discrete-logarithm-related assumptions; signatures depend on the unforgeability of the scheme, secure hashing, protected private keys, and reliable randomness. The security proof of an algorithm does not cover an incorrectly implemented protocol.

Important failure boundaries include:

• Key compromise: A stolen private key may enable impersonation, decryption of static-key traffic, or fraudulent signatures.
• Randomness failure: Predictable primes, DH exponents, or signature nonces can expose private keys.
• Authentication failure: Unauthenticated key exchange remains vulnerable to active interception.
• Parameter failure: Weak groups, small keys, deprecated algorithms, and invalid public-key validation reduce security.
• Protocol failure: Downgrade attacks, replay, unknown-key-share attacks, and inadequate transcript binding can defeat otherwise strong primitives.
• Side channels: Timing, power consumption, cache behaviour, error messages, and fault responses may reveal secret-dependent information.
• Lifecycle failure: Expired certificates, unrevoked compromised keys, lost keys, and unsupported algorithms create operational exposure.

Threat modelling should therefore identify assets, adversaries, trust anchors, key lifetimes, compromise consequences, recovery procedures, and migration requirements. Cryptographic agility—the ability to replace algorithms and parameters without redesigning the entire system—is increasingly important because algorithms and implementation assumptions can change.

Practical and Organizational Applications

Asymmetric cryptography appears across a broad security architecture. TLS uses certificates and authenticated key exchange to secure web and service traffic. Secure email can use signatures and hybrid encryption, although usability and key-discovery challenges remain significant. Code-signing systems use signatures to establish software provenance and protect update channels. VPNs use authenticated key exchange followed by symmetric tunnel encryption. Digital identity systems use certificates or signed assertions to bind credentials to subjects.

Organizations should distinguish encryption keys, signing keys, authentication keys, and key-encryption keys where practical. Separation reduces the impact of compromise and supports clearer access control. Key management should define generation, activation, storage, backup, rotation, revocation, destruction, and incident response. HSMs can protect high-value keys, but they do not eliminate poor authorization, flawed certificate issuance, or compromised signing workflows.

Automation is useful for certificate issuance, renewal, inventory, expiry alerts, and policy enforcement. It must be monitored: an automated system that issues certificates to the wrong identity can scale an error rapidly. Security teams should maintain an inventory of algorithms, key owners, trust anchors, dependencies, and cryptographic use cases.

Illustrative Case Study: Forward Secrecy in an Enterprise Service

Background

A financial organization operates customer-facing APIs and internal microservices. The original architecture uses long-term RSA server keys to encrypt session secrets. Certificates are valid for one year, and encrypted network traffic is retained for operational and legal purposes.

Situation and Problem

A server is compromised and its RSA private key is stolen. The organization replaces the certificate, but investigators determine that an attacker may have recorded encrypted traffic for several months. Because the historical sessions used the long-term RSA key to protect their session secrets, the attacker may decrypt those recordings.

Analysis

The architecture provided server authentication but lacked forward secrecy. Certificate replacement prevents future impersonation only after all affected systems stop trusting the compromised key. It does not automatically protect old recordings. The incident also exposes weaknesses in key access controls, monitoring, and retention policy.

Approach and Strategy

The organization adopts an authenticated ephemeral ECDH design in which the certificate signs the handshake transcript while fresh ephemeral key pairs establish each session secret. Ephemeral private values are erased after the session. The service uses a modern KDF, AEAD protection, strict certificate validation, automated certificate renewal, HSM-backed long-term signing keys, and centralized detection of unusual key access. Key compromise procedures are revised to include trust-store updates, session invalidation where possible, and review of retained ciphertext.

Outcome

A future compromise of the long-term authentication key could enable impersonation until revocation and replacement, but it would not ordinarily enable decryption of previously completed sessions protected by correctly implemented ephemeral exchange. The organization also improves visibility into certificates and key usage.

Learning Points

Forward secrecy limits the consequences of later long-term-key compromise; it does not prevent active attacks during a compromise, protect endpoints after plaintext is exposed, or compensate for unauthenticated exchange. It is a protocol and lifecycle property, not merely a feature of an individual cipher.

Common Implementation Mistakes and Professional Controls

The most serious errors often arise at integration boundaries. Developers may accept any certificate, disable hostname validation, ignore key-usage constraints, or trust a public key without verifying its identity. Others may use a general-purpose random generator, reuse an ECDSA nonce, fail to validate elliptic-curve points, or reveal whether decryption failed because of padding or authentication.

Secure development should rely on mature, maintained cryptographic libraries rather than implementing primitives from mathematical descriptions. APIs should make unsafe choices difficult, and code review should examine key generation, storage, validation, error handling, algorithm negotiation, and failure recovery. Testing should include negative cases, malformed inputs, replay, downgrade attempts, expired certificates, revoked credentials, and service interruption during key rotation.

Regulatory and ethical obligations also matter. An organization must protect personal and financial information, retain only necessary keys and ciphertext, document lawful access procedures, and avoid designing systems that make accountability impossible. Strong encryption can protect citizens and businesses, but key escrow and exceptional-access proposals introduce additional trusted parties and attack surfaces. Such decisions require transparent risk analysis rather than assumptions that access mechanisms can be made risk-free.

Current Developments and Emerging Directions

Contemporary protocol design increasingly favours authenticated ephemeral key exchange, AEAD, automated certificate management, and formally analysed transcript-based protocols. Hybrid classical–post-quantum key establishment is being explored and deployed in some environments because a sufficiently capable quantum computer could threaten widely used RSA and elliptic-curve public-key systems. Migration requires inventory, interoperability testing, performance analysis, and attention to larger keys or ciphertexts.

Post-quantum transition planning should begin before a crisis. Organizations should identify where public-key cryptography is used, classify data according to confidentiality lifetime, require vendors to disclose cryptographic dependencies, and design interfaces that support algorithm replacement. Quantum-resistant algorithms do not remove the need for authentication, secure randomness, careful implementation, or sound key management.

Best-Practice Framework

A defensible asymmetric-cryptography program should follow these principles:

• use standardized, peer-reviewed algorithms and approved parameter sets;
• use authenticated ephemeral key agreement for sessions requiring forward secrecy;
• use RSA-OAEP or RSA-PSS where RSA is required, never textbook RSA;
• validate certificates, identities, key usage, algorithms, and validity status;
• protect private keys with least privilege, secure storage, and auditable access;
• use robust randomness and deterministic signing methods where appropriate;
• derive independent session keys with a standardized KDF;
• use AEAD and enforce nonce uniqueness;
• plan rotation, revocation, compromise response, backup, and destruction;
• test implementations against active attacks and malformed inputs; and
• maintain cryptographic inventories and a migration plan for emerging standards.

Chapter Summary

Asymmetric cryptography solves key-distribution problems through public and private keys, but its security depends on mathematical assumptions, authentication, implementation quality, and operational governance. RSA remains important when correctly combined with OAEP or PSS. Diffie–Hellman and ECDH establish shared secrets but require authentication to prevent man-in-the-middle attacks. Elliptic-curve systems provide compact and efficient alternatives, while digital signatures establish integrity and evidence associated with a signing key.

Practical systems use hybrid encryption: public-key mechanisms authenticate and establish keys, and symmetric AEAD protects data. Ephemeral key agreement provides forward secrecy by limiting the value of later-compromised long-term keys for historical traffic. Certificate validation, randomness, side-channel resistance, lifecycle management, key separation, and cryptographic agility are as important as the algorithms themselves. Future migration planning must also consider post-quantum threats.

Key Terms

Asymmetric cryptography: Cryptography using related public and private keys for encryption, signatures, or key agreement.

Public key: A key intended for distribution and used for verification, encryption, or agreement.

Private key: A secret key used for decryption, signing, or key agreement.

RSA: A public-key system based primarily on the difficulty of factoring large composite integers.

RSA-OAEP: A randomized encoding scheme used with RSA encryption.

RSA-PSS: A randomized, modern padding scheme used with RSA signatures.

Diffie–Hellman: A protocol that establishes a shared secret using discrete-logarithm-based mathematics.

ECDH: Elliptic-curve Diffie–Hellman key agreement.

Elliptic-curve cryptography: Public-key cryptography based on operations on elliptic-curve points.

Digital signature: A value generated with a private key and verified with the corresponding public key.

PKI: The framework of certificates, trust anchors, policies, and procedures supporting public-key trust.

Certificate: A signed binding between an identity and a public key.

Forward secrecy: Protection of past session secrets against later compromise of long-term keys.

Hybrid encryption: Use of asymmetric cryptography to establish or protect a symmetric key, followed by symmetric data encryption.

AEAD: Authenticated encryption with associated data, providing confidentiality and integrity.

KDF: A key derivation function that produces independent keys from shared secret material.

Nonce: A value intended for one-time use in a cryptographic operation.

Man-in-the-middle attack: An active attack in which an adversary intercepts and potentially alters communication between parties.

Cryptographic agility: The capacity to replace algorithms, parameters, or protocols with limited system disruption.

Review Questions

Short Answer Questions

1. Why is raw textbook RSA unsuitable for practical encryption?

2. What security service does a digital signature provide that encryption alone does not?

3. Why must Diffie–Hellman be authenticated?

4. Define forward secrecy.

5. What is the purpose of a key derivation function?

Long Answer Questions

1. Explain RSA encryption and signature use, including the different roles of OAEP and PSS.

2. Compare finite-field Diffie–Hellman, ECDH, and RSA-based key establishment.

3. Describe how PKI supports the secure use of public keys in enterprise networks.

4. Explain the architecture and security benefits of hybrid encryption.

5. Analyse the major implementation vulnerabilities affecting elliptic-curve signatures.

Analytical / Application Questions

1. A company discovers that its server’s long-term private key was stolen after years of recorded TLS traffic. Explain what determines whether the recorded traffic can be decrypted and recommend a redesign.

2. An application verifies a signature but does not validate the certificate’s hostname, expiry, or key usage. Analyse the resulting risks and propose controls.

3. Design a cryptographic migration plan for an organization preparing for post-quantum public-key standards while maintaining interoperability with existing clients.

22. Multiple Choice Questions with Answers

Question 1

Which mechanism most directly provides forward secrecy in a secure session?

A. A static RSA key encrypting every session key

B. An ephemeral Diffie–Hellman exchange with deletion of ephemeral private values

C. A long-lived symmetric key shared by all servers

D. A certificate with a longer validity period

Correct Answer: B. An ephemeral Diffie–Hellman exchange with deletion of ephemeral private values

Question 2

Why is textbook RSA encryption insecure?

A. It cannot use a public key

B. It is deterministic and lacks secure randomized encoding

C. It requires elliptic curves

D. It provides forward secrecy automatically

Correct Answer: B. It is deterministic and lacks secure randomized encoding

Question 3

What is the principal role of authentication in Diffie–Hellman?

A. To make the shared secret public

B. To prevent a man-in-the-middle attack

C. To eliminate the need for randomness

D. To replace symmetric encryption

Correct Answer: B. To prevent a man-in-the-middle attack

Question 4

Which pairing is correct?

A. RSA-OAEP—RSA signatures; RSA-PSS—RSA encryption

B. RSA-OAEP—RSA encryption; RSA-PSS—RSA signatures

C. RSA-OAEP—certificate revocation; RSA-PSS—key derivation

D. RSA-OAEP—hash collision detection; RSA-PSS—nonce generation

Correct Answer: B. RSA-OAEP—RSA encryption; RSA-PSS—RSA signatures

Question 5

In hybrid encryption, what normally protects the bulk application data?

A. A symmetric AEAD algorithm

B. Repeated RSA signatures

C. A certificate authority private key

D. A raw elliptic-curve point

Correct Answer: A. A symmetric AEAD algorithm

Question 6

What can result from reusing an ECDSA signing nonce?

A. The public key becomes smaller

B. The private signing key may be recovered

C. Forward secrecy is strengthened

D. Certificate validation becomes unnecessary

Correct Answer: B. The private signing key may be recovered

Question 7

Which statement best describes a digital signature?

A. It hides the message from the public key holder

B. It provides evidence of correspondence to a private key and message integrity

C. It automatically proves the legal identity of a human signer

D. It replaces certificate validation

Correct Answer: B. It provides evidence of correspondence to a private key and message integrity

Question 8

Why should a raw Diffie–Hellman shared value normally be processed by a KDF?

A. To make the public keys secret

B. To derive independent, context-specific cryptographic keys

C. To factor the group modulus

D. To remove the need for authentication

Correct Answer: B. To derive independent, context-specific cryptographic keys

Question 9

Which is a serious AEAD implementation requirement?

A. Reuse the same nonce for every message

B. Ensure nonce uniqueness under a given key

C. Publish the encryption key with the ciphertext

D. Disable integrity verification for performance

Correct Answer: B. Ensure nonce uniqueness under a given key

Question 10

What does cryptographic agility mean?

A. Using as many algorithms as possible simultaneously

B. Replacing algorithms or parameters without redesigning the entire system

C. Allowing users to select algorithms without policy controls

D. Removing all certificates from a network

Correct Answer: B. Replacing algorithms or parameters without redesigning the entire system