\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[brazilian]{babel}
\renewcommand{\familydefault}{\sfdefault}
\usepackage{ifpdf}
\usepackage{fullpage}
\usepackage{hyperref}
\usepackage{url}
\usepackage{amssymb}

\title{Protocolo de troca de chaves Diffie-Hellmann}
\author{João Paulo Pizani Flor}
\date{\today}

\ifpdf
	\pdfinfo {
		/Author (João Paulo Pizani Flor)
		/Title (Protocolo de troca de chaves Diffie-Hellmann)
		/Subject (SUBJECT)
		/Keywords (KEYWORDS)
		/CreationDate (D:20100509201552)
	}
\fi


\begin{document}
	\maketitle
	
	\section{Introdução}
	    O protocolo de troca de chave Diffie-Hellmann\cite{wp-dhke} é uma maneira segura de
	    se criar um segredo compartilhado através de uma rede de computadores. Tal método
	    pode ser utilizado, por exemplo, para estabelecer uma chave de sessão através de
	    um meio de comunicação não-confiável. Tal chave acordada pode então ser usada em um
	    algoritmo de criptografia simétrica.
	    
	    Os passos gerais do acordo de chaves Diffie-Hellmann (em cada uma dos lados na
	    comunicação) são os seguintes:
	    \begin{itemize}
	        \item Obtém os parâmetros públicos G e N, que devem ser comuns a ambos os lados
	        e pode mser previamente combinados.
	        \item Gera um número aleatório $E$
	        \item Calcula a potência $X = G^{E}\,\bmod\,N$ e a envia ao lado remoto
	        \item Recebe o número $Y$, vindo do lado remoto
	        \item A chave acordada será o número $Z = Y^{E}\,\bmod\,N$
	    \end{itemize}
	    
	    A segurança do protocolo está baseada na dificuldade de se resolver o problema do
	    logaritmo discreto. O atacante em potencial só conseguirá obter através da rede os
	    parâmetros G e N, além das potências, os quais são enviados em texto plano. Para
	    quebrar o protocolo e obter a chave Z, o atacante deve obter os expoentes secretos
	    a partir das potência, caracterizando assim o logaritmo discreto.
	    
	    O presente trabalho consistiu em uma implementação do acordo de chaves Diffie-Hellmann
	    escrito na linguagem \emph{Java}. Ainda, deve ser possível utilizar duas instâncias
	    do programa desenvolvido para negociar uma chave secreta de sessão através de redes
	    TCP/IP. As seguintes seções detalham as abordagens adotadas para cada passo do
	    protocolo de acordo de chaves. A última seção contem instruções de como rodar o
	    pacote .jar desenvolvido em ambas as máquinas que desejam acordar uma chave.
	    
	\section{Geração de números aleatórios}
	    A troca de chaves Diffie-Hellmann precisa de parâmetros gerados aleatoriamente,
	    especialmente o expoente Ex, secreto para cada um dos lados da transação.
	    
	    Nessa implementação, o servidor gera de forma \emph{também aleatória} os parâmetros
	    públicos G e N, e para tal geração utiliza o mesmo algoritmo que gera Ex. Foi
	    utilizada, para a geração de todos os parâmetros aleatórios necessários, a classe
	    java.security.SecureRandom\cite{net-securerandom}, a qual fornece serviços de
	    geração de objetos aleatórios \emph{criptograficamente seguros}, ou seja, adequados à
	    utilização para propósitos criptográficos.
	    
	    A classe SecureRandom pode realizar a geração através de diversos algoritmos, porém
	    o algoritmo default (que foi utilizado nesse trabalho) é o \emph{SHA1RNG}.
	    
	\section{Teste de primalidade}
	    Para atender ao requerimento de se gerar um número primo aleatório suficientemente
	    grande (40 bits), foi utilizado o método \emph{probablePrime}, da classe
	    java.lang.BigInteger\cite{net-biginteger}. Tal método recebe como parâmetro uma
	    instância de Random (que fornecerá a aleatoriedade na geração do número) e um
	    parâmetro inteiro \emph{bits}, o qual dita o tamanho aproximado em bits do número
	    gerado.
	    
	    O algoritmo de teste de primalidade utilizado internamente no método
	    BigInteger.probablePrime é o \emph{Teste de Rabin-Miller}\cite{wp-rabin}. Ele é um
	    algoritmo probabilístico, isto é, fornece uma saída não-determinística, porém com uma
	    \emph{(alta) probabilidade} de corretude. Um número reportado como primo pelo teste
	    de Rabin-Miller é dito ``primo provável'', e podem existir números compostos que
	    passam no teste. Tais números são chamados \emph{pseudo-primos}, mas sua ocorrência
	    pode ser feita tão rara quanto desejável, porém ao se aumentar a certeza na resposta
	    do algoritmo seu tempo de execução também aumenta.
	    
	    A precisão do algoritmo é controlada através de uma parâmetro $k$. A probabilidade
	    $P_{c}$ de que um número composto passe no teste é dada pela expressão:
	    $P_{c} = 2^{-k}$. No caso do método BigInteger.probablePrime, $k = 100$, portanto a
	    probabilidade de que um número composto seja gerado nesta implementação é de
	    $ 2^{-100} $. Abaixo é mostrado um pseudo-código para o algoritmo de Miller-Rabin:
	    
	    \begin{verbatim}
