Public-Key Cryptography and Digital Signatures

Introduction and Context

Public-key cryptography is a foundational technology for secure digital communication. Unlike symmetric cryptography, which uses one shared secret key for encryption and decryption, public-key systems use a mathematically related key pair: a public key that may be distributed openly and a private key that must remain secret. This separation enables secure communication between parties who have never previously shared a secret, as well as authentication, integrity protection and non-repudiation-oriented evidence.

Blockchain systems depend heavily on public-key cryptography. A blockchain address is commonly derived from a public key, while transactions are authorized with a digital signature generated using the corresponding private key. Consensus nodes verify signatures without learning the private key. Public-key infrastructure extends this model by binding public keys to identities through certificates and trust authorities.

The security of these systems does not arise from secrecy of the algorithms. It depends on the computational difficulty of particular mathematical problems, secure key generation, correct protocol design, authenticated public-key distribution and protection against implementation attacks.

Learning Objectives

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

1. Explain the purpose and operation of public-key cryptography and key exchange.
2. Describe RSA, elliptic-curve cryptography and their security assumptions.
3. Distinguish encryption, authentication, integrity and digital signatures.
4. Generate the logic of signing and signature verification.
5. Explain certificates, certificate authorities and public-key infrastructure.
6. Identify common implementation attacks and recommend appropriate controls.
7. Apply these concepts to blockchain transaction authorization and key management.

1. Public-Key Cryptography

1.1 Core idea

A public-key cryptosystem generally consists of three algorithms:

• Key generation produces a public key and a private key.
• Encryption uses the recipient’s public key to protect a message.
• Decryption uses the recipient’s private key to recover the message.

For digital signatures, the operations are different:

• Signing uses the signer’s private key.
• Verification uses the signer’s public key.

Encryption provides confidentiality; signatures primarily provide authenticity, integrity and evidence that a particular private key was used. A signature does not automatically encrypt the signed message.

A secure public-key scheme should satisfy the following practical requirements:

• Computing the public key from the private key is easy.
• Valid encryption or signing is efficient.
• Reversing the operation without the private key is computationally infeasible.
• Key generation produces unpredictable private keys.
• The public key can be authenticated or obtained through a trustworthy channel.

The word “infeasible” is important. Security normally means that the cost of attack is beyond the resources and time available to an adversary, not that reversal is mathematically impossible.

1.2 Hybrid encryption

Public-key encryption is computationally more expensive than symmetric encryption and is therefore usually used to protect a short symmetric session key. The resulting design is called hybrid encryption:

1. The sender generates a random session key.
2. The message is encrypted with an authenticated symmetric cipher such as AES-GCM or ChaCha20-Poly1305.
3. The session key is protected using the recipient’s public key or an established key-agreement protocol.
4. The recipient uses the private key to recover the session key and then decrypts and authenticates the message.

This design combines public-key convenience with symmetric-key efficiency. In modern systems, authenticated encryption is preferred because confidentiality without integrity permits message modification attacks.

2. Key Exchange and Key Agreement

Key exchange allows two parties to establish a shared secret over an untrusted network. The classic example is Diffie–Hellman key agreement.

Let p be a large prime and g a generator of a suitable subgroup modulo p. Alice chooses a private random value a and publishes:

Bob chooses a private random value b and publishes:

Alice computes:

Bob computes:

Because:

both obtain the same shared value. Here, p and g are public, while a and b are private. The security assumption is that an observer who knows p, g, A and B cannot efficiently compute g^{ab} or recover a or b. This is related to the discrete logarithm problem.

Plain Diffie–Hellman does not authenticate the parties. An active attacker can intercept the exchange and establish one shared key with Alice and another with Bob. This is the man-in-the-middle attack. Authentication is therefore added using certificates, digital signatures, pre-shared keys or an authenticated protocol such as TLS.

Ephemeral Diffie–Hellman uses fresh private values for each session. When combined with authentication, it provides forward secrecy: compromise of a long-term private key does not normally reveal past session keys. Elliptic-curve Diffie–Hellman (ECDH) provides the same conceptual function using elliptic-curve groups with substantially smaller keys than traditional finite-field systems for comparable security levels.

3. RSA

3.1 Mathematical foundation

RSA security is associated with the difficulty of factoring a large composite integer. Select two large distinct primes p and q and calculate:

Compute Euler’s totient for distinct primes:

Choose a public exponent e such that:

Then calculate d, the modular multiplicative inverse of e modulo φ(n):

The public key is (n, e), and the private key contains d together with protected information about p and q. In practice, RSA uses standardized padding schemes rather than applying the raw exponentiation directly to messages.

For textbook notation, encryption of a suitably encoded message m is:

Decryption is:

The variables m and c must represent integers in the permitted range, and real implementations must use secure encoding and padding. Raw RSA is insecure because it is deterministic and malleable.

3.2 Worked miniature example

This example is educational only; its numbers are far too small for security. Let p = 5 and q = 11. Then n = 55 and φ(n) = 4 × 10 = 40. Choose e = 3, since gcd(3, 40) = 1. The inverse of 3 modulo 40 is d = 27 because 3 × 27 = 81 ≡ 1 mod 40.

For m = 7:

Decryption gives:

The example demonstrates the modular relationship, not an implementation recommendation.

3.3 Correct RSA use

For encryption, RSA-OAEP is the established padding approach in many standards. For signatures, RSA-PSS is preferred over older deterministic approaches because it provides a randomized encoding and stronger modern security properties. RSA keys must be sufficiently large, generated with a cryptographically secure random number generator and protected against factor leakage.

RSA has practical disadvantages: relatively large keys, expensive operations compared with elliptic-curve alternatives and vulnerability to poor padding, weak randomness, side channels and incorrect parameter validation.

4. Elliptic-Curve Cryptography

4.1 Group structure

Elliptic-curve cryptography uses points on a curve over a finite field. A commonly used form over a prime field is:

Here, x and y are coordinates, a and b are curve parameters and p is a large prime defining the field. The curve must be non-singular, which requires that the discriminant condition is satisfied; for the short Weierstrass form, this means 4a³ + 27b² is not congruent to zero modulo p.

The curve points, together with a special point at infinity, form a mathematical group under a defined point-addition operation. A private key d is a randomly selected scalar. A public key is computed as:

where G is a standardized base point and dG means adding G to itself d times. Given d and G, calculating Q is efficient. Recovering d from Q and G is believed to be computationally infeasible for properly selected curves; this is the elliptic-curve discrete logarithm problem.

4.2 ECDH and ECDSA

In ECDH, Alice publishes A = aG and Bob publishes B = bG. Alice computes aB = abG, while Bob computes bA = abG. Both derive the same shared secret and pass it through a key-derivation function before using it as a symmetric key.

ECDSA is a signature scheme. Conceptually, the signer hashes a message, uses a private scalar and a fresh secret nonce to create a signature pair, and the verifier uses the public point to check the relation. The exact standardized equations involve modular inverses and curve operations; implementations should use reviewed libraries rather than hand-coded arithmetic.

Nonce security is critical. Reuse or predictable generation of an ECDSA nonce can reveal the private key. Deterministic nonce generation, as specified in appropriate standards, can reduce dependence on runtime randomness, although the implementation must still be correctly designed.

4.3 Key-size comparison

Key sizes are not directly comparable across algorithms. Roughly, a 256-bit elliptic-curve key is commonly regarded as offering security comparable to a 3072-bit RSA key, although exact equivalence depends on the security model, algorithm and standard. Organizations should follow current recommendations from recognized standards bodies rather than selecting sizes solely from informal comparisons.

Blockchain platforms commonly use elliptic-curve signatures because compact keys and signatures reduce transaction size. Different platforms use different curves and signature formats; interoperability must never be assumed.

5. Digital Signatures

A digital signature scheme consists of key generation, signing and verification. For message M and private key sk:

A verifier uses the public key pk to evaluate:

A secure signature should provide:

• Integrity: modification of M causes verification to fail.
• Authentication: a valid signature indicates control of the corresponding private key, subject to correct key ownership assumptions.
• Public verifiability: anyone with the public key can verify the signature.
• Existential unforgeability under chosen-message attack: an attacker should not be able to create a valid signature on a new message, even after obtaining signatures on selected messages.

Signatures are normally computed over a cryptographic hash rather than the complete message. If H is a collision-resistant hash function, the signed representative is derived from H(M), together with scheme-specific encoding. Collision resistance is necessary but not sufficient: the signature scheme and encoding must also be secure.

A signature does not prove that a human personally approved an action. It proves possession or use of a private key under the protocol’s assumptions. Legal attribution requires identity binding, key-control evidence, reliable records and applicable law.

