Asymmetric Cryptography, Digital Signatures and PKI

Introduction and Context

Cryptography enables confidentiality, integrity, authentication and non-repudiation in environments where communicating parties may not trust the network. Earlier chapters commonly introduce symmetric cryptography, in which the same secret key is used for encryption and decryption. Symmetric systems are efficient, but they create a difficult distribution problem: two parties must already share a secret key securely.

Asymmetric cryptography addresses this problem by using a mathematically related key pair. A public key may be distributed openly, while a private key remains under the exclusive control of its owner. This model supports secure key establishment, digital signatures, identity binding and large-scale trust infrastructures. It is fundamental to TLS, secure email, software signing, virtual private networks, online banking and identity systems.

This chapter explains public- and private-key concepts, RSA, elliptic-curve cryptography (ECC), Diffie–Hellman key exchange, digital signatures and public key infrastructure (PKI). It also examines certificates, certificate authorities, trust chains, revocation and operational responsibilities.

Learning Objectives

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

1. Distinguish symmetric encryption, asymmetric encryption, key exchange and digital signatures.
2. Explain the roles and protection requirements of public and private keys.
3. Describe the principles and limitations of RSA and elliptic-curve cryptography.
4. Explain Diffie–Hellman and elliptic-curve Diffie–Hellman key exchange.
5. Describe how digital signatures provide integrity and authentication.
6. Interpret the main fields in an X.509 certificate.
7. Explain certificate authorities, trust chains, revocation and PKI operations.
8. Apply secure key-management and certificate-management practices.

1. The Public-Key Model

In a public-key system, each participant has a key pair:

• Public key: distributed to other parties and used according to the algorithm’s purpose.
• Private key: kept secret and protected against disclosure or unauthorized use.

The keys are mathematically related, but a secure design makes it computationally infeasible to derive the private key from the public key. “Computationally infeasible” does not mean mathematically impossible; it means that the required resources and time are beyond a practical attacker’s capability under the assumed security level.

Public-key cryptography supports several different operations. Public-key encryption normally uses the recipient’s public key for encryption and the recipient’s private key for decryption. A digital signature is normally created with the signer’s private key and verified with the signer’s public key. Key agreement, such as Diffie–Hellman, allows two parties to derive a shared secret without transmitting that secret directly.

These operations must not be confused. RSA encryption, RSA signatures and RSA key transport use related mathematical foundations but different schemes, encodings and security requirements. An implementation must use a standardized scheme rather than treating raw mathematical operations as a complete cryptographic protocol.

Why Hybrid Cryptography Is Used

Asymmetric operations are computationally expensive compared with symmetric encryption and are unsuitable for encrypting large files directly. Most practical systems therefore use hybrid cryptography:

1. The parties use public-key cryptography to authenticate or establish a session key.
2. They use a symmetric authenticated-encryption algorithm, such as AES-GCM or ChaCha20-Poly1305, to protect the actual data.
3. The session key is discarded or replaced according to the protocol’s key-lifetime policy.

This combines scalable key establishment with efficient data protection.

2. Mathematical Foundations

Many public-key systems rely on one-way functions: operations that are easy to perform in one direction but difficult to reverse without special information. Security depends on specific hard problems, not merely on the existence of a one-way-looking formula.

Important examples include:

• Integer factorization: given a large composite integer, finding its prime factors is difficult for appropriately chosen parameters. RSA security is related to this problem, although precise security claims involve the selected RSA scheme and assumptions.
• Discrete logarithm problem: in a suitable group, computing the exponent that produced a known group element is difficult. Traditional Diffie–Hellman uses this problem in multiplicative groups.
• Elliptic-curve discrete logarithm problem: on a properly selected elliptic curve, finding the scalar that maps one point to another is difficult. ECC uses smaller keys for comparable classical security, but implementation details and curve selection are critical.

Modular Arithmetic

Public-key algorithms frequently use modular arithmetic. The notation a mod n means the remainder obtained when integer a is divided by positive integer n. Congruence is written as:

This means that n divides (a − b). Exponentiation modulo n is written a^b mod n. The notation is especially important in RSA and Diffie–Hellman.

3. RSA

RSA is an asymmetric cryptographic system based on arithmetic modulo the product of two large secret primes. A simplified key-generation description is:

1. Select two large distinct primes, p and q.
2. Compute n = p × q.
3. Compute Euler’s totient for distinct primes:

