Public Key Cryptography: Asymmetric Encryption Explained

Public key cryptography, or asymmetric cryptography, uses mathematically linked key pairs: a public key for encryption and verification, and a private key for decryption and signing. It enables secure communication without sharing secrets and forms the foundation of TLS, SSH, digital signatures, and cryptocurrencies.

Public Key Cryptography: Asymmetric Encryption Explained

Public key cryptography, also known as asymmetric cryptography, is a cryptographic system that uses pairs of mathematically related keys. Each key pair consists of a public key, which can be shared openly, and a private key, which must be kept secret. The public key encrypts data or verifies signatures, while the private key decrypts data or creates signatures. This asymmetry enables secure communication without pre-shared secrets, solving the key distribution problem that plagues symmetric cryptography.

To understand public key cryptography properly, it helps to be familiar with encryption basics, symmetric encryption, and TLS protocols.

Public key cryptography architecture:

┌─────────────────────────────────────────────────────────────────────────┐
│                     Public Key Cryptography System                       │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│  ┌─────────────────────────────────────────────────────────────────────┐│
│  │                         Key Generation                              ││
│  │                    ┌─────────────────────┐                          ││
│  │                    │   Random Number     │                          ││
│  │                    │   Generator (RNG)   │                          ││
│  │                    └──────────┬──────────┘                          ││
│  │                               │                                     ││
│  │              ┌────────────────┼────────────────┐                    ││
│  │              ▼                ▼                ▼                    ││
│  │         ┌─────────┐     ┌─────────┐     ┌─────────┐                ││
│  │         │  RSA    │     │  ECC    │     │ Ed25519 │                ││
│  │         │ Key Pair│     │ Key Pair│     │ Key Pair│                ││
│  │         └────┬────┘     └────┬────┘     └────┬────┘                ││
│  │              │               │               │                      ││
│  │         ┌────▼────┐     ┌────▼────┐     ┌────▼────┐                ││
│  │         │Public   │     │Public   │     │Public   │                ││
│  │         │Key      │     │Key      │     │Key      │                ││
│  │         │(shared) │     │(shared) │     │(shared) │                ││
│  │         └────┬────┘     └────┬────┘     └────┬────┘                ││
│  │              │               │               │                      ││
│  │         ┌────▼────┐     ┌────▼────┐     ┌────▼────┐                ││
│  │         │Private  │     │Private  │     │Private  │                ││
│  │         │Key      │     │Key      │     │Key      │                ││
│  │         │(secret) │     │(secret) │     │(secret) │                ││
│  │         └─────────┘     └─────────┘     └─────────┘                ││
│  └─────────────────────────────────────────────────────────────────────┘│
│                                                                          │
│  ┌─────────────────────────────┐    ┌─────────────────────────────┐     │
│  │        Encryption           │    │       Digital Signatures    │     │
│  │                             │    │                             │     │
│  │  Sender uses recipient's    │    │  Signer uses own private    │     │
│  │  public key to encrypt      │    │  key to create signature    │     │
│  │                             │    │                             │     │
│  │  Recipient uses own         │    │  Verifier uses signer's     │     │
│  │  private key to decrypt     │    │  public key to verify       │     │
│  └─────────────────────────────┘    └─────────────────────────────┘     │
│                                                                          │
│  Trust Infrastructure:                                                   │
│  ┌─────────┐    ┌─────────┐    ┌─────────┐    ┌─────────┐              │
│  │   CA    │───→│Certificate│───→│ PKI     │───→│ Revocation│          │
│  │(Trusted)│    │ (X.509)  │    │(Mgmt)   │    │ (CRL/OCSP)│          │
│  └─────────┘    └─────────┘    └─────────┘    └─────────┘              │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Is Public Key Cryptography?

Public key cryptography is an encryption system that uses a pair of keys instead of a single shared secret. The public key is used for encryption and signature verification. The private key is used for decryption and signature creation. The two keys are mathematically related, but computing the private key from the public key is computationally infeasible with current technology.

Public Key: Distributed freely, used by anyone to encrypt messages to the key owner or verify signatures from the key owner.
Private Key: Kept secret by owner, used to decrypt messages encrypted with corresponding public key or sign digital documents.
Key Pair: The public and private keys together, generated simultaneously and mathematically linked.
One-Way Function: Mathematical operation easy to compute in one direction but extremely difficult to reverse. The basis of public key cryptography security.
Trapdoor Function: One-way function with special secret that makes reversal easy if you know the secret (the private key).

Why Public Key Cryptography Matters

Public key cryptography solved the key distribution problem that made secure communication difficult before its invention.

