Asymmetric Cryptography and Digital Signatures

Introduction and Context

Symmetric cryptography uses one shared secret key for encryption and decryption. It is efficient, but it creates a distribution problem: communicating parties must obtain the secret key securely before protected communication begins. Asymmetric cryptography, also called public-key cryptography, addresses this problem by using a mathematically related key pair: a public key that may be distributed openly and a private key that must remain confidential.

Public-key techniques support two major security services. Encryption with a recipient’s public key provides confidentiality because only the corresponding private key should decrypt the message. Signing with a sender’s private key provides authentication, integrity, and non-repudiation evidence because anyone with the sender’s public key can verify the signature. In practice, asymmetric operations are computationally expensive, so modern systems normally combine them with fast symmetric encryption in a hybrid design.

Learning Objectives

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

• explain public-key cryptography and its trust assumptions;
• describe RSA, Diffie–Hellman, and elliptic-curve cryptography (ECC);
• distinguish encryption, key exchange, authentication, and digital signatures;
• explain hybrid encryption and authenticated encryption;
• identify how certificates and public-key infrastructures establish trust;
• select appropriate algorithms and security strengths for practical systems;
• evaluate implementation, governance, and migration risks.

Public-Key Cryptography

A public-key system consists of algorithms for key generation, encryption or key encapsulation, decryption or decapsulation, signing, and verification. A simplified encryption relationship is:

where P is a public key, m is plaintext, and C is ciphertext. Decryption uses the corresponding private key S:

The security requirement is that deriving S from P, or recovering m without S, must be computationally infeasible under the assumed hard mathematical problem and threat model.

For signatures, the sender computes a signature over a message, usually after hashing it:

The verifier uses the public key:

Here H is a cryptographic hash function and σ is the signature. A signature does not normally encrypt the message. It proves possession of the private signing key and detects modification, provided the private key is controlled and the public key is correctly associated with the claimed identity.

Security Properties and Trust Assumptions

Public-key cryptography does not eliminate trust; it changes where trust is required. Important assumptions include:

1. Private-key secrecy: an attacker who obtains a private key may decrypt data, impersonate its owner, or forge signatures.
2. Algorithmic hardness: the underlying mathematical problem must resist available attacks.
3. Correct implementation: padding, randomness, validation, and error handling must be secure.
4. Authentic public keys: a public key must genuinely belong to the claimed person, service, or device.
5. Sound randomness: key generation, nonces, and ephemeral secrets require unpredictable random values.
6. Lifecycle control: keys must be generated, stored, rotated, backed up, revoked, and destroyed appropriately.

A public key obtained through an unauthenticated channel is vulnerable to a man-in-the-middle attack. An attacker can substitute their own key, causing each participant to believe that the attacker’s key belongs to the other participant. Certificates, authenticated key exchange, fingerprints, or trusted directories help prevent this attack.

RSA: Factoring-Based Cryptography

RSA security is associated with the difficulty of factoring a large composite integer. Key generation selects two large distinct primes p and q, then computes:

The modulus n is public. A commonly used totient value is:

An exponent e is selected so that gcd(e, φ(n)) = 1. The private exponent d satisfies:

The public key is (n, e), and the private key contains d and the prime-related parameters. Basic textbook RSA is often represented as:

and

These equations describe the mathematical core, not a safe application protocol. Plain RSA encryption is deterministic and malleable, and it must not be used directly. Modern RSA encryption uses randomized padding such as RSA-OAEP. RSA signatures use a secure encoding scheme such as RSA-PSS rather than raw exponentiation.

RSA signing and verification are conceptually different from encryption. In practical implementations, a hash of the message is encoded and processed with the private exponent; verification uses the public exponent. The message itself is usually not placed directly into the RSA operation.

RSA has several limitations. Large keys and modular exponentiation make it slower and less bandwidth-efficient than symmetric cryptography. Poor prime generation, weak random-number generation, reused or exposed private factors, and incorrect padding can destroy security. RSA key sizes must be selected according to current standards and expected protection lifetime. A 2048-bit RSA key is a common minimum for many current applications, while 3072-bit or larger keys may be selected for longer-term protection. Exact choices should follow current organisational policy and standards rather than relying on outdated tables.

Small Illustrative RSA Example

