Crypto 101: Public key crypto

This post will cover the definitions of encryption schemes Diffie-Hellman, Textbook RSA, RSA-OAEP, and ElGamal.

Diffie-Hellman key exchange:

  1. A and B agree on p and g.
  2. A generates x, sends g^x mod p to B.
  3. B generates y, sends g^y mod p to A.

A and B agree on a prime p and generator g where g is the generator of the multiplicative group modulo p. A picks secret key x and sends g^x to B. B picks secret key y and sends g^y to A. Now A and B each can compute g^xy, which is their shared secret. This scheme relies on it being hard to compute g^xy given g^x and g^y, this is known as the CDH assumption. Insecure against man-in-the-middle attack, obviously. Precomputation possible for small (e.g 1024 bit) primes.

Textbook RSA is not IND-CPA secure because it’s deterministic (no deterministic scheme can be IND-CPA secure -> all IND-CPA secure schemes are randomized).

RSA assumption: Textbook RSA is one-way. Hard to find m such that m^e = c mod N for large n.

ElGamal is IND-CPA secure given the DDH assumption. DDH assumption: Hard to distinguish (g^a, g^b, g^ab) from (g^a, g^b, g^c) for randomly chosen a,b,c from Zq (i.e h^x indistinguishable from random element in G). i.e IND-CPA secure if DDH is hard in G.

Textbook RSA and ElGamal are both malleable so neither are IND-CCA secure. For both, plaintext can be recovered under CCA.

RSA-OAEP is IND-CCA secure given RSA assumption in random oracle model.

Cramer-Shoup is IND-CCA secure given DDH assumption and H is 2nd-preimage resistant.

Textbook RSA:

Gen(1^n): public key = (N,e), secret key = (N,d)

Enc(pk, m): m^e mod N = c

Dec(sk, c): c^d mod N = m

Where N = pq where p and q are n/2-bit primes, e and d where e is usually fixed and d is the modular inverse of e mod totient(N), where totient(N) = (p-1)(q-1). Note therefore that totient(N) is always even. e is usually chosen to be a small prime like 65537 so encryption is fast. This means that in RSA, encryption is fast whereas decryption is comparatively slow. The modular inverse d of e can be efficiently computed using the extended Euclidean algorithm. If either p or q is small then factorization possible using Lenstra’s method. Small m and e (e.g 3) is insecure because if m^e is smaller than N such that c is an eth power (e.g a cube) then you can directly calculate the eth root (e.g cube root) of c to find m.

Euler’s theorem: m^totient(N) = 1 mod N

Correctness (when m is coprime to N): c = m^e mod N. Dec(N, d, c) = c^d = (m^e)^d = m^(ed) = m^(1+k * totient(N)) = m * m^(k * totient(N)) = m * (m^totient(N))^k = m * 1^k = m mod N

Message recovery under CCA:

Given the ciphertext c = m^e mod N, want to compute m? Simply multiply ciphertext by ciphertext of some number r, then decrypt using the decryption oracle then divide by r.

  1. Pick a random number r.
  2. Query decryption oracle with c’ = c * r^e mod N to obtain m’ = c’^d

m’ = (m^e * r^e)^d = m^ed * r^ed = m * r mod N

m = m’ / r mod N


Gen(1^n): pk = (N, e, G, H), sk = (N, d, G, H)

Enc(m): x = m0..0 XOR G(r), y = r XOR H(x), c = (x||y)^e mod N

Dec(c): c^d = (x||y)^d = x||y, r = y XOR H(x), m0..0 = x XOR G(r)

Where G and H are hash functions. (Random oracles in the random oracle model.)


Gen(1^n): pk = (G, q, g, h), sk = (G, q, g, x)

Enc(pk, m): c1,c2 = g^r, h^r * m

Dec(sk, c1, c2): c2 / c1^x

Where G is a group of prime order q, g is the generator of G, x and r are randomly chosen elements of Zq, and h = g^x. Note that we can get x by taking the discrete log of g^x. The security of ElGamal is therefore broken if computing the discrete log is efficient. Note that unlike RSA, decryption in ElGamal is faster than encryption. So RSA encryption is faster than ElGamal encryption, but RSA decryption is slower than ElGamal decryption.

Correctness: c1^-x * c2 = (g^r)^-x * h^r * m = g^(-xr) * g^(xr) * m = m

Message recovery under CCA:

Given the ciphertext c1, c2 = g^r, h^r * m, want to compute m? Simply multiply both c1 and c2 by g^s for some random number s, and then multiply c2 by some number n.

  1. Pick a random number s.
  2. Query decryption oracle with c1′, c2′ = c1 * g^s, c2 * x * h^s

Decryption oracle returns m*n because it simply does a division:

c2′ = c2 * n * h^s = g^xr * mn * g^xs = g^x(r+s) * mn

c1’^x = (c1 * g^s)^x = (g^r * g^s)^x = g^x(r+s)

m’ = c2′ / c1’^x = (g^x(r+s) * mn) / g^x(r+s) = mn

This attack is good because both c1 and c2 are different and the returned message mn is different from m as well, so a decryption oracle that refuses to return m can still be fooled. Then simply divide mn by n to get m.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s