Public Key Cryptography

1. Public key encryption scheme

A public key encryption scheme consists of:

• M (plaintext space); C (ciphertext space)
• K_pubkey (public key space); K_privkey (private key space)
• A randomized algorithm G: K_pub x K_priv (key generation algorithm)
• A possibly randomized encryption algorithm E: K_pub x M → C
• A decryption algorithm D: K_priv x C → M

2. RSA Scheme

The scheme first introduced by Ron Rivest, Adi Shamir, and Leonard Adleman in 1978, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21 (2):pp. 120-126, 1978.

Key Generation

1. Choose random primes p and q with log₂p ≈ log₂q ≈ ℓ/2
2. Compute n = pq and φ(n) = (p-1)(q-1)
3. Choose e where 1 < e < φ(n) and gcd(e, φ(n)) = 1
4. Compute d = e⁻¹ mod φ(n)

Encryption/Decryption

• Message space: 𝕫ₙ* = {m ∈ 𝕫 | 0 ≤ m < n, gcd(m,n)=1}
• Encryption: 𝒞 = mᵉ mod n
• Decryption: m = 𝒞ᵈ mod n

Correctness of RSA

Assuming gcd(m,n)=1.

• By definition of E and D:

D((n,d),E((n,e),m))=D((n,d),mᵉ mod n)=(mᵉ mod n)ᵈ mod n = mᵉᵈ mod n

• By definition of e and d, we have ed = 1 mod φ(n).
• Since gcd(e, φ(n))=1, Euler's Theorem guarantees that

m^ed=m^1+kφ(n)=m¹(m^φ(n))^k=m mod n

Implementation Challenges

• Large prime generation

There is a determnistic primality test (PRIMES is in P, 2002), but it is much less efficient than the known best probabilisitc tests, so we use the probabilistic tests in practice. (Probabilistic primality tests such as the Miller-Rabin test are run many times with different randomness to shrink the probability of failure below an acceptable threshold.)

• Modular exponentiation (Square-and-Multiply algorithm)
• Efficient gcd computation (Extended Euclidean Algorithm)

3. Elliptic Curve Cryptography

Ground Concept: Diffie-Hellman Key Exchange

Diffie-Hellman key exchange works in every group.
Key exchange between Alice and Bob:

1. Pick a group G and an element P in G whose order is large prime q.
2. Alice: Pick a random x in Z/qZ and send xP to Bob.
3. Bob: Pick a random y in Z/qZ and send yP to Alice.
4. Now they both use xyP=y(xP)=x(yP) as their shared key.

Discrete log problem

The Diffie-Hellman key exchange mechanism is thought to be secured (against traditional computers) due to discrete log problem: Given P and aP, find a.

Diffie-Hellman Assumptions

1. Computational Diffie-Hellman assumption (CDH)

For a,b in Z/pZ and given P, aP and bP, it is computationally infeasible to determine abP.

2. Decisional Diffie-Hellman assumption (DDH)

For a,b in Z/pZ and given P, aP and bP and either abP or cP for a random c in Z/pZ, it is computationally infeasible to determine whether you were given abP or cP.

3. Discrete Logarithm assumption (DLOG)

For a in Z/pZ and given P, aP, it is computationally infeasible to determine a.

Key Components

• curve equation: y² = x³ + ax + b over finite field 𝔽ₚ
note: elliptic curve lacks an identity element to form a group. so we add one o to form a group.

e={(x,y): y²=x³+ax+b} ∪ {o}

here, the identity has the following properties:
for any p,q in a group e:
• if q=o, then p+q=p. if p=0, then p+q=q
• for p=(x_p,y_p) and q=(x_q,y_q), if x_p=x_q and y_p=-y_q, then p+q=o.
• group operations: point addition/doubling
• scalar multiplication: q = kp (double-and-add algorithm)

Common Curves

• NIST P-256: y² = x³ - 3x + b over Z/pZ
where
• p = 2²⁵⁶-2²²⁴+2¹⁹²+2⁹⁶-1
This special structure (of 256 bits) allows an efficient modular arithmetics.
• b=41058363725152142129326129780047268409114441015993725554835256314039467401291
• Curve25519: y² = x³ + 486662x² + x over Z/pZ
• p = 2²⁵⁵-19

Elgamal Public Key Encryption in Elliptic Curve

• Set up:
• Choose a single, globally public elliptic curve E
• Choose a single, globally public element P in E of large prime order q
• Key generation:
• Choose a random x in Z/qZ
• Set pk = xP and sk = x
• Encryption: Given m in E
• Choose a random r in Z/qZ
• Set E(m)=(rP, m+r(pk))
• Decryption:
• Given a ciphertext (c1,c2)\in E², compute D(c1,c2)=c2-xc1

4. Security Considerations

Basic comparison between Diffie-Hellman and RSA

• Diffie-Hellman
• Key exchange only (no arbitrary messages)
• Interactive: Both parties must be online simultaneously
• Forward secrecy: Compromising one key exchange does not compromise future key exchanges
• RSA
• Can excahnge any mesage chosen by the sender
• Non-interactive: An encrypted message can be decrypted asyncronously
• No forward secrecy: A compromised private key exposes all previous ciphertexts

RSA Security

• Depends on integer factorization hardness
• Vulnerable to Shor's algorithm (quantum)
• Textbook RSA is not semantically secure

ECC Security

• Relies on Elliptic Curve Discrete Logarithm Problem (ECDLP)
• Best attack: O(√q) using generic algorithms
• 128-bit security: 256-bit curve vs 3072-bit RSA

Security Levels Comparison

Security (bits)	AES Key	RSA Key	ECC Key
128	128	3072	256
256	256	15360	512

Post-Quantum Considerations

• NIST PQC Standards: Kyber (KEM), Dilithium (Signatures)
• Lattice-based cryptography
• Hash-based signatures (SPHINCS+)