1.2 Public-key cryptography

Public-key cryptography uses two mathematically linked keys (one public, one private) to enable secure communication and authentication over untrusted networks. It solves a fundamental problem in network security: how do two parties who have never met establish a secure channel? This topic covers the core algorithms, infrastructure, attacks, and applications that make asymmetric cryptography work.

Principles of public-key cryptography

Public-key cryptography (also called asymmetric cryptography) uses a pair of different keys for encryption and decryption. The public key can be shared openly, while the private key stays secret. Together, they enable secure communication even when the channel itself isn't trusted.

The security of this approach rests on trapdoor functions: mathematical problems that are easy to compute in one direction but computationally infeasible to reverse. Factoring the product of two large primes (used in RSA) and solving the elliptic curve discrete logarithm problem (used in ECC) are the two most common examples.

In network security and forensics, public-key cryptography provides three critical properties:

• Confidentiality: only the intended recipient can decrypt a message
• Integrity: any modification to the message is detectable
• Non-repudiation: the sender cannot deny having sent the message, since only their private key could have produced the signature

Asymmetric key pairs

Public vs private keys

The public key is freely distributed and used for encrypting messages or verifying digital signatures. The private key is kept secret by its owner and used for decrypting messages or creating digital signatures.

The relationship is strictly one-directional: a message encrypted with the public key can only be decrypted with the corresponding private key, and vice versa. This mathematical pairing is what makes the whole system work.

If a private key is compromised, the entire security model breaks down. An attacker with the private key can impersonate the owner, decrypt confidential messages, and forge digital signatures. Protecting the private key is the single most important responsibility in any public-key system.

Key generation process

Key generation produces a mathematically related pair of keys based on a specific algorithm (e.g., RSA, ECC). The process involves:

1. Selecting algorithm parameters (key size for RSA, curve selection for ECC) based on the required security level
2. Using a cryptographically secure random number generator to produce the key material
3. Computing the public and private keys from that material according to the algorithm's rules

Generated keys are typically stored in standardized formats like PEM (Base64-encoded text) or PKCS#12 (binary, often password-protected). A strong passphrase should protect stored private keys to prevent unauthorized access even if the file is stolen.

RSA algorithm

RSA is the most widely known public-key algorithm. Its security depends on the difficulty of factoring the product of two very large prime numbers.

RSA encryption process

