Algoritmo Diffie-Hellman: Visão geral e implementação em C

O algoritmo Diffie-Hellman é usado para estabelecer um segredo compartilhado entre duas partes que pode ser usado para comunicação secreta para trocar dados em uma rede pública.

Explicação Pictórica:

O processo começa fazendo com que as duas partes, Alice e Bob, concordem com uma cor inicial arbitrária que não precisa ser mantida em segredo (mas deve ser diferente a cada vez); neste exemplo, a cor é amarela. Cada um deles escolhe uma cor secreta – vermelho e aqua, respectivamente – que guardam para si. A parte crucial do processo é que Alice e Bob agora misturam sua cor secreta com sua cor mutuamente compartilhada, resultando em misturas laranja e azul, respectivamente, e depois trocam publicamente as duas cores misturadas. Finalmente, cada um dos dois mistura a cor que recebeu do parceiro com sua própria cor particular. O resultado é uma mistura de cores final (marrom) idêntica à mistura de cores do parceiro.

Diffie-Hellman_Key_Exchange

Seria impossível para a bisbilhoteira Eve determinar a cor secreta comum.

Explicação criptográfica:

O algoritmo em si é muito simples. Vamos supor que Alice queira estabelecer um segredo compartilhado com Bob. Aqui está um exemplo do protocolo com valores secretos em red.

Alice e Bob concordam em usar um número primo p = 23 e base g = 5. (Esses dois valores são escolhidos dessa maneira para garantir que o segredo compartilhado resultante possa assumir qualquer valor de 1 a p-1).
Alice escolhe um inteiro secreto uma = 6, então envia Bob UMA = g^uma mod p (UMA = 5⁶ mod 23 = 8)
Bob escolhe um inteiro secreto b = 15, então envia Alice B = g^b mod p (B = 5¹⁵ mod 23 = 19)
Alice calcula s = B^uma mod p (s = 19⁶ modo 23 = 2)
Bob calcula s = UMA^b mod p (s = 8¹⁵ modo 23 = 2)
Alice e Bob agora compartilham um segredo (o número 2).

O número que Alice obteve no passo 4 é o mesmo que Bob obteve no passo 5 como

Bob calcula

A^b mod p = (g^a mod p)^b mod p = g^ab mod p

Alice calcula

B^a mod p = (g^b mod p)^a mod p = g^ba mod p

O algoritmo Diffie-Hellman é usado principalmente para trocar chaves de criptografia para uso em algoritmos de criptografia simétrica como AES. Por favor, observe que as informações não são compartilhadas durante a troca de chaves. Aqui as duas partes estão criando uma chave juntas.

Implementação:

C

#include <stdio.h>

// Função para calcular `a^m mod n`

int compute(int a, int m, int n)

{

int r;

int y = 1;

while (m > 0)

{

r = m % 2;

//exponência rápida

if (r == 1) {

y = (y*a) % n;

}

a = a*a % n;

m = m / 2;

}

return y;

}

// Programa em C para demonstrar o algoritmo Diffie-Hellman

int main()

{

int p = 23; // módulo

int g = 5; //base

int a, b; // `a` – chave secreta de Alice, `b` – chave secreta de Bob.

int A, B; // `A` – chave pública de Alice, `B` – chave pública de Bob

// escolhe um inteiro secreto para a chave privada de Alice (conhecida apenas por Alice)

a = 6; // ou, use `rand()`

// Calcula a chave pública de Alice (Alice enviará `A` para Bob)

A = compute(g, a, p);

// escolha um inteiro secreto para a chave privada de Bob (conhecida apenas por Bob)

b = 15; // ou, use `rand()`

// Calcula a chave pública de Bob (Bob enviará `B` para Alice)

B = compute(g, b, p);

// Alice e Bob trocam suas chaves públicas `A` e `B` entre si

// Encontra a chave secreta

int keyA = compute(B, a, p);

int keyB = compute(A, b, p);

printf("Alice's secret key is %d\nBob's secret key is %d", keyA, keyB);

return 0;

}

Download Executar código

Resultado:

Alice’s secret key is 2
Bob’s secret key is 2

Isso é tudo sobre o algoritmo Diffie-Hellman.

Referência: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange