Criptografia

    O estudo da codificação e decodificação de mensagens secretas é denominado Criptografia. Os códigos secretos foram bastante utilizados nas guerras, para transmitir mensagens sem que o inimigo conseguisse compreendê-las. Hoje em dia há um grande interesse no assunto, devido a necessidade de se transmitir informações privadas em vias públicas de comunicação, como a internet.
    As cifras são os códigos usados para transformar um texto comum em um texto cifrado. O processo de converter um texto comum em cifrado é chamado cifrar ou codificar, e o processo inverso é chamado decifrar ou decodificar.
   Vamos estudar as chamadas cifras de Hill que são baseadas em transformações matriciais. Para isto, utilizaremos a aritmética modular e conceitos da Álgebra Linear, mais especificamente: matrizes, eliminação Gaussiana, dependência linear e transformações lineares.

---

    Definição: Dados um número inteiro positivo $m$ e dois inteiros $a$ e $b$ quaisquer, dizemos que $a$ é equivalente a $b$ módulo $$m, e escrevemos:

$$a = b\;\;(mod\; m)$$
se $a-b$ é um múltiplo inteiro de $m$.

    Dado um módulo $m$, qualquer inteiro $a$ é equivalente, módulo $m$, a um dos inteiros do conjunto:

$$Z_m = \left\lbrace 0, 1, 2, ..., m-1\right\rbrace$$
denominado conjunto dos resíduos de $a$ módulo $m$.

    Teorema: Dados um inteiro $a$ e um módulo $m$. Seja R o resto da divisão de $|a|$ por $m$. Então, o resíduo $r$ de $a$ módulo $m$ é dado por:

$$r = \left\lbrace \begin{array}{lcl} R \;& se & a\geq0\\ m-R \;& se & a < 0 \;\; e \;\;R \neq 0\\ 0 \;& se & a<0 \;\; e \;\;R = 0 \end{array} \right.$$
    Definição: Dado um número $a$ em $Z_m$. Dizemos que $a^{-1} \in Z_m$ é o inverso multiplicativo de $a$ módulo $m$ se a $a^{-1} = a^{-1} a = 1\; (mod\;m)$.

    Podemos mostrar que se $a$ e $m$ não têm fatores primos comuns, então $a$ tem um único inverso multiplicativo módulo $m$. E se $a$ e $m$ têm fatores primos comuns, então $a$ não possui inverso multiplicativo módulo $m$. Além disso, se $m$ for primo, então todo $a \in Z_m$ tem único inverso multiplicativo em $Z_m$.
    Com estas definições e resultados, podemos operar com os elementos de $Z_m$, no que denominamos aritmética modular, que utilizaremos mais adiante para estudar a codificação e decodificação das cifras de Hill.

    Exemplo 1: $4 = 0\;(mod\;2)$, pois $4 - 0 = 4$ é um múltiplo inteiro de $2$.

    Exemplo 2: $-2 = 24\; (mod\; 26)$, pois $-2-24 = -26$ é um múltiplo inteiro de $26$.

    Exemplo 3: O resíduo módulo $26$ de $103$ é $25$.
        Dividindo $|103| = 103$ por $26$, obtemos um resto R = 25, ou seja, $r = 25$. Assim, $103 = 25\; (mod\;26)$.

    Exemplo 4: O resíduo módulo $26$ de $-64$ é $14$.
        Dividindo $|-64| = 64$ por $26$, obtemos um resto R = 12. Como $-64 < 0$, temos, $r = 26 - 12 = 14$. Assim, $-64 = 14\;(mod\;26)$.

    Exemplo 5: $1+1 = 0\;(mod\;2)$.
      Na aritmética comum, temos $1+1 = 2$. Mas dividindo $2$ por $2$, obtemos resto $0$, ou seja, $2 = 0 \;(mod\;2)$. Assim, na aritmética módulo $2$, temos $1+1 = 0\;(mod\;2)$.

    Exemplo 6:  $15$ é inverso multiplicativo de $7$ módulo $26$, pois $7\times15 = 105 = 1\;(mod\;26)$.

    Voltar ao Topo.

