Asymmetric Cryptography and Digital Signatures

Introduction and Context

Asymmetric cryptography, also called public-key cryptography, enables two parties to communicate securely without first sharing a secret key through a private channel. It also provides digital signatures, which support authentication, integrity, non-repudiation, and accountability. These capabilities distinguish asymmetric systems from symmetric encryption, where the communicating parties must already possess a shared secret.

The central design idea is a mathematically related key pair: a public key that may be distributed openly and a private key that must remain secret. An operation performed with one key is transformed or verified using the other, although the exact relationship differs among encryption, key agreement, and signature schemes.

Modern systems rarely use asymmetric cryptography to encrypt large data volumes directly. Instead, they use it to authenticate parties, establish a short-lived symmetric key, or protect a small key-encryption key. The resulting architecture is known as hybrid cryptography.

Learning Objectives

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

• explain the principles of public-key encryption, key agreement, and digital signatures;
• describe RSA, Diffie–Hellman, and elliptic-curve cryptography;
• distinguish encryption from signing and authentication from confidentiality;
• evaluate cryptographic assumptions and common attacks;
• explain hybrid encryption and secure key exchange;
• compare algorithms in terms of security, performance, interoperability, and operational risk;
• select suitable cryptographic mechanisms for practical systems.

1. Foundations of Asymmetric Cryptography

A public-key cryptosystem normally contains four algorithms:

1. Key generation produces a public key and a private key.
2. Encryption transforms plaintext into ciphertext using a recipient’s public key.
3. Decryption recovers plaintext using the recipient’s private key.
4. Signature generation and verification allow a private-key holder to sign a message and others to verify the signature with the corresponding public key.

These functions should not be conflated. Encryption protects confidentiality; a digital signature primarily provides origin authentication and integrity. A signature does not automatically encrypt the signed message.

A secure public-key system depends on a computational asymmetry. The legitimate operation is efficient when the appropriate secret is known, while reversing or forging the operation without that secret is computationally infeasible under the stated security model.

The term computationally infeasible does not mean mathematically impossible. It means that the best known attack would require resources or time beyond an acceptable operational limit. Security therefore depends on key size, algorithm design, implementation quality, system lifetime, and the expected capabilities of attackers.

Important terminology

• Public key: Information intended for distribution and used for encryption, verification, or key-agreement operations.
• Private key: Secret information used for decryption, signing, or authenticated key agreement.
• Key pair: The mathematically related public and private keys.
• Plaintext: Original readable or structured data.
• Ciphertext: Data produced by an encryption operation.
• Cryptographic assumption: A computational problem believed to be difficult, such as factoring a large integer or solving a discrete logarithm.
• Forward secrecy: Protection of past session traffic even if a long-term private key is later compromised.
• Certificate: A signed data structure binding an identity to a public key.
• Certificate authority (CA): An entity that issues and signs certificates within a public-key infrastructure.

2. RSA: Encryption and Signatures

RSA is based on the practical difficulty of factoring a large composite integer. Two large primes are selected, multiplied, and then used to construct a modulus. Factoring the modulus is intended to be difficult when the primes are sufficiently large and generated securely.

Let p and q be distinct large primes. Define:

The modulus n is public. In the traditional description, Euler’s totient is:

A public exponent e is selected such that:

The private exponent d is the modular multiplicative inverse of e modulo φ(n):

For an encoded message representative m satisfying the required RSA domain and padding conditions, textbook RSA encryption is represented as:

and decryption as:

Here, c is the ciphertext, and exponentiation is modular exponentiation. These equations describe the algebraic core only. Textbook RSA must never be used directly in a production protocol because it is deterministic and malleable.

RSA padding and secure use

For encryption, modern RSA deployments use a randomized encoding such as RSAES-OAEP. OAEP prevents deterministic encryption and provides security properties under appropriate assumptions and implementation conditions. For signatures, RSA-PSS is preferred to older deterministic schemes because it incorporates randomized encoding and has stronger modern security properties.

