Assinatura e troca de chaves

$\newcommand{\Z}{\mathbb Z}$Vamos estudar dois problemas nesta aula relacionados com criptigrafia:

  1. Como enviar uma mensagem criptografada e assinada?
  2. Como dois parceiros podem gerar uma chave privada comunicando em um canal aberto?

Assinatura

Assuma que a Alice quer enviar uma mensagem para o Bob. Neste caso é importante que o Bob consiga verificar que a mensagem foi enviada pela própria Alice. Para isso, a Alice precisa assinar a mensagem em alguma forma que a sua assinatura seja verificável.

Isso pode ser feito na maneira seguinte:

  1. Alice e Bob vão escolher suas funções de codificação e descodificação. Assuma que as funções da Alice são $C_A$ (codificação), $D_A$ (descodificação), enquanto as funções do Bob são $C_B$ (codificação) e $D_B$ (descodificação).
  2. Alice quer enviar uma mensagem $b$ para o Bob a quer assinar a mensagem para seja verificável por Bob que a mesma foi de fato enviada pela Alice. Então Alice vai criptografar a mensagem calculando $c=C_B(b)$, mas vai enviar também a mensagem $a=D_A(b)$ como sua assinatura.
  3. Ao receber as mensagens  $c$ e $a$ da Alice, o Bob descodifica a mensagem $c$ usando sua chave de descodificação e obtém a mensagem original  $b$. Depois o Bob aplica a função de codificação $C_A$ da Alice na assinatura e verifica se $C_A(a)=b$. Se sim, então Bob pode ter certeza que a mensagem foi muito provavelmente enviada pela Alice, pois a assinatura $a$ foi produzida pela chave privada da Alice (desconhecida por todos outros).
No exemplo da aula anterior, a chave pública de Bob foi $(77,13)$ e a sua chave privada foi $(60,37)$. Para enviar uma mensagem assinada, Alice também vai precisar de um par de chaves e suponha que a chave pública da Alice é $(143,17)$ (chave pública) e a chave privada dela é $(120,113)$. A mensagem da Alice é o número $30$. Alice vai calcular $C_B(30)=30^{13}\pmod{77}=72$ e vai também calcular $D_A(30)=30^{113}\pmod{143}=127$. Ao receber as mensagens, Bob aplica primeiro a sua função de descodificação no primeiro pedaço da mensagem recebida $D_B(72)=72^{37}\pmod{77}=30$, mas vai também aplicar a função de codificação da Alice no segundo pedaço: $C_A(39)=127^{17}\pmod{143}=30$. Bob nota que os dois resultados são iguais, então a mensagem foi de fato enviada por Alice.

Troca de chaves

Em muitas situações os dois parceiros de uma comunicação secreta precisam escolher uma chave comum para poderem enviar mensagens criptografadas. O problema é que eles se comunicam usando um canal aberto, mas querem que a chave escolhida seja sigilosa. O seguinte procedimento é conhecido como a Troca de Chaves de Diffie-Hellman. Foi publicada em 1976 e é baseado no fato que não conhecemos algoritmo eficiente para o seguinte problema.

Problema (logaritmo discreto). Seja $p$ um primo e seja $\bar g$ um elemento primitivo de $\Z_p$. Dado $\bar g^k$, determine o número $k$.

O procedimento de Diffie-Hellman é o seguinte:

  1. Alice e Bob vão escolher um primo $p$ grande e escolhem um elemento primitivo $\bar g$ em $\Z_p$. Estes dados não precisam ser sigilosos.
  2. Alice escolha um inteiro secreto $a\in\{1,\ldots,p-1\}$ e envia $\bar x=\bar g^a$ ao Bob.
  3. Bob também escolha um número $b\in\{1,\ldots,p-1\}$ secreto e envia $\bar y=\bar g^b$ à Alice.
  4. Alice vai calcular $\bar y^a$ e Bob vai calcular $\bar x^b$. Note que
    \[
    \bar y^a=(\bar g^b)^a=\bar g^{ab}=(\bar g^a)^b=\bar x^b.
    \]
    Ou seja, os valores calculados neste passo por Alice e por Bob serão iguais. Este valor comum pode ser usado por Alice e por Bob como um secreto conhecido apenas por eles.

Note que se Eva interceptar as mensagem comunicadas entre Alice e Bob, ela vai conhecer os valores de $p$, $\bar g$, $\bar g^a$ e $\bar g^b$. Mas para determinar $(\bar g^a)^b$, ela precisaria do valor de $b$ (ou de $a$), e isso significa resolver o problema de logaritmo discreto.

 Assuma que $p=23$, $\bar g=5$, $a=10$, $b=20$. Alice vai calcular $\bar x=\bar 5^{10}=9$ e manda para o Bob. Bob vai calcular $\bar y=\bar 5^{20}=\overline{12}$. Depois Alice faz $\overline{12}^{10}=\bar 2$ enquanto Bob computa $\bar 9^{20}=\bar 2$. Depois desta computação, os dois obtiveram o mesmo valor $2$ e ele vai ser a chave secreta que eles podem usar para comunicar.