\chapter{Vulnerabilidades da Cifra de Hill}
	A Cifra de Hill foi altamente revolucionária quando de sua criação, pois era a
	primeira cifra de substituição poligráfica com a qual era prática trabalhar em
	blocos de mais que três caracteres. Porém ela tornou-se obsoleta e suas
	fraquezas a tornam inutilizável nos tempos modernos. Nesta seção vamos abordar
	alguns ataques aos quais a Cifra de Hill é vulnerável, e quais
	são os aspectos da cifra (relacionados à Geometria Analítica) que causam essas
	vulnerabilidades.
	
	Pretendemos ainda mencionar alguns pequenos ``ajustes'' que poderiam ser
	adicionados ao processo de encriptação/decriptação com a Cifra de Hill, e que
	aumentariam sua segurança.
	
	\section{Número de possíveis chaves}
		O número de chaves possíveis de serem usadas é uma medida importante da
		segurança de um algoritmo de critografia. Isso porque, com o imenso poder
		computacional disponível nos dias de hoje, a busca de uma chave por força
		bruta (tentativa de todas as opções possíveis) é muito rápida. Portanto um
		padrão criptográfico deve ter um grande número de possíveis chaves, tornando
		inviável uma busca por força bruta.
		
		Se temos um conjunto de k números, e uma matriz quadrada de ordem $n \times
		n$, então o número de matrizes diferentes que podemos formar,
		\emph{escolhendo livremente} dentre esses k elementos é:
		\[
			k^{n^2}
		\]
		Essa quantidade é encontrada facilmente usando o conceito de arranjos. Se
		usarmos o alfabeto usual com 26 letras, teremos um limite superior
		de $26^{n^2}$ possíveis chaves. Esse número é apenas um limite superior pois
		dentre esse grupo, devemos escolher como chave somente as matrizes
		\emph{inversíveis em módulo 26}.
		
		Mas e o que significa uma matriz ser inversível módulo 26? Relembrando a
		fórmula para inverter uma matriz: 
		\[
			A^{-1} = \frac{1}{|A|} cof(A)^{t}
		\]
		Usamos o determinante para encontrar a inversa de uma matriz. E como usamos
		aritmética modular na Cifra de Hill, a matriz inversa $A^{-1}$ deve conter
		somente números inteiros. Isso implica que a o determinante deve ser divisor
		dos elementos da matriz adjunta. Com essa restrição reduzimos bastante o
		número de possíveis chaves. Apesar disso, aumentando a ordem da matriz chave,
		aumentamos esse número, mas então a encriptação começa a se tornar
		inviavelmente lenta.
		
		De fato, esse aspecto (número de chaves) contribui para a vulnerabilidade da
		Cifra de Hill. O número de chaves possíveis não é suficiente para tornar
		extremamente impraticável um ataque por força bruta. Porém ele não é o mais
		problemático. A Cifra de Hill sofre também de \emph{linearidade}.
		
	\section{Linearidade da cifra}
		A Cifra de Hill também é vulnerável a ataques de ``Texto plano conhecido''.
		Esses ataques ocorrem quando alguém ``escutando'' o canal da mensagem
		consegue ter acesso a alguns (poucos) pares de caracteres originais/cifrados.
		Alguém com acesso a esses pares tem grandes chances de descobrir a chave
		sendo usada, isso pois a Cifra de Hill é completamente \emph{linear}.
		
		Diz-se que a Cifra de Hill é linear pois suas operações são lineares
		(multiplicação por escalares e adição); A própria ``natureza'' da cifra é
		linear pois ela usa dos conceitos da Álgebra Linear e Geometria Analítica.
		
		Um interceptador, ``escutando'' uma mensagem sendo transmitida com Cifra de
		Hill de ordem 2 precisa de apenas 4 pares de caracteres original/cifrado para
		descobrir a chave. Por exemplo:
		
		\[
			\begin{bmatrix}
            	k_{11} & k_{12} \\
            	k_{21} & k_{22} \\
            \end{bmatrix}
			\begin{bmatrix} 4 \\ 5 \end{bmatrix}
            = \begin{bmatrix} 1 \\ 7 \end{bmatrix}
            \quad
			\begin{bmatrix}
            	k_{11} & k_{12} \\
            	k_{21} & k_{22} \\
            \end{bmatrix}
			\begin{bmatrix} 17 \\ 3 \end{bmatrix}
            = \begin{bmatrix} 12 \\ 5 \end{bmatrix}
            \Longrightarrow
            \begin{bmatrix}
            	k_{11} & k_{12} \\
            	k_{21} & k_{22} \\
            \end{bmatrix}
			\begin{bmatrix}
            	4 & 17 \\
            	5 & 3 \\
            \end{bmatrix}
			=
			\begin{bmatrix}
            	1 & 12 \\
            	7 & 5 \\
            \end{bmatrix}
		\]
		
		Da multiplicação matricial mais à direita pode-se montar um sistema de
		equações lineares, que resolvido nos dá a chave sendo usada. Claramente esse
		exemplo com chaves de ordem 2 é apenas didático. Mesmo em 1929 a Cifra de
		Hill já usava matrizes chave de ordem 6 ou superior. O fato, porém, é que
		mesmo assim a linearidade continua, e como resolver sistemas lineares se
		tornou trivial com computadores, a Cifra de Hill ficou vulnerável.
		
		De modo geral, para descobrir a chave de ordem n da Cifra de Hill basta que o
		atacante conheça $n^2$ pares de caracteres originais/cifrados. Ele poderá
		montar um sistema lineares de $n^2$ equações e $n^2$ incógnitas, e ao
		resolvê-las terá descoberto a chave.
		
		
	\section{Sugestões para adicionar segurança à cifra}
		Quanto ao ``núcleo'' da Cifra de Hill não se pode fazer nada para aumentar
		sua segurança; ela é totalmente linear pela própria natureza das operações. O
		que se pode fazer é adicionar algumas \emph{camadas extras} no processo de
		encriptação/decriptação usando a Cifra de Hill. Os dois ``passos'' do
		processo que podem ser \emph{parametrizados} são:
		
		\subsection{Escolha da função bijetora entre caracteres e números}
			Em todos os exemplos deste trabalho considerou-se a associação entre as
			letras do alfabeto e os inteiros de 0 a n-1 como sendo a usual, ou seja:
			a=0, b=1, c=2, \ldots, z=25. Mas também se enfatizou que QUALQUER
			mapeamento, e não especificamente esse, funcionaria.
			
			Uma possibilidade seria então a de \emph{parametrizar} a escolha dessa
			função bijetora, ou seja, fornecer ao algoritmo cifrador que usa a Cifra de
			Hill uma espécie de ``chave extra'', a qual serviria para identificar qual
			permutação do alfabeto deve ser usada no mapeamento. Isso aumentaria
			a segurança pois mesmo conhecendo-se a matriz chave ainda não se sabe quais
			são os caracteres correspondentes aos números da mensagem.
			
		\subsection{Permutações entre os blocos de texto encriptados (vetores)}
			Uma outra operação que poderia ser adicionada à Cifra de Hill para
			aumentar sua segurança seria mudar a ordem dos blocos de texto
			encritpados. Novamente seria usado um parâmetro também aleatório nesse
			processo, e que seria uma terceira ``chave'', de conhecimento mútuo de
			quem envia e recebe a mensagem.
			
			Tendo k blocos encriptados, o números de possíveis permutações desses k
			blocos é similarmente k!. Conjuntamente com o processo descrito na
			subseção anterior, é adicionada uma camada de operações não-lineares à
			cifra, o que a torna mais segura.			
		
        
        