The following deliberately small example is for learning only. Let p = 5 and q = 11. Then n = 55 and φ(n) = 4 × 10 = 40. Choose e = 3, since gcd(3,40)=1. The value d = 27 satisfies 3 × 27 = 81 ≡ 1 mod 40. For a small message m = 7, encryption gives:

Decryption gives:

The tiny factors could be found immediately, so this example provides no security.

Diffie–Hellman Key Exchange

Diffie–Hellman (DH) allows two parties to derive a shared secret over a public channel without transmitting the secret itself. In a finite-field version, the parties agree on a large prime p and a generator g. Alice chooses a private random value a and sends:

Bob chooses b and sends:

Alice computes B^a mod p, while Bob computes A^b mod p. Both obtain the same value because:

The shared value should not normally be used directly as an encryption key. A key-derivation function (KDF) combines it with context, identities, and transcript information to derive independent keys.

Static DH keys do not automatically authenticate the parties. An active attacker can perform two separate exchanges and relay messages. Ephemeral Diffie–Hellman, especially ephemeral elliptic-curve DH, creates fresh session secrets and can provide forward secrecy when long-term authentication keys are not used to derive the session secret directly. Forward secrecy means that compromise of a long-term private key does not ordinarily reveal previously recorded session traffic.

A simplified finite-field illustration uses p = 23, g = 5, a = 6, and b = 15. Alice sends A = 5⁶ mod 23 = 8, and Bob sends B = 5¹⁵ mod 23 = 19. Alice computes 19⁶ mod 23 = 2, while Bob computes 8¹⁵ mod 23 = 2. The small numbers are educational only and are easily attacked.

Elliptic-Curve Cryptography

ECC uses algebraic operations on points of an elliptic curve over a finite field. A commonly written curve form is:

where p is a prime defining the finite field and a and b are curve parameters. A public key is generated by multiplying a standard base point G by a private scalar d:

The security of recovering d from G and Q depends on the elliptic-curve discrete logarithm problem. ECC provides comparable security with substantially smaller keys than traditional finite-field DH or RSA. For example, a 256-bit elliptic-curve key is commonly regarded as offering approximately 128-bit classical security, whereas RSA requires a much larger modulus for a broadly comparable level. Comparisons depend on the algorithm, implementation, and standards assumptions.

ECDH is the elliptic-curve form of Diffie–Hellman key agreement. If Alice has private scalar a and public point A = aG, and Bob has b and B = bG, both derive:

Alice computes aB, while Bob computes bA. ECDSA and EdDSA are elliptic-curve signature families, but they are not interchangeable. EdDSA designs, such as Ed25519, are often attractive because they provide deterministic signing procedures and simpler misuse-resistant interfaces. ECDSA requires careful nonce generation; reuse or predictability of a signing nonce can reveal the private key.

ECC implementation requires strict curve and point validation, secure libraries, protected private keys, and standards-approved parameter choices. Quantum computers capable of running large-scale Shor’s algorithm would threaten RSA, DH, and ECC; this motivates post-quantum migration planning.

Hybrid Encryption and Secure Protocol Design

A practical secure communication system normally combines asymmetric and symmetric cryptography:

1. The recipient publishes an authenticated public key.
2. The sender generates a random symmetric session key.
3. The sender encrypts the data using an authenticated-encryption algorithm such as AES-GCM or ChaCha20-Poly1305.
4. The sender encrypts or encapsulates the session key using the recipient’s public key, or derives it through authenticated key exchange.
5. The recipient uses the private key to recover or derive the session key.
6. The recipient verifies the authentication tag before accepting plaintext.

Authenticated encryption produces ciphertext and an authentication tag. Associated data can be authenticated without being encrypted, for example a protocol version or message identifier. Nonces must be unique under a given key; accidental nonce reuse can severely compromise some modes, especially GCM.

Hybrid encryption is efficient because bulk data is processed symmetrically while asymmetric operations protect only a short key or establish a shared secret. TLS is a major example: modern TLS commonly uses an ephemeral key exchange, certificate-based authentication, and symmetric authenticated encryption for application traffic.

Digital Signatures

A digital signature binds a message to a signing key. It provides:

• Integrity: a changed message should fail verification.
• Origin authentication: verification indicates control of the signing private key at signing time, subject to trust in the key binding.
• Evidence: a signature can support accountability and non-repudiation processes, although legal non-repudiation also depends on policy, identity proofing, key protection, and applicable law.

