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)`

- select random
`D(sk, (u, c))`

- get
`v = u^a`

,`k = H(u, v)`

- then output
`m = Ds(k, c)`

- get