Criptografia

Prévia do material em texto

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO GRANDE DO SUL 
 Faculdade de Matemática – Departamento de Matemática 
 Disciplina de Álgebra Linear e Geometria Analítica 
 
 
 
Professores Francisco Silveira e Paulo Winterle 
 
 MATRIZES E CRIPTOGRAFIA 
 
Muitas técnicas para codificar e decodificar mensagens secretas fazem vasto uso de álgebra linear. Aqui 
descrevemos um método bastante simples que envolve apenas um par de matrizes inversas, A e B = A-1, cujos 
elementos são todos inteiros. Primeiro ilustramos este método utilizando o par 
 ⎥⎦
⎤⎢⎣
⎡=
12
13
A e ,
32
11
⎥⎦
⎤⎢⎣
⎡
−
−=B (1) 
para o qual você pode verificar imediatamente que AB = BA = 1. O remetente vai usar uma matriz A para 
codificar a mensagem, e o destinatário vai usar a matriz B para decodificar a mensagem. O objetivo deste 
método é que a mensagem seja codificada utilizando pares de caracteres, de modo que tabelas de freqüência 
de letras e coisas do tipo não ajudem em nada a um decodificador não-amigável: aqui descrevemos um código 
em vez de um criptograma. 
 Dada uma mensagem para ser codificada, o primeiro passo é convertê-la da forma alfabética para a forma 
numérica. Para isso usamos a seguinte correspondência entre letras e números. 
 
 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 . , # 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
 
Qualquer outra numeração dos 29 símbolos tipográficos também seria possível, mas o remetente e o destinatário 
teriam que combinar uma específica. Para maior clareza usamos o símbolo # , indicando um espaço entre as 
palavras (ou em outros lugares). Suponha que THE GAME IS A FOOT, que, em português seria algo como “O 
PLANO ESTÁ EM AÇÃO”, é a mensagem a ser codificada e transmitida. Para convertê-la para forma numérica, 
usamos o pareamento exibido acima: escrevemos. 
 
 T H E # G A M E # I S # A F O O T 
 20 8 5 29 7 1 13 5 29 9 19 29 1 6 15 15 20 
 
Uma vez que a matriz codificadora A é uma matriz 2 x 2, arranjamos nossa seqüência de números como os 
elementos de uma matriz com duas linhas: 
⎥⎦
⎤⎢⎣
⎡=
292015156129199
2951317295820
M 
Como a mensagem tem um número ímpar de elementos, completamos o fim da segunda linha com 29, que 
representa um espaço final inofensivo ( um “zero” ) somado à mensagem. 
 Para codificação da mensagem, multiplicamos a matriz M à esquerda pela matriz codificada A: 
N = AM 
⎥⎦
⎤⎢⎣
⎡⎥⎦
⎤⎢⎣
⎡=
292015156129199
2951317295820
12
13
N 
tal que 
⎥⎦
⎤⎢⎣
⎡=
873541172059393549
1163554182788444369
N 
Os elementos de N = AM constituem a mensagem codificada 
 69, 43, 44, 88, 27, 18, 54, 35, 116, 49, 35, 39, 59, 20, 17, 41, 30, 87 
com utilização de vírgulas para maior clareza. Veja que, enquanto havia repetições representando letras repetidas 
na mensagem original, não há nenhuma mensagem codificada, de modo que os decifradores de código simples 
não têm por onde começar. 
 Quando esta mensagem codificada chega, o destinatário utiliza a matriz decodificadora B para reverter os 
passos acima, sabendo que 
BN = BAM = IM = M. (2) 
Portanto, se o decodificador usar a mensagem codificada para construir uma matriz com duas linhas e depois 
multiplicar esta matriz à esquerda por B, ele ou ela irá obter a matriz M do remetente. Esta multiplicação é 
⎥⎦
⎤⎢⎣
⎡⎥⎦
⎤⎢⎣
⎡
−
−=
873041172059393549
1163554182788444369
32
11
BM 
 
 
 
Professores Francisco Silveira e Paulo Winterle 
2
⎥⎦
⎤⎢⎣
⎡=
292015156129199
2951317295820
BM 
Note que o produto é de fato a matriz M do remetente. O passo final de decodificação é 
 
 20 8 5 29 7 1 13 5 29 9 19 29 1 6 15 15 20 29 
 T H E # G A M E # I S # A F O O T # 
 
A Equação (2) é o X da questão. Em resumo, o remetente multiplica a mensagem original (na forma matricial 
numérica M) por A para obter a mensagem codificada. O destinatário multiplica a mensagem codificada ( em 
forma matricial N ) por B para reconstruir a mensagem original. Como A e B são matrizes inversas, a 
multiplicação do destinatário por B desfaz o efeito da multiplicação do remetente por A. 
 Note que o processo pode ser levado a cabo rápido e automaticamente por computador ( aumentando, 
portanto, a sua segurança ) mas, se for preciso, pode ser feito com lápis e papel apenas (realçando, portanto, sua 
utilidade ). Tudo o que precisa ser secreto são as matrizes codificadora e decodificadora, uma tarefa muito mais 
simples do que esconder um volumoso livro de códigos de um decifrador não-amigável. 
 Como um segundo exemplo, usamos as matrizes inversas 3 x 3. 
eA
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=
313
112
213
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−
−
−−
=
101
739
314
B (3) 
e vamos supor que THE PLOT THICKENS seja a mensagem, que em português significa “ENTROU AREIA”, a 
ser codificada. Primeiro, convertemos as letras em números ( usando o mesmo esquema que antes ) e então 
organizamos estes números em uma matriz com três linhas: 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
2919145113
9820292015
1216295829
M 
Para codificar a mensagem, multiplicamos M à esquerda por A para obter 
N = AM 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
−=
2919145113
9820292015
1216295820
313
112
213
N 
⎥⎥
⎥
⎦
⎤
⎢⎢
⎢
⎣
⎡
=
132113149597784
42164342552
10394135546681
N 
Portanto, a mensagem codificada é 
 
 81, 66, 54, 135, 94, 103, 52, 25, 34, 64, 21, 4, 84, 77, 59, 149, 113, 132. 
Deixamos como exercício para você calcular BN depois de recuperar a mensagem original. 
 
EXERCÍCIOS 
Os seguintes exercícios fazem uso destes dois pares de matrizes inversas. 
 a) ,
11
12
⎥⎦
⎤⎢⎣
⎡=A ⎥⎦
⎤⎢⎣
⎡
−
−=
21
11
B b) ⎥⎦
⎤⎢⎣
⎡=
11
23
A , ⎥⎦
⎤⎢⎣
⎡
−
−=
31
21
B 
Nos exercícios 1 e 2, use a matriz A de (a) e (b), respectivamente, para codificar a mensagem dada 
 1- SHERLOCK 2- WATSON 
Nos exercícios 3 e 4, use a matriz B de (a) e (b), respectivamente, para decodificar a mensagem dada. 
 3- 56, 27, 44, 34, 18, 29 4- 69, 78, 56, 51, 59, 30, 30, 19, 23, 26 
 
 Extraído: Introdução à ÁLGEBRA LINEAR 
 C.H.Edwards, Jr. 
 David E. Penney