week 9 asymmetric and hybrid encryption

Overview of Asymmetric and Hybrid Encryption

Chapter Focus: This material covers asymmetric encryption for secret sharing with public keys, hybrid encryption for data protection, and the specific standards governing these practices.
Symmetric Encryption Drawback: To communicate securely with multiple parties using only symmetric encryption, a unique shared secret would be required for every individual. This is unfeasible because one cannot predict who will want to message them, and the manual exchange of symmetric keys is a tedious process.
The Role of Asymmetric Encryption: It addresses symmetric limitations by allowing anyone with your public key to encrypt a message for you. Only the holder of the associated private key can decrypt these messages.
Primary Limitations of Asymmetric Encryption: * Data Size: It is constrained by the maximum size of data that can be processed in a single operation. * Rate/Speed: The encryption and decryption rates are significantly slower than symmetric counterparts because asymmetric constructions utilize mathematical operations whereas symmetric primitives manipulate bits.

Mechanics of Asymmetric Encryption

Key Generation: The algorithm produces a key pair consisting of two parts: * Public Key: Intended for distribution and public sharing. * Private Key: Must be kept strictly secret by the owner.
Security Parameters: Like other cryptographic primitives, a security parameter is used to determine the bit security of the algorithm.
Operation: Anyone uses the public key for encryption. Only the private key holder can perform decryption.
Integrity and Coherence: Similar to authenticated decryption, asymmetric decryption will fail if the provided ciphertext is incoherent.
Authentication Caveats: Currently, asymmetric encryption does not inherently solve authentication: * Users may encrypt to a public key they believe belongs to Alice without proof. * Alice receives a message but cannot be certain of the sender's identity. * Note: Real-world protocols solve this "bootstrapping" issue using digital signatures (covered in later chapters).

Use Cases and Key Exchange

Key Encapsulation: Asymmetric encryption is frequently used to perform a key exchange. A user generates a symmetric key and encrypts it using the recipient's public key (Alice). This process is known as encapsulating a key.
Shared Secret Establishment: Once Alice decrypts the encapsulated key, both parties share a symmetric secret for further communication.
Algorithm Preferences: * RSA: Historically the primary algorithm for key exchange via asymmetric encryption. * ECDH (Elliptic Curve Diffie-Hellman): Modern protocols increasingly favor ECDH over RSA. * Reasons for ECDH Preference: Many vulnerabilities discovered in RSA standards/implementations and the efficiency afforded by the smaller parameter sizes in ECDH.

Hybrid Encryption Principles

The Limitation of RSA Input Sizes: Practical asymmetric encryption is limited based on security parameters: * 1024-bit keys: Message must be $\le 117\,bytes$ . * 2048-bit keys: Message must be $\le 256\,bytes$ . * 4096-bit modulus: Message must be $\approx 500\,bytes$ or fewer.
Definition of Hybrid Encryption: To circumvent size limits, applications use hybrid encryption. The message length limit is determined by the symmetric authenticated encryption algorithm used rather than the asymmetric part.
Core Components: * Data Encapsulation Mechanism (DEM): The symmetric key is used with an authenticated encryption algorithm (e.g., $AES-CBC-HMAC$ ) to encrypt the actual message. * Key Encapsulation Mechanism (KEM): The symmetric key itself is encrypted asymmetrically using the recipient's public key.
Transmission: The sender transmits both the KEM result (encrypted key) and the DEM result (encrypted message) to the recipient.

Mathematical Foundations: Textbook RSA

