Cifra de Hill

Cifra de Hill é um tipo de cifra de substituição baseado em álgebra linear usado para codificação de mensagens. Foi inventada pelo matemático norte americano Lester S. Hill em 1929.

Máquina de Cifra de Hill

Uma mensagem codificada com uma matriz NxN é chamada de "N-Cifra de Hill". Logo, uma mensagem codificada com uma matriz 2x2 é chamada "2-Cifra de Hill".

Procedimento

Um sistema poligráfico é um sistema de criptografia no qual o texto é separado em conjuntos de n letras, cada qual é substituído por um conjunto de n letras cifradas. As cifras de Hill são uma classe de sistemas poligráficos, baseados em transformações matriciais.

CODIFICAÇÃO:

Primeiro converte-se as letras em números, depois agrupa-se os números n a n e multiplica-se cada grupo por uma matriz quadrada de ordem invertível (ou seja determinante diferente de 0). Os números resultantes são novamente passados para letras, e assim tem-se a mensagem codificada.

Caso algum resultado da multiplicação seja um número maior que o número de letras do alfabeto utilizado, então deve-se utilizar o resto desse número pelo número de letras do alfabeto.

Numerar cada letra do alfabeto de 1  a 25 e daremos o valor de 0 a letra A. Cada letra é representada por um número módulo 26. Embora esta não seja uma característica essencial da cifra, este esquema simples é frequentemente usado: estará bem determinada por seu número correspondente.

letras	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Nº	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

No caso mais simples da cifra de Hill, vamos dividir o texto comum em pares de letras e codificá-lo através do seguintes procedimentos:

1º Escolhemos uma matriz 2 X 2 com entradas inteiras: onde A matriz é a matriz codificadora

${\mathsf {A=}}{\begin{bmatrix}a11&a12\\a21&a22\end{bmatrix}}$

2º Dividimos o texto que queremos codificar em pares de letras. Caso o texto tenha um número ímpar de letras, adicionamos no final uma letra fictícia.

3º Substituímos cada letra por seu número correspondente. Escrevemos cada par de números p1 e p2 como um vetor coluna

$p={\binom {p1}{p2}}$

obtemos então os valores q=ap cifrados.

4º Por fim, substituímos cada número dos vetores cifrados q , por suas letras equivalentes. Caso algum número do vetor q não pertença ao conjunto Z26 , ou seja, não esteja entre 0  e 25 , obtemos o seu equivalente módulo 26 , que esteja em Z26, para podermos substituí-los por suas letras correspondentes. Assim, juntando as letras de cada par cifrado, teremos o texto codificado.

Nesse caso mais simples, no qual separamos o texto comum em pares de letras, teremos uma 2-cifra de Hill. Em casos mais gerais de uma n-cifra de Hill, basta separarmos o texto em grupos de n  letras e escolher 1º no  passo uma matriz codificadora n x m .

EXEMPLO: vamos codificar a palavra LINEAR utilizando 2-cifra de Hill com a seguinte matriz codificadora:

A = ${\begin{bmatrix}1&2\\3&5\end{bmatrix}}$

Primeiramente separamos o texto em pares de letras, da forma:

L	I		N	E		A	R

Substituímos então cada letra por seu correspondente numero

11	8		13	4		0	17

Escrevemos cada par de números como um vetor coluna p  e obtemos os vetores cifrados ,q da forma:q=Ap . Para o par LI, teremos: ${\begin{bmatrix}1&2\\3&5\end{bmatrix}}$. ${\begin{bmatrix}11\\8\end{bmatrix}}$= ${\begin{bmatrix}27\\73\end{bmatrix}}$= ${\begin{bmatrix}1\\21\end{bmatrix}}$${\pmod {26}}$

Para o par NE, teremos: ${\begin{bmatrix}1&2\\3&5\end{bmatrix}}$.${\begin{bmatrix}13\\4\end{bmatrix}}$= ${\begin{vmatrix}21\\59\end{vmatrix}}$ = ${\begin{bmatrix}21\\7\end{bmatrix}}$ ${\pmod {26}}$

Para o par AR, teremos: ${\begin{bmatrix}1&2\\3&5\end{bmatrix}}$.${\begin{bmatrix}0\\17\end{bmatrix}}$ = ${\begin{bmatrix}17\\85\end{bmatrix}}$ = ${\begin{bmatrix}17\\7\end{bmatrix}}$${\pmod {26}}$

