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:

clip_image002
Tabelas com m linhas e n colunas são denominadas matrizes  clip_image002[7] sendo clip_image002[5].

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.

clip_image002[13] = clip_image004[4] 

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

Fácil veja a matriz 3×3:

A= clip_image002[15]

Onde :
clip_image002[17]=-3  clip_image004[6]=-3  clip_image006=-4
clip_image008=0   clip_image010=1   clip_image012=1
clip_image014=4   clip_image016=3   clip_image018=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

clip_image002[23]
Ela é inversível se existir uma matriz B tal que:

clip_image002[21] 
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

clip_image002[25]

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

image

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

image

(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 clip_image002[28] 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.

[tabela.JPG]
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= clip_image002[19]

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.:

clip_image002[15] *clip_image002[19]

Multiplicação de Matrizes

Duas matrizes A= (aij)mxn e B(bij)nxp o produto de AB é C=(cij)mxp tal que:

 (AB)_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.

para cada par i e j com 1 ≤ im e 1 ≤ jp.

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

Smiley surpreso 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= clip_image002[37]

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

[tabela.JPG]

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

9 comentários sobre “Criptografia com Álgebra Linear (matrizes)–Parte 1

  1. Pingback: Criptografia com Álgebra Linear (matrizes)–Parte 2 « 0000 1101

  2. adorei a explicacao,muito boa.mas seria a melhor se vcs explicassem matrizes multiplicadas com letras tambem.mesmo assim valeu pela ajuda.

  3. Muito mega.
    Adorei a materia, vou imprimir e estudar no caminho para o curso, eu desenvolvi uma forma que digamos, criptografa numeros, criei o Keygen que faz o inverso dela, é tudo baseado em modulos, mas queria algo mais avançado, sua materia caiu como uma luva, vou estudar isso indo para o trabalho e indo para o curso,muito obrigado.
    Se poder postar algo sobre CRIPTOGRAFIA MILITAR, eu agradeço desde já.
    Obrigado.😄

  4. I loved your post, it helped me a lot to understand criptografy; but I have to say something… you’ve got a mistake in this, when you convert “muito loco” to its matrix form, you use ‘3’ as the value of letter ‘c’ when in your image it was said that the value for ‘c’ was ‘2’ instead of ‘3’.

    Even tough, great site!

    Regards from Guatemala!😀

  5. muito bom fazia tempo que não via esta materia ,vcs tem certeza e muito interessante

  6. Estava procurando por criptografia e achei seu blog. Acho que te conheço né? Abraço!

  7. Desculpa não entendi como voltar para a mensagem original a partir da mensagem cifrada depois de aplicada a aritmética modular?

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s