Criptografia básica com Matrizes

Definimos uma matriz como sendo um tabela ou arranjo que simplificam e por vezes representam sistemas lineares. São ferramentas muito importantes para quem deseja seguir as carreiras de Ciências Exatas. Com o intuíto de motivar um pouquinho o estudo de matrizes, principalmente se você é estudante de ensino médio, irei mostrar à você como desenvolver uma criptografia básica com matrizes e implementar em Julia Lang, uma linguagem de programação de alto nível que está encantando os matemáticos aplicados.

Requisitos: Multiplicação Matricial e Matriz Inversa.

Basicamente, teremos o trabalho de resolver um sistema linear do tipo $Ax=b$, onde iremos denominar $A=(a_{ij})_{m\times n}$ como sendo a Matriz Chave, ou seja, como o nome já diz, será a matriz que irá criptografar ou descriptografar uma mensagem. O vetor, ou matriz $x=(x_{ij})_{n\times p}$ é onde serão inserido os dados para criptografar. Ao realizarmos a multiplicação matricial $Ax$, teremos como retorno uma matriz $b=(b_{ij})_{m\ p}$ que terá a nossa mensagem criptografada. Agora, vamos supor que você recebeu uma mensagem e deseja descriptografar, você recebeu a chave e recebeu a mensagem criptografada, como descriptografar?

Note que, tudo que fizemos foi basicamente resolver uma equação $Ax=b$ onde $A$ e $x$ eram conhecidos, agora, conhecidos as matriz $A$ e $b$, como encontrar $x$ que é a mensagem descriptografada? Para quem já cursou Álgebra Linear a resposta pode parecer trivial, como esse conteúdo é voltado para um estudante do ensino médio, vamos entrar em detalhes.

Lembrando do fato de que as operações matricial formam o que chamamos de "Anel", isto é, preserva algumas operações usuais porém, nem sempre é comutativo, ou seja, nem sempre fazer $AB=BA$. Um contra exemplo disto: Basta pegar uma matriz $A=(a_{ij})_{m\times p}$ e uma matriz $B=(b_{ij})_{p\times n}$, a multiplicação $AB$ gera uma matriz $C=(c_{ij})_{m \times n}=\sum_{j=1}^{n}a_{ij}b_{jk}$, note que para se fazer uma multiplicação matricial $AB$ o número de colunas da matriz $A$ deve ser o mesmo que o número de linhas da matriz $B$. No caso, se $i\neq j$, a multiplicação $BA$ é impossível, o que já é um contra-exemplo de comutação. Outros contra-exemplos de comutação podem ser facilmente encontrados. Enfim, o que importa é que, $Ax$ por vezes é diferente de $xA$ em nosso exemplo, por isso, atento à ordem das multiplicações.

No caso, para resolvermos $Ax=b$ para $x$, multiplicamos a inversa da matriz $A$, que será denotada por $A^{-1}$ em ambos os lados. A multiplicação $AA^{-1}=A^{-1}A=I_{n}$ (se a matriz $A$ for invertível, ou seja, em termos de Álgebra Linear, não-singular). Logo, temos:

$Ax=b \therefore A^{-1}Ax=A^{-1}b \therefore I_{n}x=A^{-1}b \therefore x = A^{-1}b$

No caso, essa relação irá descriptografar a nossa mensagem. Talvez uma coisa entediante a se fazer seja inverter a matriz $A$, mas, na vida real, no dia-a-dia fora da escola, dificilmente inversões de matrizes são feitas à mão, agradecemos hoje aos computadores pela eficiência nos cálculos. Sendo assim, você pode utilizar uma linguagem de programação ou simplesmente usar uma calculadora de matriz inversa online para te auxiliar. Antes de programar, acompanhe o exemplo à seguir para entender melhor a teoria que foi desenvolvida:

Em meu exemplo, eu vou escolher a seguinte matriz para representar a chave:

$A=\left[\begin{array}{c c}1 & 2\\3 & 4\end{array}\right]$

Como eu sou uma pessoa muito criativa, irei representar $A=1$, $B=2$, $C=3$, $\cdots$ e assim por diante. Suponha que eu queira criptografar a palavra "batata", temos então, que, no modelo que prôpus, em números batata = $2\;\;\;1\;\;\;20\;\;\;1\;\;\;20\;\;\;1$. Assim, posso armazenar estes valores na matriz $x$ da seguinte forma:

$x = \left[\begin{array}{c c c}2 & 20 & 20\\1 & 1 & 1\end{array}\right]$

Agora, basta apenas fazermos a multiplicação $Ax=b$. No caso, geramos a seguinte relação:

$\left[\begin{array}{c c}1 & 2\\3 & 4\end{array}\right]\left[\begin{array}{c c c}2 & 20 & 20\\1 & 1 & 1\end{array}\right]=\left[\begin{array}{c c c}4&22&22\\10&64&64\end{array}\right]$

Que é a nossa mensagem criptografada. Logo, se quiser que alguém desvende a nossa mensagem, enviamos a matriz $b = Ax$ e a matriz chave $A$. Assim, para descriptografar, como visto na teoria, basta resolvermos para $x$ o sistema $Ax=b$, no caso, $x = A^{-1}b$. Calculando rapidamente em Julia Lang, obtemos que:

$A^{-1}=\left[\begin{array}{c c}-2 & 1\\\frac{3}{2} & -\frac{1}{2}\end{array}\right]$

Assim, temos que:

$x=\left[\begin{array}{c c}-2 & 1\\\frac{3}{2} & -\frac{1}{2}\end{array}\right]\left[\begin{array}{c c c}4&22&22\\10&64&64\end{array}\right]=\left[\begin{array}{c c c}2&20&20\\1&1&1\end{array}\right]$

Ou seja, note que de fato, ao efetuarmos a multiplicação, que $x$ satisfaz o valor que inserimos para criptografar. Bom, apesar deste modo de criptografia ser bastante simples, ainda é assim é uma criptografia difícil de se quebrar caso não tenha a chave. Levaria anos para que se possa descobrir a chave a ser descriptografada, como usamos uma "matriz chave" meio que trivial, poderia ser quebrada facilmente, mas se criásse-mos uma chave do tipo:

$A=\left[\begin{array}{c c}1023 & 2018\\8398 & 1997\end{array}\right]$

Levaria muito, mas, muito tempo para descriptografar.

Agora que já vimos a teoria e um exemplo, vamos aplicar isso com programação. No caso, irei ensinar como fazer as mesmas operações utilizando a linguagem Julia. Você pode baixar a linguagem Julia através do site oficial ou simplesmente, utilizar a interface Jupyter, que possibilita também programar em Julia online sem a necessidade de efetuar download.

Seguindo o exemplo, temos então que a Matriz $A=(a_{ij})_{2\times 2}$

A = [1 2; 3 4]
2×2 Array{Int64,2}:
 1  2
 3  4

Criamos agora a matrix $x=(x_{ij})_{2\times 3}$.

x = [2 20 20; 1 1 1]
2×3 Array{Int64,2}:
 2  20  20
 1   1   1

Resolvemos agora o sistema $Ax=b$, no caso, em Julia Lang:

B = A*x
2×3 Array{Int64,2}:
  4  22  22
 10  64  64

Pronto, agora já temos a nossa mensagem criptografada. Para descritografar, basta resolver para $x$ o sistema $Ax=b$. Em Julia Lang, basta utilizarmos o comando: A\b. No caso:

x = A\B
2×3 Array{Float64,2}:
 2.0  20.0  20.0
 1.0   1.0   1.0

Esse é o básico para resolver sistemas lineares através do Julia. Claro que, você pode ser criativo e criar um "descriptografador". No caso, utilizando o raciocínio que segui no exemplo, eu criei um vetor $z$ qualquer, da seguinte forma:

z = [: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, :?, :!, :_]

Em Julia, :a significa que você está inserindo uma variável do tipo string. Após criar esse vetor com os caracteres, criei uma função chamada "descripto" que fara todo o trabalho para mim, no caso:

function descripto(x::Array)
    for j=1:length(x[1,:])
        for i=1:length(x[:,1])
            k = round(Int, x[i,j])
            print(z[k])
        end
    end
end
Entrada: descripto(x)
Saída: batata

Pronto! Agora você já pode sair criptografando e descriptografando mensagens à vontade!

Referências:
[1] Julia Lang. www.julialang.org