Wikipédia

Troca de chaves de Diffie–Hellman: diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
m Tradução de imagem troca de chave Diffie-Hellman
Linha 15:
 
Diffie-Hellman estabelece um compartilhamento de chaves secreto que pode ser usado para troca de mensagens secretas dentro de um canal de comunicação público. O diagrama a seguir ilustra a ideia geral de troca de chaves usando cores ao invés de um número muito grande.
# Inicialmente, uma cor em comum é compartilhada entre Alice e BobJoão, cor esta que pode ser observada por um terceiro interessado na comunicação entre os dois.
# O passo seguinte é a escolha de Alice e BobJoão, cada um, de uma cor secreta própria, que não é compartilhada com ninguém.
# Cada um faz uma mistura primária com a cor comum e com suas cores secretas.
# O passo chave do processo é que Alice e BobJoão trocam apenas suas misturas primárias. Estas misturas primárias, resultado das combinações da cor comum e das cores secretas, muito dificilmente conseguem reverter e determinar quais as cores secretas Alice e BobJoão utilizaram, caso um terceiro esteja escutando a comunicação.
# Alice e BobJoão então usam suas cores secretas sobre as misturas primárias que receberam, gerando misturas secundárias (chave comum) que serão iguais tanto para Alice quanto para BobJoão, sem que um terceiro que esteja observando a comunicação consiga produzir esta mistura secundária.
 
Alice e BobJoão usam sua chave comum encriptar e desencriptar de modo secreto suas mensagens. Note que a cor amarela já foi previamente acordada por Alice e BobJoão.
[[Ficheiro:Diffie-Hellman.jpg|centro|miniaturadaimagem|468x468px|Esquema de troca de chaves de Diffie-Hellman]]
A mais simples e original implementação do protocolo utiliza grupos multiplicativos de inteiros módulo "''p"'', onde "''p"'' é um [[número primo]] e "''g"'' é uma raiz primitiva de módulo "''p"''. Aqui está um exemplo do protocolo, onde os valores públicos estão em <span style="color:blue">azul</span> e os valores secretos estão em <span style="color:red"> '''vermelho e destacados''' </span>:
Linha 29:
! colspan="3" | Alice
| <br>
| align="center" colspan="3" | '''BobJoão'''<br>
|-
| bgcolor="#d0d0d0" align="center" style="font-size: 90%;" | Secreto
Linha 72:
|}
 
# [[Alice e BobJoão]] entram em acordo para usar um número primo ''<span style="color:blue">p</span>''=<span style="color:blue">23</span> e como base ''<span style="color:blue">g</span>''=<span style="color:blue">5</span>.
# Alice escolhe um inteiro secreto '''''<span style="color:red">a</span>'''''='''<span style="color:red">6</span>''', e então envia a BobJoão <span style="color:blue">A</span> = ''<span style="color:blue">g</span><sup>'''<span style="color:red">a</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* <span style="color:blue">A</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">6</span>'''</sup> mod <span style="color:blue">23</span>
#* <span style="color:blue">A</span> = '''<span style="color:red">15.625</span>''' mod <span style="color:blue">23</span>
#* <span style="color:blue">A</span> = <span style="color:blue">8</span>
# BobJoão escolhe um inteiro secreto '''''<span style="color:red">b</span>'''''='''<span style="color:red">15</span>''', e então envia a Alice <span style="color:blue">B</span> = ''<span style="color:blue">g</span><sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* <span style="color:blue">B</span> = <span style="color:blue">5</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span>
#* <span style="color:blue">B</span> = '''<span style="color:red">30.517.578.125</span>''' mod <span style="color:blue">23</span>
Linha 85:
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">47.045.881</span>''' mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
# BobJoão calcula '''<span style="color:red">s</span>''' = ''<span style="color:blue">A</span>'' ''<sup>'''<span style="color:red">b</span>'''</sup>'' mod ''<span style="color:blue">p</span>''
#* '''<span style="color:red">s</span>''' = <span style="color:blue">8</span><sup>'''<span style="color:red">15</span>'''</sup> mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">35.184.372.088.832</span>''' mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
# Alice e BobJoão compartilham agora uma chave secreta: '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''. Isto é possível porque <span style="color:red">6</span>*<span style="color:red">15</span> é o mesmo que <span style="color:red">15</span>*<span style="color:red">6</span>. Alguém que tenha descoberto estes dois inteiros privados também será capaz de calcular <span style="color:red">s</span> da seguinte maneira:
#* '''<span style="color:red">s</span>''' = <span style="color:blue">5</span><sup>'''<span style="color:red">6*15</span>'''</sup> mod <span style="color:blue">23</span>
#* '''<span style="color:red">s</span>''' = <span style="color:blue">5</span><sup>'''<span style="color:red">15*6</span>'''</sup> mod <span style="color:blue">23</span>
Linha 96:
#* '''<span style="color:red">s</span>''' = '''<span style="color:red">2</span>'''
 
