pk-encryption.tex

\section{Asymmetric-Key Encryption (Public-Key Encryption)}\label{s:public-key-encryption}
The major problem that traditional symmetric-key algorithms face is that they require the parties to exchange keys, or more specifically to agree to a secret common private key, prior to communicating.
This needs a secure (physical or digital) communication channel accessible even for a short period of time, in order for the secret key to be exchanged. Such a channel could be a piece of paper delivered by hand or by a trusted courier, or a short in person communication.

An asymmetric or public-key cryptosystem is one where different keys are employed for the operations in the cryptosystem (\textit{e.g.}, encryption and decryption), and where one of the keys can be made public without compromising the secrecy of the other key \cite{Kaliski2011}. That way there is no need for a secure channel or prior agreement.

Usually three algorithms are needed to define a public key cryptosystem. These are a \textit{Key Generation} algorithm which produces the public and private keys (based on a security parameter $\eta$), an \textit{Encryption} and a \textit{Decryption} algorithm.

In the classic model such an encryption scheme involves a \textit{public key} which is used for encryption and a \textit{private key} which is used for decryption.
More formally, given a plaintext $P$, a public key $PubKey$, and a private key $PrivKey$ we can produce a ciphertext $C$ such that:
\begin{equation}
  \label{eq:public-key-encryption}
  \begin{aligned}
    C = Enc(P, PubKey)\\
    P = Dec(C, PrivKey)
  \end{aligned}
\end{equation}

Where $Enc$ and $Dec$ are the \textit{Encryption} and \textit{Decryption} algorithms respectively.

If Alice wants to send a message to Bob, she needs Bob's public key which could be publicly available (\textit{e.g.} on Bob's website).
Alice encrypts her message with Bob's public key and sends the resulted ciphertext to Bob. Bob then needs his private key which is only in his possession in order to decrypt the ciphertext Alice sent and retrieve the original message.
If Bob wishes to reply, he needs Alice's public key etc.
Generally, the public (encryption) key could be shared to any party that wants to communicate with the owner of that public key, while the private (decryption) key should be kept secret and used by the recipient of the ciphertext to recover the original plaintext.

The ability for two users to establish a shared secret over an insecure communication channel, despite having no prior communication or information exchange was first proposed in 1976 by Whitfield Diffie and Martin Hellman.
That method is named Diffie-Hellman (DH) key exchange \cite{diffie1976new} after its authors. The security of the algorithm is based on the difficulty of solving the Discrete Log Problem (DLP). The DLP is stated as follows: Given $g, p$ and $g^k \pmod{p}$, find $k$.

Some of the most widely used public key cryptosystems are the RSA (Rivest -- Shamir -- Adleman) \cite{rivest1978method}, the El Gamal \cite{elgamal1985public} and the Paillier \cite{paillier1999public} Cryptosystems.

\subsection{RSA}\label{s:pk-rsa}

One if the first and most widely adopted public key cryptosystem is RSA . The algorithm's difficulty reduces to the difficulty of factoring the product of two large prime numbers. Its three basic algorithms are described below.

\begin{itemize}
  \item \textit{Key Generation}
  \begin{itemize}
    \item Randomly select two large primes $p$ and $q$.
    \item Calculate modulus $n = p \cdot q$.
    \item Calculate $\phi(n) = (p-1) \cdot (q-1)$.
    \item Randomly select $e : gcd(e,\phi(n)) = 1$.
    \item Calculate reverse $d  = e ^ {-1} \pmod{\phi(n)}$.\\
    $d \cdot e = 1 \pmod{\phi(n)}$.
    \item The public key is $(n, e)$, while the private key is $d$. $p, q$ and $\phi(n)$ must also be kept private.
  \end{itemize}
  \item \textit{Encryption}
  \begin{itemize}
    \item Given a plaintext message $m$, we get a ciphertext $c = m ^ e \pmod{n}$.
  \end{itemize}
  \item \textit{Decryption}
  \begin{itemize}
    \item Given a ciphertext $c$, we get back the plaintext $m$ as follows: $c^d \pmod{n} = m^{ed} \pmod{n} = m$.
  \end{itemize}
\end{itemize}


\subsection{ElGamal}\label{s:pk-elgamal}
The ElGamal encryption system is a public-key cryptosystem based on the Diffie-Hellman key exchange. Its three basic algorithms are described below.

\begin{itemize}
  \item \textit{Key Generation}
  \begin{itemize}
    \item Select two large primes $p$ and $ q : q \mid (p - 1)$.
    \item Select a generator $g$ of group $\mathbb{G}$ which is a large enough order-$q$ subgroup of the multiplicative group $\mathbb{Z}_{p}^{*}$ of integers between $1$ and $p - 1$.
    \item Randomly select $ x \in_{R} \mathbb{Z}_{q}$.
    \item Calculate $y = g^{x} \pmod{p}$.
    \item The public key is $y$, while the private key is $x$.
  \end{itemize}
  \item \textit{Encryption}
  \begin{itemize}
    \item Given a plaintext message $m$, we get a ciphertext $c$ as follows.
    \item Randomly select $r \in_{R} \mathbb{Z}_{q}$.
    \item Calculate $G = g^{r} \pmod{p}$.
    \item Calculate $M = m \cdot y^{r} \pmod{p}$.
    \item Return $c = (G,M)$
  \end{itemize}
  \item \textit{Decryption}
  \begin{itemize}
    \item Given a ciphertext $c = (G,M)$, we get back the plaintext $m$ as follows: \\$m = M/G^{x}\pmod{p}$.
  \end{itemize}
\end{itemize}

\subsection{Paillier}\label{s:pk-paillier}
The Pallier cryptosystem is a public-key cryptosystem that relies its security upon the decisional composite residuosity assumption \cite{paillier1999public}.

\begin{itemize}
  \item \textit{Key Generation}
  \begin{itemize}
    \item Randomly and independently select two large primes $p$ and \\$ q :gcd(p-1, q-1) = 1$ If both primes have the same length this property holds.
    \item Calculate the RSA modulus $n = p \cdot q$.
    \item Calculate $\lambda = lcm(p-1, q-1)$.
    \item Select generator $g \in \mathbb{Z}_{n^{2}}^{*}$ such that the order of $g$ is a non zero multiple of $n$.
    \item Calculate $\mu = (L(g^{\lambda} \pmod{n^{2}}))^{-1} \pmod{n}$, where $L(x) = \frac{x-1}{n}$.
    \item The public key is $ (n,g) $, while the private key is $ (\lambda, \mu) $.
  \end{itemize}
  \item \textit{Encryption}
  \begin{itemize}
    \item Given a plaintext message $m$, we get a ciphertext $c$ as follows.
    \item Encode $m$ into $\mathbb{Z}_{n}$.
    \item Randomly select $ r \in_{R} \mathbb{Z}_{n}^{*}$.
    \item Return $c = g^{m} \cdot r^{n} \pmod{n^{2}}$.
  \end{itemize}
  \item \textit{Decryption}
  \begin{itemize}
    \item Given a ciphertext $c \in \mathbb{Z}_{n^{2}}$, we get back the plaintext $m$ as follows: \\$m = L(c^{\lambda} \pmod{n^{2}}) \cdot \mu \pmod{n}$.
  \end{itemize}
\end{itemize}