Verification process

A professional verification process should:

1. Parse the signature and public key according to the exact format.
2. Validate key parameters and reject invalid or non-canonical encodings.
3. Reconstruct the signed data exactly, including domain, network, version and transaction fields.
4. Hash the reconstructed data using the specified algorithm.
5. Verify the signature using a vetted cryptographic library.
6. Check certificate status or blockchain-specific key and account rules.
7. Enforce authorization, expiry, replay protection and business constraints.

A mathematically valid signature is not necessarily an authorized transaction. The verifier must check context and policy as well as cryptographic validity.

6. Certificates and Public-Key Infrastructure

A public key by itself does not identify its owner. A certificate binds a subject identity to a public key through a digitally signed data structure. In the X.509 model, a certificate commonly includes:

• Subject identity
• Issuer identity
• Subject public key and algorithm
• Validity period
• Serial number
• Key-usage and extended-key-usage constraints
• Policy information
• Issuer signature

A certificate authority (CA) signs the certificate with its private key. A relying party verifies the CA signature and constructs a trust chain to a configured trust anchor, commonly a root CA. Intermediate CAs reduce operational exposure of root keys.

A simplified trust process is:

Figure: A simplified certificate chain and relying-party validation process.

Certificate validation includes signature-chain verification, validity dates, name matching, key-usage constraints, policy checks and revocation status. Revocation may be checked through certificate revocation lists or the Online Certificate Status Protocol. Operational failures often arise from expired certificates, incomplete intermediate chains, incorrect hostname validation or failure to process revocation information.

In blockchain ecosystems, certificates may be used for enterprise identity, permissioned membership, API authentication and secure administration. Public blockchains more commonly use address derivation and decentralized verification rather than CA-issued identity certificates.

7. Blockchain Applications

A blockchain transaction typically contains an operation, a network or chain identifier, a nonce or sequence value and one or more signatures. The transaction is serialized according to a canonical format, hashed and signed. Nodes verify the signature and then evaluate state-transition rules.

Important distinctions include:

• An address is usually an encoding or derivation of a public key or script, not the private key itself.
• A valid signature authorizes only the exact message that was signed.
• Replay protection requires a nonce, chain identifier, domain separator or equivalent mechanism.
• Multisignature and threshold schemes distribute authority and reduce dependence on one key.
• Hardware wallets and secure enclaves can keep private keys away from general-purpose applications.

Blind signing is dangerous: a wallet may display insufficient information for a user to understand the exact transaction or smart-contract authorization. Human-readable transaction previews, domain separation and explicit contract warnings reduce this risk.

8. Common Implementation Attacks

Weak randomness

Private keys and nonces must be generated with a cryptographically secure random number generator. Predictable randomness can make private keys searchable or expose signing nonces.

Nonce reuse

For ECDSA, reuse of the same nonce across two different messages can reveal the private key. This is one of the most serious historical implementation failures.

Padding-oracle attacks

If an application reports different errors or timing for different RSA padding failures, an attacker may gradually recover plaintext. Implementations should use standardized schemes, uniform error handling and carefully reviewed libraries.

Timing and other side channels

Execution time, cache behavior, power consumption and electromagnetic emissions can leak secret-dependent information. Constant-time algorithms, blinding, hardware protections and isolation reduce exposure.

Invalid-curve and public-key validation attacks

Elliptic-curve implementations must validate received points and use approved curve parameters. Failure can cause private information to be exposed through malicious points.

Signature malleability and encoding errors

Some signature formats permit multiple encodings of an apparently equivalent signature. Canonical encoding and strict parsing prevent transaction identifiers or authorization checks from being manipulated.

Hash and serialization ambiguity

Different interpretations of a transaction can lead one system to sign a different byte sequence from another. Canonical serialization, domain separation and explicit versioning are essential.

Key theft and supply-chain compromise

Malware, phishing, browser extensions, compromised dependencies and leaked backups can expose private keys. Cryptographic strength cannot compensate for poor key custody.

Trust-store and certificate errors

Accepting any certificate, disabling hostname verification or failing open when revocation checks fail defeats PKI. Trust stores must be governed, monitored and updated.

Quantum threat

Large-scale fault-tolerant quantum computers could threaten RSA and elliptic-curve systems through Shor’s algorithm. Symmetric cryptography is affected differently, generally requiring larger key sizes rather than complete replacement. Organizations should inventory cryptographic dependencies, use crypto-agile designs and monitor post-quantum standardization.

