Public Key Cryptography Foundations

John

Complete Guide to RSA, Rabin, Goldwasser-Micali, and ElGamal Cryptosystems

Part I: RSA Encryption – Plain and OAEP

RSA Algorithm Overview

RSA remains one of the most widely used public-key cryptosystems. Understanding both its basic form and secure implementations is crucial for modern cryptography.

Key Generation Process

  1. Choose two large primes: p and q (typically 1024+ bits each)
  2. Compute modulus: n = p × q
  3. Compute Euler’s totient: φ(n) = (p-1)(q-1)
  4. Choose public exponent: e such that gcd(e, φ(n)) = 1 (commonly e = 65537)
  5. Compute private exponent: d such that ed ≡ 1 (mod φ(n))

Key Distribution

  • Public Key: (n, e) – shared with everyone
  • Private Key: (n, d) – kept secret by owner
  • Secret Values: p, q, φ(n) – must be destroyed after key generation

Encryption and Decryption Operations

Operation Formula Who Performs Key Used
Encryption c = m^e mod n Sender (Anyone) Public Key (n, e)
Decryption m = c^d mod n Receiver (Key Owner) Private Key (n, d)

Small RSA Example

Key Generation:

  • Choose p = 7, q = 11
  • n = 7 × 11 = 77
  • φ(n) = (7-1)(11-1) = 6 × 10 = 60
  • Choose e = 13 (gcd(13, 60) = 1)
  • Find d: 13d ≡ 1 (mod 60) → d = 37
  • Public Key: (77, 13)
  • Private Key: (77, 37)

Encryption Example:

  • Message: m = 5
  • Encryption: c = 5^13 mod 77 = 26

Decryption Verification:

  • Ciphertext: c = 26
  • Decryption: m = 26^37 mod 77 = 5 ✓

Mathematical Foundation

Why RSA Works:

RSA’s security relies on Euler’s Theorem: If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n)

RSA Correctness Proof:

Given: ed ≡ 1 (mod φ(n)), so ed = kφ(n) + 1 for some integer k

Decryption:
c^d = (m^e)^d = m^ed = m^(kφ(n) + 1) = m^(kφ(n)) × m = (m^φ(n))^k × m

By Euler's Theorem: m^φ(n) ≡ 1 (mod n)
Therefore: c^d ≡ 1^k × m ≡ m (mod n)

Plain RSA Vulnerabilities

1. Deterministic Encryption

Problem: Same plaintext always produces same ciphertext
Attack: Dictionary attacks, pattern recognition
Example: Encrypt “YES” → always produces same ciphertext, allowing vote tracking

2. Multiplicative Property

Property: RSA(m₁) × RSA(m₂) = RSA(m₁ × m₂)
Attack Example:

  • Attacker intercepts c = RSA(m)
  • Computes c’ = c × RSA(2) = RSA(2m)
  • Tricks receiver into decrypting c’ → gets 2m
  • Computes m = (2m)/2

3. Small Message Attack

Problem: If m^e < n, then c = m^e (no modular reduction)
Attack: Simply compute eth root of c to recover m

4. Common Modulus Attack

Setup: Two users share same n but have different exponents e₁, e₂
Attack: If gcd(e₁, e₂) = 1, can recover plaintext without private keys

OAEP (Optimal Asymmetric Encryption Padding)

Purpose and Goals

  • Randomization: Make encryption probabilistic
  • All-or-Nothing: Attacker must recover entire padded message
  • Chosen Ciphertext Security: Provably secure against adaptive attacks
  • Practical: Efficient and implementable

OAEP Construction

Input: Message m, random string r

Parameters:

  • k₀ = length of r (typically 160 bits)
  • k₁ = number of zero bits added to message
  • G: {0,1}^k₀ → {0,1}^(n-k₀) (mask generation function)
  • H: {0,1}^(n-k₀) → {0,1}^k₀ (hash function)

OAEP Padding Process

  1. Pad message: m’ = m || 0^k₁
  2. Apply first mask: X = m’ ⊕ G®
  3. Apply second mask: Y = r ⊕ H(X)
  4. Concatenate: padded_message = X || Y
  5. Convert to integer: apply RSA encryption

Security Properties of OAEP

  • Randomness: Different random r produces different ciphertexts
  • All-or-Nothing: Can’t partially decrypt without knowing both X and Y
  • Integrity: Invalid padding detected during decryption
  • Chosen Ciphertext Security: Secure against adaptive attacks

Plain RSA vs RSA-OAEP Comparison

