Aplicação Da Álgebra Linear

MINISTÉRIO DA EDUCAÇÃO E CULTURA

CURSO DE BACHARELADO EM CIÊNCIA E TECNOLOGIA

DISCIPLINA: ÁLGEBRA LINEAR

DOCENTE:

APLICAÇÕES DA ÁLGEBRA LINEAR: CRIPTOGRAFIA

INTRODUÇÃO

O uso da matemática se fez necessário de maneira contínua e cada vez mais constante do dia-a-dia das pessoas. Desde a antiguidade até os tempos atuais sua utilização se mostra indispensável, onde cada vez mais é aprimorada e possibilita uma diversificada área de estudos.

Desde muito cedo somos introduzidos nesse campo tão vasto por meio da escola e muitas vezes nos perguntamos como usaremos a matemática nas ações corriqueiras. Adotando o segmento da álgebra linear, explicaremos nesse trabalho uma de suas aplicações, o método da criptografia, onde será discutido como é feito esse processo e suas finalidades.

2. CRIPTOGRAFIA

O envio e recebimento de informações sigilosas é uma necessidade antiga, que existe há centenas de anos. Com o surgimento da internet e sua facilidade de entregar informações de maneira precisa e extremamente rápida, a criptografia tornou-se uma ferramenta fundamental para permitir que apenas o emissor e receptor tenham acesso livre a informação trabalhada.

O termo criptografia surgiu da junção das palavras gregas “kryptós” e “gráphien”, que significa “oculto” e “escrever”, respectivamente. Trata-se de um conjunto de conceitos e técnicas que visam codificar uma informação de forma que somente o emissor e o receptor possam acessa-la, evitando que um intruso consiga interpretá-la. Para isso, uma série de técnicas é utilizada e varias outras surgem com o passar do tempo. Descrevemos abaixo um método muito simples, para codificar e decodificar mensagens, que envolve apenas um par de matrizes de ordem n, A e A^(-1), cujos elementos devem ser números inteiros.

Primeiramente ilustraremos o método utilizando uma matriz A e sua inversa A^(-1).

Sejam A = [■(3&1@2&1)] e A^(-1) = [■(1&-1@-2&3)]

A matriz é apropriada, pois seus elementos são números inteiros assim como os da matriz A^(-1).

O remetente vai usar a matriz A para codificar a mensagem, e o destinatário vai usar a matriz A^(-1) para decodificá-la. O objetivo desse método é que a mensagem seja codificada utilizando pares de caracteres, de modo que tabelas de frequências de letras e alternativas não ajudem em nada a um decodificador não-amigável.

Dada uma mensagem para ser codificada, o primeiro passo será convertê-la da forma alfabética para a forma numérica. Para isso usamos a seguinte correspondência entre letras e números:

A ou à B C ou Ç D E F G H I J K L M N O ou Õ

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

P Q R S T U V W X Y Z . , #

16 17 18 19 20 21 22 23 24 25 26 27 28 29

Qualquer outra numeração dos 29 símbolos também seria possível, mas o remetente e o destinatário teriam de combiná-las previamente. Para maior clareza usamos o símbolo # para indicar inexistência de letras.

Exemplo 01: Suponha que “AMAR E RESPEITAR” é a mensagem a ser codificada e transmitida. Para convertê-la para forma numérica, usamos a correspondência entre letras e números exibida acima:

A M A R # E # R E S P E I T A R

01 13 01 18 29 05 29 18 05 19 16 05 09 20 01 18

Uma vez que a matriz codificadora A é uma matriz 2x2, arrumamos nossa sequência de números como os elementos de uma matriz com duas linhas:

M = [■(01&13&01&18&29&05&29&18@05&19&16&05&09&20&01&18)]

Como a mensagem tem um número par de elementos, a matriz se completa naturalmente. No caso de uma mensagem com um número impar de elementos, completamos o fim da última com o número 29 que está associado ao símbolo #, que representa um espaço final inofensivo (um zero) somado a mensagem.

Para codificação da mensagem, multiplicamos a matriz M a esquerda pela matriz codificadora A:

N = AM

N = [■(3&1@2&1)]. [■(01&13&01&18&29&05&29&18@05&19&16&05&09&20&01&18)],

Ou seja,

N = [■(08&58&19&59&96&35&88&71@07&45&18&41&47&30&59&54)]

Os elementos de N=AM constituem a mensagem codificadora, e utilizaremos as vírgulas entre esses elementos para maior clareza:

08, 58, 19, 59, 96, 35, 88, 71, 07, 45, 18, 41, 47, 30, 59, 54.

Quando esta mensagem codificada chegar ao destinatário este deve utilizar a matriz decodificadora A^(-1) para reverter os passos acima, pois

A^(-1). N = A^(-1).AM = I.M = M

Portanto, se o decodificador usar a mensagem codificada para construir uma matriz com duas linhas e depois multiplicar esta matriz a esquerda por A^(-1), irá obter a matriz M do remetente.

Vejamos:

A^(-1) N = [■(1&-1@-2&3)]. [■(08&58&19&59&96&35&88&71@07&45&18&41&47&30&59&54)]

= [■(01&13&01&18&29&05&29&18@05&19&16&05&09&20&01&18)]

Note que o produto é de fato a matriz M do remetente. O passo final da decodificação é:

A M A R # E # R E S P E I T A R

01 13 01 18 29 05 29 18 05 19 16 05 09 20 01 18

EXEMPLO 02: Utilizando uma matriz 3x3

Sejam A = [■(3&1&2@2&1&-1@3&1&3)] e A^(-1) = [■(4&-1&-3@-9&3&7@-1&0&1)]

Suponhamos que a mensagem a ser