52 Things: Number 15: Key generation, encryption and decryption algorithms for RSA-OAEP and ECIES.

This is the latest in a series of blog posts to address the list of  '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We came back to "more crypto" staff by describing the key generation, encryption and decryption algorithms for RSA-OAEP and ECIES. 

1. RSA-OAEP
RSA-OAEP  stands for RSA encryption/decryption scheme and OAEP padding scheme respectively. They are often used conjointly in real world.

1.1 RSA[1]
RSA is one of the earliest public key encryption scheme that has been deployed widely in real world. It is based on the assumption of the hardness of RSA problem which has been described in previous blog (here).

Key Generation:

1.  Generate two large primes $p$, $q$, and compute the modulo $N = pq$.
2.  Selects a random number $e \in \mathbb{Z}_N$ s.t. $gcd(\phi(N),e)=1$ where $gcd$ stands for Greatest Common Divisor. 
3.  Since $\phi(N)$ and $e$ are co-prime ($gcd(\phi(N),e) = 1$), we can use XGCD to find the multiplicative inverse $d$ of $e$ over modulo $\phi(N)$: $d = e^{-1} \mod \phi(N)$.
4. We distribute $(N,e)$ as our public key and hold $(p,q,d)$ as our secret key.

Encryption:

1. Parse the message to an integer $m \in \mathbb{Z}_N$.
2. Compute $c = m^e \mod N$.
3. Output $c$ as our ciphertext.

Decryption:
Before we receive the ciphertext, we precompute some values: $d \mod p-1$, $q^{-1} \mod p$, $d \mod q-1$ and $p^{-1} \mod q$.
Then upon receiving the ciphertext $c$, we

1. Compute\begin{equation}m = ((c ^{d \mod p-1}\mod p)q({q^{-1} \mod p})\\ + (c^{d \mod q-1}\mod q)p({p^{-1} \mod q})) \mod N\end{equation}
2. Output $m$ as our plaintext.

Notice that the computation of $m$ is in fact $m=c^d \mod N$ using CRT. The reason is that performing exponentiations over small modulo($p$ and $q$) are faster than doing it over large modulos($N$). The decryption works by applying  Fermat's Little Theorem and we will have $c^d =m^{ed}= m ^{1 \mod \phi(N)} = m (\mod N)$ .

1.2 OAEP[2]
OAEP stands for Optimal Asymmetric Encryption Padding. It is a padding scheme used together with asymmetric encryption (usually RSA). It can bring some randomness to a deterministic encryption scheme. When used with RSA, the combined scheme is proven to be IND-CCA secure.

Let

• $f$ be a $k$-bit trapdoor one-way permutation. $f:\{0,1\}^k \rightarrow \{0,1\}^k$
• $m$ be the $n$-bit message
• $G$, $H$ be two psudorandom functions: $G: \{0,1\}^s \rightarrow \{0,1\}^{n+t}$ and $H:\{0,1\}^{n+t} \rightarrow \{0,1\}^s$, where $k = n + t + s$
• $R$ be $s$-bit random number: $R \leftarrow \{0,1\}^s$

Encryption:
We compute the $k$-bit ciphertext as follows:
\begin{equation}
Encrypt(m) = f_{pk}(\{(m||0^t) \oplus G(R) \}||\{R \oplus H((m||0^t) \oplus G(R))\})
\end{equation}

Decryption:
By using the trapdoor, we can recover the following value:
\begin{equation}
f_{sk}(c) =  \{(m||0^t) \oplus G(R) \}||\{R \oplus H((m||0^t) \oplus G(R))\}
\end{equation}

Then

1.  Let the first $n+t$ bits be $T$: $T = (m||0^t) \oplus G(R)$, and the other $s$ bits be $S$: $S = R \oplus H((m||0^t) \oplus G(R))$
2.  Compute $R$ as $R=H(T) \oplus S$
3.  Compute $m||0^t = T \oplus G(R)$
4. Verify if there is exactly $t$ 0s following the $n$-bit message $m$. If validated, remove the $t$ 0 bits and output $m$.

In practice, we replace $f_{pk}$ and $f_{sk}$ by RSA encryption and decryption function respectively.

ECIES

Elliptic Curve Integrated Encryption Scheme is a variation of ElGamal public key encryption scheme based on Elliptic Curve Cryptography (click here to find more about elliptic curve).

For simplicity, we define an Elliptic Curve in the form:

\begin{equation}
E: y^2 = x^3 + ax +b
\end{equation}

To further simplify our problem, we only discuss a curve $E$ on a prime field $\mathbb{F}_q$ with a base point $P$ having a prime order $n$. Then we can define a simplified domain parameter: $ D = (q, a, b, P, n)$ where:

• $q$ is the prime field order. i.e. $q$ is a prime and $x, y, a, b$ are reduced to $\{0, 1, 2, ..., q-1\}$
• $a,b$ are the coefficients of the curve.
• $P$ is a point on the curve.
• $n$ is the prime order of $P$. i.e. additions of $P$ yields $n$ points on the curve where $n$ is a prime.

The domain parameter are made public.

ECIES are always associated with a symmetric encryption scheme and a MAC scheme. We denote them as $\{Enc_k(m)=c, Dec_k(c)=m\}$ and $\{MAC_k(m)=t, Very(t,m)=T/F\}$ respectively.

We also denote $KDF(s_1,  s_2) = (k_{enc}, k_{MAC})$ as the Key Derivation Function which takes two seeds $s_1, s_2$ and outputs a pair of symmetric encryption key and MAC key.

Then we describe the scheme as:

Key Generation:

1. Pick a random integer $d \in [1, n - 1]$.
2. Compute a new point $Q = dP$.
3.  Output $Q$ as the public key and $d$ as the secret key.

Then the encryption of a message $m$ is done as follows:

Encryption:  

1.  Pick a random integer $k \in [1, n-1]$.
2.  Compute $R=kP, Z=kQ$. If $Z=\infty$ then we restart the process and pick a different $k$.
3.  Generate $(k_1, k_2) = KDF(x_Z, R)$ where $x_Z$ is the $x$-coordinate of $Z$.
4. Compute $c = Enc_{k_1}(m)$ and $t=MAC_{k_2}(c)$.
5. Output $(R, c, t)$ as the ciphertext.

On receiving a ciphertext $(R,c,t)$,

Decryption:

1.  Verify if $R$ is valid. This can be easily done by substituting $R$ in to the curve.
2. Compute $Z'=dR$.
3. Generate $(k'_1, k'_2) = KDF(x_{Z'}, R)$, where $x_{Z'}$ is the $x$-coordinate of $Z'$.
4. Verify if MAC is correct by calling $Very(t, c)$.
5. Decrypt $m' = Dec_{k'_1}$.
6. Output $m'$ as the plaintext.

Since $Z' = dR = dkP = kQ = Z$; therefore seeds fed to KDF() are in fact same. Hence receiver can generate keys as same as the sender's and decrypt the message.

However, my knowledge to ECC is very limited. For those who are interested, you can find more in [4].

References:
[1] http://people.csail.mit.edu/rivest/Rsapaper.pdf
[2] http://tools.ietf.org/html/rfc2437
[3] http://www.shoup.net/papers/iso-2_1.pdf
[4] http://www.springer.com/computer/security+and+cryptology/book/978-0-387-95273-4