After completing this tutorial, you should be able to:
Public-key cryptography, also known as asymmetric cryptography, represents a revolutionary advancement in the field of cryptography. Unlike symmetric cryptography, which uses a single shared secret key for both encryption and decryption, public-key cryptography uses a pair of mathematically related keys: a public key that can be freely distributed and a private key that must be kept secret. This key pair enables a wide range of security services, including confidentiality, authentication, and non-repudiation, and solves the long-standing problem of secure key distribution.
The concept of public-key cryptography was first proposed by Whitfield Diffie and Martin Hellman in their groundbreaking 1976 paper "New Directions in Cryptography." They introduced the idea of a one-way function that could be used for encryption and key exchange. Shortly after, Rivest, Shamir, and Adleman developed the RSA algorithm in 1977, which became the first practical public-key cryptosystem. Today, public-key cryptography is the foundation of modern secure communications, including SSL/TLS, SSH, PGP, and many other protocols.
In this tutorial, we will explore the fundamental concepts of public-key cryptography. We begin by examining the key distribution problem that motivated its invention. We then introduce the public-key cryptosystem model and contrast it with symmetric encryption. We discuss the security services that public-key cryptography provides and the mathematical foundations that underpin it. We provide an overview of the major algorithms—RSA, Diffie-Hellman, and ECC—and introduce the concept of Public-Key Infrastructure (PKI). We also examine hybrid cryptosystems, which combine the efficiency of symmetric encryption with the key management advantages of public-key cryptography.
By the end of this tutorial, you will understand the principles, advantages, and limitations of public-key cryptography and be prepared for deeper dives into specific algorithms in subsequent tutorials.
In Tutorials 2.4–2.10, we studied symmetric cryptography, including encryption, modes, hashing, and MACs. Public-key cryptography provides complementary capabilities and addresses the key distribution problem. Tutorials 2.12–2.15 will delve into RSA, Diffie-Hellman, ECC, and digital signatures, building on the foundations established here. Tutorial 2.16 will cover cryptographic protocols and applications.
Symmetric cryptography, for all its efficiency, suffers from a fundamental challenge: how to securely distribute the secret key to all communicating parties before any encrypted communication can take place. This is known as the key distribution problem.
Public-key cryptography solves the key distribution problem by using a pair of keys: a public key that can be openly distributed and a private key that is kept secret. To send an encrypted message, a sender uses the recipient's public key to encrypt; only the recipient's private key can decrypt. The recipient's public key can be published freely—there is no need for a secure channel to distribute it. This eliminates the need for a pre-shared secret.
Public-key cryptography is based on the concept of a trapdoor one-way function—a function that is easy to compute in one direction but hard to invert without special information (the trapdoor). In public-key systems:
Public-key cryptography provides three primary security services:
A public-key cryptosystem consists of three components:
For the system to be correct, for every message M and key pair (PK, SK), we must have:
DSK(EPK(M)) = M
Figure 1: Public-key encryption model.
To send a confidential message to Alice, Bob encrypts it with Alice's public key. Only Alice, with her private key, can decrypt it.
Limitation: Public-key encryption is computationally expensive. It is typically used to encrypt small amounts of data (e.g., session keys) rather than bulk data.
To sign a message, the sender uses their private key to create a digital signature. Anyone can verify the signature using the sender's public key, confirming that the message originated from the sender and has not been altered.
Signing: σ = SignSK(M)
Verification: VerifyPK(σ, M) = True/False
Because the private key is known only to the signer, a valid digital signature provides evidence of the signer's action, preventing them from denying having signed the message.
Public-key cryptography enables secure key exchange protocols (e.g., Diffie-Hellman) that allow two parties to establish a shared secret over an insecure channel.
| Feature | Symmetric | Asymmetric (Public-Key) |
|---|---|---|
| Keys | Single shared key | Key pair (public/private) |
| Key distribution | Difficult, requires secure channel | Easy; public keys can be shared openly |
| Scalability | O(n²) keys for n users | O(n) keys (each user has one pair) |
| Performance | Very fast (suitable for bulk data) | Slow (100–1000× slower than symmetric) |
| Security services | Confidentiality, some authentication (with MAC) | Confidentiality, authentication, non-repudiation |
| Key size | 128–256 bits | 2048–4096 bits (RSA), 256–384 bits (ECC equivalent) |
| Use cases | Bulk encryption, disk encryption, file encryption | Key exchange, digital signatures, secure email |
Public-key cryptography relies on certain difficult mathematical problems. The main problems are:
Given a large composite integer n (the product of two large primes), find its prime factors p and q. This is the basis for RSA security.
Given a prime p, a primitive root g modulo p, and an element h ∈ Zp*, find x such that gx ≡ h (mod p). This is the basis for Diffie-Hellman and DSA.
The discrete logarithm problem on an elliptic curve. This is the basis for ECC.
These concepts were covered in detail in Tutorial 2.3. Public-key algorithms leverage the computational difficulty of the above problems to provide security.
RSA is the most widely used public-key cryptosystem. It is based on the difficulty of factoring large integers.
Diffie-Hellman allows two parties to establish a shared secret over an insecure channel.
ECC uses the algebraic structure of elliptic curves over finite fields. It provides the same security as RSA with much smaller key sizes.
| Symmetric Key Size (bits) | RSA Key Size (bits) | ECC Key Size (bits) |
|---|---|---|
| 80 | 1024 | 160 |
| 112 | 2048 | 224 |
| 128 | 3072 | 256 |
| 192 | 7680 | 384 |
| 256 | 15360 | 512 |
ECC provides equivalent security to RSA with significantly smaller key sizes, making it attractive for constrained environments (e.g., mobile devices, IoT).
A major challenge in public-key cryptography is ensuring that a public key truly belongs to the entity it claims to. Public-Key Infrastructure (PKI) addresses this by binding public keys to identities through digital certificates.
A CA is a trusted third party that issues digital certificates. The certificate contains:
Anyone can verify the certificate by checking the CA's signature using the CA's public key (which is trusted).
Certificates can be chained: a CA can issue a certificate for a subordinate CA, which then issues certificates to end entities. The root CA is the ultimate trust anchor.
Certificates may need to be revoked before expiration (e.g., if the private key is compromised). Revocation is managed through Certificate Revocation Lists (CRLs) and Online Certificate Status Protocol (OCSP).
Hybrid cryptosystems combine the efficiency of symmetric encryption with the key management advantages of public-key cryptography. The typical approach is:
The recipient uses their private key to decrypt the session key, then decrypts the message.
Advantages:
Figure 2: Hybrid encryption process.
Public-key algorithms rely on the assumption that certain mathematical problems are hard to solve. The security is computational (not information-theoretic), meaning it is based on the computational difficulty of solving the underlying problem.
The security level (in bits) corresponds to the number of operations required to break the system. For example, RSA-2048 provides about 112 bits of security (similar to AES-112). As computational power increases, recommended key sizes increase.
Quantum computers, using Shor's algorithm, can factor integers and compute discrete logarithms in polynomial time. This would break RSA and ECC. Post-quantum cryptography (PQC) is an active area of research.
Private keys must be protected against theft and misuse. Hardware Security Modules (HSMs), secure elements, and strong access controls are essential.
TLS uses public-key cryptography for authentication and key exchange (e.g., RSA or ECDHE) and symmetric encryption for bulk data. The server presents a certificate signed by a CA to prove its identity.
SSH uses public-key cryptography for host authentication and user authentication. RSA and ECDSA are commonly used.
PGP (and GPG) use hybrid encryption for email and file encryption. Public keys are distributed via a web of trust or key servers.
Digital signatures are used for code signing, document signing, and certificate signing. They provide authentication and non-repudiation.
Bitcoin uses ECDSA for transaction signing. Each user has a public key (address) and a private key for spending.
IPsec uses public-key certificates for authentication and key exchange (IKE).
In 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography," which introduced the concept of public-key cryptography and the Diffie-Hellman key exchange. Their work was groundbreaking because it solved the key distribution problem without a pre-shared secret. The paper laid the foundation for all modern public-key cryptography.
In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman developed the RSA algorithm, which is based on the difficulty of factoring large composite numbers. RSA quickly became the de facto standard for public-key encryption and digital signatures. It is still widely used today, though larger key sizes are now required.
Heartbleed was a serious vulnerability in OpenSSL that allowed attackers to read memory of servers, potentially exposing private keys. This highlighted the importance of secure implementation and private key protection in public-key systems.
Explain the steps for generating an RSA key pair. What are the key components, and what mathematical properties make them work?
RSA key generation steps:
Public key: (n, e). Private key: (n, d).
The mathematical properties rely on Euler's theorem: for any M, Med ≡ M (mod n), because ed ≡ 1 (mod φ(n)).
Using prime p = 23 and primitive root g = 5, suppose Alice chooses a = 6 and Bob chooses b = 15. Compute the public values A and B, and the shared secret s.
A = ga mod p = 56 mod 23 = 15625 mod 23 = 8.
B = gb mod p = 515 mod 23 = 30517578125 mod 23 = 19.
Alice computes s = Ba mod p = 196 mod 23 = 47045881 mod 23 = 18.
Bob computes s = Ab mod p = 815 mod 23 = 35184372088832 mod 23 = 18.
Shared secret s = 18.
Let p = 11, q = 13. Compute n and φ(n). Choose e = 7. Compute d. Encrypt the message M = 5 using the public key and decrypt the ciphertext.
n = 11·13 = 143.
φ(n) = 10·12 = 120.
e = 7, gcd(7,120)=1.
d = e−1 mod 120. 7·103 = 721 ≡ 1 (mod 120), so d = 103.
Public key: (143, 7). Private key: (143, 103).
Encrypt M=5: C = 57 mod 143 = 78125 mod 143. 143·546 = 78078, remainder 47. So C = 47.
Decrypt: M = 47103 mod 143 = 5 (verifiable by modular exponentiation).
Describe how a hybrid encryption system would work for sending a large file to a recipient. What are the steps, and what keys are used at each step?
Steps:
The recipient uses their private key to decrypt K, then uses K to decrypt the file.
Compare the key sizes required for RSA and ECC to achieve 128-bit security. What are the recommended key sizes, and why is ECC more efficient?
For 128-bit security, RSA requires a key size of approximately 3072 bits, while ECC requires about 256 bits. ECC is more efficient because the ECDLP is believed to be harder than the integer factorization problem for equivalent key sizes, allowing smaller keys.
Write a 500-word report on the history of public-key cryptography. Include the contributions of Diffie and Hellman, the RSA inventors, and the role of the NSA and GCHQ in early research. Discuss the impact of the 1976 paper and the subsequent development of practical systems.
Complete answer would cover the 1976 Diffie-Hellman paper, the RSA invention in 1977, and the earlier classified work by James Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ. It would discuss how the Diffie-Hellman paper sparked a revolution in cryptography and led to the development of PKI and digital signatures.
Explain the concept of a certificate chain in PKI. How does a client validate a server certificate using a chain? What is the role of the root CA?
A certificate chain consists of a root CA certificate, one or more intermediate CA certificates, and the end-entity certificate. The client validates the chain by verifying each signature up to the root CA, which is trusted (stored in the client's trust store). The root CA is the ultimate trust anchor; its public key is pre-installed in the client's software.
Research post-quantum cryptography. Write a 500-word report that explains:
Complete answer would cover Shor's algorithm and its impact, the NIST PQC competition, finalists such as CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and SPHINCS+, and the expected timeline for transitioning to PQC.
Describe how digital signatures are used in software distribution (e.g., code signing). What security properties does code signing provide, and what are the risks if the private key is compromised?
Code signing ensures that the software comes from the claimed publisher and has not been altered. It provides integrity and authentication. If the private key is compromised, an attacker could sign malicious code that would appear legitimate, leading to widespread compromise.
Implement RSA key generation, encryption, and decryption for small primes (e.g., 16-bit) in your preferred language. Test it with sample messages. Write a report on your implementation and observations.
Complete answer would include code, test results, and a discussion of the modular exponentiation algorithm (e.g., square-and-multiply). Observations might include the slow speed of RSA for large keys and the importance of using a secure random source for prime generation.
This tutorial has introduced the fundamental concepts of public-key (asymmetric) cryptography. We began with the key distribution problem, which motivated the invention of public-key cryptography, and we explored how the key pair model solves this problem. We contrasted symmetric and asymmetric cryptography, highlighting the trade-offs in performance, key management, and security services.
We described the public-key cryptosystem model and the security services it provides: confidentiality, authentication, and non-repudiation. We reviewed the mathematical foundations—integer factorization, discrete logarithms, and elliptic curve discrete logarithms—that underpin the major algorithms. We provided an overview of RSA, Diffie-Hellman, and ECC, and we introduced the concept of Public-Key Infrastructure (PKI) for binding public keys to identities.
We discussed hybrid cryptosystems, which combine the efficiency of symmetric encryption with the key management advantages of public-key cryptography, and we analyzed the security of public-key systems, including known attacks and the post-quantum threat. Finally, we surveyed real-world applications and presented case studies that illustrate the historical and practical significance of public-key cryptography.
With this foundation, you are now prepared to dive deeper into each major algorithm in the upcoming tutorials.
In Tutorial 2.12: RSA Cryptography, we will explore the RSA algorithm in detail, including key generation, encryption, decryption, security analysis, and implementation considerations. RSA is the most widely used public-key algorithm and serves as a cornerstone of modern security.