\chapter{Noções básicas de criptografia}
	Criptografia (Kriptós = escondido, oculto; grapho = escrita) é o estudo de
	maneiras de se transmitir mensagens através de um meio inseguro, na qual alguém
	que consiga interceptá-la no meio do caminho tenha uma probabilidade
	praticamente nula de descobrir a mensagem original.
	
	Desde as sociedades antigas (babilônicos, egípcios, etc) sentiu-se a
	necessidade de manter informações secretas. Os métodos amplamente usados desde
	esse período até o final da Segunda Guerra Mundial eram baseados essencialmente
	na simples substituição de caracteres (permutações).
	
	A partir da década de 1950, com o aumento do poder computacional, as cifras
	usadas até então passaram a ser mais facilmente quebradas. Então houve a
	necessidade de se criar novos modelos não tão frágeis como os anteriores. Esses
	novos modelos se baseiam sobretudo nas chamadas \emph{funções de uma direção};
	São funções computacionalmente fáceis de serem computadas, mas que se acredita
	ser extremamente complexo de se inverter. Um desses modelos é o RSA, muito
	popular atualmente. O RSA se baseia no fato de que realizar o produto de dois
	inteiros primos é muito fácil, mas decompor enormes inteiros em seus fatores
	primos é computacionalmente inviável. Os números usados no RSA são de ordem de
	grandeza igual ou maior a $10^{100}$.
	
	Na sequência comentaremos um pouco sobre alguns modelos de codificação chamados
	de Cifras de substituição, Criptografia de chave simétrica e de chave
	assimétrica.
	
	\section{Cifras de substituição}
		A cifra de substituição faz a codifição da mensagem de acordo com uma regra
		pré-definida (chamada de chave), de acordo com uma tabela, na qual se
		estabelece a correspondência entre o símbolo orginal e o criptografado. As
		cifras de substituição são assim meras funções permutação. Para se fazer a
		decriptação é necessário saber a chave (e portanto a tabela de substituição)
		e fazer a substituição. Algumas das principais cifras de substituição:
		
		\begin{itemize}
          \item Cifras monoalfabéticas ou de substituição simples;
          \item Cifras polialfabéticas;
          \item Cifras homofônicas;
          \item Cifras poligráficas ou de múltiplos símbolos.
        \end{itemize}
        
        \begin{description}
			\item[Cifras monoalfabéticas]
				A codificação de mensagens é feita através de uma tabela, em que o alfabeto
				na sua ordem usual é colocado em uma linha, e uma das possíveis permutações
				desse alfabeto é colocada na linha logo abaixo. A codificação se faz com
				uma função bijetora, na qual um $f(a)$ corresponde a um $a'$ e a
				decodificação faz-se com a função inversa.
				
				\begin{description}		
				\item[Exemplo] Cifra de Cesar: \\
				\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
                	\hline
					a & b & c & d & e & f & g & h & \ldots & r & s & t & u & v
					& w & x & y & z \\
					\hline
					d & e & f & g & h & i & j & k & \ldots & u & v & w & x & y
					& z & a & b & c \\
					\hline
				\end{tabular}
				\end{description}

			\item[Cifras polialfabéticas]
				A tabela de codificação é montada contendo n linhas por n colunas, onde n é
				o número de símbolos do alfabeto. As linhas da tabela são preenchidas com
				algumas das possíveis permutações sobre o alfabeto. A encriptação é feita
				transformando-se cada bloco de texto usando uma linha da tabela.
				
				\textbf{Exemplo}: Mensagem original - cada decada \newline				
				\begin{tabular}{c||c|c|c|c|c}
                	X & a & b & c & d & e \\ \hline \hline
                	a & a & b & c & d & e \\ \hline
                	b & b & c & d & e & a \\ \hline
                	c & c & d & e & a & b \\ \hline
                	d & d & e & a & b & c \\ \hline
                	e & e & a & b & c & d \\
                \end{tabular}

				A palavra ``cada'' foi cifrada com a linha e (cada = bece) e ``decada'' foi
				cifrada com a linha c (decada = abecac)
				
			\item[Cifras homofônicas]
				Nesse tipo de cifra, os caracteres com incidência acima da média 
				(por ex: a no português) têm mais de uma opção de substituição quando a
				encriptação é feita. Isso visa diminuir os riscos da mensagem ser
				descoberta por análise estatística, que será explicada mais adiante.
			\item[Cifras poligráficas]
				A encriptação de uma mensagem é feita substituindo o caractere original por
				um conjunto de símbolos. Assume-se que esse conjunto de símbolos seja
				conhecido por poucas pessoas.
        \end{description}

	\section{Criptografia de chave simétrica}
		Um modelo de criptografia em que o emissor e o receptor têm a mesma chave, ou
		seja, a codificação e a decodificação são feitas com uma única chave, ou
		então a chave de codificação e a de decodificação têm uma relação matemática
		trivial (uma pode ser muito facilmente obtida tendo-se a outra). A Cifra de
		Hill é uma cifra simétrica, e algumas cifras simétricas modernas são o DES e
		o AES.
		
		\begin{description}
			\item[DES (Data Encryption Standard)]
				O modelo opera sobre blocos de texto com 64 bits cada, e usa uma chave de
				56 bits (72 quadrilhões de chaves possíveis). A codificação é feita
				usando-se uma função inversível sob blocos de bits representando a
				mensagem. A função que encripta a mensagem é parametrizada pela chave, o
				que fornece a segurança do sistema, mesmo o algoritmo em si sendo público.
			\item[AES (Advanced Encryption Standard)]
				Esse padrão de criptografia surgiu em 1998 após um concurso promovido pelo
				governo americano para substituir o DES, padrão internacional até então.
				
				A codificação do texto plano utiliza operações matriciais sobre blocos de
				bytes armazenados em matrizes $4 \times 4$. A encriptação começa combinando
				cada byte com uma subchave (derivada da chave principal], depois cada byte
				é substituído por outro de acordo com uma tabela de referência, em seguida
				cada linha da matriz é deslocada n posições, então é feita uma
				multiplicação da matriz original com a resultante desse deslocamento e a
				matriz resultante multiplicada por $x^4 + 1$.
        \end{description}
	
	\section{Criptografia de chave assimétrica}
		São modelos de criptografia onde cada pessoa porta duas chaves, uma chamada
		de \emph{chave pública} (amplamente divulgada) e outra é a chave privada.
		
		Uma mensagem encriptada usando uma chave só poderá ser decriptada usando a
		outra correspondente. Se desejo enviar uma mensagem secreta a um amigo meu,
		devo encriptá-la usando a chave pública dele, assim somente ele (o portador
		de sua chave privada) poderá decifrar a mensagem.
		
		De modo semelhante, posso enviar uma mensagem cifrada com minha chave
		privada, e todos que possuem minha chave pública (TODOS) poderão lê-la. O
		grande benefício é que assim posso provar que FUI EU quem escrevi a mensagem,
		e isso faz com que a criptografia de chave assimétrica também dê
		autenticidade.
		
		O algoritmo mais usado para implementar a criptgrafia assimétrica é o RSA,
		inventado por Rivest, Shamir e Adleman. Ele será descrito a seguir:
		
		\begin{description}
			\item[RSA]
				A codificação da mensagem é feita multiplicando-se dois números
				primos muito grandes (da ordem de $10^{100}$). A segurança do RSA vem do
				fato de que decompor um grande número em seus fatores primos é impraticável
				computacionalmente. Para se decompor um número da ordem de $10^{100}$ em
				seus dois fatores primos se levaria um tempo maior que a IDADE DO UNIVERSO,
				usando todo o poder computacional atualmente disponível na Terra.
        \end{description}

	\section{Criptoanálise}
		A criptoanálise estuda maneiras de se chegar a mensagem original (plaintext)
		sem o conhecimento da chave (key) a partir do texto cifrado (ciphertext),
		assim como também maneiras de se descobrir a chave. Algumas das técnicas de
		criptoanálise são:
		
		\begin{itemize}
          \item Brute force
          \item Ciphertext only
          \item Known text
          \item Timing
          \item Análise estatística
        \end{itemize}
        
        \begin{description}
			\item[Brute force]
				Tenta-se chegar à chave testando-se todas as possibilidades. A eficácia
				desse método depende do tamanho e da complexidade da chave. Já se conseguiu
				descobrir uma chave do DES por força bruta em cerca de 20h.
			\item[Ciphertext only]
				Tenta-se chegar à chave ou ao texto original conhecendo-se apenas uma parte
				da mensagem codificada. Nas cifras de substituição simples é relativamente
				fácil descobrir a chave apenas com papel e caneta.
			\item[Known text]
				Tenta-se chegar à chave conhecendo-se uma pequena parte do texto original e
				do cifrado correspondente. A Cifra de Hill é \emph{bastante} vulnerável à
				ataques desse tipo. 
			\newpage
			
			\item[Timing]
				Tenta-se descobrir a chave de acordo com o tempo de execução do algoritmo
				que criptografa a mensagem.
			\item[Análise Estatística]
				Busca na mensagem criptografada a freqüência com que os símbolos aparecem a
				compara com a distribuição de freqüências dos símbolos na língua em que se
				supõe estar a mensagem original. A partir de então tenta chegar à algumas
				prováveis mensagens originais (usando o Teorema de Bayes). A Cifra de Hill
				também é vulnerável a esse tipo de ataque.
        \end{description}
