(Parte 1 de 3)

ALGEBRA APLICADA A CRIPTOGRAFIA:UTILIZAÇÃO DE MATRIZES PARA CODIFICAÇÃO DE MENSAGENS

Maria Alcilene Souza Vasconcelelos1

Dirceu Prediger2

RESUMO

Algebra aplicada a criptografia diz respeito ao estudo dos principais fundamentos da criptografia, bem como seus objetivos e os recursos utilizados por ela. Este estudo faz uma analise simplificada da sua evolução histórica e demonstra também de forma simplificada como a utilização de recursos matemáticos podem ser utilizados para se conseguir manejar essa técnica brilhante de codificação de informações. Neste estudo foram utilizadas noções de matrizes para criptação e um software como auxilio para se conseguir tal feito. Chegando a conclusão de que as bases de teorias matemáticas e o surgimento de sistemas computacionais foram fundamentais pra fazer a criptografia passar de arte a ciência exata, e a utilização de seus recursos Como vetor facilitador de nossas vidas tem hoje grande importância.

PALAVRAS-CHAVE: Criptografia, Matemática, Matrizes.

.

ABSTRACT

Algebra Applied cryptography concerns the study of the core foundations of cryptography, as well as their goals and the resources used by it .This study is a simplified analysis of their historical development and also shows in simplified form the use of mathematical resources can be used to manage to achieve this brilliant technique of encoding information. this study used concepts of matrices for encrypting and software as an aid to achieve such a feat. Reaching the conclusion that the foundations of mathematical theories and the emergence of computer systems were essential to make the move from art encryption exact science, and use its resources as vector facilitator of our lives today has great importance.

KEYWORDS: Cryptography, Mathematics,Matrices

INTRODUÇÃO

Os códigos secretos remontam os primórdios da comunicação escrita, e a importância de não revelar segredos motivou o desenvolvimento de códigos para mascarar mensagens, possibilitando apenas ao destinatário ler o conteúdo.

Durante milênios, Generais, reis, rainhas e governantes buscaram formas seguras e eficientes de comunicação, de como comandar seus exércitos e governar seus países sem que informações valiosas caíssem em mãos inimigas. Essa situação motivou o desenvolvimento da codificação de mensagens. As nações passaram então a criar departamentos para elaboração de códigos cada vez mais evoluídos.

Todo código sempre está em ataque constante de decifradores, colaborando assim para a evolução dos sistemas de codificação de mensagens, a evolução dos mesmos passaram então de simples sistemas de substituição como o método utilizado por César imperador romano (100 – 44 a.C.), conhecido como “cifra da troca” ou “cifras de César”. Onde cada letra é substituída por uma outra letra utilizando 3 posições do alfabeto ( tabela 1), até codificação complexas como a utilizada na navegação em rede sociais.

Segundo o livro de Anton Rorres álgebra linear com aplicações criptografia se define como sendo o estudo de codificação e decodificação de mensagens secretas.

No livro Criptografia Segredos Embalados para Viagem a autora Viktoria Tkotz ressalta que poucos se dão conta de que a criptografia faz parte da vida moderna protegendo informações e mantendo em sigilo dados confidenciais. Essa afirmação verídica nos da uma dimensão do quão pouco entendemos do nosso cotidiano e como estudos que julgamos apenas presentes em sistemas acadêmicos teóricos fazem parte de ativamente do nosso dia-a-dia.

A matemática e a criptografia

m jgtpm dm kslbm cqrx cqapgrm ck jglesxeck kxrckxrgax

A frase acima parece não ter nenhum significado, quando olhada de uma primeira vez, parece até um idioma desconhecido, mas se tentarmos decifrá-la logicamente após algumas tentativas iremos perceber que ocorre apenas uma substituição das letras originais pelas segundas letras anteriores a elas, no alfabeto de 26 letras. Sem grande dificuldade você terá escrito

“O livro do mundo está escrito em linguagem matemática”.

Do célebre Galileu Galilei.

Consegui-se facilmente identificar e decifrar o segredo, pois existe um padrão utilizado para codificação da mensagem. Isso é um grande problema em codificações, pois quando o sistema de codificação consegue ser facilmente quebrado, a segurança que o mesmo proporciona é baixa e falha. Mesmo assim esse é um bom exemplo de criptografia, e por muitos séculos foi usado sem oferecer riscos ao conteúdo da mensagem.

Quando alguém deseja transmitir alguma informação que não deseja partilhada com outros, a não ser o destinatário final ela pode se utilizar dos recursos da criptografia e combinar uma chave qualquer para transmissão e recepção da informação. O receptor, de posse da chave, decodifica a mensagem, transformando-a novamente para que possa entender e ler o que lhe foi enviado. No simples exemplo citado o emissor substituiu cada letra do alfabeto por uma outra que ficava duas posições antes dela, no alfabeto. O receptor, sabendo da chave dessa “criptografia”, aplica a operação inversa na frase recebida, ou seja, substituía cada letra recebida pela que ficava duas posições depois dela, no alfabeto.

Se designarmos por x a letra original e por y a letra que a substituirá no código, é como se tivéssemos uma função, definida por y = x + 2.

Sabe-se que uma das primeiras aplicações de criptografia foi inventada pelo imperador romano Julio César, que enviava mensagens aos seus generais trocando letras do alfabeto a partir de uma simples regra, similar que seria "pule três" (chave 3). Através deste esquema, as letras eram trocadas pela terceira letra anterior no alfabeto. Desta forma, somente quem soubesse da regra conseguia desfazer o algoritmo e ler a mensagem original.

Veja como funcionava essa chave 3, de Julio César:

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

