criptografia-assimetrica.tex

\chapter{Criptografia Assimétrica}
\label{cha:criptografia-assimetrica}

Concluímos o capítulo anterior apresentando um protocolo de troca de chaves que não requer que as partes se encontrem pessoalmente -- ou com um terceiro confiável -- em nenhum momento.
Essa ideia revolucionária foi proposta inicialmente em um artigo seminal de Diffie e Hellman \cite{Diffie76}.
Neste mesmo artigo os autores propõe a possibilidade de construção de um esquema de {\em criptografia assimétrico}.
O modelo sugerido pela dupla se assemelha ao esquema de um cadeado em que qualquer um pode usar para trancar, mas apenas o dono da chave possui a forma de abrir.
No modelo assimétrico cada ator possui duas chaves: uma pública (cadeado) que pode ser exposta no meio inseguro e uma secreta.
Quando Alice quer se comunicar com Bob ela precisa acessar a chave pública $pk$ de Bob que pode estar disponível publicamente em um site ou Bob pode enviá-la por qualquer canal inseguro.
Com a chave pública de Bob, Alice pode criptografar uma mensagem que apenas ele será capaz de descifrar com sua chave secreta $sk$.
O esquema está representado no digrama a seguir:

\begin{center}
\begin{tikzpicture}[node distance=2cm,auto,>=latex]
\node (alice) at (0, 2){Alice};
\node (bob) at (10, 2) {Bob};
\node (eva) at (5, 2) {Eva};

\node (m1) at (0,1) {$m$};
\node (pk1) at (0,-2) {$pk$};
\node (E)  at (2,0) {$E(pk,m) = c$};
\node (D)  at (8,0) {$D(sk,c) = m$};
\node (sk) at (10,-1) {$sk$};
\node (pk2) at (10,-2) {$pk$};
\node (m2) at (10,1) {$m$};

\path[->] (eva) edge (5,1);
\draw[->] (m1) -> (E);
\draw[->] (pk1) -> (E);
\draw[->] (D) -> (m2);
\draw[->] (k2) -> (D);
\draw[->] (pk2) -> (pk1);
\draw[->] (E) -> node[above]{$c$} (D);
\end{tikzpicture}
\end{center}

Formalmente, o {\em sistema de criptografia assimétrico} $\Pi$ é formado por três algoritmos $\langle Gen, E, D \rangle$, $Gen(1^n)$ produz um par de chaves $\langle sk, pk \rangle$ e precisamos garantir que:
\begin{displaymath}
  D(sk, E(pk, m)) = m
\end{displaymath}

Um sistema de criptografia assimétrico é {\em seguro} se não é viável para um adversário distinguir duas mensagens a partir de uma cifra mesmo na posse da chave pública.
A posse da chave pública dá ao adversário um capacidade equivalente ao CPA, mesmo que ele não tenha acesso à um oráculo.


\section{El Gammal}
\label{sec:el-gammal}
O primeiro sistema de criptografia assimétrico foi descoberto por Rivest, Shamir e Adelman um ano depois do trabalho de Diffie e Hellman.
Essa solução será apresentada em seguida, antes disso mostraremos um esquema que se assemelha muito ao protocolo apresentado no capítulo anterior.
Apesar das semelhanças, esse sistema só foi formalizado em 1985 por Taher El Gamal \cite{ElGamal85}.
O sistema parte do modelo de criptografia assimétrica e é definido como $\Pi= \langle Gen, E, D\rangle$:
\begin{itemize}
\item $Gen(1^n) := \langle sk, pk \rangle$ em que $\mathcal{G}(1^n) = \langle \mathbb{G}, g \rangle$,
\begin{itemize}
\item  $sk = \langle \mathbb{G}, g, x \rangle$ com $x \leftarrow \mathbb{Z}_{|\mathbb{G}|}$ e
\item  $pk = \langle \mathbb{G}, g, h \rangle$ com $h := g^x$.
\end{itemize}