A secure signing process hashes the message, applies a standardized signature encoding, and uses a private key. Verification checks the signature, algorithm parameters, certificate validity, trust chain, and often the signing time. Signatures do not prove that the signed content is truthful, safe, or authorized. They prove a cryptographic relationship, not the correctness of business claims.

A signature system must define what exactly is signed. Canonicalization is important when the same logical data can have multiple textual representations. For example, inconsistent whitespace, field ordering, character encoding, or line endings can cause validly intended documents to produce different hashes. Protocols should sign a canonical, unambiguous representation and should prevent substitution of one context for another by including domain, purpose, algorithm identifiers, and relevant metadata in the signed message.

Certificates and Public-Key Infrastructure

A public-key certificate is a signed statement binding an identity or subject to a public key. In a typical public-key infrastructure (PKI), a certificate authority (CA) signs certificates, and relying parties validate a chain from the end-entity certificate to a trusted root. Validation may include:

• signature verification for each certificate;
• validity-period checking;
• subject and issuer constraints;
• key-usage and extended-key-usage restrictions;
• hostname or identity matching;
• basic constraints and path-length rules;
• revocation status or an accepted short validity period.

The root trust anchor is accepted through a configuration decision, such as an operating-system trust store. A CA signature alone does not make a certificate universally trustworthy; the relying party must trust the CA for the relevant purpose. Certificate transparency, automated issuance monitoring, short-lived certificates, and automated renewal improve operational assurance.

Revocation is difficult in distributed systems. Certificate revocation lists can be large or stale, while online status checks can create privacy, availability, and dependency concerns. Organisations should define how compromise, expiry, algorithm deprecation, and employee departure trigger replacement and revocation.

Selecting Algorithms and Key Sizes

Selection should begin with the required security service and threat model rather than with a popular algorithm name.

Key-size decisions should consider classical security strength, expected data lifetime, performance, interoperability, hardware capability, regulatory requirements, and post-quantum risk. “Larger” is not automatically better: an unsupported algorithm, unsafe mode, or poorly protected key remains insecure. Use current recommendations from recognised standards bodies and vendor security guidance; do not hard-code obsolete algorithms such as RSA with small keys, MD5 signatures, SHA-1 signatures, or unauthenticated encryption.

Key Management and Operational Controls

Cryptographic design is only as strong as key management. A professional key lifecycle includes generation, registration, distribution, activation, rotation, backup, recovery, suspension, revocation, archival, and destruction. Private keys should be protected using hardware security modules, platform secure elements, or carefully controlled encrypted key stores where appropriate. Access should follow least privilege and separation of duties.

Logs should record key events without exposing private keys or sensitive plaintext. Backup keys require equivalent protection to operational keys. Organisations should maintain an inventory mapping keys to systems, owners, algorithms, purposes, creation dates, and expiry dates. Incident response plans must specify how compromised keys are isolated, replaced, and investigated.

Applied Case: Illustrative Online Health-Records Portal

Background

A regional clinic wants patients and hospitals to exchange medical documents through a web portal. Documents contain sensitive personal data and must be protected in transit and at rest. Hospitals also need confidence that a document has not been altered.

Problem

A simple shared password between all institutions would create a large compromise domain and would not scale. Sending documents with RSA alone would be inefficient, and signing only the transport connection would not protect a document after download.

Analysis

The portal requires confidentiality, integrity, endpoint authentication, key rotation, auditability, and controlled sharing. It also needs to distinguish transport protection from document-level protection. A compromised web server must not automatically expose every historical document.

Approach and Solution

The portal uses TLS with server certificates and authenticated ephemeral key exchange. Each session derives symmetric traffic keys, and application data uses authenticated encryption. For document-level protection, the portal generates a fresh random data-encryption key per document. The document is encrypted with an authenticated symmetric algorithm, while the data key is wrapped for each authorised recipient using an approved public-key mechanism. The document metadata and a canonical representation of the content are digitally signed by the issuing institution.

Institutional signing keys are stored in a managed hardware security module. Certificates restrict key usage to document signing, and automated monitoring detects unexpected certificate issuance. Recipient authorisation is enforced separately from cryptographic verification: a valid signature does not by itself grant a user permission to view a record. Key rotation and revocation procedures are tested through incident exercises.

Outcome