Portanto, obtemos os respectivos pares de letras cifrados : BV , VH , RH Assim, juntando todos os pares de texto codificados, teremos a mensagem codificada: BVVHRH.

DECODIFICAÇÃO:

Para decodificar a mensagem basta aplicar o mesmo processo, porém utilizando a matriz inversa. Por isso que deve-se usar apenas matrizes invertíveis.

Supondo que recebemos um texto cifrado e conhecemos a matriz codificadora de uma 2-cifra de Hill

$A={\begin{vmatrix}a11&a12\\a21&a22\end{vmatrix}}$

Na qual deve ser invertível módulo 26

Se p  é um vetor com os correspondentes numéricos de um par de letras de texto comum, sabemos pela regra de codificação que os vetores q , de correspondentes numéricos dos pares de letras cifradas, são obtidos da forma:

q= p

Assim, podemos dividir o texto cifrado que conhecemos em pares de letras, substituí-los por seus correspondentes numéricos, escrever cada vetor coluna q  e por fim obter os correspondentes vetores p  da forma:

p = $A^{-1}$ q

Onde, nesse caso, $A^{-1}$ é a inversa módulo 26  de A . Substituindo cada número dos vetores p  por suas letras correspondentes, conseguimos decifrar qual é a mensagem.

EXEMPLO: Vamos decodificar a palavra MTUYFM utilizando a cifra de Hill com a seguinte matriz:

A= ${\begin{bmatrix}7&5\\18&17\end{bmatrix}}$

p= $A^{-1}$.q ${\pmod {26}}$

$A^{-1}$=${\frac {1}{A}}adj(A)$

A = ${\begin{bmatrix}7&5\\18&17\end{bmatrix}}$ = 11 -90 =29 ${\pmod {26}}$ = 3

${\frac {1}{3}}{\begin{bmatrix}17&-5\\-18&7\end{bmatrix}}$

adj $A^{-1}=3^{-1}{\begin{bmatrix}17&-5+26\\-18+26&7\end{bmatrix}}{\pmod {26}}$

$A^{-1}$ = 9${\begin{bmatrix}17&21\\8&7\end{bmatrix}}={\begin{bmatrix}153&189\\72&63\end{bmatrix}}{\pmod {26}}$

$A^{-1}$ = ${\begin{bmatrix}23&7\\20&11\end{bmatrix}}$

p= $A^{-1}.q{\pmod {26}}$

q= MTUYFM

Primeiramente separamos o texto em pares de letras, da forma:

M	T		U	Y		F	M

Substituímos então cada letra por seu correspondente numero:

12	19		20	24		5	12

Escrevemos cada par de números como um vetor coluna :

Para o par MT, teremos: ${\begin{bmatrix}23&7\\20&11\end{bmatrix}}$.${\begin{bmatrix}12&\\19&\end{bmatrix}}$= ${\begin{bmatrix}409&\\449&\end{bmatrix}}{\pmod {26}}$ = ${\begin{bmatrix}19&\\7&\end{bmatrix}}$= ${\begin{bmatrix}T&\\H&\end{bmatrix}}$

Para o par UY, teremos: ${\begin{bmatrix}23&7\\20&11\end{bmatrix}}.{\begin{bmatrix}20&\\24&\end{bmatrix}}$ = ${\begin{bmatrix}628&\\664&\end{bmatrix}}{\pmod {26}}={\begin{bmatrix}4&\\14&\end{bmatrix}}$= ${\begin{bmatrix}E&\\O&\end{bmatrix}}$

Para o par FM , teremos: ${\begin{bmatrix}23&7\\20&11\end{bmatrix}}.{\begin{bmatrix}5&\\12&\end{bmatrix}}={\begin{bmatrix}199&\\232&\end{bmatrix}}$${\pmod {26}}$ = ${\begin{bmatrix}17&\\24&\end{bmatrix}}={\begin{bmatrix}R&\\Y&\end{bmatrix}}$

Portanto, obtemos os respectivos pares de letras cifrados : TH , EO , RY Assim, juntando todos os pares de texto teremos a mensagem decodificada: THEORY.