No Shared Secret Required: Symmetric encryption requires both parties to have same secret key, which must be distributed securely. Public key cryptography eliminates need for pre-shared secret. Recipient publishes public key, anyone can encrypt messages only recipient can decrypt.
Digital Signatures: Public key cryptography enables digital signatures that prove message authenticity and integrity. Private key holder signs message; anyone with public key can verify signature. Provides non-repudiation: signer cannot deny signing later.
Secure Key Exchange: Diffie-Hellman key exchange allows two parties to agree on shared secret over insecure channel. Used in TLS to establish session keys for symmetric encryption, combining performance of symmetric encryption with security of public key distribution.
Authentication: Public key certificates (X.509) bind identities to public keys through certificate authorities. Foundation of TLS/HTTPS, SSH, and code signing.
Cryptocurrencies: Bitcoin and other cryptocurrencies use public key cryptography for ownership verification. Public key serves as wallet address; private key authorizes transactions.
End-to-End Encryption: Messaging apps like Signal, WhatsApp use public key cryptography for ratcheting and initial key establishment, ensuring messages readable only by intended recipients.

How Public Key Cryptography Works

Key Generation

User generates random key pair using cryptographic algorithm. Private key never leaves user's secure storage. Public key published to certificate authority, keyserver, or shared directly. Mathematical relationship ensures what one key encrypts, only other key can decrypt. Algorithm selection determines key sizes and security strength.

Encryption and Decryption

To send encrypted message to Bob: Alice obtains Bob's public key from certificate or keyserver. Alice encrypts message using Bob's public key. Only Bob's private key can decrypt ciphertext. Bob uses private key to decrypt and read original message. Confidentiality assured even if attacker intercepts public key or ciphertext.

Digital Signatures

To sign message: Alice hashes message to create digest. Alice encrypts digest with her private key, creating signature. Alice sends message and signature to Bob. Bob hashes message independently. Bob decrypts signature using Alice's public key to get digest. Bob compares digests; if match, signature valid, message authentic, from Alice, unaltered.

Public Key Algorithms

RSA (Rivest-Shamir-Adleman)

RSA is the most widely used public key algorithm, based on difficulty of factoring large prime numbers. Security relies on fact that multiplying two large primes is easy, but factoring their product is extremely difficult with large enough numbers (2048-4096 bits). RSA supports both encryption and digital signatures. Common uses include TLS certificates, PGP/GPG, and SSH.

ECC (Elliptic Curve Cryptography)

ECC is based on algebraic structure of elliptic curves over finite fields. ECC provides same security as RSA with much smaller key sizes, making it more efficient for constrained environments like mobile devices and IoT. ECC used in TLS 1.3, cryptocurrencies (Bitcoin, Ethereum), and modern hardware security keys.

Diffie-Hellman Key Exchange

Diffie-Hellman allows two parties to establish shared secret over insecure channel without pre-shared keys. Not encryption or signing itself, but used to derive session keys for symmetric encryption. Security based on discrete logarithm problem. Used in TLS, IPsec, SSH, and many other protocols.

Algorithm	Security Basis	Key Size	Primary Use
RSA	Integer factorization	2048-4096 bits	General purpose, TLS certs
ECC	Elliptic curve discrete log	256-384 bits	Modern systems, mobile, crypto
Diffie-Hellman	Discrete logarithm	2048-4096 bits	Key exchange (TLS, SSH, IPsec)
Ed25519	Elliptic curve	256 bits	Signatures, SSH, blockchain

Public Key vs Symmetric Cryptography

Aspect	Symmetric Cryptography	Asymmetric (Public Key)
Key Type	Single shared secret key	Key pair (public + private)
Key Distribution	Problematic, needs secure channel	Easy: public keys can be shared openly
Number of Keys	O(N²) for N users	2N for N users
Performance	Fast (millions of bytes per second)	Slow (thousands of bytes per second)
Use Cases	Bulk data encryption, storage encryption	Key exchange, signatures, certificates

In practice, systems combine both: public key for secure key exchange and authentication, symmetric for bulk data encryption. TLS uses public key to establish shared secret, then symmetric encryption (AES) for encrypting HTTP traffic. This hybrid approach provides security and performance.

Digital Certificates and PKI

Public key cryptography requires trust: how do you know a public key belongs to claimed identity? Public Key Infrastructure (PKI) solves this through digital certificates, covered in our PKI guide.

X.509 Certificate: Digital document binding identity (domain name, organization) to public key. Contains subject name, public key, validity period, issuer signature, and extensions.
Certificate Authority (CA): Trusted third party that issues certificates after verifying identity. Browser and operating systems trust root CAs.
Chain of Trust: Certificate signed by intermediate CA, intermediate signed by root CA. Client validates signatures up to trusted root.
Certificate Revocation: CRL (Certificate Revocation List) or OCSP (Online Certificate Status Protocol) to check if certificate still valid before trust.

Digital Signatures

Digital signatures provide authentication, integrity, and non-repudiation.