The architecture provides efficient bulk encryption, authenticated exchange, document integrity, recipient-specific access, and auditable key ownership. It also limits the effect of one compromised session key because other documents use different data keys.

Learning Points

The case demonstrates that confidentiality, authentication, authorisation, integrity, and audit are distinct controls. It also shows why hybrid encryption, certificate validation, key lifecycle management, and application-level policy must operate together.

Limitations, Ethics, and Governance

Cryptography can protect information but cannot correct weak identity proofing, excessive permissions, insecure endpoints, dishonest data entry, or poor organisational governance. Strong encryption may complicate lawful access, incident investigation, and recovery from lost keys. Policies must balance privacy, safety, legal obligations, and proportionality. Backdoors and universal decryption keys create high-value targets and generally weaken security for legitimate users.

Sensitive personal data should be minimised, retained only as necessary, and processed under applicable privacy and sector regulations. Key escrow, where required, must have narrowly defined authority, independent oversight, dual control, tamper-evident logging, and documented recovery procedures. Organisations should assess export controls, contractual requirements, accessibility of cryptographic services, and the consequences of algorithm failure.

Contemporary Developments

Post-quantum cryptography seeks algorithms resistant to quantum attacks. Standardisation efforts have focused on lattice-based key encapsulation and signatures, among other families. Organisations should inventory where RSA, DH, and ECC are used, identify data requiring long-term confidentiality, and test crypto-agility—the ability to replace algorithms and key sizes without redesigning every application. Hybrid deployments may combine classical and post-quantum mechanisms during transition.

Cloud key-management services, confidential-computing technologies, automated certificate management, and hardware-backed identities are increasingly important. Automation reduces expiry failures but must be protected against configuration errors and supply-chain compromise. Artificial intelligence can help classify cryptographic assets and detect anomalous signing activity, but it does not replace sound algorithms, verified implementations, or human governance.

Best-Practice Checklist

• Use standardised, peer-reviewed algorithms and authenticated modes.
• Separate encryption keys, signing keys, and key-encryption keys by purpose.
• Authenticate public keys through certificates, secure directories, or verified fingerprints.
• Prefer ephemeral authenticated key exchange for forward secrecy.
• Use cryptographic libraries rather than implementing primitives from scratch.
• Ensure cryptographically secure randomness and unique nonces.
• Validate certificates, signatures, algorithms, key usage, and identity context.
• Maintain a complete key inventory and tested compromise-response plan.
• Plan for algorithm replacement and post-quantum migration.
• Treat cryptographic controls as part of a wider security and governance system.

Chapter Summary

Asymmetric cryptography uses related public and private keys to support confidentiality, authentication, key agreement, and digital signatures. RSA relies on factoring-related assumptions and requires secure padding such as OAEP or PSS. Diffie–Hellman establishes a shared secret but must be authenticated to resist man-in-the-middle attacks; ephemeral forms support forward secrecy. ECC provides comparable classical security with smaller keys, while ECDH, ECDSA, and EdDSA serve different purposes and have distinct implementation requirements.

Real systems use hybrid encryption: asymmetric mechanisms establish or protect a symmetric session key, and authenticated symmetric encryption protects bulk data. Digital signatures provide integrity and evidence of private-key control, but certificates and PKI are needed to bind public keys to identities. Algorithm selection must consider security strength, performance, standards, key lifetime, implementation quality, and post-quantum transition. Effective cryptography ultimately depends on disciplined key management, trustworthy identity processes, secure implementation, and responsible governance.

Key Terms

Public key: A key distributed openly for encryption, verification, or key agreement.

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

Asymmetric cryptography: Cryptography based on mathematically related public and private keys.

RSA: A public-key algorithm associated with the integer-factorisation problem.

Diffie–Hellman: A protocol for deriving a shared secret over a public channel.

ECDH: Elliptic-curve Diffie–Hellman key agreement.

ECC: Cryptography based on elliptic-curve group operations.

Digital signature: A cryptographic value that supports integrity and authentication evidence.

Hash function: A one-way function that maps input data to a fixed-length digest.

Hybrid encryption: A design combining asymmetric protection of keys with symmetric encryption of data.

Forward secrecy: Protection of past sessions after compromise of a long-term key.

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

Certificate authority: An entity trusted to issue and sign certificates.

PKI: The policies, technologies, roles, and processes managing certificates and trust.

KDF: A key-derivation function that produces cryptographic keys from secret material.