RSA key generation must use a cryptographically secure random number generator, independently generated primes, sufficient modulus length, and reliable primality testing. Private keys should be protected in hardware security modules, trusted platform facilities, or carefully controlled key stores where appropriate.

Small illustrative RSA example

The following example uses deliberately tiny numbers for teaching and is not secure. Let p = 5 and q = 11. Then:

and:

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

For the representative m = 7:

Decrypting gives:

The example demonstrates the key relationship, not a deployable security level. Real RSA requires standardized padding and much larger keys; a commonly deployed RSA modulus is 2048 bits, although organizational policy and expected lifetime may require larger parameters.

RSA strengths and limitations

RSA benefits from extensive standardization, broad library support, and well-understood certificate usage. Its disadvantages include relatively large keys and signatures, computational cost compared with elliptic-curve operations, and the danger of catastrophic failure when padding, randomness, or error handling is incorrect. Timing attacks, fault attacks, chosen-ciphertext attacks, and padding-oracle attacks are important implementation concerns.

3. Diffie–Hellman Key Agreement

Diffie–Hellman (DH) is primarily a key-agreement mechanism rather than an encryption scheme. It allows two parties to derive a common secret over a public channel.

In a finite cyclic group, let g be a generator and let p be a suitable large prime. Alice chooses a private random value a and publishes:

Bob chooses private random value b and publishes:

Alice computes:

Bob computes:

Both values are equal because:

The shared group element should normally be passed through a key-derivation function (KDF), rather than used directly as a symmetric key. The KDF can incorporate protocol labels, identities, transcript data, and a salt.

Authentication is essential

Unauthenticated DH is vulnerable to a man-in-the-middle attack. An attacker can establish one key with Alice and a different key with Bob, then relay and modify messages. DH therefore needs authentication, usually through digital signatures, certificates, pre-shared keys, or a trusted protocol context.

Ephemeral DH and forward secrecy

In ephemeral Diffie–Hellman, fresh private values are generated for each session. If long-term authentication keys are later compromised, previously recorded sessions remain protected, assuming the ephemeral secrets were erased and the underlying assumptions hold. This property is called forward secrecy.

Finite-field DH requires careful parameter validation and protection against weak groups and small-subgroup attacks. Modern protocols commonly prefer standardized groups or elliptic-curve variants rather than arbitrary user-selected parameters.

4. Elliptic-Curve Cryptography

Elliptic-curve cryptography (ECC) uses algebraic groups formed by points on an elliptic curve over a finite field. A simplified short-Weierstrass equation over a field of suitable characteristic is:

The parameters a and b define the curve. The cryptographic group consists of valid curve points together with a special identity element, often called the point at infinity. Security depends on the difficulty of the elliptic-curve discrete logarithm problem (ECDLP): given points G and Q = dG, finding the scalar d should be infeasible.

A private key is a randomly selected scalar d. The corresponding public key is:

where G is a standardized base point and scalar multiplication means repeated group addition. The operation is efficient even though reversing it is believed to be difficult.

ECDH and ECDSA

Elliptic-Curve Diffie–Hellman (ECDH) performs key agreement. Alice publishes A = aG and Bob publishes B = bG. Both derive:

Alice computes aB and Bob computes bA. The resulting point is then processed by a KDF.

Elliptic-Curve Digital Signature Algorithm (ECDSA) provides signatures. It requires a fresh, secret, uniformly generated per-signature nonce. Reuse or predictable generation of this nonce can reveal the private key. Deterministic nonce generation, as standardized in suitable specifications, can reduce dependence on runtime randomness, although implementation must still be correct.

Other modern signature systems, such as Ed25519, use different elliptic-curve constructions and are designed to provide simple, fast, and robust signing. Algorithm names should not be treated as interchangeable: ECDSA, EdDSA, ECDH, and X25519 have distinct formats, parameters, and protocol requirements.

Advantages and limitations