1. The plaintext message is converted into a numerical representation $M$ using a padding scheme (e.g., OAEP, which is preferred over the older PKCS#1 v1.5)
2. The ciphertext $C$ is computed as: $C = M^e \mod n$, where $e$ is the public exponent and $n$ is the modulus (the product of two large primes $p$ and $q$)
3. Only the holder of the corresponding private key can reverse this operation

RSA decryption process

1. The recipient raises the ciphertext $C$ to the power of their private exponent $d$, modulo $n$: $M = C^d \mod n$
2. The private exponent $d$ was computed during key generation using the extended Euclidean algorithm, satisfying the relationship $ed \equiv 1 \mod \phi(n)$, where $\phi(n) = (p-1)(q-1)$
3. The recovered number $M$ is then unpadded to obtain the original plaintext

RSA security considerations

• Security depends on the difficulty of factoring $n$ back into $p$ and $q$. A 2048-bit modulus is currently considered the minimum for most applications, with 3072-bit or 4096-bit recommended for long-term protection.
• Implementation flaws are often more dangerous than mathematical weaknesses. Padding oracle attacks, timing attacks, and key leakage through poor random number generation have all been exploited in practice.
• Key size should match the sensitivity and expected lifetime of the data being protected. NIST recommends 2048-bit RSA as equivalent to roughly 112 bits of symmetric security.

Elliptic curve cryptography (ECC)

ECC vs RSA

ECC achieves comparable security to RSA using much smaller key sizes. A 256-bit ECC key provides roughly the same security as a 3072-bit RSA key. This difference matters because smaller keys mean faster key generation, encryption, decryption, and lower bandwidth usage.

These efficiency gains make ECC especially well-suited for resource-constrained environments like smartphones, IoT devices, and embedded systems. ECC's security relies on the elliptic curve discrete logarithm problem (ECDLP), which is considered harder to solve than integer factorization for equivalent key sizes.

ECC key generation

1. Select an appropriate elliptic curve and its domain parameters. Common choices include NIST P-256 (widely used in TLS) and Curve25519 (favored for its resistance to implementation errors).
2. Choose a base point $G$ on the curve (this is typically defined by the curve standard).
3. Generate the private key $d$ as a randomly selected integer.
4. Compute the public key as $Q = dG$ (scalar multiplication of the base point $G$ by the private key $d$).

Both parties must agree on the same domain parameters (curve, base point, order) for the system to work.

ECC encryption & decryption

ECC encryption (using the ElGamal scheme on elliptic curves) works as follows:

1. The plaintext message is encoded as a point $M$ on the elliptic curve
2. The sender generates a random integer $k$ and computes two points: $C_1 = kG$ and $C_2 = M + kQ$, where $Q$ is the recipient's public key
3. The ciphertext pair $(C_1, C_2)$ is sent to the recipient

To decrypt:

1. The recipient computes $M = C_2 - dC_1$, where $d$ is their private key

2. This works because $dC_1 = d(kG) = k(dG) = kQ$, so subtracting it from $C_2$ cancels out the $kQ$ term and recovers $M$

3. The recovered point $M$ is decoded back into the original plaintext

Digital signatures

Digital signatures use public-key cryptography in reverse: the private key signs, and the public key verifies. They prove who sent a message and that it hasn't been altered.

Digital signature creation

1. The signer hashes the message using a cryptographic hash function (e.g., SHA-256) to produce a fixed-size digest
2. The digest is then signed using the signer's private key (the exact operation depends on the algorithm, such as RSA-PSS or ECDSA)
3. The resulting digital signature is attached to the original message and sent to the recipient

Digital signature verification

1. The recipient hashes the received message using the same hash function the signer used
2. The recipient uses the signer's public key to process the signature and extract the hash digest the signer computed
3. If the two hash values match, the signature is valid: the message hasn't been tampered with and was signed by the holder of the corresponding private key

Non-repudiation of digital signatures

Digital signatures provide non-repudiation, meaning the signer cannot credibly deny having signed the message. Since only the signer's private key could have produced that signature, the act of signing is tied to the key owner.

This property is critical in legal and financial contexts like e-contracts and online transactions, where parties must be held accountable for their actions. When combined with trusted timestamping, digital signatures can also prove when a signature was created, adding another layer of evidentiary value.

Public key infrastructure (PKI)

PKI is the framework of policies, procedures, and technology that manages digital certificates and public keys. It answers a crucial question: how do you know a public key actually belongs to who it claims to?

Role of certificate authorities

Certificate authorities (CAs) are trusted third parties that issue, manage, and revoke digital certificates. Each certificate binds a public key to an identity (a person, organization, or device).

Before issuing a certificate, the CA verifies the identity of the requestor. The level of verification varies: Domain Validation (DV) just confirms domain ownership, while Extended Validation (EV) involves thorough organizational checks.

CAs are organized in a hierarchy:

• Root CAs sit at the top and are trusted by default by operating systems and browsers. Their certificates are self-signed.
• Intermediate CAs are certified by root CAs (or other intermediates), forming a chain of trust from any certificate back to a trusted root.

X.509 certificate format

X.509 is the standard format for digital certificates in PKI. A certificate contains:

• Subject identity: name, email, domain name
• Public key: the subject's public key
• Issuer identity: the CA that issued the certificate
• Validity period: start and expiration dates
• Serial number: unique identifier assigned by the CA
• Digital signature: the issuing CA's signature over all the above fields

Extensions can add information like key usage restrictions, subject alternative names (SANs) for multiple domains, and certificate policies.

Certificate revocation lists (CRLs)

Sometimes certificates need to be invalidated before they expire. Reasons include private key compromise, changes in the subject's identity, or policy violations. CAs handle this through two mechanisms:

• CRLs: periodically published lists of revoked certificate serial numbers. Relying parties download and check these lists. The downside is that CRLs can be large and may not reflect very recent revocations.
• OCSP (Online Certificate Status Protocol): provides real-time revocation status for individual certificates on demand. It's faster and more current than CRLs but requires the OCSP responder to be available.

Key management

Secure key storage

Private keys must be stored securely. Common storage options, in order of increasing security:

• Encrypted key files on disk, protected with strong passphrases
• Smart cards or USB tokens that store keys in tamper-resistant hardware
• Hardware security modules (HSMs): dedicated devices designed for key storage and cryptographic operations, used in enterprise and high-security environments

Access to private keys should follow the principle of least privilege: only the people and applications that genuinely need the key should have access.

Key backup & recovery

Losing a private key means losing access to everything encrypted with the corresponding public key. Regular backups are essential.

• Backups should be stored in a secure, off-site location
• Backup media should be encrypted and protected with strong access controls
• Recovery procedures should be documented and periodically tested so they actually work when needed

Key expiration & rotation

Cryptographic keys should not be used indefinitely. Regular rotation limits the damage if a key is compromised and aligns with security best practices.

• Expiration dates are set based on data sensitivity, key strength, and risk assessment
• Key rotation involves generating a new key pair, distributing the new public key, and revoking the old one
• The transition period needs careful planning to avoid disrupting services that depend on the old key

Applications of public-key cryptography

Secure email with S/MIME

S/MIME (Secure/Multipurpose Internet Mail Extensions) applies public-key cryptography to email. It provides two capabilities:

• Encryption: the sender encrypts the email contents and attachments using the recipient's public key, so only the recipient can read them
• Digital signing: the sender signs the message with their private key, giving the recipient proof of authenticity, integrity, and non-repudiation

Secure web browsing with SSL/TLS

TLS (Transport Layer Security), the successor to the now-deprecated SSL, secures web traffic. The TLS handshake uses public-key cryptography for authentication and key exchange, then switches to symmetric encryption (e.g., AES) for the actual data transfer. Symmetric encryption is used for bulk data because it's far faster than asymmetric encryption.

Websites using TLS show "https" in the URL and a padlock icon in the browser. The server presents its X.509 certificate during the handshake so the client can verify its identity.

Cryptocurrencies & blockchain

Public-key cryptography is foundational to cryptocurrencies like Bitcoin and Ethereum. Your cryptocurrency "address" is derived from your public key, and you authorize transactions by signing them with your private key.

The blockchain itself uses cryptographic hashes and digital signatures to create a tamper-evident, decentralized ledger. Every transaction's authenticity can be verified using the sender's public key, and the chain of hashes makes altering past records computationally infeasible.

Attacks on public-key systems

Brute force attacks

A brute force attack tries every possible private key until the correct one is found. For properly sized keys, this is computationally infeasible: a 2048-bit RSA key has a keyspace so large that no current or foreseeable classical computer could exhaust it.

The defense is straightforward: use sufficiently large key sizes (2048-bit minimum for RSA, 256-bit for ECC) and follow proper key management practices.

Man-in-the-middle attacks

In a man-in-the-middle (MITM) attack, an attacker intercepts communication between two parties and substitutes their own public key for the legitimate one. Both parties think they're communicating securely, but the attacker can read and modify everything.

Public-key cryptography alone doesn't prevent MITM attacks. You need a way to verify that a public key genuinely belongs to who it claims to. That's exactly what PKI and digital certificates solve. Additional countermeasures include:

• Certificate pinning: the client remembers which certificate or CA a server should use and rejects unexpected changes
• Secure protocols like TLS and SSH that incorporate certificate verification into the handshake

Side-channel attacks

Side-channel attacks don't target the math directly. Instead, they exploit information leaked by the physical implementation: how long an operation takes (timing attacks), how much power the device draws (power analysis), or what electromagnetic signals it emits.

Real-world examples include timing attacks on RSA implementations that reveal private key bits based on decryption speed, and power analysis attacks on smart cards. Mitigations include:

• Constant-time algorithms that take the same amount of time regardless of the input
• Blinding and randomization techniques that mask the relationship between input data and physical measurements
• Physical countermeasures like electromagnetic shielding and tamper detection

Future of public-key cryptography

Post-quantum cryptography

Quantum computers, once they reach sufficient scale, could break RSA and ECC by efficiently solving integer factorization and discrete logarithm problems (using Shor's algorithm). Post-quantum cryptography refers to algorithms designed to resist quantum attacks.

NIST finalized its first set of post-quantum standards in 2024, selecting algorithms based on different mathematical foundations:

• Lattice-based (e.g., ML-KEM, formerly CRYSTALS-Kyber)
• Hash-based (e.g., SLH-DSA, formerly SPHINCS+)
• Code-based and multivariate schemes are also under investigation

Organizations handling long-lived sensitive data should already be planning their migration, since data encrypted today could be captured and decrypted later when quantum computers become available ("harvest now, decrypt later" attacks).

Homomorphic encryption

Homomorphic encryption allows computations to be performed on encrypted data without decrypting it first. This is valuable for secure cloud computing, where you want a server to process your data without ever seeing the plaintext.

• Fully homomorphic encryption (FHE) supports arbitrary computations on ciphertext but currently carries very high computational overhead, making it impractical for most real-time applications
• Partially homomorphic encryption (PHE) supports specific operations (e.g., addition or multiplication, but not both) and is more efficient, though limited in scope

Advancements in quantum computing

Quantum computers use principles like superposition and entanglement to perform certain computations exponentially faster than classical computers. The development of large-scale, fault-tolerant quantum machines would render RSA and ECC insecure.

Two main approaches are being pursued to address this threat:

• Post-quantum algorithms (described above) that run on classical hardware but resist quantum attacks
• Quantum key distribution (QKD), which uses quantum mechanics itself to establish provably secure keys, though it requires specialized hardware and has distance limitations

The timeline for "cryptographically relevant" quantum computers remains uncertain, but the consensus in the security community is to prepare now rather than wait.