Public key cryptography, RSA and key exchange notes — Unit 4

In 1976, Whitfield Diffie and Martin Hellman published a paper that revolutionized security by solving the symmetric key distribution problem. They proposed an 'asymmetric' cryptosystem.

⇒1.1 The Concept

Instead of one shared secret key, every user generates a mathematically linked pair of keys:

• Public Key: Published openly to the entire world. Used by anyone to encrypt messages intended for you.
• Private Key: Kept absolutely secret. Used by you to decrypt messages that were encrypted with your public key.

It is mathematically infeasible to determine the Private Key even if you know the Public Key.

⇒2.1 Encryption (Confidentiality)

Alice wants to send a secret message to Bob. Alice looks up Bob's Public Key. She encrypts the message using Bob's Public Key. The resulting ciphertext can ONLY be decrypted by Bob's Private Key. Even Alice cannot decrypt it after she encrypts it.

⇒2.2 Digital Signatures (Authentication)

Alice wants to prove she wrote a message. Alice encrypts the message using her own Private Key. She sends the ciphertext to Bob. Bob decrypts it using Alice's Public Key. Because only Alice's Private Key could have generated a ciphertext that successfully decrypts with Alice's Public Key, Bob is 100% certain Alice sent it.

Created by Rivest, Shamir, and Adleman in 1977, RSA was the first algorithm to practically implement both public-key encryption and digital signatures. It relies on the mathematical difficulty of factoring the product of two large prime numbers.

⇒3.1 Key Generation Step 1

• 1. Choose two very large, random prime numbers, `p` and `q` (e.g., 1024 bits each).
• 2. Calculate the modulus `n = p * q`. The value `n` will be part of the public key.
• 3. Calculate Euler's totient function: `φ(n) = (p-1) * (q-1)`. Keep this secret.

⇒4.1 Generating e and d

• 4. Choose a public exponent `e`. It must be an integer between 1 and `φ(n)`, and it must be coprime to `φ(n)` (i.e., `gcd(e, φ(n)) = 1`). Commonly, `e = 65537`.
• 5. Calculate the private exponent `d` such that `(d * e) ≡ 1 (mod φ(n))`. This is done using the Extended Euclidean Algorithm.

⇒4.2 The Keys

Public Key = `{e, n}`
Private Key = `{d, n}`
The primes `p` and `q`, and `φ(n)`, are securely deleted.

To encrypt or decrypt, the plaintext message `M` must be represented as an integer such that `0 ≤ M < n`.

⇒5.1 The Operations

• Encryption: `C = M^e mod n`
• Decryption: `M = C^d mod n`

Because of Euler's theorem, `(M^e)^d mod n = M^(e*d) mod n = M`. The math guarantees that applying exponent `d` perfectly reverses exponent `e`.

Why can't a hacker derive the private key `d` if they know the public key `{e, n}`?

To calculate `d`, the hacker must use the formula: `d e ≡ 1 (mod φ(n))`. The hacker knows `e`. But to solve the equation, the hacker needs `φ(n)`. To calculate `φ(n)`, which is `(p-1)(q-1)`, the hacker must know `p` and `q`.
To find `p` and `q`, the hacker must factor the massive number `n`.

Currently, no classical algorithm exists that can factor a 2048-bit number in a realistic timeframe. The security of RSA relies entirely on the premise that prime factorization is a computationally intractable problem.

RSA allows encryption, but Diffie-Hellman (DH) serves a different, crucial purpose: allowing two parties with no prior knowledge of each other to jointly establish a shared secret key over an insecure channel.

⇒7.1 The Setup

Alice and Bob publicly agree on two numbers (not secret): a large prime `p`, and `g`, which is a primitive root modulo `p`.

• 1. Alice selects a random private number `a`. She calculates her public value `A = g^a mod p` and sends `A` to Bob.
• 2. Bob selects a random private number `b`. He calculates his public value `B = g^b mod p` and sends `B` to Alice.
• 3. Alice receives `B`. She calculates the shared key `K = B^a mod p`.
• 4. Bob receives `A`. He calculates the shared key `K = A^b mod p`.

Mathematically, Alice did `(g^b)^a mod p`, and Bob did `(g^a)^b mod p`. Both calculate `g^(ab) mod p`, resulting in the exact same key.

A hacker listening sees `p`, `g`, `A`, and `B`. Because calculating the discrete logarithm is hard, the hacker cannot find `a` or `b` to recreate the key.

While mathematically secure against eavesdroppers, raw Diffie-Hellman is completely defenseless against an active Man-in-the-Middle attack.

⇒9.1 The Exploit

Darth intercepts Alice's public value `A`. Darth generates his own private number `d`, creates a public value `D = g^d mod p`, and sends `D` to Bob, pretending it's from Alice.

Bob calculates a shared key with Darth. Alice calculates a shared key with Darth. Alice thinks she is encrypting data for Bob, but Darth intercepts it, decrypts it, reads it, re-encrypts it with Bob's key, and passes it on. Neither Alice nor Bob knows Darth is there.

RSA requires 2048-bit keys to be secure. The math required to compute exponents on 2048-bit numbers drains the batteries of smartphones and IoT devices quickly. ECC offers a solution.

⇒10.1 The Concept

Instead of modular exponentiation on integers, ECC performs math on the algebraic structure of elliptic curves over finite fields. The equation takes the form `y^2 = x^3 + ax + b`.

You can define an 'addition' operation between two points on the curve. Point `P + P = 2P`. Adding `P` to itself `k` times is scalar multiplication: `Q = kP`. Given `P` and `Q`, finding `k` is the Elliptic Curve Discrete Logarithm Problem (ECDLP).

⇒11.1 Key Size Efficiency

The ECDLP is mathematically much harder to crack than RSA's prime factorization problem. Therefore, ECC achieves the same level of security with vastly smaller keys.

• A 256-bit ECC key provides the exact same security as a 3072-bit RSA key.

Smaller keys mean less data transmitted over networks, less memory used for storage, and most importantly, much faster calculations for the CPU, preserving battery life. Modern protocols (like WhatsApp encryption and Bitcoin) use ECC almost exclusively.

If public-key cryptography (RSA) solves the key distribution problem, why do we still use AES?

⇒12.1 The Speed Discrepancy

Because RSA requires massive modular exponentiation, it is roughly 1,000 times slower than AES in hardware. Encrypting a 1GB video file with RSA is practically impossible.

⇒12.2 The Hybrid Solution

Real-world systems (like HTTPS) use a hybrid approach. The parties use RSA or Diffie-Hellman to securely establish a 256-bit shared session key. Once the key is established, they switch to AES (using that session key) to encrypt the actual bulk data at high speed.

Public keys are meant to be public. If Bob wants to send Alice a message, he needs her public key. But how does Bob know the public key he downloaded actually belongs to Alice and not Darth (who is attempting a MitM attack)?

⇒13.1 Public-Key Infrastructure (PKI)

We need a trusted authority to bind an identity to a public key. This introduces the concept of Digital Certificates and the web of trust, which we will explore in the next unit.

• RSA: Based on Integer Factorization. Used for encryption and digital signatures. Requires large keys.
• Diffie-Hellman: Based on Discrete Logarithms. Used strictly for establishing shared keys. Cannot be used to encrypt bulk data.
• ECC: Based on Elliptic Curve Discrete Logarithms. Provides the functionality of RSA/DH but with vastly smaller key sizes and better performance.