Nonce: A value intended for one-time or non-repeating use under a key.

Authenticated encryption: Encryption that also provides integrity and authenticity checking.

Key rotation: Replacement of a cryptographic key according to a defined lifecycle policy.

Crypto-agility: The ability to change cryptographic algorithms and parameters safely.

Post-quantum cryptography: Cryptography designed to resist attacks by sufficiently capable quantum computers.

Review Questions

Short Answer Questions

1. What is the principal difference between a public key and a private key?
2. Why must textbook RSA not be used directly for encryption?
3. What security problem does authenticated Diffie–Hellman solve?
4. State two services provided by a digital signature.
5. Why is hybrid encryption more practical than using asymmetric encryption for all data?

Long Answer Questions

1. Explain RSA key generation and distinguish its mathematical core from secure RSA-OAEP and RSA-PSS applications.
2. Describe an ephemeral ECDH exchange and explain how it can provide forward secrecy.
3. Explain how certificates and certificate authorities establish public-key trust, including important validation checks.
4. Compare RSA, finite-field Diffie–Hellman, and ECC in terms of assumptions, key sizes, performance, and implementation risks.
5. Design a key-management lifecycle for an organisation handling sensitive customer records.

Analytical / Application Questions

1. A company encrypts a large database separately for ten authorised recipients. Propose a hybrid-encryption design and explain how recipient removal would be handled.
2. A web service accepts signatures but does not check certificate hostname, key usage, or algorithm restrictions. Analyse the risks and recommend controls.
3. An organisation must protect records for twenty years and currently uses RSA and ECDH. Develop a practical crypto-agility and post-quantum migration plan.

Multiple Choice Questions with Answers

Question 1

Which key is normally used to verify a digital signature?

A. The signer’s public key

B. The signer’s private key

C. The recipient’s private key

D. A symmetric session key

Correct Answer: A. The signer’s public key

Question 2

What is the main purpose of authenticated encryption?

A. To compress plaintext before transmission

B. To provide confidentiality and detect unauthorised modification

C. To eliminate the need for key management

D. To generate public and private keys

Correct Answer: B. To provide confidentiality and detect unauthorised modification

Question 3

In Diffie–Hellman, why is authentication required?

A. Without it, the exchanged values are always too large

B. Without it, a man-in-the-middle attacker can establish separate secrets with each party

C. Without it, symmetric encryption cannot be used

D. Without it, hashing becomes impossible

Correct Answer: B. Without it, a man-in-the-middle attacker can establish separate secrets with each party

Question 4

Which RSA padding scheme is intended for secure public-key encryption?

A. RSA-OAEP

B. RSA-ECB

C. Raw RSA

D. RSA-CRC

Correct Answer: A. RSA-OAEP

Question 5

What does forward secrecy primarily protect?

A. Future passwords from being hashed

B. Previously recorded sessions after compromise of a long-term private key

C. Public certificates from expiring

D. Symmetric ciphers from brute force

Correct Answer: B. Previously recorded sessions after compromise of a long-term private key

Question 6

What is the main efficiency benefit of hybrid encryption?

A. It avoids all authentication

B. It uses asymmetric cryptography for bulk data and symmetric cryptography only for keys

C. It uses symmetric cryptography for bulk data and asymmetric cryptography for key protection

D. It requires no random numbers

Correct Answer: C. It uses symmetric cryptography for bulk data and asymmetric cryptography for key protection

Question 7

In the illustrative RSA example, what is the modulus when p = 5 and q = 11?

A. 16

B. 40

C. 55

D. 81

Correct Answer: C. 55

Question 8

What does a certificate primarily bind together?

A. A plaintext and its compression ratio

B. An identity and a public key

C. A nonce and a password

D. A private key and a database row

Correct Answer: B. An identity and a public key

Question 9

Which issue is especially dangerous in ECDSA implementations?

A. Using a predictable or reused signing nonce

B. Using a public key for verification

C. Hashing the message before signing

D. Publishing a certificate chain

Correct Answer: A. Using a predictable or reused signing nonce

Question 10

What is crypto-agility?

A. The ability to increase network bandwidth automatically

B. The ability to replace cryptographic algorithms and parameters safely

C. The use of only one permanent key

D. The removal of all certificates from a system

Correct Answer: B. The ability to replace cryptographic algorithms and parameters safely