ECC provides security comparable to RSA with substantially smaller keys. Smaller keys reduce certificate size, bandwidth, storage, and often computational cost. This is valuable in mobile, embedded, and high-volume environments. ECC nevertheless requires careful point validation, secure implementation, correct serialization, and resistance to side-channel attacks. Curve selection must follow recognized standards; designing a new curve or parameter set without specialist review is inappropriate for ordinary engineering teams.

5. Hybrid Encryption and Secure Key Exchange

Asymmetric operations are relatively expensive and are poorly suited to encrypting large files or streams. Hybrid encryption combines asymmetric cryptography with symmetric authenticated encryption.

A typical design follows these steps:

1. The sender obtains and validates the recipient’s public key.
2. The sender generates a fresh random symmetric key.
3. The sender encrypts the data using an authenticated-encryption scheme such as AES-GCM or ChaCha20-Poly1305.
4. The sender protects the symmetric key using the recipient’s public-key encryption mechanism, or establishes it through authenticated DH/ECDH.
5. The recipient recovers or derives the symmetric key and verifies the authentication tag before releasing plaintext.

Authenticated encryption produces ciphertext and an authentication tag. Associated data, such as a protocol version or message identifier, may be authenticated without being encrypted. The receiver must verify the tag before accepting the message as valid.

A secure key exchange must address more than mathematical agreement. It should provide:

• Key authenticity: assurance that the peer’s public key belongs to the intended party;
• Key confirmation: evidence that both parties derived the same secret;
• Transcript binding: protection against negotiation and downgrade manipulation;
• Freshness: use of nonces or ephemeral keys to prevent replay;
• Forward secrecy: protection of historical sessions after long-term-key compromise;
• Key separation: different derived keys for encryption, authentication, and protocol directions;
• Explicit failure handling: no information-revealing error distinctions.

A KDF is often expressed abstractly as:

where Z is the shared secret, salt is optional or protocol-defined randomness, context identifies the session and purpose, and the outputs are separate keys. The exact KDF must be specified by the protocol; arbitrary hashing of a shared value is not a substitute for a reviewed key schedule.

6. Digital Signatures

A digital signature scheme consists of key generation, signing, and verification. To sign a message M, the signer computes a digest or structured representation and applies the private signing operation. A verifier uses the public key to determine whether the signature corresponds to the message and key.

In practice, a signature is generated over a precisely defined encoded message, often involving a cryptographic hash. If the hash function is collision resistant, it should be computationally difficult to find two different messages M and M′ such that:

Collision resistance alone does not provide all signature security, and a secure hash cannot compensate for a flawed signature scheme or poor key management.

Signatures provide:

• Integrity: changes to the signed data should cause verification failure;
• Authentication: possession of the private key is evidence of signing authority;
• Accountability: signatures can support audit and dispute resolution when identity binding and governance are reliable.

The term non-repudiation should be used cautiously. A mathematical signature does not by itself prove who controlled a private key, whether the key was shared, or whether the signer understood the transaction. Legal effect depends on jurisdiction, contracts, identity proofing, records, and operational controls.

Signature validation and certificates

A verifier must validate the signature, the certificate chain, validity periods, key usage, revocation status or revocation model, algorithm constraints, and the exact data that was signed. A certificate does not make every use of a key valid; key-usage extensions and application policy matter.

7. Cryptographic Assumptions and Attack Resistance

Algorithm selection should begin with the security assumption and the attack model, not with a brand name. Important assumptions include:

• factoring large integers is difficult for properly generated RSA moduli;
• discrete logarithms are difficult in approved finite groups;
• elliptic-curve discrete logarithms are difficult for approved curves;
• cryptographic hash functions resist relevant preimage and collision attacks;
• random-number generation produces unpredictable values;
• implementations do not leak exploitable information through timing, power, memory access, or errors.

Common attacks

Man-in-the-middle attack: An attacker substitutes public keys during unauthenticated key exchange. Certificates, authenticated transcripts, or verified fingerprints mitigate this risk.

