\chapter{A Cifra de Hill}
	A Cifra de Hill foi inventada por Lester S. Hill em 1929 e é uma cifra de
	substituição polialfabética \emph{em bloco}. A encriptação e a decriptação são
	realizadas através de operações com matrizes e vetores, e a chave é uma matriz
	quadrada inversível (uma base para um espaço vetorial).
	
	\section{Operação de encriptação}
		A encriptação de uma determinada mensagem é feita tomando-se cada letra do
		alfabeto e associando-se a ela um número inteiro de 0 a n-1 de forma
		biunívoca (onde n é o número de letras do alfabeto). Pode-se, por exemplo,
		fazer a=0, b=1, c=2, \ldots, z=25. Divide-se então o texto em blocos de
		tamanho n, e cada um desses blocos então é considearado um vetor de n
		dimensões. É escolhida então uma matriz quadrada inversível de ordem n para
		servir de chave. Essa matriz chave é então multiplicada pelos vetores, um de
		cada vez, resultando nos ``vetores encriptados''.
		
		As operações de multiplicação/adição sobre inteiros que estão implícitas na
		multiplicação matricial são todas realizadas \emph{módulo n}. No caso do
		alfabeto latino, como temos 26 letras, realizamos adição e multiplicação
		\emph{módulo 26}.
		
		Ao final das repetidas multiplicações da chave por cada um dos blocos,
		convertemos os resultados obtidos de volta para as letras usando a inversa da
		função que converteu letras em números. Assim temos a mensagem criptografada.
		
		A matriz utilizada como chave deve ser inversível. Caso ela não seja
		inversível, não será possível voltar à mensagem original depois de encriptada.
		
	\section{Operação de decriptação}
		Para se obter a mensagem original a partir da encriptada, multiplica-se a
		INVERSA da matriz chave por cada um dos blocos (vetores) e assim obtém-se os
		vetores originais, bastando então substituirmos cada número pelo seu caractere
		correspondente e então teremos a mensagem original de volta.
		
	\section{Interpretação geométrica - Mudança de base}
		A operação de encriptação realizada pela Cifra de Hill pode ser interpretada
		puramente como uma mudança de base realizada sobre um conjunto de vetores. A
		mudança de base é uma dentre várias transformações lineares, estudadas pela
		Geometria Analítica e Álgebra Linear.
		
		Consideremos um vetor $\vec{v}$ com n coordenadas e na base usual. Multiplicar
		uma matriz quadrada de ordem n por esse vetor $\vec{v}$ (vetor coluna) é
		totalmente análogo (pode ser interpretado como) uma \emph{mudança de base} de
		$\vec{v}$. Isso significa que agora as coordenadas do vetor v serão a
		representação de v como combinação linear dessa nova base, e não mais
		de \{i,j,k\}.
		
		Se tomarmos uma base $B = \{\vec{b_1},\vec{b_2},\vec{b_3}\}$ e situarmos cada
		um dos vetores dessa base nas colunas de uma matriz, teremos a matriz
		quadrada $M_B$. Se tomarmos a \emph{inversa} dessa matriz, temos a matriz que
		realizará a mudança de base. Representando essa matriz por T, fica:
		$ T = (M_B)^{-1} $
		
		Dizer que T é uma matriz de mudança de base significa que, se a
		multiplicarmos por um vetor na base usual, teremos como resultado o \emph{mesmo vetor}, mas sendo
		representado como combinação linear dos vetores da nova base.
		
		Depois dessa explicação, pode-se notar que a matriz chave da Cifra de Hill
		nada mais é que uma matriz T (transformação), e que ela (a chave) muda a base
		de cada um dos vetores que estão na mensagem. \emph{Isso} constitui a
		encriptação realizada pela Cifra de Hill. Na decriptação apenas se usa
		$K^{-1} = T^{-1} = M_B$, que é a própria matriz contendo nas colunas os
		vetores que formam a base do ``espaço vetorial encriptado''.
	
	\section{Exemplo passo-a-passo}
		Desejamos encriptar o texto ``GEOMETRIA'' usando a Cifra de Hill.
		Primeiramente estabelecemos a função já mencionada entre as letras do 
		alfabeto e números inteiros.
		
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
        	\hline
        	a & b & c & d & e & f & g & h & i & j & k & l & m  \\ \hline
        	0 & 5 & 16& 2 & 9 & 22& 15& 13& 6 & 8 & 20& 3 & 10 \\ \hline
        	\hline
        	n & o & p & q & r & s & t & u & v & w & x & y & z \\ \hline
        	17& 21& 1 & 24& 18& 25& 4 & 11& 19& 12& 7 & 23& 14 \\
        	\hline
        \end{tabular}
		
		Dividimos então o texto em blocos de n componentes (no nosso caso 3). Ficamos
		então com os vetores do texto original (vetores no $\mathbb{R}^3$). GEO =
		(6,4,14); MET = (12,4,19); RIA = (17,8,0). Escolhemos (aleatóriamente,
		com distribuição uniforme) uma matriz quadrada inversível de ordem n para ser
		a \emph{chave} da cifra. Essa matriz chave é aqui representada por K.
		
		\[ 
			K = \begin{bmatrix}
                	1 & 1 & 2 \\
                	2 & 1 & 3 \\
                	0 & 2 & 1 \\
                \end{bmatrix} 
		\]
		
		Considerando os vetores como colunas (matrizes $n \times 1$) fazemos
		então a multiplicação da matriz K por cada um dos vetores do texto: Sendo
		$\vec{v}_1 = (15,9,21)$, $\vec{v}_2 = (10,9,4)$, $\vec{v}_3 = (18,6,0)$,
		temos:
		\[
			K \cdot \vec{v}_1 = (66,102,39) \quad
			K \cdot \vec{v}_2 = (27,41,22) \quad
			K \cdot \vec{v}_3 = (24,42,12) 
		\]
		
		Agora devemos tirar módulo 26 desses vetores resultantes, obtendo assim:
		\begin{align*}
			& \vec{e}_1 = (66,102,39) \bmod 26 = (14,24,13) \\
			& \vec{e}_2 = (27,41,22) \bmod 26 = (1,15,22) \\
			& \vec{e}_3 = (24,42,12)  \bmod 26 = (24,16,12)
		\end{align*}

		Ao fim do da encriptação, obtemos (14,24,13) = ZQH; (1,15,22) = PGF
		e (24,16,12) = QCW. O nosso texto encriptado então é ``ZQHPGFQCW''. (Note que
		no texto original GEOMETRIA tínhamos duas letras E, mas no texto encriptado o
		E é substituído por letras diferentes, Q e G. Isso aumenta a segurança de uma
		cifra.)
		
		Para decriptar o texto ``ZQWPGFQCW'' basta seguir o mesmo caminho, mas usando
		agora a inversa da matriz chave. Os vetores voltam a serem representados na
		base usual.
		\[
			K^{-1} \cdot \vec{e}_1 = (15,9,-5) \quad
			K^{-1} \cdot \vec{e}_2 = (62,35,-48) \quad
			K^{-1} \cdot \vec{e}_3 = (-60,-20,52) 
		\]
		
		Tirando o módulo 26 como na encriptação, temos (15,9,21) = GEO; (10,9,4) =
		MET e (18,6,0) = RIA. Nosso texto secreto ``GEOMETRIA'' de volta!
		
		