1. Choose a public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
2. Compute private exponent d such that:

The public key is generally (n, e), while the private key contains d and normally additional secret parameters. The security intuition is that an attacker who can factor n can calculate the private relationship, whereas factoring a sufficiently large, well-generated modulus is difficult.

For textbook RSA encryption, a message represented by integer m is transformed as:

and decrypted as:

Here, m must satisfy the required range and encoding assumptions. These equations describe the mathematical core only. Raw textbook RSA must not be used in real systems. Modern RSA encryption uses randomized padding such as RSA-OAEP, and modern RSA signatures use a standardized encoding such as RSA-PSS. Padding prevents deterministic outputs and protects against practical attacks.

RSA Worked Example (Educational Only)

Choose the small primes p = 5 and q = 11. Then:

Choose e = 3, since gcd(3,40) = 1. The value d = 27 satisfies:

For the small message m = 7, textbook encryption gives:

Decryption gives:

This example demonstrates the relationship but provides no security because the modulus is tiny and no secure encoding is used.

RSA Strengths and Limitations

RSA is widely supported and well understood. However, it requires relatively large keys, can be computationally expensive, and is vulnerable if random-number generation, padding or private-key protection is weak. RSA does not provide forward secrecy when used merely to encrypt a long-term key. Organizations should follow current standards for minimum key sizes and approved padding rather than relying on historical defaults.

4. Elliptic-Curve Cryptography

ECC uses points on an elliptic curve over a finite field. A simplified short-Weierstrass curve is expressed as:

where p is commonly a prime defining the finite field, and parameters a and b must satisfy a non-singularity condition. For a prime field, the curve must satisfy:

This condition prevents the curve from having a singular point and ensures that the point operations form a suitable group structure, together with a defined point at infinity.

A private ECC key is a randomly selected scalar d. A public key is a point:

where G is a standardized base point and dG means adding G to itself d times under the elliptic-curve group operation. The security problem is to recover d from G and Q, which is intended to be computationally infeasible for approved curves and parameters.

ECC can provide strong security with smaller public keys and signatures than RSA. This reduces bandwidth and storage, which is valuable in mobile, embedded and high-volume systems. ECC is not automatically secure: weak random generation, invalid-curve attacks, side channels, incorrect point validation and unsuitable curves can compromise implementations.

Common families include elliptic-curve Diffie–Hellman (ECDH) for key agreement and elliptic-curve digital signature algorithms such as ECDSA. Modern protocols may also use EdDSA and X25519, which are designed with implementation simplicity and strong performance in mind. The exact algorithm must match the protocol and compliance requirements.

5. Diffie–Hellman Key Exchange

Diffie–Hellman (DH) allows two parties to derive a shared secret over a public channel. In a simplified multiplicative-group version, the parties agree publicly on a large prime p and generator g.

• Alice chooses private random a and sends A = g^a mod p.
• Bob chooses private random b and sends B = g^b mod p.
• Alice computes S = B^a mod p.
• Bob computes S = A^b mod p.

Both obtain the same value because:

The shared value is normally processed through a key-derivation function (KDF), rather than used directly as an encryption key. The KDF incorporates context, protocol labels and often both public contributions.

Unauthenticated DH is vulnerable to a man-in-the-middle attack. An attacker can establish one exchange with Alice and another with Bob, thereby relaying and possibly modifying traffic. Authentication is therefore essential. TLS commonly authenticates one or both endpoints with certificates and digital signatures while using ephemeral DH or ECDH to establish a session key.

Forward secrecy is achieved when ephemeral private values are used and then erased. If a server’s long-term signing key is stolen later, past recorded sessions should remain protected, assuming the ephemeral secrets were not recovered and the protocol was correctly implemented.

6. Digital Signatures

A digital signature is a cryptographic value created with a private key and verified with the corresponding public key. A secure signature scheme provides:

• Integrity: modification of the signed data causes verification to fail.
• Authenticity: verification connects the signature to control of the private key.
• Non-repudiation evidence: signatures can support accountability, although legal non-repudiation also depends on identity proof, key custody, policy and applicable law.

Signatures normally operate on a cryptographic hash of the message. If H is a collision-resistant hash function and m is the message, the signed digest is:

The signer applies the signature algorithm to h using the private key. The verifier independently computes H(m) and checks the signature using the public key. Hash functions are not encryption: a digest is not intended to be decrypted to recover the message.

