Diversos conceitos da teoria dos números são essenciais para o projeto de algoritmos de chave pública. Um exemplo de algoritmo de chave pública que, para sua segurança, depende da

Gabarito

A

Comentário do professor

Diffie-Hellman é um protocolo de troca de chaves cuja segurança se baseia no problema do logaritmo discreto: é fácil elevar, mas difícil “reverter”.

No procedimento, escolhem-se um número primo \(p\) e um gerador \(g\) do grupo multiplicativo módulo \(p\) (p, g).

Cada participante escolhe um segredo privado (\(a\) e b) e calcula \(A=g^a \bmod p\) e \(B=g^b \bmod p\), que são trocados publicamente.

Ao receber \(A\) e \(B\), cada um computa \(s=A^b \bmod p = B^a \bmod p = g^{ab} \bmod p\), obtendo assim a chave compartilhada.

A segurança decorre da facilidade da exponenciação modular versus a dificuldade prática de extrair \(a\) de \(A\) (resolver o logaritmo discreto) sem conhecer os segredos.