seguro, pode ser remediada usando um protocolo para que ambos usem um canal inseguro (aberto) para estabelecer uma chave privada a ser usada em suas comunicações, sem que outros tenham acesso à chave. A comunicação subsequente poderá se dar usando apenas esta chave, e o canal seguro estará, então, estabelecido. De�niremos segurança para protocolos de estabelecimento de chaves antes de apresentar o protocolo de Di�e e Hellman. Começamos com o experimento KE_EAV (�key establishment / eavesdropping�), que identi�ca a probabilidade com que o segredo (chave) comum pode ser capturado por um adversário. Experimento 9.1 (KE_EAV(Π,A, n)). 1. Duas entidades A e B, ambas conhecendo n, executam o protocolo Π. Todas as mensagens trocadas entre A e B são guardadas em uma listaM . Ambos devem calcular uma chave k (que não é incluída na lista M). 2. Um bit aleatório b é escolhido. Se b = 0, k′ é escolhida uniformemente ao acaso. Se b = 1, k′ = k. 3. A lista de mensagens M e a chave k′ são enviadas ao adversário A. 4. A envia um bit b′ 5. O resultado do experimento é um se b = b′ ou zero em caso contrário. � De�nição 9.2 (Segurança para protocolo de estabelecimento de chaves). Um protocolo de estabelecimento de chaves Π é seguro se para todo adversário polinomial A existe uma função desprezível negl tal que Pr[KE_EAV(Π,A, n) = 1] ≤ 1 2 + negl(n). � Esta noção de segurança é adequada a protocolos de estabelecimento de chaves: como há apenas dois atores e presumimos que há con�ança mútua, só temos que nos preocupar com a possibilidade de obtenção da chave por um adversário que não participa do protocolo. 9.3 Protocolo Di�e-Hellman para estabelecimento de chaves O protocolo de estabelecimento de chaves de Di�e e Hellman usa um algoritmo G que, dado um parâmetro n, retorna a descrição de um grupo cíclico G de ordem q tal que q tem n bits, e um gerador g de G. Construção 9.3 (Protocolo de Di�e e Hellman para estabelecimento de chaves). Dois participantes, A e B, estabelecem uma chave simétrica da seguinte maneira: • A usa G para obter (G, q, g) • A escolhe x ∈R Zq e calcula h1 = gx 9.3. PROTOCOLODIFFIE-HELLMAN PARA ESTABELECIMENTODE CHAVES153 • A envia (G, q, g, h1) para B • B escolhe y ∈R Zq e calcula h2 = gy. • B envia h2 para A e determina a chave secreta kB = hy1. • A recebe h2 e determina a chave secreta kA = hx2 . � Ao �nal da execução do protocolo, A como B tem chaves secretas kA e kB . Estas chaves são iguais, porque kA = hx2 = (gy)x = gxy kB = hy1 = (gx)y = gxy. É importante observar que o protocolo não especi�ca nada a respeito do grupo, exceto que q deve ter n bits. Com isso é possível usar diferentes grupos na construção prática do protocolo. Um exemplo é o ECDH (Elliptic Curve Di�e-Hellman), onde são usados pontos em uma curva elíptica. Um requisito evidente do Di�e-Hellman é que o problema do Logaritmo Discreto seja difícil � caso contrário qualquer um que observe as mensagens trocadas poderá inferir a chave. Este é, no entanto, apenas necessário. Podemos identi�car outro problema, relacionado ao logaritmo discreto, que captura a essência da di�culdade do protocolo. Este problema leva o mesmo nome do protocolo. De�nição 9.4 (Problema de Di�e-Hellman). Dados um grupo cíclico G e um gerador g gerados por um algoritmo G(1n), denotamos DHg(a, b) = gab. O problema Di�e-Hellman computacional (ou CDH, �Computational Di�e- Hellman�) consiste em calcular DHg(a, b) dados ga e gb escolhidos ao acaso em G. O problema Di�e-Hellman decisional (ou DDH, �Decisional Di�e-Hellman�) consiste em reconhecer se um elemento x foi escolhido ao acaso em G ou se é igual a DHg(a, b) para algum a e algum b gerados aleatoreamente. Dizemos que CDH e DDH são difíceis com relação a um algoritmo G se não houver algoritmo polinomial que os resolva quando os grupos são gerados por G. � Há algoritmos G para os quais não se conhece algoritmo e�ciente para resolver CDH ou DDH (mas não há tampouco prova de que não existam). O que demonstramos então é que o protocolo de Di�e-Hellman é seguro se o problema é difícil para um algoritmo G. Teorema 9.5. Se o problema Di�e-Hellman decisional é difícil para um algo- ritmo G, o protocolo Di�e-Hellman (Construção 9.3) é seguro de acordo com a De�nição 9.2 quando G é usado. Demonstração. Supomos que o grupo G usado no experimento 9.1 foi gerado por um algoritmo G. O bit b é escolhido ao acaso, então Pr[b = 0] = 1/2. Pr[KE_EAV(Π,A, n) = 1 ] = 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 1 ] + 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 0 ]. No experimento KE_EAV o adversário recebe k′, que pode ser um elemento ale- atório do grupo ou a chave. Assim, A pode ter, com igual probabilidade: • (G, q, g, h1, h2, g xy), ou • (G, q, g, h1, h2, k ′), sendo que k′ foi escolhida aleatoreamente. Distinguir entre ambos é exatamente resolver o problema Di�e-Hellman decisi- onal: Pr[KE_EAV(Π,A, n) = 1 ] = 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 1 ] + 1 2 Pr[KE_EAV(Π,A, n) = 1|b = 0 ] = 1 2 Pr[A(G, q, g, gx, gy, gxy) = 1 ] + 1 2 Pr[A(G, q, g, gx, gy, gz) = 0 ] = 1 2 Pr[A(G, q, g, gx, gy, gxy) = 1 ] + 1 2 1− Pr [A(G, q, g, gx, gy, gz) = 1 ] = 1 2 Pr[A(G, q, g, gx, gy, gxy) = 1 ] + 1 2 1− Pr [A(G, q, g, gx, gy, gz) = 1 ] = 1 2 + 1 2 ( Pr[A(G, q, g, gx, gy, gxy) = 1 ] − Pr [A(G, q, g, gx, gy, gz) = 1 ]) ≤ 1 2 + 1 2 ∣∣∣Pr[A(G, q, g, gx, gy, gxy) = 1 ] − Pr [A(G, q, g, gx, gy, gz) = 1 ]∣∣∣. Como g é gerador de G, gz é distribuído uniformemente no grupo se z for uniformemente distribuído em Zq. Se o problema Di�e-Hellman decisional é difícil para G, então existe negl desprezível tal que∣∣∣Pr[A(G, q, g, gx, gy, gxy) = 1 ] − Pr [A(G, q, g, gx, gy, gz) = 1 ]∣∣∣ ≤ negl(n). Concluímos que Pr[KE_EAV(Π,A, n) = 1 ] ≤ 1 2 + 1 2 negl(n). � Note que esta demonstração parece ter um pequeno problema: quando b = 0, o adversário recebe um elemento aleatório do grupo G, e não uma cadeia alea- tória de bits. Para que a diferença �que clara, suponha que tenhamos escolhido o grupo Zq e que a ordem do grupo seja q = 257, que é representado por 100000001 em binário. Apenas um elemento do grupo tem o primeiro bit igual a um: 256 = 100000000. Este não é um problema com a demonstração, mas um fato a que o implementador deve dar atenção: não se pode usar números diretamente para representar elementos de G; ao invés disso deve