Criptografia com Álgebra Linear (matrizes)–Parte 1

Uma das perguntas quando a gente aprende matriz é:
- Para que eu preciso disso?

Matrizes são uteis em diversos campos como em economia, engenharia, física, tecnologia (grafos) e também pode ser aplicada em criptografia.
A área da criptografia é bem abrangente e usa diversos métodos para transformar dados normal (texto puro) e texto cifrado.
Podemos empregar álgebra linear, mais especificamente matriz a fim de criarmos um sistema de criptografia. O método envolve duas matizes, uma para criptografar e uma descriptografar.

Para entender o artigo é bom lembrar ou aprender o básico de matrizes, portanto além de ver um processo bem legal de criptografia, você vai entender matrizes, matriz inversa, determinante, regra de “Sarrus”, Multiplicação de matriz e aritmética modular, e na sugunda parte desse artigo entenderá matriz adjunta (transposta) menor complementar e co-fator e é claro um bom método de criptografia simétrica.

Matriz

Matriz = Uma tabela de números dispostos em linhas e colunas colocados entre parênteses ou colchetes:

Tabelas com m linhas e n colunas são denominadas matrizes  sendo .

Uma matriz é representada por letras maiúsculas e seus elementos por letras minúsculas, acompanhadas de dois índices que indicam a linha e a coluna.

=  

Abreviando a matriz A podemos escrever
 
O i representa a linha e o j representa a coluna que o elemento ocupa.

Fácil veja a matriz 3×3:

A=

Onde :
=-3  =-3  =-4
=0   =1   =1
=4   =3   =4

Essa matriz poderá ser utilizada em nossa criptografia. (Se quiser fazer diferente do exemplo escolha números aleatórios e crie uma matriz 3×3).
Desde que ela possua uma inversa.
A inversa de A somente irá existir se e somente se a determinante de A for diferente de zero.

Se esta matriz possuir a inversa ela será a nossa Chave de Criptografia.

Matriz Inversa parte 1

Ela é inversível se existir uma matriz B tal que:

 
Neste caso B é dita como inversa de A e pode ser escrita como A^-1.

Determinante

Determinante é um número real associado a uma matriz usado no calculo da matriz inversa, resolução de alguns sistemas lineares e em calculo de área de triângulos quando se conhece as coordenadas do vértice.
Vamos verificar se a matriz A possui uma inversa e para isso temos que descobrir o determinante.

Por se tratar de uma matriz 3×3 a determinante é de 3ª ordem, assim temos que usar um dispositivo conhecido como regra de Sarrus (“lê-se Sarrí”).
1º passo – Repetir as duas primeiras colunas al lado da terceira

2º passo – Multiplicar os elemento da diagonal principal de A conservando os sinais.

(-3*1*4)+( -3*1*4)+( -4*0*3)=-24
3º passo – Multiplicar os elementos da diagonal secundaria trocando o sinal

(4*1*-4)+(3*1*-3)+(4*0*-3) = –25 (inverte o sinal)

4º passo – Somar os produtos obtidos:
25+(-24)=1

1 é o determinante da matriz A
det(A)=1 Existe a inversa de A

Criptografando

Continuando o processo de criptografia o próximo passo é pensar em nosso alfabeto e para fins de simplificação, vamos transformar as letras do alfabeto em números sequencias, poderíamos fazer a utilização da tabela ASCII.

Que tal incluir o espaço e adicionar o valor 26;
Vamos imaginar agora uma mensagem a ser criptografada.
”Muito loco”

Frase	Valor na Tabela	Valor na Matriz
M	12	a11
U	20	a21
I	8	a31
T	19	a12
O	14	a22
	26	a23
L	11	a13
O	14	a23
C	3	a33
O	14	a14
	26	a24
	26	a34

Resultando na seguinte matriz.
B=

Com a matriz A que é a nossa chave de criptografia e a matriz B que é nosso texto puro, basta fazer a multiplicação das matrizes para termos um mensagem criptografada.:

 *

Multiplicação de Matrizes

Duas matrizes A= (a_ij)_mxn e B(b_ij)_nxp o produto de AB é C=(c_ij)_mxp tal que:

para cada par i e j com 1 ≤ i ≤ m e 1 ≤ j ≤ p.

Somente se A_nxm*B_mxp=Nxp Ou seja, desde que o numero de colunas de A sejam iguais ao numero de linhas de B

Não se assuste é fácil:
É a soma dos produtos das linhas de A por todas as colunas de B.

(-3*12)+(-3*20)+(-4*8)    (-3*19)+(-3*14)+(-4*26)    (-3*11)+(-3*14)+(-4*3)     (-3*14)+(-3*26)+(-4*26)
(0*12)+(1*20)+(1*8)        (0*19)+(1*14)+(1*26)        (0*11)+(1*14)+(1*3)        (0*14)+(1*26)+(1*26)
(4*12)+(3*20)+(4*8)        (4*19)+(3*14)+(4*26)        (4*11)+(3*14)+(4-3)        (4*14)+(3*26)+(4*26)

C=

Essa é a mensagem criptografada.

Aritmética Modular

 

Se você quiser visualizar os caracters gerados você deve usar aritmética modular MOD(26) pois nossa tabela só vai até 26 – Calculo modular não é dificil.
-128:26 = 5 sobra 2 portanto 128 MOD(26) = 2
203:26 dá 7 e sobra 21 portanto MOD(26)=21
87 MOD(26)=9
224 MOD(26)=16
28 MOD(26)=2
40 MOD(26) = 14
17 não precisa
52 MOD(26) =0 (não tem resto)
140 MOD(26)=10
222 MOD(26)=14
98 MOD(26)=20
238 MOD(26)=4

Temos então o valor 2, 21, 9, 16 ,2,14,17,0,10,14,20 e 4

Formando a frase criptografada:

Valor	Frase Criptografada
2	C
21	V
9	J
16	Q
2	C
14	O
17	R
0	A
10	K
14	O
20	U
4	E