Property Plain RSA RSA-OAEP
Deterministic Yes – same input always gives same output No – random padding makes it probabilistic
Malleable Yes – can modify ciphertext predictably No – modification breaks padding structure
CCA Secure No – vulnerable to chosen ciphertext attacks Yes – provably secure against CCA
Message Size Up to n-1 Reduced due to padding overhead
Performance Fast – direct RSA operation Slower – additional padding operations
Security Level Weak for practical use Strong – recommended for real applications

Part II: Rabin and Goldwasser-Micali Encryption Systems

The Rabin Cryptosystem

Mathematical Foundation: Quadratic Residues

Definition: An integer a is a quadratic residue modulo n if there exists an integer x such that x² ≡ a (mod n)

Examples:

  • Modulo 7: 1² ≡ 1, 2² ≡ 4, 3² ≡ 2, 4² ≡ 2, 5² ≡ 4, 6² ≡ 1
  • Quadratic residues mod 7: {1, 2, 4}
  • Non-residues mod 7: {3, 5, 6}

Rabin Key Generation

  1. Choose two large primes: p, q where p ≡ q ≡ 3 (mod 4)
  2. Compute modulus: n = p × q
  3. Public Key: n
  4. Private Key: (p, q)

Rabin Encryption and Decryption

Encryption: c = m² mod n
Decryption (using Chinese Remainder Theorem):

  1. Compute square roots modulo p: r₁ = ±c^((p+1)/4) mod p
  2. Compute square roots modulo q: r₂ = ±c^((q+1)/4) mod q
  3. Use CRT to combine: four possible messages m₁, m₂, m₃, m₄
  4. Select correct message using additional information

The Ambiguity Problem

Core Issue: Decryption produces four possible messages

Solutions:

  1. Redundancy in Message: Add known pattern to message
  2. Hash-based Selection: Include hash of message
  3. Parity Bits: Include least significant bits of message

The Goldwasser-Micali Cryptosystem

Historical Significance

  • First provably secure public-key cryptosystem (1982)
  • Introduced concept of semantic security
  • Demonstrated that probabilistic encryption is essential for security
  • Foundation for modern security definitions in cryptography

Mathematical Foundation: Quadratic Residuosity Problem

Problem Statement: Given n = pq (product of two primes) and an integer y with Jacobi symbol (y/n) = 1, determine whether y is a quadratic residue modulo n.

Goldwasser-Micali Key Generation

  1. Choose two large primes: p, q
  2. Compute modulus: n = p × q
  3. Find quadratic non-residue: y such that (y/n) = +1 but y is non-residue
  4. Public Key: (n, y)
  5. Private Key: (p, q)

Goldwasser-Micali Encryption (Bit-by-Bit)

Input: Single bit b ∈ {0, 1}

Process:

  1. Choose random r with gcd(r, n) = 1
  2. If b = 0: c = r² mod n (quadratic residue)
  3. If b = 1: c = y × r² mod n (quadratic non-residue)

Goldwasser-Micali Decryption

Input: Ciphertext c, private key (p, q)

Process:

  1. Compute Legendre symbol (c/p) using private key
  2. If (c/p) = +1: output bit 0
  3. If (c/p) = -1: output bit 1

Security Properties

  • Based on QRP: Security reduces to quadratic residuosity problem
  • Probabilistic: Same bit encrypted differently each time
  • Provable: First cryptosystem with provable security
  • IND-CPA Secure: Indistinguishable under chosen plaintext attack

Rabin vs Goldwasser-Micali Comparison

Property Rabin Goldwasser-Micali
Security Basis Integer Factorization Quadratic Residuosity Problem
Message Size Large (up to n) Single bit
Ciphertext Expansion 1:1 (same size as modulus) Very large (n bits per message bit)
Deterministic Yes No (probabilistic)
Decryption Ambiguity Four possible messages Unique decryption
Semantic Security Not semantically secure First semantically secure system
Practical Efficiency Reasonable Very inefficient
Historical Importance Early public-key system Foundation of modern crypto theory

Part III: ElGamal Encryption System

Mathematical Foundation: Discrete Logarithm Problem

The Discrete Logarithm Problem (DLP)

Definition: Given a cyclic group G, generator g, and element y ∈ G, find integer x such that g^x = y

In multiplicative group mod p:

  • Given: prime p, generator g, and y ∈ Z*_p
  • Find: x such that g^x ≡ y (mod p)
  • Constraint: 0 ≤ x ≤ p-2 (since |Z*_p| = p-1)

Why DLP is Hard

  • Exponentiation is easy: Computing g^x mod p is efficient (O(log x))
  • Logarithm is hard: No known polynomial-time algorithm
  • Best known algorithms: Sub-exponential but still impractical for large p
  • Comparison: Similar difficulty to integer factorization

ElGamal Key Generation