---

    Uma maneira de tornar o código mais difícil de ser quebrado é dividir o texto em grupos e criptografar o texto comum por grupos. 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.

    Vamos numerar cada letra do alfabeto de $1$ a $25$, e ao Z daremos o valor $0$. Cada letra estará bem determinada por seu número correspondente.

$$\begin{array}{c} 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 \\ 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 & 0 \end{array$$
    No caso mais simples da cifra de Hill, vamos dividir o texto comum em pares de letras e codificá-lo através do seguinte procedimento:

$1^{\underline{o}}$) Escolhemos uma matriz $2 \times 2$ com entradas inteiras:

$$A = \left[ \begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]$$
$A$ é denominada matriz codificadora.

$2^{\underline{o}}$) 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^{\underline{o}}$) Substituímos cada letra por seu número correspondente. Escrevemos cada par de números $p_1$ e $p_2$ como um vetor coluna:

$$p = \left[ \begin{array}{l} p_1 \\ p_2 \end{array}\right]$$
Obtemos então os vetores $q = Ap$ cifrados.

$4^{\underline{o}}$) 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 $Z_{26}$, ou seja, não esteja entre $0$ e $25$, obtemos o seu equivalente módulo $26$, que esteja em $Z_{26}$, 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 no $1^{\underline {o}}$ passo uma matriz codificadora $n \times n$.

    Exemplo: Vamos codificar o seguinte texto: ALGEBRA LINEAR, utilizando uma $2$-cifra de Hill, com a seguinte matriz codificadora:

$$A = \left[ \begin{array}{ll} 1 & 2 \\ 3 & 5 \end{array} \right]$$
    Primeiramente separamos o texto em pares de letras, da forma:

$$AL \;\; GE \;\; BR \;\; AL \;\; IN \;\; EA \;\; R$$
    Como temos um número ímpar de letras, completamos o último par com uma letra fictícia qualquer:

$$AL \;\; GE \;\; BR \;\; AL \;\; IN \;\; EA \;\; RZ$$
    Substituímos então cada letra por seu correspondente numérico:

$$1\;12 \;\;\; 7\;5 \;\;\; 2\;18 \;\;\; 1\;12 \;\;\; 9\;14 \;\;\; 5\;1 \;\;\; 18\;0$$
    Escrevemos cada par de números como um vetor coluna $p$ e obtemos os vetores cifrados $q$, da forma: $q = Ap$. Para o par AL, teremos:

$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \; \left[ \begin{array}{c} 1 \\ 12 \end{array}\right] = \left[ \begin{array}{c} 25 \\ 63 \end{array}\right]$$
   Neste caso, o número $63$ não está entre $0$ e $25$ e não podemos substituí-lo por sua letra correspondente. Assim, obtemos o seu equivalente módulo $26$, que esteja em $Z_{26}$.
    Dividindo $|63| = 63$ por $26$, obtemos um resto R = 11, assim, $63 = 11\;(mod\;26)$. Dessa forma, obtemos o vetor cifrado do par de letras AL:

$$q = \left[ \begin{array}{c} 25 \\ 63 \end{array}\right] = \left[ \begin{array}{c} 25 \\ 11 \end{array}\right] \; (mod\; 26)$$
    Substituindo pelas letras correspondentes, obtemos o par cifrado: YK. Fazendo o mesmo para os demais pares de letras, teremos:

$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \;\left[ \begin{array}{c} 7 \\ 5 \end{array}\right] = \left[ \begin{array}{c} 17 \\ 46 \end{array}\right] = \left[ \begin{array}{c} 17 \\ 20 \end{array}\right]\; (mod\; 26)$$
$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \; \left[ \begin{array}{c} 2 \\ 18 \end{array}\right] = \left[ \begin{array}{c} 38 \\ 96 \end{array}\right] = \left[ \begin{array}{c} 12 \\ 18 \end{array}\right]\; (mod\; 26)$$
$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \; \left[ \begin{array}{c} 1 \\ 12 \end{array}\right] = \left[ \begin{array}{c} 25 \\ 63 \end{array}\right] = \left[ \begin{array}{c} 25 \\ 11 \end{array}\right]\; (mod\; 26)$$
$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \; \left[ \begin{array}{c} 9 \\ 14 \end{array}\right] = \left[ \begin{array}{c} 37 \\ 97 \end{array}\right] = \left[ \begin{array}{c} 11 \\ 19 \end{array}\right]\; (mod\; 26)$$
$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \; \left[ \begin{array}{c} 5 \\ 1 \end{array}\right] = \left[ \begin{array}{c} 7 \\ 20 \end{array}\right] = \left[ \begin{array}{c} 7 \\ 20 \end{array}\right]\; (mod\; 26)$$
$$\left[ \begin{array}{cc} 1 & 2 \\ 3 & 5 \end{array} \right] \; \left[ \begin{array}{c} 18 \\ 0 \end{array}\right] = \left[ \begin{array}{c} 18 \\ 54 \end{array}\right] = \left[ \begin{array}{c} 18 \\ 2 \end{array}\right]\; (mod\; 26)$$
    Portanto, obtemos os respectivos pares de letras cifrados: $QT, \;\; LR, \;\; YK, \;\; KS, \;\; GT, \;\; RB$. Assim, juntando todos os pares de texto codificados, teremos a mensagem codificada:

$$YWQTLRYKKSGTRB$$
    Voltar ao Topo.

---

    Para conseguir decodificar uma cifra de Hill, iremos usar a inversa módulo $26$ da matriz $A$ codificadora. Usamos o número $26$ pois estamos trabalhando apenas com as $26$ letras do alfabeto, caso se queira utilizar acentuações e pontuação, por exemplo, seria necessário trabalhar com outro módulo e seguir os mesmos passos.

    Definição: Seja $m$ um inteiro positivo. Dizemos que uma matriz $A$, com entradas em $Z_m$, é invertível se existir uma matriz $B$, com entradas em $Z_m$, tal que:
$$AB = BA = I\; (mod\;m)$$
$B$ é a matriz inversa de $A$ módulo $m$, que denotamos por $A^{-1}\; (mod\;m)$. Dizer que uma matriz está em módulo $m$ significa que cada uma das suas entradas está em módulo $m$.

  Teorema: Uma matriz quadrada $A$ com entradas em $Z_m$ possui inversa módulo $m$, se e somente se, $det(A)\;(mod\;m)$ possui inverso multiplicativo módulo $m$.

    Com isso, podemos determinar quais as matrizes quadradas que são invertíveis em $Z_m$, para qualquer $m$. Isso nos ajuda pois ao codificar algum texto é preciso que a pessoa que receba a mensagem seja capaz de decifrá-la, caso contrário o texto ficaria para sempre codificado e não transmitiria nenhuma informação. Para podermos decifrar o código, no primeiro passo da codificação precisamos escolher uma matriz $A$ que seja invertível.

    Teorema: Seja$\mathrm{<br>}$
$$A = \left[ \begin{array}{rr} a & b \\ c & d \end{array} \right]$$uma matriz $2 \times 2$ com entradas em $Z_m$, invertível módulo $m$, isto é, $det(A)\; (mod\; m)$ possui inverso multiplicativo módulo $m$. Então a inversa de $A$ módulo $m$ é:

$$A^{-1} = det(A)^{-1} \; \left[ \begin{array}{rr} d & -b \\ -c & a \end{array} \right]$$
Onde $det(A)^{-1}$ é o inverso multiplicativo módulo $m$ do determinante de $A$.

    Esse teorema nos dá um meio para calcular a inversa módulo $m$ de uma matriz $2 \times 2$, que para os propósitos desta aplicação é suficiente. O cálculo de inversas de matrizes de ordem maior envolveria outros cálculos e definições, que não faremos aqui.

    Exemplo: Calcule a inversa módulo $26$ da matriz:
$$A = \left[ \begin{array}{ll} 1 & 2 \\ 3 & 5 \end{array} \right]$$
    Temos que $det(A) = 5 - 6 = -1 = 25\;(mod\;26)$. O determinante de $A$ módulo $26$, portanto, possui inverso multiplicativo módulo $26$. Temos: $25\times 25 = 625 = 1\;(mod\;26)$. Logo, $25$ é o inverso multiplicativo de $25$ módulo $26$. Assim, a inversa de A módulo 26 é dada por:

$$A^{-1} = 25 \; \left[ \begin{array}{rr} 5 & -2 \\ -3 & 1 \end{array} \right] = \left[ \begin{array}{rr} 125 & -50 \\ -75 & 25 \end{array} \right] = \left[ \begin{array}{cc} 21 & 2 \\ 3 & 25 \end{array} \right]\;(mod\;26)$$
    Voltar ao Topo.

---

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

$$A = \left[ \begin{array}{ll} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right]$$
que 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 = Ap$$
    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: Suponha que recebemos a mensagem: LQPQEECWBY, que foi criptografada por uma $2$-cifra de Hill, com a seguinte matriz codificadora:

$$A = \left[ \begin{array}{ll} 3 & 0 \\ 2 & 1 \end{array} \right]$$
Vamos obter a mensagem decodificada.

    Para isso, vamos obter a matriz inversa módulo $26$ da matriz $A$. Efetuando os cálculos, temos:

$$A^{-1} = \left[ \begin{array}{ll} 9 & 0 \\ 8 & 1 \end{array} \right]\; (mod\; 26)$$
    Separamos o texto cifrado em pares de letras, da forma:

$$LQ\;\; PQ\;\; EE\;\; CW\;\; BY$$
    E substituindo cada letra por seu correspondente numérico, teremos:

$$12\;17 \;\;\;\; 16\;17 \;\;\;\; 5\;5 \;\;\;\; 3\;23 \;\;\;\; 2\;25$$
    Escrevemos cada par de números como um vetor $q$ e obtemos os correspondentes vetores de texto comum $p$ em módulo $26$, da forma: $p = A^{-1}q$. Teremos:

$$\left[ \begin{array}{cc} 9 & 0 \\ 8 & 1 \end{array} \right] \; \left[ \begin{array}{c} 12\\ 17 \end{array} \right] = \left[ \begin{array}{c} 108 \\ 113 \end{array} \right] = \left[ \begin{array}{r} 4 \\ 9 \end{array} \right]\; (mod\;26)$$
$$\left[ \begin{array}{cc} 9 & 0 \\ 8 & 1 \end{array} \right] \; \left[ \begin{array}{c} 12\\ 17 \end{array} \right] = \left[ \begin{array}{c} 108 \\ 113 \end{array} \right] = \left[ \begin{array}{r} 4 \\ 9 \end{array} \right]\; (mod\;26)$$
$$\left[ \begin{array}{cc} 9 & 0 \\ 8 & 1 \end{array} \right] \; \left[ \begin{array}{c} 16\\ 17 \end{array} \right] = \left[ \begin{array}{c} 144 \\ 145 \end{array} \right] = \left[ \begin{array}{r} 14 \\ 15 \end{array} \right]\; (mod\;26)$$
$$\left[ \begin{array}{cc} 9 & 0 \\ 8 & 1 \end{array} \right] \; \left[ \begin{array}{c} 5\\ 5 \end{array} \right] = \left[ \begin{array}{c} 45 \\ 45 \end{array} \right] = \left[ \begin{array}{r} 19 \\ 19 \end{array} \right]\; (mod\;26)$$
$$\left[ \begin{array}{cc} 9 & 0 \\ 8 & 1 \end{array} \right] \; \left[ \begin{array}{c} 3\\ 23 \end{array} \right] = \left[ \begin{array}{c} 27 \\ 47 \end{array} \right] = \left[ \begin{array}{c} 1 \\ 21 \end{array} \right]\; (mod\;26)$$
$$\left[ \begin{array}{cc} 9 & 0 \\ 8 & 1 \end{array} \right] \; \left[ \begin{array}{c} 2\\ 25 \end{array} \right] = \left[ \begin{array}{c} 18 \\ 41 \end{array} \right] = \left[ \begin{array}{r} 18 \\ 15 \end{array} \right]\; (mod\;26)$$
    Assim, substituindo cada número, dos pares de vetores $p$ obtidos, por suas letras correspondentes, obtemos os pares de letras de texto comum:

$$DI\;\; NO \;\; SS \;\; AU \;\; RO$$
    Juntando os pares de letras, descobrimos que a palavra codificada era: DINOSSAURO.

---

   Suponha agora, que recebemos um texto cifrado e sabemos uma parte do texto decodificado. Vamos utilizar conceitos da Álgebra Linear e eliminação Gaussiana para obter a matriz decodificadora $A^{-1}$. Da Álgebra Linear, sabemos que uma transformação fica bem determinada por seu efeito nos elementos de uma base. Com esse princípio, teremos o seguinte teorema:

    Teorema: Sejam $p_1, ..., p_n$ vetores de texto comum, linearmente independentes, e $q_1, ..., q_n$ os correspondentes vetores cifrados de uma
$n$-cifra de Hill. Seja:

$$P = \left[ \begin{array}{c} p_1^t \\ \vdots \\ p_n^t \end{array} \right]$$
a matriz $n \times n$ de vetores linha $p_1, ..., p_n$ transpostos. E seja:

$$Q = \left[ \begin{array}{c} q_1^t \\ \vdots \\ q_n^t \end{array} \right]$$
a matriz $n \times n$ de vetores linha $q_1, ..., q_n$ transpostos. Então, as operações elementares de linha que reduzem $Q$ a matriz identidade $I_n$, transforma $P$ na matriz $(A^{-1})^t$, sendo $A^{-1}$ a matriz decodificadora.

   Assim, para encontrar a transposta da matriz decodificadora $A^{-1}$, basta sabermos uma sequência de operações elementares de linha que reduzem $Q$ a $I_n$ e aplicarmos essas operações na matriz $P$.

    Exemplo 1: Suponha que recebemos a mensagem criptografada BEWIXSMFNC e sabemos apenas que o texto original começa com a palavra MOVA. Vamos obter a mensagem decodificada.

    Separamos o texto comum conhecido em pares de letras e substituímos por seu equivalente numérico:

$$MO \;\;\;\$$$$13\;15 \;\;\;\;\; 22\;1$$
    Fazemos o mesmo com o correspondente texto cifrado:

$$BE \;\;\;\; WI$$$$2\;5 \;\;\;\;\; 23\;9$$
    De modo que os vetores p de texto comum e seus correspondentes vetores cifrados $q$ são:

$$p_1 = \left[ \begin{array}{c} 13 \\ 15 \end{array} \right], \;\;\;\; q_1 = \left[ \begin{array}{c} 2 \\ 5 \end{array} \right]$$
$$p_2 = \left[ \begin{array}{c} 22 \\ 1 \end{array} \right], \;\;\;\; q_2 = \left[ \begin{array}{c} 23 \\ 9 \end{array} \right]$$

    Queremos reduzir a matriz
$$Q = \left[ \begin{array}{c} q_1^t \\ q_2^t \end{array} \right] = \left[ \begin{array}{cc} 2 & 5 \\ 23 & 9 \end{array} \right]$$
a matriz identidade de ordem $2$, aplicando operações elementares de linhas, e simultaneamente, aplicar essas mesmas operações na matriz

$$P = \left[ \begin{array}{c} p_1^t \\ p_2^t \end{array} \right] = \left[ \begin{array}{cc} 13 & 15 \\ 22 & 1 \end{array} \right]$$obtendo assim a matriz $(A^{-1})^t$. Isso pode ser feito juntando $P$ à direita de $Q$ e aplicando as operações elementares de linhas na matriz resultante $[Q|P]$ até que o lado esquerdo seja reduzido a matriz $I_2$. A matriz no lado direito será a que queremos.

$$\left[ \begin{array}{cccc} 2 & 5 & 13 & 15 \\ 23 & 9 & 22 & 1 \end{array} \right] \rightarrow l_1 \leftrightarrow l_2 \rightarrow \left[ \begin{array}{cccc} 23 & 9 & 22 & 1 \\ 2 & 5 & 13 & 15 \end{array} \right] \rightarrow multiplicamos\; a \; linha \; 1 \; por \; 23^{-1} = 17\;(mod\;26) \rightarrow$$
$$\rightarrow \left[ \begin{array}{cccc} 1 & 153 & 374 & 17 \\ 2 & 5 & 13 & 15 \end{array} \right] \rightarrow substituímos \; cada \; entrada \; da \; matriz \; por \; seu \; equivalente \; módulo \; 26 \rightarrow$$
$$\rightarrow \left[ \begin{array}{cccc} 1 & 23 & 10 & 17 \\ 2 & 5 & 13 & 15 \end{array} \right] \rightarrow l_2 \leftrightarrow l_2 - 2l_1 \rightarrow \left[ \begin{array}{cccc} 1 & 23 & 10 & 17 \\ 0 & -41 & -7 & -19 \end{array} \right] \rightarrow mod \; 26 \rightarrow \left[ \begin{array}{cccc} 1 & 23 & 10 & 17 \\ 0 & 11 & 19 & 7 \end{array} \right] \rightarrow$$
$$\rightarrow multiplicamos \; a \; linha \; 2 \; por \; 11^{-1} = 19\;(mod\;26) \rightarrow \left[ \begin{array}{cccc} 1 & 23 & 10 & 17 \\ 0 & 1 & 361 & 133 \end{array} \right] \rightarrow mod\; 26 \rightarrow$$ 
$$\rightarrow \left[ \begin{array}{cccc} 1 & 23 & 10 & 17 \\ 0 & 1 & 23 & 3 \end{array} \right] \rightarrow l_1 \leftrightarrow l_1 - 23l_2 \rightarrow \left[ \begin{array}{cccc} 1 & 0 & -519 & -52 \\ 0 & 1 & 23 & 3 \end{array} \right] \rightarrow mod \; 26 \rightarrow \left[ \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 23 & 3 \end{array} \right]$$
    Assim, do lado direito, obtemos a matriz transposta da matriz decodificadora, logo, temos:

$$A^{-1} = \left[ \begin{array}{cc} 1 & 23 \\ 0 & 3 \end{array} \right] \; (mod\; 26)$$
    Agora, para decifrar a mensagem, separamos o texto criptografado em pares de letras e substituímos cada letra por seu número correspondente:

$$BE \;\;\; WI \;\;\; XS \;\;\; MF \;\;\; NC$$$$2\;5 \;\;\; 23\;9 \;\;\; 24\;19 \;\;\; 13\;6 \;\;\; 14\;3$$
    Escrevemos cada par de números como um vetor $q$ e obtemos os correspondentes vetores de texto comum $p$ em módulo $26$. Precisamos fazer isso apenas para a parte do texto que ainda não conhecemos:

$$\left[ \begin{array}{cc} 1 & 23 \\ 0 & 3 \end{array} \right] \; \left[ \begin{array}{c} 24\\ 19 \end{array} \right] = \left[ \begin{array}{c} 461 \\ 57 \end{array} \right] = \left[ \begin{array}{c} 19 \\ 5 \end{array} \right]\; (mod\;26)$$$$\left[ \begin{array}{cc} 1 & 23 \\ 0 & 3 \end{array} \right] \;\left[ \begin{array}{c} 13\\ 6 \end{array} \right] = \left[ \begin{array}{c} 151 \\ 18 \end{array} \right] = \left[ \begin{array}{c} 21 \\ 18 \end{array} \right]\; (mod\;26)$$$$\left[ \begin{array}{cc} 1 & 23 \\ 0 & 3 \end{array} \right] \; \left[ \begin{array}{c} 14\\ 3 \end{array} \right] = \left[ \begin{array}{c} 83 \\ 9 \end{array} \right] = \left[ \begin{array}{c} 5 \\ 9 \end{array} \right]\; (mod\;26)$$
    Assim, substituindo os pares de números pelas letras correspondentes, obtemos o restante do texto: $SE\;\;UR\;\;EI$. Logo, conseguimos decifrar a mensagem: $MOVA \;\; SEU \;\; REI$.

   Exemplo 2: Suponha que recebemos um texto que foi criptografado com uma $3$-cifra de Hill e sabemos que a palavra criptografada FIKYRVMWG, corresponde a palavra de texto comum UNICORNIO. Vamos obter a matriz inversa $A^{-1}$ da matriz codificadora A, módulo $26$, com a qual podemos decifrar o restante do texto.

    Como o texto foi criptografado por uma $3$-cifra de Hill, vamos separar o texto comum conhecido em grupos de $3$ letras e substituí-las por seus equivalentes numéricos:

$$UNI \;\;\;\;\;\; COR \;\;\;\;\;\; NIO$$$$21\;14\;9 \;\;\;\; 3\;15\;18 \;\;\;\; 14\;9\;15$$
    Fazemos o mesmo com o correspondente texto cifrado:

$$FIK \;\;\;\;\;\; YRV \;\;\;\;\;\; MWG$$$$6\;9\;11 \;\;\;\; 25\;18\;22 \;\;\;\; 13\;23\;7$$
    De modo que, os vetores $p$ de texto comum e seus correspondentes vetores cifrados $q$ são:

$$p_1 = \left[ \begin{array}{c} 21 \\ 14 \\ 9 \end{array} \right], \;\;\;\; q_1 = \left[ \begin{array}{c} 6 \\ 9 \\ 11 \end{array} \right]$$
$$p_2 = \left[ \begin{array}{c} 3 \\ 15 \\ 18 \end{array} \right], \;\;\;\; q_2 = \left[ \begin{array}{c} 25 \\ 18 \\ 22 \end{array} \right]$$
$$p_3 = \left[ \begin{array}{c} 14 \\ 9 \\ 15 \end{array} \right], \;\;\;\; q_3 = \left[ \begin{array}{c} 13 \\ 23 \\ 7 \end{array} \right]$$
    Queremos reduzir a matriz $$Q = \left[ \begin{array}{c} q_1^t \\ q_2^t \\ q_3^t \end{array} \right]$$
a matriz identidade de ordem $3$, aplicando operações elementares de linhas, e simultaneamente, aplicar as mesmas operações na matriz

$$P = \left[ \begin{array}{c} p_1^t \\ p_2^t \\ p_3^t \end{array} \right]$$obtendo a matriz $(A^{-1})^t$. Para isso, fazemos do mesmo modo que no exemplo anterior e obtemos:

$$\left[ \begin{array}{cccccc} 6 & 9 & 11 & 21 & 4 & 9 \\ 25 & 18 & 22 & 3 & 15 & 18 \\ 13 & 23 & 7 & 14 & 9 & 15 \end{array} \right] \longleftrightarrow \left[ \begin{array}{cccccc} 1 & 0 & 0 & 9 & 17 & 18 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 8 & 18 & 17 \end{array} \right]$$
    Assim, a matriz inversa da matriz codificadora $A$, módulo $26$ é:

$$A^{-1}\; (mod\; 26) = \left[ \begin{array}{ccc} 9 & 1 & 8 \\ 17 & 0 & 18 \\ 18 & 0 & 17 \end{array} \right]$$
    Com esta matriz, podemos decifrar o restante do texto. Observe que quando utilizamos uma $3$-cifra de Hill para a codificação, precisamos conhecer pelo menos $9$ letras de uma palavra de texto comum para conseguirmos decodificá-lo. Quanto maior a dimensão da matriz codificadora $A$, mais difícil se tornam os cálculos e mais segura se torna a mensagem codificada.


    Voltar ao Topo.