\item $E(pk, m) = \langle g^y, h^y \cdot m\rangle$ em que $y \leftarrow \mathbb{Z}_n$ e $m \in \mathbb{G}$
\item $D(sk, \langle c_1, c_2 \rangle) = \frac{c_2}{c_1^x}$
\end{itemize}

A correção do sistema segue abaixo:
\begin{displaymath}
  D(sk, E(pk, m)) =  \frac{h^y \cdot m}{(g^y)^x} = \frac{(g^x)^y \cdot m}{g^{y \cdot x}} = m
\end{displaymath}

Como no caso do protocolo de Diffie-Hellman, normalmente os valores $\mathbb{G}$ e $g$ são definidos pelo protocolo e reutilizados por todos os usuários.
Isso não causa nenhum efeito deletério à segurança do sistema.

\section{RSA}
\label{sec:rsa}

Em 1978 Rivest, Shamir e Adelman apresentaram o primeiro sistema de criptografia assimétrica conforme concebido um ano antes por Diffie e Hellman \cite{Rivest78}.
Diferente do protocolo de seus colegas e do sistema de El Gamal que se baseiam na dificuldade do problema do logaritmo discreto, o sistema RSA dependende da dificuldade de outro problema matemático, o problema da fatoração.

Antes de apresentar o sistema precisamos fazer uma pequena digressão matemática e aproveitaremos para dar um exemplo concreto de grupo finito.

Primeiro lembremos o que é chamado de Algoritmo da Divisão.
Para quaisquer $a, b \in \mathbb{Z}$ temos que existem $q, r \in \mathbb{Z}$ tal que $0 \leq r < b$ e:
\begin{displaymath}
  a = bq + r
\end{displaymath}

O inteiro $q$ é chamado {\em quociente da divisão} e $r$ o {\em resto}.
Além disso, usaremos diversas vezes o seguinte resultado:

\begin{proposition}
Se $n|a$ e $n|b$ então $n|(ax + by)$.
\end{proposition}
\begin{proof}
Por definição existem $n'$ e $n''$ tais que $nn' = a$ e $nn'' = b$.
Segue que $n(n'x + n''y) = ax + by$ e portanto $n|(ax + by)$.
\end{proof}

Com esses resultados podemos mostrar a chamada {\em Identidade de Bezout}:

\begin{proposition}[Identidade de Bezout]
  Para quaisquer $a,b \in \mathbb{Z}$ existem $X, Y \in \mathbb{Z}$ tais que $Xa + Yb = mdc(a,b)$.
\end{proposition}
\begin{proof}
  Considere o conjunto $I = \{X'a + Y'b: X', Y' \in \mathbb{Z}\}$ e seja $d = Xa + Yb$ o menor inteiro positivo em $I$.
  Seja $c \in I$, ou seja, $c = X'a + Y'b$.
  Usando o algoritmo da divisão temos que $c = qd + r$ e, então:
  \begin{displaymath}
    r = c - qd = X'a + Y'b - q(Xa + Yb) = (X' - qX)a + (Y' - qY)b \in I
  \end{displaymath}
  Se $r \neq 0$ então como $r < d$ isso contradiria o fato de que $d$ é o menor inteiro positivo em $I$, logo, $r = 0$ e, portanto $d|c$.
  Ou seja, para qualquer $c \in I$ temos que $d|c$.

  Como $a, b \in I$ temos que $d|a$ e $d|b$.
  Agora assuma por absurdo que existe $d' > d$ tal que $d'|a$ e $d'|b$.
  Neste caso, pela propriedade acima teríamos que $d'|(Xa + Yb)$, ou seja, $d'|d$, mas isso é impossível porque $d' > d$.
  Concluímos que $d = mdc(a,b)$.
\end{proof}

Podemos considerar $\langle \mathbb{Z}_n, \cdot \rangle$ em que a multiplicação é calculada módulo $n$, neste caso, porém, nem todo $n$ forma um grupo (o Exercício \ref{ex:grupo} pede para mostrar que $6$ não possui inverso em $\langle \mathbb{Z}_{12}, \cdot \rangle$).
A seguinte proposição estabelece uma condição necessária e suficiente para que $a$ possua inverso em $\langle \mathbb{Z}_n, \cdot \rangle$:

\begin{proposition}
\label{prop:inverso}
Um número $a$ possui inverso em $\langle \mathbb{Z}_n, \cdot \rangle$ se e somente se $mdc(a,n) = 1$.
\end{proposition}
\begin{proof}
  Se $mdc(a, n) = 1$ usando o {\em Identidade de Bezout} temos $1 = aX + nY$ para $X, Y \in Z$.
  Neste caso $aX \equiv 1\ (mod\ n)$, ou seja, $X$ é o inverso de $a$ em $\langle \mathbb{Z}_n, \cdot \rangle$.

Agora considere que $mdc(a, n) = b \neq 1$ e suponha por absurdo que $X$ é o
inverso de $a$ em $\langle \mathbb{Z}_n , \cdot \rangle$.
Então temos que $1 \equiv Xa\ (mod\ n)$, ou equivalentemente, $Xa - 1 \equiv 0\ (mod\ n)$ e, portanto, $n|(Xa - 1)$.
Portanto, existe $n'$ tal que $nn' = Xa - 1$ e então $1 = Xa - n \cdot n'$.
Como $b \in D(a,n)$ então $b|(Xa - nn')$, ou seja, $b|1$, mas isso é impossível se $b \neq 1$.
\end{proof}

Será útil para isso apresentar uma versão extendida do algoritmo de Euclides que calcula o {\em máximo divisor comum} entre dois valores $a$ e $b$ e calcula os coeficientes $X$ e $Y$ tais que $Xa + Yb = mdc(a,b)$.

\begin{codebox}
\Procname{$\proc{AEE}(a, b)$}
\li \Comment Recebe $a, b \in \mathbb{Z}$ com $a > b$
\li \Comment Devolve $t$, $X$ e $Y$ tais que $t = mdc(a,b) = Xa + Yb$
\li \If $b|a$
\li     \Then
        \Return $b, 0, 1$
\li \Comment $a = bq + r$
\li \Else $t, X, Y \gets \proc{AEE}(b, r)$
\li     \Return $t, Y, X - Y \cdot q$
\End
\end{codebox}

Para mostrar a correção do algoritmo primeiro considere a seguinte proposição:

\begin{proposition}
  Seja $a = bq + r$ com $r < b$ e $D(a, b) := \{ x \in \mathbb{Z} : x|a$ e $x|b \}$ então $D(a,b) = D(b,r)$.
\end{proposition}

\begin{proof}
  Por definição temos que $r = a - qb$ e, portanto, $x|a$ e $x|b$ sse $x|r$.
Além disso, $x|b$ e $x|r$ sse $x|a$, pois $a = bq + r$.
Concluímos que $x|a$ e $x|b$ sse $x|b$ e $x|r$.
\end{proof}

\begin{corollary}
Se $a = bq + r$ então:
\begin{displaymath}
  mdc(a,b) = mdc(b, r)
\end{displaymath}
\end{corollary}

O corolário acima justifica que $t = mdc(a,b)$ no Algoritmo Extendido de Euclides.
Agora note que se o algoritmo for correto na linha 5 temos que $Xb + Yr$ e o valor devolvido será:

\begin{eqnarray*}
  Ya + (X - Yq)b & = & Ya + Xb + Xqb \\
                 & = & Xb + Y(a + qb) \\
                 & = & Xb + Yr
\end{eqnarray*}

Ou seja, o valor $Xa + Yb$ é um invariante.

Na base temos que $b|a$ e, portanto, $mdc(a,b) = b$.
Além disso, $X = 0$ e $Y = 1$, logo $Xa + Yb = b = mdc(a,b)$.
Concluímos que o algoritmo é correto.

\begin{example}
    Simularemos a execução de $\proc{AEE}(42, 22)$:
    \begin{displaymath}
      \proc{AEE}(42, 22) \vdash \proc{AEE}(22, 20) \vdash \proc{AEE}(20, 2)
    \end{displaymath}
    Neste ponto temos que $2|20$ então calculamos recursivamentes:
    \begin{displaymath}
      \begin{array}{lllr}
        t \gets 2 & r \gets 0 & s \gets 1 & 0 \cdot 20 + 1 \cdot 2 = 2\\
        t \gets 2 & r \gets 1 & s \gets -1 & 1 \cdot 22 - 1 \cdot 20 = 2\\
        t \gets 2 & r \gets -1 & s \gets 2 & -1 \cdot 42 + 2 \cdot 22 = 2\\
      \end{array}
    \end{displaymath}
\end{example}



Definimos enfim $\mathbb{Z}_n^\star$ como os elementos em $\mathbb{Z}_n$ que possuem inverso multiplicativo:
\begin{displaymath}
  \mathbb{Z}_n^\star := \{a \in \mathbb{Z}_n : mdc(a,n) = 1\}
\end{displaymath}

Note que se $mdc(a,n) = 1$ então o Algoritmo Extendido de Euclides devolve $X$ e $Y$ tais que $Xa + Yn = 1$.
Se fizermos essa conta em $\mathbb{Z}_n$ temos que $Xa \equiv 1\ (mod\ n)$.
Ou seja, para os elementos $a \in \mathbb{Z}_n^\star$ o AEE nos dá uma forma de computar o inverso.

Não é difícil mostrar que $\langle \mathbb{Z}_n^\star, \cdot \rangle$ é um grupo visto que todos os elementos possuem inverso por definição (Exercício \ref{ex:euler}).
A {\em função de Euler} atribui a cada $n$ o tamanho de $\mathbb{Z}_n^\star$:

\begin{displaymath}
  \phi(n) := |\mathbb{Z}_n^\star|
\end{displaymath}

No caso em que $n$ é o produto de dois número primos calcular a função de Euler é relativamente simples:

\begin{proposition}
Sejam $p$ e $q$ números primos:
\begin{displaymath}
  \phi(pq) = (p - 1)(q - 1)
\end{displaymath}
\end{proposition}
\begin{proof}
Seja $a \in \mathbb{Z}_n$ e $mdc(a, n) \neq 1$ então $p|a$ ou $q|a$ (se ambos dividissem então $n|a$, mas como $a \in \mathbb{Z}_n$ então $a < n$).
Os elementos de $\mathbb{Z}_n$ divisíveis por $p$ são $p, 2p, \dots , (q - 1) \cdot p$ e os elementos divisíveis por $q$ são $q, 2q, \dots , (p - 1) \cdot q$.
Assim, o total de elementos que não são divizíveis por nenhum dos dois é:
\begin{displaymath}
  \phi(n) = n - 1 - (p - 1) - (q - 1) = p \cdot q - p - q + 1 = (p - 1)(q - 1)
\end{displaymath}


\end{proof}

A geração de chaves no sistema RSA segue os seguintes passos:
\begin{enumerate}
\item Recebe o parâmetro de segurança $1^n$ e sorteia dois primos $p$ e $q$ com $n$ bits.
\item Calcula $N = pq$ e $\phi(N) := (p - 1)(q - 1)$
\item Escolhe $e > 1$ de forma que $mdc(e, \phi(N)) = 1$
\item Computa $d = [e^{-1}\ mod\ \phi(N)]$
\item Devolve $N$, $e$ e $d$
\end{enumerate}

Na prática podemos fixar a escolha de $e$ e computar $d$ de acordo.
Se lembrarmos o algoritmo que $\proc{FastExp}$ notaremos que uma boa escolha para $e$ deve possuir poucos bits $1$ para tornar esse procedimento mais eficiente.
Dois valores usados na prática são $3$ e $2^{16}+1$.

Vimos que para calcular $d$ basta usar o Algoritmo Extendido de Euclides.
Falta uma forma eficiente de sortear primos de tamanho $n$, o que está fora do escopo destas notas.
%Voltaremos a este problema na Seção \ref{}.

Em sua versão crua, o sistema de RSA é definido pela seguinte tripla de algoritmos:

\begin{itemize}
\item $Gen(1^n) = \langle sk, pk \rangle$. Conforme descrito acima temos:
\begin{itemize}
\item $sk = \langle N, d \rangle$
\item $pk = \langle N, e \rangle$
\end{itemize}
\item $E(pk, m) = [m^e\ mod\ N]$ para $m \in \mathbb{Z}_n^\star$
\item $D(sk, c) = [c^d\ mod\ N]$
\end{itemize}

Como $\langle \mathbb{Z}_n^\star, \cdot \rangle$ é um grupo, segue do Teorema \ref{theo:gen-euler} que para qualquer $a$ temos que:
\begin{displaymath}
  a^{\phi(n)} \equiv 1\ (mod\ n)
\end{displaymath}

Esse resultado é chamado de {\em Teorema de Euler}.

\begin{corollary}
  Para todo $a \in \mathbb{Z}_n^\star$ temos que $a^x \equiv a^{[x\ mod\ \phi(n)]}\ (mod\ n)$.
\end{corollary}
\begin{proof}
  Seja $x = q \cdot \phi(n) + r$ em que $r = [x\ mod\ \phi(n)]$:
  \begin{displaymath}
    a^x \equiv a^{q \cdot \phi(n) + r} \equiv a^{q \cdot \phi(n)} \cdot a^r \equiv (a^{\phi(n)})^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r\ (mod\ n)
  \end{displaymath}
\end{proof}


\begin{corollary}
\label{cor:euler}
Seja $x \in \mathbb{Z}_n^\star$, $e > 0$ tal que $mdc(e, \phi(n)) = 1$ e $d \equiv e^{-1}\ (mod\ \phi(n))$ então $(x^e)^d \equiv x\ (mod\ n)$
\end{corollary}

\begin{proof}
  \begin{displaymath}
    x^{ed} \equiv x^{[ed\ mod\ \phi(n)]} \equiv x\ (mod\ n)
  \end{displaymath}
\end{proof}

Esses são os resultados necessários para mostrar a corretude do sistema RSA:
\begin{displaymath}
D(sk, E(pk, m)) = [(m^e)^d\ mod\ N] = [m^{ed}\ mod\ N] = [m\ mod\ N] = m
\end{displaymath}

Notem que uma condição necessária, porém não suficiente, para a segurança dos sistemas RSA é a dificuldade do {\em problema da fatoração} que pode ser descrito formalmente da seguinte forma:
\begin{itemize}
\item O sistema gera dois números primos aleatórios $p$ e $q$ de tamanho $n$ e envia $N = pq$ para o adversário
\item O adversário $\mathcal{A}$ deve produzir $p'$ e $q'$
\end{itemize}

Dizemos que o adversário venceu o desafio se $p' \cdot q' = N$.
O problema da fatoração é considerado {\em difícil} pois não se conhece nenhum adversário eficiente capaz de vencer o jogo com probabilidade considerável.

Caso um adversário eficiente fosse capaz de fatorar $N$, ele produziria $p$ e $q$ e seria então capaz de gerar $\phi(N) = (p-1)(q-1)$ sem nenhuma dificuldade.
Com isso o sistema se torna completamente inseguro.
Ou seja, a dificuldade do problema da fatoração é necessária para garantir a segurança do sistema.
Não sabemos, porém, se essa condição é suficiente.

A construção apresentada acima é chamada de RSA simples ({\em plain RSA}) e é insegura por uma série de motivos.
Um mecanismo para torná-la mais segura é sortear uma sequência de bits $r$ aleatóriamente e usar $m' = r||m$ como mensagem.
O mecanismo segue de maneira identica, a única diferença é que ao decifrar se recupera $r||m$ e então é preciso descartar os primeiros bits.
Essa versão é chamada {\em padded RSA} e uma adaptação dela é usada no padrão {\tt RSA PKCS \#1 v1.5} usada na prática.

\section{Sistemas Híbridos}
\label{sec:sistemas-hibridos}

Os sistemas de criptografia assimétricos que vimos são pelo menos uma ordem de grandesa menos eficientes do que os sistemas de criptografia simétrica que vimos anteriormente.
Além disso, é difícil garantir a segurança desses sistemas pra mensagens em qualquer distribuição de probabilidades.
Por esses motivos, o modelos mais popular de criptografia assimétrica segue um modelo híbrido dividido em duas fases: uma fase de encapsulamento de chave (KEM) seguido de uma fase de encapsulamento dos dados (DEM).

Um {\em mencanismo de encapsulamento de chave} (KEM) é um sistema $\Pi = \langle Gen, Encaps, Decaps \rangle$ tal que:
\begin{itemize}
\item $Gen(1^n) := \langle sk, pk \rangle$ em que $pk$ é uma chave pública e $sk$ uma chave secreta
\item $Encaps$ recebe a chave pública $pk$ e o parâmetro de segurânça $1^n$ e produz uma cifra $c$ e uma chave $k \in \{0,1\}^{l(n)}$
\item $Decaps$ recebe a chave secreta $sk$ e a cifra $c$ e produz uma chave.
\end{itemize}

Um sistema KEM em que $Encaps(pk, 1^n) = \langle c, k \rangle$ é {\em correto} se:
\begin{displaymath}
  Decaps(sk, c) =  k
\end{displaymath}

Um sistema KEM é {\em seguro contra CPA} se um adversário polinomial não é capaz de distinguir com probabilidade considerável a chave produzida por $Encaps$ de uma chave de mesmo tamanho escolhida aleatóriamente.
Se $\Pi_K = \langle Gen_K, Encaps, Decaps \rangle$ é um KEM seguro contra CPA, e $\Pi' = \langle Gen', E', D' \rangle$ é um sistema de criptografia simétrica seguro contra ataques ``ciphertext only'' então o seguinte sistema $\Pi = \langle Gen, E, D \rangle$, chamado de {\em híbrido}, é seguro contra CPA:

\begin{itemize}
\item $Gen(1^n) := Gen_k(1^n) = \langle sk, pk \rangle$
\item $E(pk, m) := \langle c_k, c \rangle$ em que:
\begin{itemize}
\item $Encaps(pk, 1^n) = \langle c_k, k \rangle$ e
\item $E'(k, m) = c$
\end{itemize}
\item $D(sk,\langle c_k, c \rangle) = m$ tal que:
\begin{itemize}
\item $Decaps(sk, c_k) = k$ e
\item $D'(k, c) = m$
\end{itemize}
\end{itemize}

Uma forma natural de produzir um KEM é produzir uma chave $k$ e usar um sistema de criptografia assimétrica $\Pi$ para criptografar a chave.
Esse esquema é seguro desde que o sistema desde que $\Pi$ seja seguro, mas veremos que existem sistemas mais eficientes em determinados casos.
O Apêndice \ref{cha:sistemas-hibridos} apresenta dois sistemas híbridos: um baseado no problema do logartimo discreto e outro no problema da fatoração.



\section{Exercícios}
\label{sec:exercicios}


\begin{exercicio}
  \label{ex:euler}
  Mostre que para qualquer $n \in \mathbb{Z}$ a estrutra $\langle \mathbb{Z}_n^\star, \cdot \rangle$ é um grupo.
\end{exercicio}


%\begin{exercicio}
  % sobre a distribuição dos primos
%\end{exercicio}