Algorithm:

  1. Choose large prime p (typically 1024-3072 bits)
  2. Choose generator g of Z*_p
  3. Choose private key x randomly from {1, 2, …, p-2}
  4. Compute public key y = g^x mod p

Key Distribution:

  • Public Parameters: (p, g) – can be shared by multiple users
  • Public Key: y – specific to each user
  • Private Key: x – kept secret by key owner

ElGamal Encryption

Algorithm:
Input: Message m, public key (p, g, y)

Steps:

  1. Choose random k from {1, 2, …, p-2}
  2. Compute c₁ = g^k mod p
  3. Compute c₂ = m × y^k mod p
  4. Output ciphertext: (c₁, c₂)

Key Properties:

  • Probabilistic: Different random k produces different ciphertext
  • Ciphertext Expansion: One plaintext block → two ciphertext blocks
  • Same Security: Each encryption uses fresh randomness

ElGamal Decryption

Algorithm:
Input: Ciphertext (c₁, c₂), private key x

Steps:

  1. Compute shared secret: s = c₁^x mod p
  2. Compute modular inverse: s^(-1) mod p
  3. Recover message: m = c₂ × s^(-1) mod p

Why Decryption Works:

  • From encryption: c₁ = g^k, c₂ = m × y^k
  • Since y = g^x: c₂ = m × (gx)k = m × g^(xk)
  • Compute: s = c₁^x = (gk)x = g^(kx) = g^(xk)
  • Therefore: c₂ × s^(-1) = m × g^(xk) × (g(xk))(-1) = m

Security Analysis

ElGamal Security Assumptions

1. Computational Diffie-Hellman (CDH) Problem:

  • Given: (g, g^a, g^b) in group G
  • Find: g^(ab)

2. Decisional Diffie-Hellman (DDH) Problem:

  • Given: (g, g^a, g^b, g^c) in group G
  • Decide: Is c = ab (mod |G|)?

ElGamal Security Properties

  • IND-CPA Secure: Secure against chosen plaintext attacks under DDH assumption
  • Not IND-CCA Secure: Vulnerable to chosen ciphertext attacks
  • Malleable: Can manipulate ciphertexts to get related plaintexts
  • Probabilistic: Same plaintext produces different ciphertexts

Malleability Property

Property: ElGamal(m₁) × ElGamal(m₂) = ElGamal(m₁ × m₂)

Proof:

  • ElGamal(m₁) = (g^k₁, m₁ × y^k₁)
  • ElGamal(m₂) = (g^k₂, m₂ × y^k₂)
  • Product = (g^(k₁+k₂), m₁m₂ × y^(k₁+k₂))
  • This is ElGamal encryption of m₁m₂ with randomness k₁+k₂

ElGamal Variants and Improvements

ElGamal in Different Groups

Group Advantages Disadvantages Key Size
Z*_p Well-studied, mature Large key sizes 1024-3072 bits
Elliptic Curves Smaller keys, same security More complex implementation 160-521 bits
Class Groups Different hardness assumptions Less studied Variable

Advanced Variants

Cramer-Shoup Cryptosystem:

  • Motivation: ElGamal is not CCA-secure
  • Solution: Add hash-based authentication
  • Result: First practical CCA-secure cryptosystem

Integrated Encryption Scheme (IES):

  • Hybrid Approach: Use ElGamal to encrypt symmetric key
  • Use symmetric encryption for bulk data
  • Combine with MAC for integrity

Implementation Considerations

Parameter Selection

  • Prime p: Use safe primes (p = 2q + 1 where q is also prime)
  • Generator g: Order should be large prime q
  • Random k: Must be fresh for each encryption
  • Key sizes: 1024 bits minimum, 2048-3072 recommended

Security Pitfalls

  • k Reuse: Never reuse random value k
  • Small Subgroup Attack: Ensure generator has large order
  • Invalid Curve Attack: Validate all public keys
  • Side-Channel Attacks: Use constant-time implementations

Conclusion

This comprehensive overview covers four fundamental cryptographic systems that have shaped modern cryptography:

  • RSA: From vulnerable plain implementation to secure OAEP variant
  • Rabin: Theoretically optimal but practically limited by decryption ambiguity
  • Goldwasser-Micali: Historically significant as the first provably secure system
  • ElGamal: Practical and widely used, forming the basis for many modern protocols

Understanding these systems provides crucial insight into cryptographic design principles, security assumptions, and the evolution of practical cryptography. While plain RSA and Goldwasser-Micali are primarily of theoretical interest today, RSA-OAEP and ElGamal (especially on elliptic curves) continue to secure communications worldwide.

Each system demonstrates different trade-offs between security, efficiency, and practical implementation concerns, illustrating the ongoing challenge of balancing theoretical security with real-world usability in cryptographic system design.