After completing this tutorial, you should be able to:
Digital signatures are the public-key equivalent of handwritten signatures. They provide a way to verify the authenticity and integrity of a message or document, and they ensure that the signer cannot later deny having signed it—a property known as non-repudiation. Digital signatures are fundamental to modern security systems, enabling secure software distribution, electronic commerce, legal documents, and authentication protocols such as TLS.
Unlike MACs, which use symmetric keys and do not provide non-repudiation, digital signatures use asymmetric cryptography. A signer uses their private key to create a signature, and anyone with the corresponding public key can verify it. This binding between a public key and an identity is achieved through Public Key Infrastructure (PKI), which issues digital certificates that attest to the ownership of a public key by a named entity.
In this tutorial, we explore digital signatures in depth. We begin by defining their properties and security requirements. We then examine the major signature schemes: RSA signatures, DSA, ECDSA, and EdDSA. We discuss the importance of padding schemes and hash functions. We then introduce PKI, covering X.509 certificates, Certificate Authorities (CAs), Registration Authorities (RAs), certificate validation, and revocation mechanisms (CRLs and OCSP). We also discuss trust models and the challenges of PKI deployment.
The tutorial concludes with real-world applications and case studies that illustrate the importance and vulnerabilities of digital signatures and PKI.
In Tutorials 2.11–2.14, we studied public-key cryptography, RSA, Diffie-Hellman, and ECC. This tutorial builds on those algorithms to provide digital signatures. It also introduces PKI, which is essential for using public keys in practice. Tutorial 2.16 will cover cryptographic protocols and applications that rely on digital signatures and PKI.
Digital signatures are typically created by hashing the message and then signing the hash. This is more efficient than signing the entire message and allows for signing large documents.
Figure 1: Digital signature creation and verification.
A secure digital signature scheme must satisfy the following properties:
It must be computationally infeasible for an adversary to create a valid signature for a message without the private key.
Once a signature is verified, the signer cannot deny having signed the message.
Any modification to the message will cause the signature verification to fail.
The adversary cannot generate a valid signature for any new message, even if they have seen signatures for other messages.
The scheme remains secure even if the adversary can obtain signatures for messages of their choice.
RSA can be used for both encryption and signatures. The RSA signature scheme is similar to encryption but with the roles of the keys reversed.
1. Compute hash h = Hash(M). 2. Encode h using a padding scheme (e.g., PSS or PKCS#1 v1.5). 3. Compute signature σ = hd mod n, where d is the private key. 4. Output σ.
1. Compute h = Hash(M). 2. Compute h' = σe mod n, where e is the public exponent. 3. Decode h' and compare to h (with padding check). 4. Accept if equal; reject otherwise.
DSA is a U.S. government standard for digital signatures (FIPS 186). It is based on the discrete logarithm problem in a finite field.
1. Compute hash h = Hash(M). 2. Generate random ephemeral key k ∈ [1, q−1]. 3. Compute r = (gk mod p) mod q. If r = 0, choose new k. 4. Compute s = k−1 (h + x·r) mod q. If s = 0, choose new k. 5. Output signature (r, s).
1. Check 0 < r < q and 0 < s < q. 2. Compute h = Hash(M). 3. Compute w = s−1 mod q. 4. Compute u₁ = h·w mod q, u₂ = r·w mod q. 5. Compute v = (gu1 · yu2 mod p) mod q. 6. Accept if v = r; reject otherwise.
ECDSA is the elliptic curve variant of DSA. It provides the same security as DSA with much smaller key sizes.
1. Compute hash h = Hash(M). 2. Generate random ephemeral key k ∈ [1, n−1]. 3. Compute R = [k]P = (x₁, y₁). If R = O, choose new k. 4. Compute r = x₁ mod n. If r = 0, choose new k. 5. Compute s = k−1 (h + d·r) mod n. If s = 0, choose new k. 6. Output signature (r, s).
1. Check 0 < r < n and 0 < s < n. 2. Compute h = Hash(M). 3. Compute w = s−1 mod n. 4. Compute u₁ = h·w mod n, u₂ = r·w mod n. 5. Compute V = [u₁]P + [u₂]Q. 6. If V = O, reject. 7. Let x-coordinate of V be x₁. Accept if x₁ mod n == r; reject otherwise.
EdDSA is a modern digital signature scheme designed by Daniel J. Bernstein, using the Edwards curve Ed25519. It provides high security, excellent performance, and resistance to side-channel attacks.
1. Compute deterministic nonce k = H(d || M) mod n. 2. Compute R = [k]P. 3. Compute h = H(R || A || M) where A is the public key. 4. Compute s = k + h·d mod n. 5. Output signature (R, s).
1. Check that R is a valid point and s is in range. 2. Compute h = H(R || A || M). 3. Check that [s]P = R + [h]A. 4. Accept if valid.
EdDSA is used in many modern protocols, including TLS 1.3, SSH, and OpenPGP.
The PKCS#1 v1.5 signature padding format is:
0x00 || 0x01 || PS || 0x00 || ASN.1(hash)
where PS is a string of 0xFF bytes (to make the block length equal to the modulus size).
Vulnerability: PKCS#1 v1.5 is not provably secure; it is vulnerable to some attacks (e.g., Bleichenbacher's attack on RSA encryption, though less severe for signatures). However, it is widely used in legacy systems.
PSS is a modern padding scheme for RSA signatures, defined in PKCS#1 v2.1. It provides provable security against existential forgery attacks.
PSS uses:
Advantage: PSS is provably secure in the random oracle model.
A digital signature is only as trustworthy as the binding between the public key and the identity. PKI provides this binding through digital certificates issued by trusted entities.
Figure 2: Public Key Infrastructure architecture.
The most common certificate format is X.509, defined by ITU-T and used in TLS, S/MIME, and many other protocols.
| Field | Description |
|---|---|
| Version | X.509 version (1, 2, or 3) |
| Serial Number | Unique identifier assigned by the CA |
| Signature Algorithm | Algorithm used by the CA to sign the certificate (e.g., SHA-256 with RSA) |
| Issuer | Distinguished Name (DN) of the CA |
| Validity | Not Before and Not After dates |
| Subject | DN of the certificate holder |
| Subject Public Key Info | The public key and its algorithm |
| Extensions | v3 extensions (e.g., Subject Alternative Name, Key Usage, Basic Constraints) |
| Signature | Digital signature of the CA over the certificate |
A certificate chain starts from the end-entity certificate and goes up through intermediate CA certificates to a root CA certificate, which is trusted (the trust anchor).
Validation involves:
The end entity generates a public/private key pair. The private key is kept secret; the public key is submitted to the CA.
The end entity sends a CSR containing the public key, identity information, and a signature (proving possession of the private key).
The RA verifies the identity of the requester (e.g., domain validation, organization validation, extended validation).
The CA signs the certificate and publishes it.
The end entity installs the certificate on their server or device.
Certificates have a validity period (e.g., 1-2 years). Before expiry, the entity obtains a new certificate.
If the private key is compromised or the certificate is no longer valid, the CA revokes it.
A CRL is a list of revoked certificates, signed by the CA and published periodically. It contains the serial numbers of revoked certificates and the revocation date.
Limitations: CRLs are large, may be out of date (periodic updates), and require downloading the entire list.
OCSP allows a relying party to query the CA (or an OCSP responder) for the revocation status of a specific certificate in real time.
Advantage: Timely and lightweight (only one certificate per query).
Security: OCSP responses must be signed by the CA or a trusted responder.
To reduce load on OCSP servers and improve privacy, the server includes an OCSP response in the TLS handshake (stapling). This allows the client to verify the certificate's status without contacting the CA directly.
A newer approach that uses a compact Bloom filter to efficiently distribute revocation information.
Root CA → Intermediate CA → End Entity. This is the standard model used in web PKI. Trust is anchored in a root CA whose public key is pre-installed in browsers and operating systems.
Used in PGP/GPG. Users sign each other's public keys, creating a distributed network of trust. There is no central authority; trust is transitive.
Parties manually exchange and verify each other's public keys (e.g., SSH with known_hosts).
A CA that cross-certifies with other CAs to enable inter-domain trust.
TLS uses digital certificates for server authentication (and optionally client authentication). The server presents a certificate signed by a CA; the client verifies the certificate chain.
S/MIME uses X.509 certificates to sign and encrypt emails. PGP uses a web of trust for key verification.
Software developers sign their code with a digital signature. Users (or operating systems) verify the signature to ensure the software comes from the claimed publisher and has not been tampered with.
Digital signatures are used to sign legal documents, contracts, and PDFs. Standards include PDF signatures (based on X.509) and electronic signatures (e.g., eIDAS in Europe).
SSH uses public keys (often self-signed) for user authentication, sometimes with certificates for host authentication. VPNs (IPsec) use certificates for authentication.
Bitcoin and other cryptocurrencies use ECDSA signatures to authorize transactions.
DigiNotar, a Dutch CA, was compromised, leading to the issuance of fraudulent certificates for high-profile domains including google.com. Attackers used these certificates to perform man-in-the-middle attacks against Iranian users. The incident led to the removal of DigiNotar's root certificate from all major browsers and the eventual bankruptcy of the company.
Lesson: CA security is critical; a single compromised CA can undermine trust in the entire PKI.
Flame used an MD5 collision to forge a Microsoft certificate, allowing it to appear as legitimate Windows Update software. This demonstrated that weak hash functions in signature schemes can have severe consequences.
Heartbleed exposed private keys on many servers. The affected certificates had to be revoked. The incident highlighted the importance of timely revocation (CRL/OCSP) and the challenges of large-scale revocation.
With the SHAttered collision attack, SHA-1 was broken. Major browsers and CAs stopped issuing SHA-1 certificates, migrating to SHA-256. This illustrates the need for agility in signature algorithms.
Using RSA with n=391, e=7, d=151, sign a message with hash h=55 and verify the signature.
Sign: σ = 55151 mod 391. Compute using modular exponentiation: 552=3025 mod391=278; 554=2782=77284 mod391=... We can shortcut: Since d is large, it's easier to compute with square-and-multiply. The result is σ = 55151 mod 391. (In practice, we'd use a calculator or code.)
Verify: h' = σ7 mod 391. Since we used the private key, h' should equal 55, confirming the signature is valid.
Explain the steps a browser takes to validate a server certificate chain. What happens if an intermediate certificate is missing?
The browser: 1) Verifies the signature on the server certificate using the issuer's public key; 2) Checks the validity period; 3) Checks revocation status; 4) Builds the chain up to a trusted root CA; 5) Verifies each signature in the chain; 6) Checks the certificate's Key Usage extensions.
If an intermediate certificate is missing, the browser may fail to build the chain. Some browsers will attempt to download the missing intermediate using the Authority Information Access (AIA) extension in the certificate.
Show that if the same ephemeral key k is used for two ECDSA signatures (r, s₁) and (r, s₂), the private key d can be recovered. Derive the formula.
Given s₁ = k⁻¹(h₁ + d·r) mod n and s₂ = k⁻¹(h₂ + d·r) mod n.
Subtract: s₁ − s₂ = k⁻¹(h₁ − h₂) mod n → k = (h₁ − h₂)/(s₁ − s₂) mod n.
Then d = (s₁·k − h₁) / r mod n.
Compare hierarchical trust (web PKI) and the web of trust (PGP). What are the advantages and disadvantages of each?
Hierarchical: Centralized, easier for users (trust is anchored in pre-installed root CAs), but single point of failure (a compromised CA can break trust).
Web of Trust: Decentralized, no single point of failure, but requires users to manually manage trust relationships and is more complex.
Explain what OCSP stapling is and why it improves performance and privacy in TLS.
OCSP stapling allows the server to obtain an OCSP response from the CA and include it in the TLS handshake (as a "staple") to the client. This avoids the client making a separate OCSP query, reducing latency and hiding the client's browsing history from the CA.
Research the DigiNotar CA compromise (2011). Write a 500-word report covering:
Complete answer would describe the CA compromise, issuance of fraudulent certificates for google.com and other domains, the use in man-in-the-middle attacks in Iran, the removal of DigiNotar's root from browsers, and the subsequent improvements in CA security (e.g., Certificate Transparency).
Write a 500-word report comparing RSA signatures and ECDSA. Address:
Complete answer would compare key sizes (e.g., 3072-bit RSA vs 256-bit ECC), performance (RSA signing is slower, ECDSA verification is fast), security (both based on hard problems; ECDSA has smaller keys), padding (RSA uses PSS, ECDSA has built-in randomness), and adoption (both are used; ECDSA is preferred in TLS 1.3).
Obtain the certificate chain of a website (e.g., using OpenSSL). Describe the chain, including the root, intermediate, and end-entity certificates. Verify the signatures and identify the algorithms used.
Complete answer would include the command used (e.g., openssl s_client -connect example.com:443 -showcerts), the output showing the chain, and analysis of the root CA, intermediate CA, and server certificate. It would note the signature algorithms (e.g., RSA-SHA256, ECDSA-SHA256), validity dates, and key sizes.
Design a PKI for a medium-sized organization with 1000 employees, using internal CA and client certificates. Specify:
Complete answer would propose an offline root CA, an online issuing CA, automated certificate enrollment using SCEP or EST, CRL distribution via HTTP, and use of certificates for authentication (TLS client certificates) and signing (S/MIME). Private keys would be stored on smart cards or HSMs.
Implement RSA signature generation and verification using the PSS padding scheme (or use a library that supports it). Test with a sample message. Report on:
Complete answer would include code (e.g., using OpenSSL or a language library), sample key generation, signing a message, verifying the signature, and a discussion of the salt length and MGF. It would note that PSS signatures are randomized, so two signatures of the same message differ.
This tutorial has provided a comprehensive examination of digital signatures and the Public Key Infrastructure (PKI) that supports them. We began by defining digital signatures and their core properties: authentication, integrity, and non-repudiation. We explored the major signature schemes—RSA signatures (with PSS padding), DSA, ECDSA, and EdDSA—each with its own strengths and security considerations. We emphasized the critical importance of secure nonce generation in DSA/ECDSA and the advantages of deterministic schemes like EdDSA.
We then introduced PKI, the framework that binds public keys to identities through digital certificates. We examined the X.509 certificate format, the roles of Certificate Authorities (CAs) and Registration Authorities (RAs), and the certificate lifecycle—from generation to issuance to renewal. We discussed revocation mechanisms, including CRLs and OCSP, and their role in maintaining trust.
We compared different trust models: hierarchical (web PKI), web of trust (PGP), and direct trust. We surveyed standards and formats (X.509, PKCS, PEM, DER) and explored real-world applications: TLS, S/MIME, code signing, document signing, and blockchain.
The case studies illustrated the real-world impact of PKI vulnerabilities and the importance of robust CA security, timely revocation, and algorithm agility. These lessons underscore the need for continuous vigilance in the PKI ecosystem.
With this knowledge, you are now equipped to understand, implement, and evaluate digital signatures and PKI in cryptographic systems, and to appreciate their role in enabling secure digital communication and transactions.
In Tutorial 2.16: Cryptographic Protocols and Applications, we will bring together symmetric encryption, MACs, hash functions, and public-key cryptography to examine complete cryptographic protocols such as TLS, SSH, IPsec, and PGP. You will see how digital signatures and PKI are integrated into practical secure communication systems.