A signature proves that the holder of the private key signed—or authorized the signing operation for—the data under the scheme’s assumptions. It does not prove that the signed content is truthful, safe or legally binding. Systems should define exactly what is signed, include context and prevent replay by incorporating timestamps, sequence numbers, transaction identifiers or domain separation.

Signature and Encryption Comparison

7. Certificates and X.509

A public key alone does not identify its owner. An attacker could publish a key while claiming to represent a bank, university or website. A digital certificate solves this binding problem by having a trusted authority sign a structured statement that associates an identity with a public key.

The most common certificate format for internet PKI is X.509. Important fields include:

For modern TLS server certificates, the SAN field is central to hostname verification. A client should not accept a certificate merely because the common name appears plausible. It must validate the requested hostname against permitted identity fields, verify the chain and check validity and policy requirements.

8. Certificate Authorities and Trust Chains

A certificate authority (CA) issues and signs certificates. A root CA is usually self-signed and distributed as a trust anchor in operating systems, browsers or enterprise trust stores. Intermediate CAs are signed by a root or another intermediate and issue end-entity certificates.

A typical chain is:

Figure: A simplified PKI trust chain. Each issuer signs the certificate below it; the verifier begins with a configured trust anchor.

A relying party validates a chain by checking, among other requirements:

1. Each certificate signature is valid under the issuer’s public key.
2. The chain terminates at a locally trusted root.
3. The current time falls within each certificate’s validity period.
4. Basic Constraints and path-length rules permit the issuing relationship.
5. Key Usage and Extended Key Usage permit the intended operation.
6. The subject identity matches the service or identity being authenticated.
7. Revocation and policy requirements are satisfied.

Trust is therefore partly technical and partly administrative. Installing an untrusted root certificate can allow its holder to intercept traffic within that trust domain. Root-store governance is consequently a major security responsibility.

9. PKI Operations and Revocation

PKI is the combination of technology, people, procedures, policies and governance used to manage digital certificates and keys. A practical lifecycle includes:

1. Planning: define certificate policies, approved algorithms, identity-proofing levels and responsibilities.
2. Key generation: generate keys with an approved cryptographic random-number generator, preferably in a hardware security module (HSM) or protected platform where appropriate.
3. Enrollment: submit a certificate request and prove control of the identity or resource.
4. Issuance: the CA validates the request, applies policy and signs the certificate.
5. Deployment: install the certificate and required intermediates without exposing the private key.
6. Monitoring: track expiration, algorithm strength, configuration and suspicious use.
7. Renewal or replacement: issue a new certificate before expiration or after a key rotation.
8. Revocation and recovery: revoke certificates when keys are compromised, identity information is incorrect or authorization ends.
9. Retirement: securely destroy obsolete private keys and preserve required audit records.

A certificate may need revocation before its expiration. Common reasons include private-key compromise, unauthorized issuance, change of ownership, incorrect identity information or cessation of the subject’s authorization.

Revocation mechanisms include:

• Certificate Revocation Lists (CRLs): signed lists published by a CA. They may be large and can become stale between publication intervals.
• Online Certificate Status Protocol (OCSP): a client asks a responder about a certificate’s status. It offers fresher information but introduces availability, privacy and performance concerns.
• OCSP stapling: a server obtains a signed status response and sends it to the client, reducing direct client queries to the CA.
• Short-lived certificates: reduce the window of misuse and can lessen dependence on real-time revocation, but require reliable automation.

A system must define its failure policy. Treating every unavailable revocation service as “valid” can weaken security; treating every temporary outage as “invalid” can harm availability. The appropriate choice depends on risk, protocol behavior and organizational policy.

10. Applied Case: Certificate Failure in an Online Service

This is an illustrative case. A university’s student portal uses TLS certificates issued by an intermediate CA. The web server certificate is valid, but administrators renew only the leaf certificate and omit the intermediate certificate from the server configuration. Some browsers build the chain successfully because they have cached the intermediate; mobile applications and newly installed systems cannot.

Problem

Students receive certificate errors, while the operations team observes inconsistent behavior across clients. The issue is not that the public key is mathematically invalid; it is a failure in certificate-chain deployment.

Analysis

The server presents the end-entity certificate but not the required intermediate. A client must either already possess the intermediate or retrieve it through supported mechanisms. Because relying on client retrieval is unreliable, chain construction fails for some clients.

Approach and Solution

