Public‑Key Cryptography and Advanced Protocols

Public-Key Cryptography Introduction Public-key cryptography revolutionized secure communication by solving a fundamental problem: how can two parties communicate securely without first sharing a secret key? Unlike symmetric cryptography, where the same key encrypts and decrypts, public-key systems use a pair of mathematically related keys. This section explains how these systems work, why they're secure, and how they're used in modern cryptography. The Public-Key Principle In a public-key cryptosystem, each person has two mathematically related keys: Public Key: Can be freely shared with anyone and used by others to encrypt messages or verify signatures Private Key: Kept secret by the owner and used to decrypt messages or create digital signatures The crucial property is this: it must be computationally infeasible to derive the private key from the public key, even if an attacker knows the public key and has powerful computers. This asymmetry is what makes public-key cryptography possible. Consider how this differs from symmetric encryption: With symmetric keys, both parties need the same secret key. In contrast, public-key encryption looks like this: Bob can encrypt a message using Alice's public key, and only Alice (who has the private key) can decrypt it. Notice that the public key is green (shareable) while the private key is red (secret). Digital Signatures: Authentication and Non-Repudiation While public-key encryption provides confidentiality, digital signatures solve a different problem: How can Alice prove she created a message, and prove that Bob can't deny receiving it? Digital signatures work in reverse from encryption: Alice uses her private key to "sign" a message (creating a signature) Bob uses Alice's public key to verify the signature If the signature is valid, Bob knows the message came from Alice and hasn't been altered This provides two important security properties: Authentication: The signature proves the message came from Alice (the only one with her private key) Non-repudiation: Alice cannot later claim she didn't send the message, since only she could have created a valid signature with her private key Common digital signature schemes include RSA signatures and the Digital Signature Algorithm (DSA). The process typically involves hashing the message first, then signing the hash—this is faster and more secure than signing the entire message. The Hard Mathematical Problems Public-key cryptography's security rests entirely on the assumption that certain mathematical problems are computationally hard—meaning no efficient algorithm exists to solve them in polynomial time, even for the world's most powerful computers. Integer Factorization RSA's security depends on the difficulty of the integer factorization problem: given a large number $n$ that is the product of two large prime numbers (a semiprime), find those two prime factors. Why is this hard? Multiplying two large primes is easy: $p \times q = n$ takes milliseconds. But reversing this—factoring $n$ back into $p$ and $q$—appears to require exponential time. No one has found a fast factorization algorithm, and many believe none exists for classical computers. Discrete Logarithm Problem Diffie-Hellman and Digital Signature Algorithm rely on the discrete logarithm problem: given a group $G$, a generator $g$, and a value $y = g^x$, find the exponent $x$. Again, the forward direction is fast: compute $g^x$ using fast exponentiation. But finding $x$ from $g^x$ seems to require trying exponentially many possibilities (on average, half of all possible values). Elliptic Curve Problems Elliptic Curve Cryptography (ECC) relies on the discrete logarithm problem over elliptic curves. Interestingly, the elliptic curve discrete logarithm problem is believed to be harder than regular integer factorization for equivalent key sizes. This is why ECC became popular in the 1990s—it provides the same security strength with much shorter keys. Why does this matter? Shorter keys mean faster computation, smaller hardware, and lower power consumption. A 256-bit elliptic curve key provides roughly the same security as a 2048-bit RSA key. <extrainfo> A Note on Quantum Computers Quantum computers could theoretically solve both integer factorization and discrete logarithm problems efficiently using Shor's algorithm. However, quantum computers capable of breaking current encryption don't yet exist. This remains an active area of research, and efforts are underway to develop "post-quantum" cryptographic algorithms. </extrainfo> Key Size Implications The security of public-key systems depends critically on key size. Larger keys are harder to break, but they also increase computation time and storage requirements. RSA requires much larger keys than ECC to achieve the same security level: RSA: 2048-bit keys are standard for current security needs; 3072 or 4096 bits for long-term security ECC: 256-bit keys provide equivalent security to 2048-bit RSA; 384-bit keys provide equivalent security to 3072-bit RSA This difference is why ECC has become increasingly popular for modern applications, especially on devices with limited computational power or battery life. Real-World Security: Beyond Mathematics Theoretical mathematical security is necessary but not sufficient. Real cryptographic systems can fail due to implementation flaws and real-world attacks. Side-Channel Attacks Side-channel attacks exploit information leaked from how a cryptographic algorithm is physically implemented, rather than attacking the mathematics directly. Timing attacks are a common example: if decryption takes different amounts of time depending on the key value, an attacker can measure these differences and gradually learn the secret key. For instance, if a comparison operation exits early when it finds a mismatch, the time taken reveals information about the correct key bytes. Traffic Analysis Even when messages are encrypted, attackers can gather information by observing: Patterns: Who communicates with whom Message lengths: Encrypted messages reveal their size, which can hint at content Timing: When messages are sent can reveal activities Administrative Weaknesses No cryptosystem is stronger than how it's managed. Common failures include: Using keys that are too short Reusing keys across different purposes Storing keys insecurely Poor random number generation Social Engineering Often the weakest link isn't mathematics—it's people. Techniques like bribery, extortion, blackmail, espionage, and coercive interrogation are often more cost-effective than mathematical cryptanalysis. Hybrid Cryptosystems While public-key cryptography solves the key exchange problem, it's much slower than symmetric encryption. The solution is hybrid cryptosystems, which combine the best of both worlds: How they work: Use a symmetric cipher (like AES) to encrypt the actual data—this is fast Use a public-key cipher (like RSA or ECC) to encrypt the symmetric key itself For example, Alice can: Generate a random symmetric key $K$ Encrypt her message with $K$ using AES Encrypt $K$ with Bob's public key using RSA Send both the encrypted message and encrypted key to Bob Bob decrypts by: Using his private key to decrypt the symmetric key $K$ Using $K$ to decrypt the message with AES This approach gets the security benefits of public-key cryptography (no need to pre-share secrets) while maintaining the speed of symmetric encryption. Nearly all real-world secure communication uses this hybrid approach. Typical Cryptographic Systems El-Gamal Encryption El-Gamal is a public-key encryption scheme based on the discrete logarithm problem. It's less commonly used than RSA today, but it's important because: It demonstrates how the discrete logarithm problem can be used for encryption It's probabilistic (the same plaintext encrypts to different ciphertexts), which provides better security than deterministic schemes Schnorr Signatures The Schnorr signature algorithm creates digital signatures using the discrete logarithm problem. It's notable for having provable security—its security can be proven under reasonable assumptions about the difficulty of the discrete logarithm problem. Signal Protocol The Signal protocol is a modern secure messaging protocol used by applications like Signal and WhatsApp. It combines multiple cryptographic primitives: Elliptic curve cryptography for key exchange AES for message encryption HMAC for message authentication It's designed to provide forward secrecy (old messages remain secure even if a key is later compromised) and authentication between parties. <extrainfo> Advanced Systems (Possibly Beyond Exam Scope) Several sophisticated cryptographic systems exist for specialized purposes: Zero-knowledge proofs: Allow proving knowledge of a secret without revealing it. Useful for authentication and privacy-preserving protocols. Secret sharing: Distribute a secret among multiple participants so that a threshold number (e.g., 3 out of 5) must cooperate to reconstruct it. Useful for protecting critical keys. Electronic cash systems: Enable anonymous digital payments using cryptographic protocols. Signcryption: Combines digital signature and encryption into a single efficient operation, useful when both authentication and confidentiality are needed. </extrainfo> Summary Public-key cryptography solves the fundamental problem of secure communication without pre-shared secrets by relying on the computational difficulty of problems like integer factorization and discrete logarithms. Digital signatures provide authentication and non-repudiation using the private/public key pair. While the mathematical foundations are strong, real-world security depends on proper implementation (avoiding side-channel leaks), careful key management, and awareness of social engineering threats. Hybrid cryptosystems combine public-key and symmetric encryption to gain both security and speed, and they form the basis of most modern secure communication protocols.