X

Y

Z

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

Tabela 1: transposição de letras

Uma palavra simples pode ser codificada e enviada podendo passar-se por uma mensagem difícil e complicada de entender-se. Como citado estes sistemas e sistemas similares, obtidos através de permutações, em que as letras são "embaralhadas", são simples, mas serviram como base para o desenvolvimento da criptografia como a conhecemos na atualidade.

Outro exemplo mais completo relacionado com a aritmética modular é o seguinte:

Constrói-se uma tabela de letras com a representação de suas respectivas posições.

Codificando a mensagem original com uma chave.

a

b

c

d

e

f

g

h

i

j

k

l

m

1

2

3

4

5

6

7

8

9

10

11

12

13

n

o

p

q

r

s

t

u

v

w

x

y

z

14

15

16

17

18

19

20

21

22

23

24

25

26

Tabela 2: tabela de posições de letras

Chave: Somar 4

Com essa chave, ela fica substituída pela letra cujo número corresponde ao número original, aumentado de 4. Quando acontecer do resultado ser superior ao 26, voltamos ao início do alfabeto. Por exemplo, o número 28 corresponderá à letra b, pois 28 = 26 + 2 e, como já sabemos 28 ≡ 2 (mod 26).

Através de uma chave dada : somar 4 ou y = x + 4

Se a mensagem a ser enviada fosse “O homem é o que ele acredita”, o grupo emissor teria que criptografá-la como:

S LSQIQ I S UYI IPI EGVIHMXE

O grupo receptor da mensagem, sabendo que a chave foi “somar 4”, teria agora que subtrair 4 unidades dos números que representam cada letra da mensagem criptografada, para obter a mensagem original, decifrando o código. Vejamos:

S = 19 – 4 = 15 = O S = 19 – 4 = 15 = O E = 5 – 4 = 1 = A E...= 1= A

L = 12 – 4 = 8 = H U = 21 – 4 = 17 = Q G = 7 – 4 = 3 = C

S = 19 – 4 = 15 = O Y = 25 – 4 = 21 = U V = 22 – 4 = 18 = R

Q = 17 – 4 = 13 = M I = 9 – 4 = 5 = E I = 9 – 4 = 5 = E

I = 9 – 4 = 5 = E I = 9 – 4 = 5 = E H = 8 – 4 = 4 = D

Q = 17 – 4 = 13 = M P = 16 – 4 = 12 = L M = 13 – 4 = 9 = I

I = 9 – 4 = 5 = E I = 9 – 4 = 5 = E X = 24 – 4 = 20 = T

Durante a segunda guerra mundial sistemas eletromecânicos na codificação e decodificação das mensagens foram muito usados. Nestes dispositivos, rotores incorporavam internamente uma permutação e sua instalação em mecanismos parecidos com "counters" (ou contadores) permitiam transformações polialfabéticas produzindo uma quantidade impressionante de combinações.

Ainda durante a guerra computadores (como o "Colossus") foram usados na "quebra" de códigos alemães, italianos e japoneses e, desde então, a Criptografia passou a ser estudada de forma mais científica.

Depois da Segunda Guerra Mundial, com o desenvolvimento dos computadores, a área realmente floresceu incorporando complexos algoritmos matemáticos. Na verdade, esse trabalho criptográfico formou a base para a ciência da computação moderna.

Matrizes e criptografia

Uma desvantagem de cifras de substituição é que elas preservam as freqüências de letras individuais, tornando relativamente fácil quebrar o código por métodos estatísticos. Uma maneira de superar este problema é dividir o texto em grupos de letras e criptografar o texto comum por grupo, em vez de uma letra de cada vez. Um sistema poligráfico é um sistema de criptografia no qual o texto comum é dividido em conjuntos de n letras, cada um dos quais é substituído por um conjunto de n letras cifradas. As cifras de Hill, que foi inventada em 1929 por Lester S.Hill, são baseadas em transformações matriciais.

Se tentarmos definir matriz de forma generalizada chegamos a conclusão que matrizes são informações organizadas em linha e colunas formando agrupamentos retangulares.

Figura 1 : esquematização de matriz

Sendo cada elemento presente na matriz indicado por dois índices:

Formando assim um conjunto m x n elementos dispostos em m linhas e n colunas onde aij é o elemento associado a i-ésima linha e j-ésima coluna.

Muitas técnicas para codificar e decodificar mensagens secretas fazem vasto uso de álgebra linear.

Inicialmente vamos supor que cada letra de texto comum e de texto cifrado, excetuando o Z, tem um valor numérico que especifica sua posição no alfabeto padrão. A letra Z será atribuído o valor zero, pois estaremos interessados em trabalhar com aritmética módulo 26.

a

b

c

d

e

f

g

h

i

j

k

l

m

1

2

3

4

5

6

7

8

9

10

11

12

13

n

o

p

q

r

s

t

u

v

w

x

y

z

14

15

16

17

18

19

20

21

22

23

24

25

0

Tabela 3: Relação de letras com números.

Para transformarmos um texto em texto cifrado seguiremos os seguintes procedimentos:

Passo 1. Escolha uma matriz 2x2.

A = a11 a12

a21 a22

Com entradas inteiras para efetuar a codificação.

Passo 2. Agrupar letras sucessivas de texto comuns em pares, adicionando uma letra fictícia para completar o último par se o texto comum tiver um número ímpar de letras; substitua cada letra de texto de texto comum por seu valor numérico

Passo 3. Converta cada par sucessivo p1, p2 de letras de texto comum em um vetor-coluna

(Parte 1 de 3)

Comentários