Replay attack: An attacker retransmits a valid old message. Nonces, timestamps, sequence numbers, and stateful replay protection are required.

Chosen-ciphertext attack: An attacker submits selected ciphertexts and learns information from responses. CCA-secure padding, authenticated encryption, uniform errors, and strict protocol design are necessary.

Padding oracle: Different decryption errors reveal information about plaintext or padding. Constant behavior, authenticated designs, and carefully reviewed libraries reduce this risk.

Side-channel attack: Timing, cache behavior, power consumption, electromagnetic emissions, or faults reveal secret-dependent information. Constant-time implementations, blinding, isolation, and hardened hardware are relevant countermeasures.

Key-compromise impersonation: In some protocols, compromise of one party’s key may enable impersonation of others. Protocol analysis must examine this property explicitly.

Downgrade attack: An attacker forces participants to use weaker algorithms. Negotiation must authenticate the selected suite and disable obsolete options.

Quantum threat: A sufficiently capable cryptographically relevant quantum computer could threaten RSA and conventional DH/ECC through Shor’s algorithm. Symmetric cryptography and hash functions are affected differently, generally requiring parameter adjustments rather than complete replacement. Post-quantum key-establishment and signature standards are therefore becoming part of migration planning.

8. Performance and Algorithm Selection

Performance is multidimensional. It includes key-generation time, handshake latency, signing and verification throughput, message size, memory consumption, hardware acceleration, library maturity, and energy use. Security strength is also not identical to key length across algorithm families.

A practical selection process should ask:

1. Is the requirement confidentiality, integrity, authentication, key agreement, or several of these?
2. Is the environment constrained by bandwidth, latency, hardware, or legacy interoperability?
3. Is forward secrecy required?
4. What is the expected data lifetime and threat horizon?
5. Which algorithms are approved by organizational policy and applicable regulation?
6. Are libraries, hardware modules, certificate profiles, and monitoring available?
7. Is migration to post-quantum mechanisms required?

Algorithm agility is useful when it permits controlled migration, but excessive agility can create downgrade risk and testing complexity. A small, explicitly configured set of modern algorithms is generally safer than an unrestricted menu.

9. Applied Case: Protecting a Cloud Document-Exchange Service

Background

This illustrative case concerns a university research service that allows laboratories to upload confidential datasets and share them with external collaborators. The service must protect data in transit, support automated processing, authenticate users, and preserve audit evidence.

Problem

The initial design encrypts each file directly with RSA and accepts public keys supplied in email messages. It has high latency for large files, weak assurance that a key belongs to the stated recipient, and no reliable forward secrecy for interactive sessions.

Analysis

Direct RSA encryption is inefficient for large objects and introduces unnecessary exposure to padding and message-size constraints. Email-based key distribution is vulnerable to substitution. The service also needs to distinguish user authentication from file confidentiality and must support key rotation and revocation.

Approach and solution

The redesigned service uses authenticated TLS with ephemeral ECDH for session establishment and certificate-based server authentication. Each uploaded file receives a fresh random data-encryption key. The file is encrypted with an authenticated symmetric scheme. The data key is then wrapped for authorized recipients using a reviewed public-key mechanism or a managed key-encryption service.

User actions are recorded with digital signatures or trusted audit controls, depending on the legal and operational requirement. Public keys are distributed through a managed certificate or directory infrastructure rather than unverified email. The protocol binds file identifiers, recipient identities, algorithm identifiers, and version information as authenticated metadata.

Private keys are stored in a hardware-backed service where feasible. Rotation policies distinguish short-lived session keys, file-encryption keys, and long-term identity keys. Backups are encrypted, access is logged, and compromise procedures include revocation, re-encryption, and incident investigation.

Outcome

The architecture reduces bulk-encryption cost, improves authentication, supports forward secrecy for transport sessions, and makes key lifecycle responsibilities explicit. It also permits algorithm migration without redesigning the file format, provided that versioning and downgrade resistance are carefully implemented.