9. Case Study: Protecting a Blockchain Treasury

Background

This illustrative case concerns a digital-asset organization whose treasury was controlled by one software wallet. The private key was stored in an encrypted file on an employee workstation.

Problem

An attacker gained access through malware and extracted the key after the employee approved a transaction. The signature was mathematically valid, so network nodes accepted the transfer. The organization had no independent approval policy, transaction delay or recovery arrangement.

Analysis

The failure was not a weakness in elliptic-curve mathematics. It was a governance and key-management failure. A single key represented excessive authority, user confirmation did not clearly display the destination, and backups were not tested.

Approach and solution

The organization adopted a threshold multisignature arrangement requiring three of five authorized keys. Keys were distributed across hardware devices and geographic locations. Transaction policies imposed daily limits, a time delay for large transfers and independent review. The wallet software displayed decoded transaction details and included chain-specific replay protection. Key-generation ceremonies were documented, backups were encrypted and recovery exercises were performed.

Outcome

Compromise of one device no longer enabled immediate transfer of treasury assets. Monitoring detected unusual proposals, while the delay allowed cancellation. The organization also separated operational, administrative and emergency-recovery roles.

Learning points

Cryptographic verification answers whether a signature is valid; governance determines whether the signer was authorized. Strong systems combine sound algorithms, secure implementations, distributed authority, clear user interfaces, monitoring and tested recovery procedures.

10. Best Practices and Professional Implications

Use standardized, actively maintained cryptographic libraries rather than implementing RSA or elliptic-curve arithmetic from scratch. Select algorithms and parameters according to current standards. Separate signing keys from encryption keys and from administrative credentials. Protect private keys with hardware-backed storage where the threat model justifies it.

Use authenticated encryption for confidential data, authenticated key exchange for sessions and forward secrecy for long-lived communications. Apply strict input validation, canonical serialization, domain separation and replay protection. Test failure paths as carefully as successful paths.

Organizations should maintain a cryptographic inventory describing algorithms, key owners, expiry dates, dependencies and migration plans. Key rotation and revocation procedures must be practical before an incident occurs. Access should follow least privilege, and sensitive operations should require independent authorization.

Ethically and legally, developers must avoid implying that a valid signature proves a person’s intention in every circumstance. Identity binding, consent, accessibility, data protection and incident notification remain organizational responsibilities. In regulated environments, certificate policies, electronic-signature laws, custody requirements and audit obligations may apply.

Chapter Summary

Public-key cryptography uses related public and private keys to support secure communication, authentication and signatures. Diffie–Hellman and ECDH establish shared secrets but require authentication to prevent man-in-the-middle attacks. RSA relies on modular arithmetic and the practical difficulty of factoring large integers; secure padding such as OAEP and PSS is essential. Elliptic-curve systems use group operations and the elliptic-curve discrete logarithm problem, providing compact keys and signatures.

Digital signatures are generated with private keys and verified with public keys. They protect integrity and authenticate control of a key, but they do not independently establish human identity or authorization. Certificates bind keys to identities through certificate authorities, while PKI provides trust chains, policy controls and revocation mechanisms. Blockchain transactions use signatures together with canonical serialization, nonces and network-specific rules.

Weak randomness, nonce reuse, padding oracles, side channels, invalid-curve attacks, malleability, serialization ambiguity and key theft are major practical threats. Secure deployment therefore requires more than choosing a strong algorithm: it requires sound libraries, secure key custody, governance, monitoring, recovery planning and crypto-agile architecture.

Key Terms

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

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

Key exchange: A protocol for establishing secret material over a network.

Diffie–Hellman: A public-key key-agreement method based on discrete logarithms.

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

RSA: A public-key algorithm associated with modular arithmetic and integer factoring.

Elliptic-curve cryptography: Cryptography based on groups of elliptic-curve points.

ECDH: Elliptic-curve Diffie–Hellman key agreement.

ECDSA: Elliptic Curve Digital Signature Algorithm.

Digital signature: A private-key-generated value that can be publicly verified.

Hash function: A function mapping data to a fixed-length digest.

Nonce: A value intended for controlled, usually single-use, protocol use.

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

Certificate authority: An entity that issues and signs certificates.

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