Entrada: n > 3, inteiro ímpar a ser testado; 
Entrada: k, parâmetro definindo a precisão do teste;
Saída: false se for composto, true se for primo provável;

write n - 1 as 2s·d with d odd by factoring powers of 2 from n - 1
LOOP: repeat k times:
   pick a randomly in the range [2, n - 2]
   x = (a*d) mod n
   if x == 1 or x == n - 1 then do next LOOP
   for r = 1 .. s - 1
      x = x2 mod n
      if x == 1 then return false
      if x == n - 1 then do next LOOP
   return false
return true
	    \end{verbatim}
	    
	    A complexidade assintótica do algoritmo é de $O(k * (\log{n})^3)$, onde $k$ é o número
	    de valores distintos de $a$ que são testados e $n$ é o inteiro sendo testado.
	    
	
	\section{Raiz primitiva}
	    O protocolo de troca de chaves Diffie-Hellmann realiza entre as duas partes a troca
	    de potências, calculadas a partir dos parâmetros públicos e de um número aleatório,
	    segundo a fórmula:
	    \[
	        P_{x} = G^{E_{x}} mod N
	    \]
	    $E_{x}$ é um número aleatório qualquer, gerado pela parte $x$ na comunicação. Este
	    número é o parâmetro secreto, exclusivo de cada lado no protocolo. Já G e N são
	    parâmetros públicos do protocolo Diffie-Hellmann, e devem ser acordados previamente.
	    
	    O parâmetro G deve ser uma \emph{raiz primitiva} de N. Isso explica a necessidade
	    de N ser um número primo, isso pois todo número primo possui uma raiz primitiva.
	    Uma raiz primitiva de um inteiro n é um número capaz de produzir todos os elementos
	    do grupo multiplicativo $\mathbb{Z}_{n}$ através da potenciação modular. Isto é:
	    \[
	        \forall a \in \mathbb{Z} \quad gcd(a,n) = 1 \rightarrow
	        \exists k : g^{k} \equiv a \pmod{n}
	    \]
	    Se g é uma base de $\mathbb{Z}_{n}$, então todo número coprimo com n é
	    \emph{congruente} a uma potência de g. Por isso também se diz que g é um
	    \emph{gerador} do grupo $\mathbb{Z}_{n}$. Neste trabalho foi utilizada um
	    procedimento para cálculo da raiz primitiva bastante semelhante ao que pode ser
	    encontrado em \cite{wp-primitive}.
	    
	    Em passos gerais, o algoritmo pode ser descrito como segue:
	    \begin{itemize}
	        \item Se obtém $\phi(n)$, que é $(n-1)$, pois n é primo.
	        \item A realizada a decomposição de $\phi(n)$ no conjunto $\mathbb{P}$ de seus
	        fatores primos.
	        \item Todos os valores no intervalo [1,n-1] que atenderem ao seguinte critério
	        são raízes primitivas de n:
	        \[
	            \forall p \in \mathbb{P} \quad m^{\phi(n)/p}\,\bmod\,n = 1
	        \]
	    \end{itemize}
	    
	
	\section{Instruções de execução}
	    O programa desenvolvido está empacotado em um arquivo .jar, e pode ser executado em
	    qualquer computador que possua uma instalação da máquina virtual Java, sem nenhuma
	    outra dependência.
	    
	    Pode-se executar o programa em dois modos: Servidor e cliente. A instância servidora
	    é responsável por gerar os parâmetros públicos (G e N) e então aguardar por uma
	    conexão de um cliente. Na execução do cliente deve-se passar como parâmetros na linha
	    de comando o IP do servidor, assim como G e N. O cliente irá então conectar-se
	    ao servidor remoto, e acordar uma chave, que será então exibida (tanto no lado local
	    quanto no lado remoto da conexão). Os comandos para executar lado servidor e
	    cliente seguem:
	    \begin{description}
	        \item[Servidor]
	        \begin{verbatim} java -jar DHKE.jar server <bits> \end{verbatim}
	        \item[Cliente]
	        \begin{verbatim} java -jar DHKE.jar client <ipservidor> <N> <G> \end{verbatim}
	    \end{description}
	    
	    Significado de cada um dos parâmetros:
	    \begin{description}
	        \item[bits] Número de bits que o primo N aleatório gerado deve possuir
	        \item[ipservidor] Endereço IP ou hostname do servidor ao qual se conectar
	        \item[N] Primo combinado previamente, usado nas operações modulares
	        \item[G] Raiz primitiva de N, usada como base na potenciação
	    \end{description}
	    
	    
	    
	    
	\bibliographystyle{plain}
	\bibliography{referencias}
	    
\end{document}
