Unit 5: Public Key Cryptography

Public-key (asymmetric) cryptography, introduced by Diffie and Hellman (1976), replaces the single shared secret of symmetric ciphers with a mathematically linked key pair: a public key that anyone may use to encrypt or verify, and a private key held only by the owner. Its security rests on one-way functions with trapdoors — operations easy to compute but computationally infeasible to invert without secret information. The number-theoretic hard problems below underpin every scheme in this unit.

• Key pair: each user owns (public key, private key); the public key is published, the private key never leaves the owner.
• Trapdoor one-way function: f(x) is easy, f⁻¹(y) is infeasible unless a secret (the trapdoor) is known — e.g. multiplying primes is easy, factoring their product is hard.
• Discrete logarithm problem (DLP): given g, p, and g^x mod p, recovering x is infeasible for large prime p.
• Integer factorisation problem (IFP): given n = p·q for large primes p, q, recovering p and q is infeasible.
• Convention: all arithmetic is modular; mod denotes remainder, gcd the greatest common divisor, and φ(n) Euler's totient (count of integers < n coprime to n).

II. Diffie–Hellman Key Exchange — Establishing a shared secret over a public channel

A protocol (not an encryption scheme) that lets two parties agree on a common secret key without ever transmitting it, its security resting on the DLP.

A. Introduction to Public-Key Cryptography

The founding idea that a secret can be built from public exchanges.

• Break with symmetric crypto: removes the need for a pre-shared key distributed over a secure channel — the central weakness of symmetric systems.
• Public parameters: a large prime p and a primitive root (generator) g of the multiplicative group mod p are agreed openly.
• Asymmetry of effort: computing g^a mod p is fast (square-and-multiply); reversing it to find a requires solving the DLP.
• Scope: produces a shared key for later symmetric encryption; it does not itself encrypt messages.

B. Diffie–Hellman Key Exchange

The protocol steps and the algebraic identity that makes both sides arrive at the same value.

• Setup: public p (prime) and g (generator mod p).
• Private choices: Alice picks secret a, Bob picks secret b.
• Public exchange: each sends a power of g:

Alice computes  A = g^a mod p  → sends A to Bob
Bob   computes  B = g^b mod p  → sends B to Alice

• Shared secret: each raises the received value to their own secret:

Alice: K = B^a mod p = (g^b)^a mod p = g^(ab) mod p
Bob:   K = A^b mod p = (g^a)^b mod p = g^(ab) mod p

• Symbols: p prime modulus; g generator; a, b private exponents; A, B public values; K shared key g^(ab) mod p.
• Worked example: let p = 23, g = 5, a = 6, b = 15.
  • A = 5^6 mod 23 = 8; B = 5^15 mod 23 = 19.
  • Alice: 19^6 mod 23 = 2; Bob: 8^15 mod 23 = 2. Shared key K = 2.
• Limitation — man-in-the-middle: an attacker who intercepts A and B can substitute their own values, since the protocol offers no authentication; it must be paired with signatures or certificates.

III. The RSA Cryptosystem — Encryption and signatures from the hardness of factoring

The first practical public-key encryption scheme (Rivest, Shamir, Adleman, 1977), whose trapdoor is the difficulty of factoring n = p·q.

A. The RSA Cryptosystem (Key Generation)

RSA's security follows from the fact that knowing n does not reveal φ(n) without the factors p and q.

• Choose primes: select two large distinct primes p and q.
• Compute modulus: n = p·q — published as part of the public key.
• Compute totient: φ(n) = (p−1)(q−1) — kept secret; its secrecy is equivalent to factoring n.
• Choose public exponent: pick e with 1 < e < φ(n) and gcd(e, φ(n)) = 1 (commonly e = 65537).
• Compute private exponent: d ≡ e⁻¹ mod φ(n), i.e. e·d ≡ 1 (mod φ(n)), found via the extended Euclidean algorithm.
• Key pair: public key (e, n); private key (d, n) (with p, q, φ(n) discarded or secured).
• Symbols: p, q primes; n modulus; φ(n) totient; e encryption exponent; d decryption exponent.

B. RSA Encryption

Turning a message into ciphertext using only the recipient's public key.

• Message encoding: represent the plaintext as an integer m with 0 ≤ m < n.
• Encryption rule:

c = m^e mod n

• Public operation: anyone with (e, n) can encrypt; no secret is needed to produce c.
• Symbols: m plaintext integer; c ciphertext; (e, n) public key.
• Why it is hard to invert: recovering m from c without d requires taking an e-th root mod n, believed as hard as factoring n.
• Practical note: raw ("textbook") RSA is deterministic and insecure; real use applies padding (e.g. OAEP) so identical messages do not yield identical ciphertexts.

C. RSA Decryption

Recovering the plaintext with the private exponent, justified by Euler's theorem.

• Decryption rule:

m = c^d mod n

• Correctness: since e·d ≡ 1 (mod φ(n)), we have e·d = 1 + k·φ(n), so c^d = m^(ed) = m^(1+kφ(n)) = m·(m^φ(n))^k ≡ m (mod n) by Euler's theorem.
• Symbols: c ciphertext; d private exponent; n modulus; m recovered plaintext.
• Efficiency: decryption is sped up using the Chinese Remainder Theorem, computing m mod p and m mod q separately then recombining — roughly four times faster.
• Worked example: p = 5, q = 11 → n = 55, φ(n) = 40. Choose e = 3 (gcd(3,40)=1); then d = 27 (3·27 = 81 ≡ 1 mod 40).
  • Encrypt m = 7: c = 7^3 mod 55 = 343 mod 55 = 13.
  • Decrypt: m = 13^27 mod 55 = 7. ✓

D. Applications and Limitations

The reach and constraints of RSA in practice.

• Confidentiality and signatures: encrypting with the public key gives secrecy; "encrypting" a hash with the private key gives a verifiable digital signature.
• Speed: slow relative to symmetric ciphers, so RSA typically encrypts only a symmetric session key (hybrid encryption).
• Key size: requires ≈2048–3072-bit n for current security; keys grow as factoring methods improve.
• Vulnerabilities: small e with unpadded messages, shared moduli, or poor prime generation break the scheme — hence mandatory padding.

IV. The ElGamal Cryptosystem — Public-key encryption from the discrete logarithm

An encryption scheme (Taher ElGamal, 1985) built directly on the DLP, extending the Diffie–Hellman idea from key agreement to full message encryption.

A. The ElGamal Cryptosystem (Structure and Keys)

ElGamal encrypts by masking the message with a freshly generated Diffie–Hellman-style secret each time.

• Public parameters: large prime p and generator g of the group mod p.
• Key generation: recipient picks private key x (1 < x < p−1) and computes public key h = g^x mod p.
• Key pair: public (p, g, h); private x.
• Randomised encryption — the sender chooses a fresh ephemeral key k per message:

c1 = g^k mod p
c2 = m · h^k mod p       (m = plaintext, 0 ≤ m < p)

ciphertext is the pair (c1, c2).

• Decryption — recover the mask, then divide it out:

s = c1^x mod p = g^(kx) mod p
m = c2 · s⁻¹ mod p

since c2 = m·(g^x)^k = m·g^(kx) and s = g^(kx), the factor cancels.

• Symbols: x private key; h public key; k ephemeral secret; (c1, c2) ciphertext pair; s shared mask; s⁻¹ its modular inverse.

B. Comparison and Limitations

How ElGamal contrasts with RSA and where it is weak.

1. RSA: based on factoring (IFP); deterministic without padding; ciphertext is a single value the size of n.
2. ElGamal: based on the DLP; inherently randomised via k, so the same plaintext yields different ciphertexts; ciphertext is a pair, doubling its size.
   • Ephemeral-key rule: a fresh, unpredictable k is essential — reusing k across messages leaks relationships and can expose plaintexts.
   • Ciphertext expansion: encrypted output is twice the plaintext length, a cost of the randomisation.
   • Foundation for other schemes: its structure generalises to elliptic-curve encryption and to the Digital Signature Algorithm (DSA), giving it lasting theoretical importance.