Mathematical Context: RSA operates within the multiplicative group of numbers modulo a prime $p$ , defined as the set of strictly positive integers ${1, 2, 3, 4, \dots, p-1}$ .
Data as Numbers: Computers interpret messages as a series of bytes, which are then treated as numbers. For a 4,096-bit prime, a message can contain up to approximately 500 characters.
Generators and Subgroups: Exponentiating a number can generate other numbers that form a subgroup. In RSA, the "generator" is effectively the message itself.
Key Generation Procedure: 1. Generate two large prime numbers $p$ and $q$ . 2. Compute the modulus $N = p \times q$ . 3. Compute Euler's totient function $\phi(N) = (p - 1) \times (q - 1)$ . 4. Select a public exponent $e$ such that 1 < e < \phi(N) and $e$ is co-prime to $\phi(N)$ . 5. Calculate the private exponent $d$ such that $(d \times e) \pmod{\phi(N)} = 1$ .
Public and Private Key Pairs: * Public Key: $(e, N)$ * Private Key: $(d, N)$
Operational Formulas: * Encryption: $ciphertext = message^e \pmod N$ * Decryption: $message = ciphertext^d \pmod N$
Hard Problem (Security Basis): RSA relies on the Factorization Problem. Without knowing $p$ and $q$ , one cannot compute $\phi(N)$ or the private key $d$ .

Comparative Hard Mathematical Problems

Diffie-Hellman (DH): Relies on the Discrete Logarithm Problem ( $A = g^a \pmod p$ is easy, finding $a$ is hard).
Elliptic Curve Diffie-Hellman (ECDH): Relies on the Elliptic Curve Discrete Logarithm Problem ( $A = [a]G$ is easy, finding $a$ is hard).
RSA: Relies on the Factoring Problem ( $N = p \times q$ is easy, finding $p, q$ is hard).

RSA Standards and Padding

The Brute-Force Problem in Textbook RSA: If small messages (e.g., $m=2$ ) are encrypted, an attacker can encrypt all small numbers and compare them to the ciphertext to deduce the original message.
Padding Solution: Standards use non-deterministic padding to maximize message size before encryption, making brute-force impossible.
RSA PKCS#1 v1.5: * Structure: Starts with message bytes where the first two bytes are $0x00$ and $0x02$ , followed by non-zero random bytes, then a $0x00$ byte to signal the end of padding, followed by the actual message bytes. * Format: $0x00\,0x02\,[some\,non-zero\,bytes]\,0x00\,[message\,bytes]$ . * Vulnerability: Daniel Bleichenbacher demonstrated that this padding can be cracked using a chosen cipher attack (the "Million Message Attack").
RSA-OAEP (Optimal Asymmetric Encryption Padding): * Standardized as RSA PKCS#1 v2.2. * Requires a modulus $N$ between 2,048 and 4,096 bits. * Utilizes a Mask Generation Function (MGF) to randomize and enlarge/reduce input. * MGF Definition: A function that takes an arbitrary length input and produces a random-looking arbitrary length output by hashing the input with a counter and concatenating digests. * Encoding components: Label ( $L$ ), Hash Function ( $Hash$ ), seed, and data block ( $DB$ ).

ECIES and RSA-KEM

RSA-KEM: A variant of hybrid encryption that utilizes a Key Derivation Function (KDF) to derive the symmetric key.
ECIES (Elliptic Curve Integrated Encryption Scheme): * A hybrid encryption scheme substituting the asymmetric primitive with ECDH-based key exchange. * Process: Sender generates an ephemeral key pair. They perform an (EC)DH key exchange using Alice's public key and the ephemeral private key. * Data Protection: The resulting shared secret is used with an authenticated symmetric algorithm (e.g., $AES-GCM$ ) to encrypt the message. * Communication: Sender transmits the ephemeral public key and the ciphertext to Alice. * Alice's Decryption: Alice uses her private key and the sender's ephemeral public key to recreate the shared secret and decrypt the message.

Chapter Summary

Asymmetric encryption is rarely used directly for messages due to size limitations.
Hybrid encryption is the standard for large datasets, combining asymmetric (or key exchange) with symmetric authenticated encryption.
RSA PKCS#1 v1.5 is considered broken; RSA-OAEP (v2.2) is the preferred alternative.
ECIES is the most widely used hybrid scheme because of its smaller parameter sizes and reliance on robust ECC standards.
Implementation variations are acceptable as long as interoperable applications utilize the same standards.