quarta-feira, 6 de novembro de 2013

Criptografia

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”
FraseValor na TabelaValor na Matriz
M12a11
U20a21
I8a31
T19a12
O14a22
26a23
L11a13
O14a23
C3a33
O14a14
26a24
26a34
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 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 ≤ i ≤ m e 1 ≤ j ≤ p.
Somente se Anxm*Bmxp=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= 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) = 2203: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:
ValorFrase Criptografada
2C
21V
9J
16Q
2C
14O
17R
0A
10K
14O
20U
4E

Nenhum comentário: