This is a note of week 6 of the Coursera course Cryptography I. The topic is public key encryption.

1 Definitions and Security

A public-key encryption (PKE) system is a triple of algorithms: (G, E, D):

  • G(): randomized algorithm outputs a key pair (pk, sk)
  • E(pk, m): randomized algorithm that encrypts m and outputs c
  • D(sk, c): deterministic algorithm that decrypt c and outputs m or bottom(invalid).

For PKE, one time security is the same as many-time security. This is not the case for symmetric ciphers.

In the Chosen Ciphertext Attack(CCA), the attacker can see plaintext for any ciphertext before and after (except the two challenge messages) the challenge.

A Trapdoor Function(TDF) uses G and a inversable functions F for encryption and its inverse F' for decryption. It is secure if F(pk, _) is a one-way funciton: the attack cannot find the input from output without sk.

With a TDF, we can construct a CCA-secure PKE using the ISO standard.

  • (G, F, F'): secure TDF defined over X -> Y
  • (Es, Ds): symmetric authenticated cipher defined over (K, M, C)
  • H: X -> K: a hash funciton

Use the TDF G for PKE, the E(pk, m) is constructed as follows:

  • select a uniform random value x
  • y = F(pk, x), k=H(x), c=Es(k, m)
  • output (y, c)

The D(sk, (y,c)) is:

  • x = F'(sk, y)
  • k = H(x), m = Ds(k, c)
  • output m

It is important to introduce random value of x so the encryption is not deterministic. Never apply the trapdoor function directly to the message.

2 The RSA Trapdoor Permutation

RSA trapdoor perputation was published in 1977 and was widely used in SSL, TLS, secure email and file systems. It is defined as follows:

  • choose random primes p, q about 1024 bits
  • set N = pq
  • choose intergers e, d such that ed = 1 mod phi(N).
  • G() produces pk = (N, e), sk = (N, d)
  • F(pk, x) = x ^ e, F'(sk, y) = y^d.

RSA is one-way permutation because the probability of computing the result of y^(1/e) is negligible.

Since ISO standard is not often used, RSA in practice like PKCS1 developed in 1980s uses an expanded key generated from a given symmetric key. It was used in HTTPS but is insecure. New verisons such as RSA-OAEP fixed the bug but there are many details.

3 PKE from DH

It is easy to convert DH to PKC by treating A of A=g^a as a public key and a as a private key. The ElGamal system by letting

  • G: finite cyclic group of order n
  • (Es, Ds): symmetric authenticated encryptioin defined over (K, M, C)
  • H: G^2 -> K: a has function

To construct a PKE system (Gen, E, D):

  • Key generation Gen: choose ramdom generator g in Gen and random a in Zn, compute h=g^a and output sk = a, pk = (g, h)
  • E(pk, m)
    • select random b from Zn, u = g^b, v = h^b, k = H(u, v)
    • create ciphertext c = Es(k, m), output (u, c)
  • D(sk, (u, c))
    • get v = u^a, k = H(u, v)
    • then output m = Ds(k, c)