assinaturas-digitais.tex

\chapter{Assinaturas Digitais e PKI}
\label{cha:assinaturas-digitais}

No capítulo anterior vimos que é possível construir um sistema de criptografia em que as partes não precisam trocar um segredo de antemão.
Os esquemas da criptografia assimétrica pressupõe a geração de um par de chaves, uma pública e outra secreta.
As assinaturas digitais, que veremos neste capítulo, seriam o equivalente àos códigos de autenticação de mensagem que vimos no Capítulo \ref{cha:mac} no contexto da criptografia assimétrica.

\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 (Sign)  at (2,0) {$Sign(sk,m) = t$};
\node (Ver)  at (8,0) {$Ver(pk, m, t)$};
\node (sk) at (0,-1) {$sk$};
\node (pk2) at (10,-2) {$pk$};

\path[->] (eva) edge (5,1);
\draw[->] (m1) -> (Sign);
\draw[->] (sk) -> (Sign);
\draw[->] (pk2) -> (Ver);
\draw[->] (pk1) -> (pk2);
\draw[->] (Sign) -> node[above]{$m, t$} (Ver);
\end{tikzpicture}
\end{center}

Um {\em sistema de assinatura digital} consiste de três algoritmos:
\begin{itemize}
\item $Gen$ recebe o parâmetro de segurança $1^n$ e produz um par de chaves $\langle sk, pk \rangle$.
A primeira deve ser mantida em sigilo e a segunda pode ser publicada.
\item $Sign$ recebe a chave secreta $sk$ e uma mensagem $m$ e produz uma assinatura $t$.
\item $Ver$ recebe a chave pública $pk$, uma mensagem $m$ e uma assinatura $t$ e verifica se essa assinatura é válida para mensagem $m$ e de fato da pessoa que possui a chave secreta.
Em caso positivo o algritmo deve devoler $1$ e em caso negativo $0$.
\end{itemize}

Note que no meio digital, para cada mensagem direferente uma mesma pessoa produz assinaturas diferentes.
Um sistema de assinatura digital é {\em correto} se:
\begin{displaymath}
  Ver(pk, m, Sign(sk, m)) = 1
\end{displaymath}

Um sistema como esse é {\em seguro contra falsificação} se qualquer adversário eficiente, mesmo com acesso a um oráculo que lhe entregue assinaturas para mensagens diferentes de $m$, não é capaz de produzir uma assinatura válida para $m$ com probabilidade considerável.

Da mesma forma que os sistemas de criptografia assimétrica, produzir uma assinatura digital para uma mensagem muito grande pode ser um processo lento.
Uma técnica usada na prática para mitigar este problema é assinar não a mensagem $m$ em si, mas um hash da mensagem $H(m)$.
Neste caso, para verificar a integridade e autenticidade da mensagem, basta gerar $H(m)$ e verificar a assinatura.
Essa construção é chamada de {\em paradigma Hash-and-Sign}.
É possível provar a segurança contra falsificação em uma construção como essa no caso em que o esquema de assinatura usado é seguro contra falsificação e o hash é resistente à colisão.


\section{Assinatura RSA}
\label{sec:assinatura-rsa}