Learning points

The case demonstrates that cryptography is a system discipline. Selecting a strong primitive is insufficient when key distribution, identity binding, randomness, error handling, logging, lifecycle management, and recovery are neglected.

10. Governance, Ethics, and Contemporary Practice

Cryptographic systems affect privacy, safety, evidence, and institutional power. Organizations should apply data-minimization principles, restrict access to private keys, document lawful access procedures, and avoid designing hidden bypasses that weaken protection for all users. Key escrow may be justified in narrowly governed enterprise settings, but it creates concentrated risk and must be evaluated against threat models and legal obligations.

Security governance should define approved algorithms, minimum parameters, certificate profiles, rotation intervals, incident-response procedures, cryptographic inventories, and deprecation timelines. Developers should use well-maintained libraries rather than implementing RSA, ECC, padding, or signature encodings from scratch.

Artificial intelligence does not remove the need for cryptographic verification. AI systems may generate code, certificates, or configuration suggestions, but those outputs require expert review, automated testing, provenance controls, and policy validation. Conversely, AI-assisted analysis may help identify weak configurations or unusual key usage, but it should not be treated as a replacement for formal protocol analysis and secure key custody.

Best practices include:

• use standardized, peer-reviewed algorithms and parameter sets;
• prefer authenticated encryption and authenticated ephemeral key exchange;
• never use textbook RSA or unauthenticated DH in production;
• generate keys and nonces with a cryptographically secure random source;
• separate keys by purpose and context;
• validate certificates, algorithms, parameters, and transcript context;
• protect private keys with least privilege and hardware-backed controls where justified;
• test for side channels, downgrade paths, replay, malformed inputs, and error leakage;
• maintain a cryptographic inventory and plan for post-quantum migration;
• define recovery and revocation procedures before deployment.

Chapter Summary

Asymmetric cryptography uses related public and private keys to provide encryption, key agreement, and digital signatures. RSA relies principally on the difficulty of factoring large integers and requires secure padding such as OAEP for encryption and PSS for signatures. Diffie–Hellman establishes a shared secret but must be authenticated to resist man-in-the-middle attacks; ephemeral forms provide forward secrecy. ECC achieves strong security with smaller keys through elliptic-curve group operations, while ECDH, ECDSA, EdDSA, and related mechanisms serve different purposes.

Production systems normally use hybrid encryption: asymmetric mechanisms authenticate participants or protect a short symmetric key, while symmetric authenticated encryption protects bulk data. Digital signatures establish integrity and evidence of signing authority, but their legal and organizational meaning depends on identity management and key custody. Security depends on assumptions, randomness, implementation resistance, parameter choice, and lifecycle governance. Algorithm selection should balance security strength, performance, interoperability, operational maturity, threat horizon, and migration requirements.

Key Terms

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

Private key: Secret key used for decryption, signing, or authenticated agreement.

RSA: Public-key system based on the difficulty of factoring a composite modulus.

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

Elliptic-curve cryptography: Public-key cryptography based on elliptic-curve groups.

ECDH: Elliptic-curve Diffie–Hellman key-agreement mechanism.

ECDSA: Elliptic-curve digital-signature algorithm.

Ed25519: A modern elliptic-curve signature scheme.

Digital signature: Cryptographic evidence that binds data to a signing key.

Hybrid encryption: Combination of public-key techniques and symmetric bulk encryption.

Forward secrecy: Protection of past sessions after later compromise of long-term keys.

KDF: Key-derivation function that produces context-specific keys from secret material.

Certificate: Signed binding between an identity and a public key.

Certificate authority: Trusted issuer of public-key certificates.

Padding oracle: Attack exploiting informative decryption or padding errors.

Man-in-the-middle attack: Interception and substitution of communication between parties.

Cryptographic assumption: Hardness belief underlying a cryptographic construction.

Nonce: Value intended for one-time or freshness-sensitive use.

Authenticated encryption: Encryption that provides confidentiality and integrity together.

Algorithm agility: Controlled capability to migrate among approved cryptographic algorithms.

Review Questions

Short Answer Questions

1. What is the difference between a public key and a private key?
2. Why should textbook RSA not be used in a production system?
3. Why is unauthenticated Diffie–Hellman vulnerable to a man-in-the-middle attack?
4. What is forward secrecy?
5. What two principal security properties does a digital signature provide?

Long Answer Questions

1. Explain RSA key generation, encryption, decryption, and the role of OAEP and PSS.
2. Compare finite-field Diffie–Hellman and ECDH, including security assumptions and implementation concerns.
3. Describe a complete hybrid-encryption architecture for protecting a large file.
4. Explain how certificate validation contributes to secure key exchange.
5. Discuss the relationship among cryptographic assumptions, implementation security, and operational governance.

Analytical / Application Questions

1. A service currently encrypts multi-gigabyte files directly with RSA. Analyze the design and propose a secure replacement.
2. A protocol uses ephemeral ECDH but does not authenticate public keys. Identify the attack and redesign the protocol.
3. An organization must select between RSA-PSS, ECDSA, and Ed25519 for a new signing service. Develop a decision framework considering interoperability, performance, key management, and migration risk.

Multiple Choice Questions with Answers

Question 1

Which operation is the primary purpose of Diffie–Hellman?

A. Bulk data encryption

B. Digital certificate issuance

C. Shared-secret key agreement

D. Hash collision detection

Correct Answer: C. Shared-secret key agreement

Question 2

What security property is provided by ephemeral key exchange when long-term keys are later compromised?

A. Forward secrecy

B. Perfect anonymity

C. Data compression

D. Automatic non-repudiation

Correct Answer: A. Forward secrecy

Question 3

Which RSA encoding is intended for modern public-key encryption?

A. RSA-OAEP

B. Textbook RSA

C. RSA without padding

D. Raw modular exponentiation only

Correct Answer: A. RSA-OAEP

Question 4

What is the main role of authenticated encryption such as AES-GCM?

A. It replaces all certificate validation

B. It provides confidentiality and integrity for data

C. It generates public/private key pairs

D. It solves the elliptic-curve discrete logarithm problem

Correct Answer: B. It provides confidentiality and integrity for data

Question 5

In ECDH, if Alice’s private scalar is a and Bob’s public point is B = bG, what shared point does Alice compute?

A. a + B

B. aB

C. aG + bG

D. B^a in an RSA modulus

Correct Answer: B. aB

Question 6

Why must a digital signature scheme hash or otherwise precisely encode the signed message?

A. To make the private key public

B. To bind the signature to the exact message representation

C. To eliminate the need for authentication

D. To guarantee legal non-repudiation in every jurisdiction

Correct Answer: B. To bind the signature to the exact message representation

Question 7

Which attack commonly results when Diffie–Hellman public values are not authenticated?

A. Man-in-the-middle attack

B. Birthday scheduling attack only

C. Denial of storage attack

D. Compression attack

Correct Answer: A. Man-in-the-middle attack

Question 8

What is the principal security assumption underlying conventional RSA?

A. The difficulty of factoring a properly generated large composite integer

B. The impossibility of modular arithmetic

C. The secrecy of the public key

D. The uniqueness of every hash output

Correct Answer: A. The difficulty of factoring a properly generated large composite integer

Question 9

Why is hybrid encryption preferred for large files?

A. Asymmetric algorithms are generally efficient for unlimited bulk data

B. It uses symmetric encryption for efficient bulk protection and public-key methods for key protection

C. It avoids all need for random numbers

D. It makes authentication unnecessary

Correct Answer: B. It uses symmetric encryption for efficient bulk protection and public-key methods for key protection

Question 10

Which factor is especially critical for ECDSA security?

A. Reusing the same signing nonce

B. Publishing the public key

C. Using a certificate chain

D. Hashing the message before signing

Correct Answer: A. Reusing the same signing nonce