Signing Process: Create cryptographic hash of message. Sign hash with sender's private key. Append signature to message or send separately.
Verification Process: Receiver calculates hash of received message. Decrypts signature with sender's public key to get original hash. Compares hashes; match confirms signature valid.
Non-Repudiation: Signer cannot deny signing because private key should be known only to signer.
Applications: Code signing (software updates, drivers), document signing (PDF signatures, contracts), email signing (S/MIME, PGP).

Hybrid Cryptographic Systems

Pure public key encryption is too slow for large data. Hybrid systems combine best of both.

Hybrid Encryption: Generate random symmetric session key. Encrypt symmetric key with recipient's public key. Encrypt actual data with symmetric key using AES. Send both encrypted key and encrypted data. Recipient decrypts symmetric key with private key, then decrypts data.
TLS/HTTPS: Public key for handshake and key exchange, symmetric encryption for application data.
SSH: Server and client keys for authentication, Diffie-Hellman for key exchange, symmetric cipher for session encryption.

Security Considerations

Key Size: Larger keys provide more security but slower performance. 2048-bit RSA minimum, 3072-bit recommended. ECC 256-bit equivalent to RSA 3072-bit.
Private Key Protection: Private key compromise defeats all security guarantees. Store in hardware security module (HSM), TPM, or secure enclave.
Man-in-the-Middle: Without authentication, attacker can substitute public keys. PKI and certificates prevent MITM.
Forward Secrecy: Without forward secrecy, compromise of long-term private key decrypts all past recorded sessions. Use ephemeral Diffie-Hellman.

Public Key Cryptography Best Practices

Use Appropriate Key Sizes: Minimum 2048-bit RSA, prefer 3072-bit or 4096-bit. Use ECC with 256-bit for better performance.
Prefer ECC Over RSA for New Systems: ECC provides better security per bit, smaller keys, faster operations.
Implement Forward Secrecy: Use ephemeral Diffie-Hellman (ECDHE) in TLS.
Protect Private Keys with Hardware: Use HSM, TPM, or cloud KMS for high-security applications.
Use Certificates for Trust: Publish public keys through X.509 certificates from trusted CA.
Regular Key Rotation: Rotate long-term keys periodically. Set certificate validity to 1-2 years maximum.
Validate Certificates Properly: Always validate certificate chain, expiration, revocation status, hostname matching.
Use Secure Randomness: Use system's cryptographically secure random number generator for key generation.

Common Anti-Patterns

Using Same Key Pair for Encryption and Signing: Different security properties needed. Separate keys for encryption and signing.
No Forward Secrecy: Using RSA key exchange without Diffie-Hellman. Enable ECDHE or DHE.
Small Key Sizes: 1024-bit RSA easily factorable. Use 2048-bit minimum, 3072-bit recommended.
Disabling Certificate Validation: Exposes to MITM attacks. Never disable in production.
Hardcoded Private Keys: Embedding private keys in source code. Use key management service.
Using Broken Hash Functions: MD5 or SHA-1 for signatures is insecure. Use SHA-256 or SHA-3.

Post-Quantum Cryptography

Quantum computers, if built large enough, could break RSA and ECC using Shor's algorithm. Post-quantum cryptography (PQC) refers to algorithms resistant to quantum attacks.

NIST Post-Quantum Standardization: CRYSTALS-Kyber (key encapsulation), CRYSTALS-Dilithium (signatures), FALCON (signatures), SPHINCS+ (hash-based signatures).
Hybrid Approaches: Combine classical and post-quantum algorithms for safety during transition.
Migration Timeline: Standards finalized. Expect migration over coming decade. Plan for crypto-agility now.

Frequently Asked Questions

What is the difference between public key and private key?
Public key is freely shared, used for encryption and signature verification. Private key is kept secret, used for decryption and signature creation. Private key must never leave secure storage.
Is public key cryptography more secure than symmetric?
Neither is inherently more secure. Public key cryptography solves key distribution problem but is much slower. Hybrid systems use public key for authentication and key exchange, symmetric for data encryption.
Why can't I derive private key from public key?
Security relies on mathematical one-way functions. Factoring product of two large primes (RSA) or solving discrete logarithm problem (ECC) is computationally infeasible with sufficiently large numbers.
What is the difference between RSA and ECC?
RSA based on factoring large integers; ECC based on elliptic curve discrete logarithms. ECC provides same security as RSA with much smaller keys. ECC recommended for new systems.
How do HTTPS and SSL/TLS use public key cryptography?
TLS uses public key cryptography for authentication (server certificate) and key exchange. Bulk data uses symmetric encryption (AES) for performance.
What should I learn next after public key cryptography?
After mastering public key cryptography, explore PKI and X.509 certificates, TLS protocol details, digital signatures in depth, cryptographic protocols, and post-quantum cryptography.

Public Key Cryptography: Asymmetric Encryption Explained