Tanto Alice quanto BobJoão chegaram no mesmo valor pois (''g<sup>a</sup>'')''<sup>b</sup>'' e (''g<sup>b</sup>'')''<sup>a</sup>'' são iguais mod ''p''. Note que apenas ''a'', ''b'' e ''g<sup>ab</sup> = g<sup>ba</sup>'' mod ''p'' são mantidos em segredo. Todos os demais valores – ''p'', ''g'', ''g<sup>a</sup> mod p'', e ''g<sup>b</sup> mod p'' – são enviados limpos no canal público. Uma vez que Alice e BobJoão calculam a chave secreta, eles podem então usá-la como chave de encriptação, conhecida apenas por eles, para enviar e receber mensagens ao longo do mesmo canal de comunicação.
É claro que valores bem maiores de ''a'', ''b'', e ''p'' seriam necessários para tornar este exemplo seguro, uma vez que é fácil tentar todos os possíveis valores de ''g<sup>ab</sup>'' mod 23. Existem apenas 23 possíveis inteiros que possuem os resultados observados para mod 23. Por outro lado, se ''p'' for um primo de ao menos 300 dígitos e ''a'' e ''b'' tenham ao menos 100 dígitos, então até os melhores algoritmos conhecidos atualmente não poderiam encontrar ''a'' dado apenas ''g'', ''p'', ''g<sup>b</sup>'' mod ''p'' e ''g<sup>a</sup>'' mod ''p'', mesmo usando todo o poder computacional existente na humanidade. Tal problema é conhecido como problema do [[logaritmo discreto]]. Note que ''g'' não precisa ser necessariamente grande, e na prática seus valores são usualmente 2 ou 5.
 
Linha 103:
Aqui está uma descrição mais genérica do protocolo:
 
# Alice e BobJoão acordam em um [[grupo cíclico]] finito ''G'' e um elemento [[Generating set of a group|gerador]] ''g'' em ''G''.( Isto é usualmente feito muito antes do resto do protocolo; assume que ''g'' é conhecido por todos os atacantes.) Nós vamos escrever o grupo ''G'' de modo multiplicativo.
# Alice escolhe um [[número natural]] aleatório ''a'' e envia ''g<sup>a</sup>'' para BobJoão.
# BobJoão também escolhe um número natural aleatório ''b'' e envia ''g<sup>b</sup>'' para Alice.
# Alice calcula (''g<sup>b</sup>'')''<sup>a</sup>''.
# BobJoão calcula(''g<sup>a</sup>'')''<sup>b</sup>''.
 
Tanto Alice quanto BobJoão estão agora de posse de elemento de grupo ''g<sup>ab</sup>'', que pode servir como a chave secreta compartilhada. Os valores de (''g<sup>b</sup>'')''<sup>a</sup>'' e (''g<sup>a</sup>'')''<sup>b</sup>'' são os mesmos porque os grupos são [[Power-associativity|associativos a potência]]. (Veja também [[exponenciação]].)
 
Com o objetivo de decifrar uma mensagem ''m'', enviada como ''mg<sup>ab</sup>'', BobJoão (ou Alice) deve primeiro calcular ''(g<sup>ab</sup>)<sup>-1</sup>'', da seguinte maneira:
 
BobJoão sabe ''|G|, b,'' e ''g<sup>a</sup>''. Um resultado da teoria de grupos estabelece que a partir da construção de G, ''x<sup>|G|</sup> = 1'' para todo ''x'' em ''G''.
 
BobJoão então calcula ''(g<sup>a</sup>)<sup>|G|-b</sup> = g<sup>a(|G|-b)</sup> = g<sup>a|G|-ab</sup> = g<sup>a|G|</sup>g<sup>-ab</sup> = (g<sup>|G|</sup>)<sup>a</sup>g<sup>-ab</sup>=1<sup>a</sup>g<sup>-ab</sup>=g<sup>-ab</sup>=(g<sup>ab</sup>)<sup>-1</sup>.''
 
Quando Alice envia a BobJoão a mensagem encriptada, ''mg<sup>ab</sup>'', BobJoão aplica ''(g<sup>ab</sup>)<sup>-1</sup>'' e recupera ''mg<sup>ab</sup>(g<sup>ab</sup>)<sup>-1</sup> = m(1) = m.''
 
=== Gráfico ===
 
== Operação com mais de duas partes ==
O esquema de acordo de chaves Diffie-Helman não está limitado à interação entre apenas dois participantes. Qualquer número de usuários pode participar no acordo, executando as interações do protocolo e trocando os dados intermediários entre si. Por exemplo, Alice, BobJoão e Carol poderiam participar em um acordo do tipo Diffie-Hellman de acordo com o exemplo a seguir, onde todas as operações tomadas com módulo <math>p</math>:
# Os participantes selecionam os parâmetros iniciais do algoritmo <math>p</math> e <math>g</math>;
# Os participantes geram suas respectivas chaves privadas, que chamaremos <math>a</math>, <math>b</math> e <math>c</math>.
# Alice calcula <math>g^a</math> e envia o resultado para BobJoão.
# BobJoão calcula <math>(g^a)^b = g^{ab}</math> e envia o resultado para Carol.
# Carol calcula <math>(g^{ab})^c = g^{abc}</math> e utiliza esse valor como sua chave secreta compartilhada.
# BobJoão calcula <math>g^b</math> e envia para Carol
# Carol calcula <math>(g^b)^c = g^{bc}</math> e envia o resultado para Alice.
# Alice calcula <math>(g^{bc})^a = g^{bca} = g^{abc}</math> e utiliza o resultado como chave secreta compartilhada.
# Carol calcula <math>g^c</math> e envia para Alice.
# Alice calcula <math>(g^c)^a = g^{ca}</math> e envia o resultado para BobJoão.
# BobJoão calcula <math>(g^{ca})^b = g^{cab} = g^{abc}</math> e utiliza o resultado como chave secreta compartilhada.
 
Um intruso com acesso ao canal onde essas mensagens foram trocadas foi capaz de observar os valores <math>g^a</math>, <math>g^b</math>, <math>g^c</math>, <math>g^{ab}</math>, <math>g^{ac}</math>, e <math>g^{bc}</math>, mas não pode usar qualquer combinação desses valores para reproduzir <math>g^{abc}</math>.
Obtida de "https://pt.wikipedia.org/wiki/Troca_de_chaves_de_Diffie–Hellman"