Trust anchor: A configured key or root certificate accepted as authoritative.

Replay attack: Reuse of a previously valid message or transaction.

Side-channel attack: Extraction of secrets from physical or operational leakage.

Multisignature: Authorization requiring signatures from multiple keys.

Crypto agility: The ability to replace cryptographic algorithms without redesigning the whole system.

Review Questions

Short Answer Questions

1. What is the principal difference between public-key and symmetric cryptography?
2. Why does unauthenticated Diffie–Hellman permit a man-in-the-middle attack?
3. What security problem is associated with RSA’s raw, unpadded form?
4. What does a digital signature prove, and what does it not necessarily prove?
5. What is the function of a certificate authority in PKI?

Long Answer Questions

1. Explain RSA key generation and encryption using modular arithmetic, and discuss why real systems require padding.
2. Compare RSA and elliptic-curve cryptography in terms of mathematical foundations, key size, performance and implementation risks.
3. Describe the complete process by which a relying party validates an X.509 certificate chain.
4. Explain how digital signatures are used in blockchain transaction authorization, including hashing, serialization and replay protection.
5. Discuss a comprehensive key-management policy for an organization holding digital assets.

Analytical / Application Questions

1. A blockchain wallet reports a valid signature, but the transaction was sent to an unintended contract. Analyze how cryptographic validity, user authorization and interface design differ, and propose controls.
2. An ECDSA service generated two signatures using the same nonce. Explain the likely security consequence and design a remediation plan.
3. Design a five-year migration strategy for an organization that must prepare RSA- and elliptic-curve-based systems for possible post-quantum threats while maintaining interoperability.

Multiple Choice Questions with Answers

Question 1

Which operation normally uses a private key in a digital-signature system?

A. Generating a certificate chain

B. Creating the signature

C. Encrypting a public key

D. Publishing a trust anchor

Correct Answer: B. Creating the signature

Question 2

What is the main purpose of authenticated key exchange?

A. To eliminate the need for hashing

B. To provide secrecy while also authenticating the communicating parties

C. To make private keys publicly recoverable

D. To replace all symmetric encryption

Correct Answer: B. To provide secrecy while also authenticating the communicating parties

Question 3

In RSA, which condition is required when selecting the public exponent e?

A. e must equal φ(n)

B. e must be divisible by φ(n)

C. gcd(e, φ(n)) must equal 1

D. e must equal one of the prime factors of n

Correct Answer: C. gcd(e, φ(n)) must equal 1

Question 4

What mathematical problem is most closely associated with standard elliptic-curve cryptography?

A. Integer sorting

B. Elliptic-curve discrete logarithm

C. Polynomial interpolation only

D. Symmetric-key collision search

Correct Answer: B. Elliptic-curve discrete logarithm

Question 5

Why is ECDSA nonce reuse dangerous?

A. It makes certificates expire immediately

B. It can reveal the private signing key

C. It prevents public-key distribution

D. It changes the elliptic curve into RSA

Correct Answer: B. It can reveal the private signing key

Question 6

What does a certificate primarily bind together?

A. A password and a database record

B. An identity and a public key

C. A private key and its backup password

D. A hash function and a symmetric cipher

Correct Answer: B. An identity and a public key

Question 7

Which feature helps prevent blockchain transaction replay across networks?

A. Removing the transaction nonce

B. Using a chain identifier or domain separator

C. Publishing the private key

D. Disabling signature verification

Correct Answer: B. Using a chain identifier or domain separator

Question 8

Which attack exploits different error behavior during RSA decryption?

A. Padding-oracle attack

B. Routing-loop attack

C. SQL aggregation attack

D. Certificate compression attack

Correct Answer: A. Padding-oracle attack

Question 9

What is the primary benefit of forward secrecy?

A. Past session traffic remains protected if a long-term key is later compromised

B. Public keys never need certificates

C. Signatures become shorter than hashes

D. It makes random-number generation unnecessary

Correct Answer: A. Past session traffic remains protected if a long-term key is later compromised

Question 10

Which statement best describes a valid digital signature?

A. It always proves the signer’s legal identity and intent

B. It proves that the signature verifies under a public key and that the corresponding private key was used, subject to system assumptions

C. It guarantees that the message was encrypted

D. It eliminates the need for authorization policies

Correct Answer: B. It proves that the signature verifies under a public key and that the corresponding private key was used, subject to system assumptions