The team inventories the complete chain, verifies the issuer signatures and validity periods, and configures the server to present the leaf certificate followed by the required intermediate certificates. The root is not unnecessarily sent by the server because it should be selected from the client’s trust store. Automated monitoring is added for expiration, chain completeness and hostname coverage. The private key is replaced through a controlled rotation process and access logs are reviewed.

Outcome

Clients consistently validate the chain. The university documents certificate ownership, renewal responsibilities and emergency procedures. A second exercise tests response to private-key compromise, including revocation, replacement and communication with affected users.

Learning Points

Certificate management is an operational discipline, not merely a one-time installation task. Availability, identity validation, private-key protection, chain construction and revocation all matter. Automation reduces avoidable expiration failures, but automated issuance must still enforce authorization and audit controls.

11. Security, Governance and Ethical Issues

Private keys are high-value credentials. Organizations should apply least privilege, strong access controls, secure backups where justified, separation of duties, tamper-resistant storage and auditable use. A CA compromise can affect many relying parties, so CA operators require rigorous change management, monitoring and incident response.

Certificate issuance also raises identity and privacy questions. Certificate authorities must validate control of domains or other identities without collecting unnecessary personal information. Mis-issuance can enable impersonation. Certificate Transparency logs improve public visibility into many publicly trusted certificates, allowing domain owners and researchers to detect suspicious issuance.

Cryptography does not eliminate legal or social responsibilities. A digital signature can be misused by an authorized insider, generated with a stolen key or applied to deceptive content. Governance must define who may sign, what signing means, how keys are recovered or destroyed, and how evidence is preserved.

Quantum computing is a future-facing concern. Large-scale quantum computers would threaten RSA and conventional discrete-logarithm systems through Shor’s algorithm. Symmetric cryptography is affected differently, and larger symmetric keys can provide mitigation. Organizations should inventory cryptographic dependencies, support algorithm agility and follow developments in post-quantum cryptography and standardized migration guidance.

12. Best Practices

• Use standardized, reviewed protocols and libraries; never implement RSA, ECC or certificate validation from scratch for production use.
• Use hybrid cryptography and authenticated encryption for application data.
• Prefer ephemeral DH or ECDH in protocols that require forward secrecy.
• Use approved RSA padding such as OAEP or PSS where RSA is selected.
• Generate private keys with a cryptographically secure random-number generator.
• Protect high-value keys with HSMs or suitable platform-backed key stores.
• Validate hostname, chain, validity, usage constraints and revocation according to policy.
• Automate certificate discovery, renewal and expiration alerting.
• Maintain accurate asset ownership and certificate inventories.
• Remove obsolete algorithms and avoid deprecated protocols and hash functions.
• Test compromise, revocation, renewal and disaster-recovery procedures.
• Keep trust stores controlled, patched and subject to change governance.
• Design for algorithm agility and future post-quantum migration.

Chapter Summary

Asymmetric cryptography uses related public and private keys to solve problems that symmetric cryptography alone cannot solve at scale. Public-key encryption supports confidentiality, digital signatures support integrity and authentication, and Diffie–Hellman supports shared-secret establishment. RSA relies on modular arithmetic and the difficulty associated with factoring; ECC relies on elliptic-curve group operations and the elliptic-curve discrete logarithm problem. In practice, secure schemes require approved encodings, parameter choices, random generation and protocol integration.

Digital certificates bind public keys to identities through CA signatures. X.509 fields, trust chains, usage constraints, validity periods and revocation status must all be evaluated by a relying party. PKI is a lifecycle and governance system involving enrollment, issuance, deployment, monitoring, renewal, revocation and key protection. Effective cybersecurity therefore depends not only on algorithms but also on sound operations, accountability, automation and preparation for changing threats.

Key Terms

Asymmetric cryptography: Cryptography using mathematically related public and private keys.

Certificate authority (CA): An entity that validates information and signs digital certificates.

Certificate revocation list (CRL): A signed list of certificates that a CA has revoked.

Digital certificate: A signed statement associating a public key with an identity or resource.

Digital signature: A private-key-generated value verified with a public key to support integrity and authentication.

Diffie–Hellman: A key-agreement method for deriving a shared secret over a public channel.

Elliptic-curve cryptography (ECC): Public-key cryptography based on elliptic-curve group operations.

Forward secrecy: Protection of past sessions if a long-term private key is later compromised.

Hash function: A function that maps data to a fixed-length digest for which reversal and collision finding are intended to be difficult.