Um sistema de assinatura digital $\Pi = \langle Gen, Sign, Ver \rangle$ pode ser construído invertendo o esquema de criptografia assimétrica que vimos no capítulo anterior.
Ou seja, criptografamos a mensagem com a chave secreta para gerar a assinatura e descriptografamos com a chave pública para verificar.
Esse esquema não é seguro até aplicarmos o paradigma {\em hash-and-sign}.
O esquema todo segue:
\begin{itemize}
\item $Gen(1^n) := \langle sk, pk \rangle$ em que:
\begin{itemize}
\item $sk := \langle N, d \rangle$ e
\item $pk := \langle N, e \rangle$
\end{itemize}
\item $Sign(sk, m) := [H(m)^d\ mod\ N]$
\item $Ver(pk, m, t) := \left\{
    \begin{array}{lcl}
      1 & \textrm{se} & t^e \equiv H(m)\ mod\ N\\
      0 & \textrm{c.c.} &\\
    \end{array}
    \right.$
\end{itemize}

A correção deste sistema segue os mesmos passos da correção do sistema de criptografia RSA que vimos no capítulo anterior.
Além disso, podemos provar que se o sistema RSA é seguro e o hash $H$ usado é resistente à colisão então o sistema acima é seguro contra falsificação.
Esse sistema é a base do sistema de assinatura do protocolo {\tt RSA PKCS \#1 v2.1}.

\section{Infraestrutura de Chaves Públicas}
\label{sec:pki}

O protocolo de Diffie-Hellman e a criptografia assimétrica garantem a segurança da comunicação contra ataques passivos sem precisarmos supor que as partes compartilhe um segredo {\em a priori}.
Um problema que ainda não tratamos até aqui é como garantir a segurança contra um ataque ativo, ou seja, contra um modelo de ameaça em que o adversario não só é capaz de observar a comunicação, como também é capaz de interferir nela.
Um ataque que os sistemas que vimos até aqui estão particularmente sujeitos é o seguinte.
Digamos que Alice pretende se comunicar com Bob usando um sistema de criptografia assimétrico.
O primeiro passo para Alice é obter a chave pública de Bob.
Neste momento Eva pode enviar a sua chave pública como se fosse a de Bob, receber as mensagens que Alice enviaria para Bob, copiá-las e re-encaminhá-las para Bob.
Este tipo de ataque é chamado de {\em Man In The Middle} e nada do que vimos até aqui o previne.

Não há como evitar este tipo de ataque sem algum encontro físico em que algum segredo seja compartilhado de maneira segura, mas os sistemas de assinatura digitais podem facilitar bastante esse processo.
A ideia é confiar a alguma autoridade a identificação das chaves públicas.
A autoridade $A$ teria então a responsabilidade de verificar se a entidade portadora da identidade $Id_B$ é de fato a o pessoa que possui a chave secreta correspondente à chave pública $pk_B$.
Neste caso a autoridade $A$ pode emitir um {\em certificado} $cert_{A \to B}$ que nada mais é do que uma assinatura de $A$ conectando $Id_B$ a $pk_B$:
\begin{displaymath}
  cert_{A \to B} := Sign(sk_A, Id_B || pk_B)
\end{displaymath}

Existem diversos modelos de {\em infraestrutura de chaves públicas} (PKI):
\begin{itemize}
\item {\em autoridade certificadora única:} Neste cenário assumimos que todos possuem a chave pública da autoridade certificadora $A$ que foi obtida de maneira segura.
Sempre que algum novo ator $B$ precisar publicar sua chave pública ele deve se apresentar à essa autoridade e comprovar sua identidade para obter o certificado $cert_{A \to B}$
\item {\em múltiplas autoridades certificadoras:} Neste cenário existem várias autoridades certificadoras e assumimos que todos possuem chaves públicas de algumas ou todas elas.
Quando um novo ator precisar publicar sua chave ele pode procurar uma ou mais autoridades para gerar o certificado que será válido para aqueles que confiarem na autoridade certificadora que o emitiu.
Neste cenário a comunicação é tão segura quanto a menos confiável das autoridades incluídas na lista das partes.
\item {\em delegação de autoridade:} Neste cenário as autoridades certificadoras não apenas podem certificar a autenticidade de uma chave pública como podem também produzir um certificado especial $cert^*$ que dá o poder a outro de produzir certificados.
Assim digamos que $C$ consiga um certificado de $B$ sobra a autenticidade de sua chave $cert_{B \to C}$ e suponha que $B$ possui um certificado especial de $A$ que o autorize a produzir certificados em seu nome $cert^*_{A \to B}$.
Assim alguém que possui a chave pública de $A$ pode verificar o certificado $cert^*_{A \to B}$ e usar a chave pública assinada de $B$ para verificar $cert_{B \to C}$.
\item {\em rede de confiança:} Neste cenário, todas as partes atuam como autoridades certificadoras e podem assinar certificados para qualquer chave que elas verificaram.
Cabe a cada um avaliar a confiança que tem em seus colegas quanto a edoniedade em produzir certificados.
\end{itemize}

Um certificado pode e deve conter uma {\em data de expiração} que limite seu tempo de validade.
Depois dessa data o certificado não dever ser mais considerado válido e precisa ser renovado.
Em alguns modelos o portador pode comprovar sua identidade com a autoridade que emitiu o certificado e esta pode assinar e publicar um {\em certificado de revogação} anunciando que a chave não deve mais ser considerada válida -- por exemplo no caso de ela ser perdida ou roubada.

Veja o apêndice \ref{cha:dsa} para outros exemplos de assinatura digital e esquemas de identificação.

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

\begin{exercicio}
  Explique com suas palavras o que é uma autoridade certificadora e qual sua importância para garantir a segurança na comunicação.
\end{exercicio}