Intermediate CA: A CA certificate issued by a root or another authorized CA and used to issue subordinate certificates.

Key pair: A mathematically related public key and private key.

Key usage: Certificate constraints describing permitted cryptographic operations.

OCSP: A protocol for obtaining the status of a certificate from a responder.

PKI: The people, policies, processes and technologies used to manage public keys and certificates.

Private key: The secret component of a public-key pair.

Public key: The distributable component of a public-key pair.

Root CA: A trust anchor, commonly self-signed and distributed through a trust store.

Trust chain: A sequence of certificates leading from an end entity to a trusted root.

X.509: A widely used standard for public-key certificates and certificate-path structures.

Review Questions

5 Short Answer Questions

1. What is the primary difference between a public key and a private key?
2. Why do practical systems combine asymmetric and symmetric cryptography?
3. What security problem does unauthenticated Diffie–Hellman have?
4. Name four important fields in an X.509 certificate.
5. What is the purpose of certificate revocation?

5 Long Answer Questions

1. Explain RSA key generation and distinguish textbook RSA from secure RSA encryption and signature schemes.
2. Describe ECC key generation conceptually and explain why ECC can use smaller keys than RSA for comparable classical security.
3. Explain how a digital signature is created and verified, including the role of a cryptographic hash.
4. Describe the steps a relying party should perform when validating a certificate chain.
5. Discuss the operational lifecycle of a certificate from key generation through retirement.

3 Analytical / Application Questions

1. A company’s TLS certificate is valid by date but fails hostname validation. Analyze the likely cause and propose corrective actions.
2. An attacker obtains a server’s long-term signing key but cannot obtain ephemeral session keys. Explain how forward secrecy affects previously recorded sessions.
3. Design a PKI governance plan for a medium-sized organization, including CA hierarchy, private-key protection, renewal automation, revocation and incident response.

Multiple Choice Questions with Answers

Question 1

Which key is normally used to create a digital signature?

A. The signer’s private key

B. The verifier’s private key

C. The recipient’s public key

D. A certificate authority’s root key in every transaction

Correct Answer: A. The signer’s private key

Question 2

What is the principal purpose of using hybrid cryptography?

A. To eliminate the need for authentication

B. To combine scalable key establishment with efficient symmetric data protection

C. To make public keys secret

D. To replace hashing with encryption

Correct Answer: B. To combine scalable key establishment with efficient symmetric data protection

Question 3

In the educational RSA example, what is the value of n when p = 5 and q = 11?

A. 16

B. 40

C. 55

D. 81

Correct Answer: C. 55

Question 4

What weakness affects unauthenticated Diffie–Hellman?

A. It cannot produce a shared value

B. It is vulnerable to a man-in-the-middle attack

C. It requires certificates to be encrypted with AES

D. It prevents forward secrecy by definition

Correct Answer: B. It is vulnerable to a man-in-the-middle attack

Question 5

Which certificate field is central to modern TLS hostname validation?

A. Serial Number

B. Subject Alternative Name

C. Authority Key Identifier

D. Signature Algorithm alone

Correct Answer: B. Subject Alternative Name

Question 6

What does a root CA normally represent in a trust chain?

A. A locally configured trust anchor

B. A temporary session key

C. An end-user password

D. A hash digest of the web page

Correct Answer: A. A locally configured trust anchor

Question 7

Which mechanism allows a client to query a responder about certificate status?

A. OCSP

B. RSA-PSS

C. ECDH

D. SAN

Correct Answer: A. OCSP

Question 8

What does forward secrecy aim to protect?

A. The certificate’s issuer name from public viewing

B. Past sessions if a long-term private key is later compromised

C. A private key from being generated

D. A CA from having a root certificate

Correct Answer: B. Past sessions if a long-term private key is later compromised

Question 9

Which statement about raw textbook RSA is correct?

A. It is recommended for production encryption because it is deterministic

B. It requires no encoding or padding

C. It demonstrates mathematical relationships but should not be used directly in production

D. It provides forward secrecy automatically

Correct Answer: C. It demonstrates mathematical relationships but should not be used directly in production

Question 10

What is a key operational responsibility in PKI?

A. Ignoring certificate expiration until users report errors

B. Publishing every private key for transparency

C. Maintaining certificate inventory, renewal and revocation processes

D. Sending the root certificate with every server response

Correct Answer: C. Maintaining certificate inventory, renewal and revocation processes