A PRESENÃA DA LGEBRA LINEAR E TEORIA DOS N+MEROS NA CRIPTà

Prévia do material em texto

A PRESENÇA DA ÁLGEBRA LINEAR E TEORIA DOS NÚMEROS NA 
CRIPTOGRAFIA 
Sandra Beatris Zatti1 
Ana Maria Beltrame2 
 
Resumo 
A Criptografia é uma técnica de escrever mensagens cifradas que, ao longo da 
História, teve larga aplicação militar. O cidadão comum, contudo, até há pouco tempo, talvez 
só tenha ouvido falar em criptografia ao assistir a filmes de guerra ou espionagem. Mais 
recentemente, esta técnica passou silenciosamente a integrar o cotidiano, sem que se perceba. 
Sistemas de caixas eletrônicos, home-banking, pay-per-view, ou de muitas páginas na Internet 
(notadamente as que pedem senha de acesso) utilizam a criptografia como meio de conferir 
segurança às suas operações. Embora desnecessário compreender todo o mecanismo 
envolvido na sua geração, mostra-se conveniente ao usuário conhecer noções básicas da 
criptografia, a fim de poder utilizá-la de modo seguro, já que o futuro – nem tão distante 
assim – das comunicações e negócios por via eletrônica se assenta no uso desta nova técnica. 
O primeiro livro impresso a abordar o tema intitula-se Poligrafia, publicado em 1510, por um 
abade alemão chamado Johannes Trithemius, hoje considerado o pai da moderna criptografia. 
 
Palavras-chave - Criptografia, matrizes 
 
Introdução 
Em grego, cryptos significa secreto, oculto. A criptografia costuma ser definida como 
a arte de escrever em cifra ou em código, de modo a permitir que somente quem conheça o 
código possa ler a mensagem; essa é uma definição que remonta às suas origens artesanais. 
Atualmente, a criptografia, que, por sua vez, dado o grau de sofisticação e embasamento 
teórico que envolve o seu estudo, é hoje considerada uma ciência, no campo das Ciências 
Exatas. E, ao lado das técnicas criptográficas para cifrar a mensagem, o estudo dos métodos 
para decifrá-la, sem conhecer a senha, é chamado de criptoanálise, constituindo-se em outra 
subdivisão de criptologia. 
Convencionado um critério entre o emissor e o receptor, a criptologia torna possível o 
envio de mensagens codificadas, incompreensíveis para um terceiro que eventualmente venha 
a interceptá-las, mas que poderão ser lidas pelo seu destinatário, que conhece o critério para 
decifrar o texto encriptado. 
O uso da criptografia não é recente e, ao longo dos tempos, teve larga aplicação 
estratégica e militar. A necessidade de enviar mensagens às tropas, que não pudessem ser 
 
1
 Aluna do curso de Matemática – UNIFRA 
2
 Professora do curso de Matemática - UNIFRA 
 
 
2 
 
compreendidas pelo inimigo, caso o mensageiro caísse em suas mãos, fez desenvolver a arte 
de escrever em código.E, evidentemente, fez crescer paralelamente a criptoanálise, arte de 
quebrar o código e decifrar a mensagem alheia. 
Considera-se que a criptografia seja tão antiga quanto a própria escrita. Há indícios de 
que, na Antiguidade, foi conhecida no Egito, Mesopotâmia, Índia e China, mas não se sabe 
bem qual foi a sua origem, e pouco se sabe acerca de seu uso nos primórdios da História. Em 
Esparta, por volta de 400 a.C., a técnica de escrever mensagens secretas envolvia enrolar, de 
forma espiral, uma tira de pergaminho ou papiro ao longo de um bastão cilíndrico. O texto era 
escrito no sentido longitudinal, de modo que cada letra fosse inscrita separadamente numa das 
voltas da tira de papiro. Desenrolada a faixa, o que se via era uma porção de letras dispostas 
sem qualquer sentido. Para ler a mensagem, seria necessário enrolar a tira em um bastão do 
mesmo diâmetro daquele em que a mensagem foi escrita, de forma que as letras novamente se 
encaixassem na posição original. 
Na Roma Antiga, Júlio César utilizava um método para cifrar sua correspondência, 
pelo qual cada letra do texto era substituída pela terceira letra subseqüente no alfabeto. Ou 
seja, para enviar uma mensagem com os dizeres “ENCONTRO CONFIRMADO PARA 
DOMINGO”, mediante o cifrado de Júlio César o texto seria escrito assim: 
HQFRQWUR FRQILUPDGR SDUD GRPLQJR 
Por também servir ao uso militar há, em certos países, algumas restrições à 
criptografia. Nos Estados Unidos, apenas em janeiro de 2000 as proibições de exportar 
produtos criptográficos foram relaxadas. Até então, o ITAR (“International Traffic in Arms 
Regulation”), lei que estabelece restrições à exportação de equipamentos militares, proibia 
não só a venda de lança-chamas, tanques, minas, torpedos, navios e aviões de guerra, mísseis 
balísticos ou armas químicas, mas também de softwares e equipamentos para criptografia. O 
uso interno da criptografia, no entanto, não é nem foi controlado naquele país, apesar de 
várias tentativas governamentais de estabelecer restrições, sempre sob o protesto da 
comunidade de defensores de direitos civis. 
Dentre os países do mundo democrático, a França era o único a estabelecer regras 
rígidas sobre o uso interno da criptografia. Até 1996, o uso da criptografia estava sujeito a 
uma prévia declaração, caso fosse utilizada apenas para autenticação ou para assegurar a 
integridade de mensagens transmitidas e, nos demais casos (inclua-se aqui proteger o sigilo da 
informação), a uma prévia autorização do Primeiro Ministro. Modificações legislativas 
posteriores flexibilizaram as restrições, embora afirme Koops [MARCACINI] que “não está 
claro em que medida as atuais regras estão sendo aplicadas na prática”, substituindo 
 
 
3 
 
dificuldades para que indivíduos ou empresas obtenham autorização para utilizar criptografia 
forte. A proibição de uso de criptografia potente em território francês tem sido motivo para 
acusações várias de espionagem industrial. 
Além da França, outro país europeu a adotar restrições é a Federação Russa. A partir de 1995, 
foi proibido o uso, o desenvolvimento ou a produção de criptografia não autorizada. As 
autorizações, no caso, são emitidas pela FAPSI, sucessora da KGB. 
 
 
2. DESENVOLVIMENTO 
Na linguagem da criptografia, os códigos são denominados cifras, as mensagens não 
codificadas são textos comuns e as mensagens codificadas são textos cifrados ou 
criptogramas. O processo de converter um texto comum em cifrado é chamado cifrar ou 
criptografar e o processo inverso, de converter um texto cifrado em comum é chamado 
decifrar. 
As cifras mais simples, denominadas de cifras de substituição, são as que substituem cada 
letra do alfabeto por uma outra letra. Por exemplo, na cifra de substituição, 
comum 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, 
na cifra D E F G H I J K L M N O P Q R S T U V W X Y Z A B C. A letra 
de texto comum A é substituída por D, a letra de texto comum B por E e assim por diante. 
Com esta cifra, a mensagem comum ROMA NAO FOI CONSTRUÍDA EM UM DIA fica 
URPD QDR IRL FRKVWUXLGD HP XP GLD. 
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. 
Cifras de Hill – é uma classe de sistemas poligráficos 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 são baseadas em transformações matriciais. 
Daqui em diante, supõe-se que cada letra de texto comum e de texto cifrado, excetuando o Z, 
tem o valor numérico que especifica sua posição no alfabeto padrão (Tabela 1). Por motivos 
que ficarão claros mais tarde, dá-se a Z o valor de 0. 
 
Tabela 1: 
 
 
 
4 
 
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 
 
Nos casos mais simples de Cifras de Hill, transformam-separes sucessivos de textos 
cifrados pelo seguinte procedimento: 
Passo 1: Escolhe-se uma matriz 22 × 






=
2221
1211
aa
aa
A 
 
com entradas inteiras para efetuar a codificação. Condições adicionais sobre A serão 
impostas mais tarde. 
 
Passo 2: Agrupam-se letras sucessivas do texto comum em pares, adicionando uma letra 
fictícia para completar o último par, se o texto comum tem um número ímpar de letras 
substitui-se cada letra de texto comum pelo seu valor numérico. 
 
Passo 3: Converte-se cada par sucessivo 1p 2p de letras de texto comum em um vetor-coluna 
 





=
2
1
p
p
p 
e forma-se o produto pA ⋅ . Chama-se p de vetor comum e pA ⋅ o correspondente vetor 
cifrado. 
 Passo 4: Converte-se cada vetor cifrado em seu equivalente alfabético. 
 
Cifra de Hill de uma mensagem 
 
Problema: Obter a Cifra de Hill da mensagem NOITE ESCURA para a matriz codificadora 






12
31
 
N O I T E E S C U R A A 
 14 15 9 20 5 5 19 3 21 18 1 1 (1) 
 
 
5 
 
 Para codificar o par NO efetua-se o par matricial 
Q
G






=





=











17
7
43
59
15
14
12
31
 
Aqui tem-se um problema, pois o número 59 não possui equivalente alfabético 
(Tabela). Para resolver este problema faz-se o seguinte acordo: 
Sempre que ocorrer um inteiro maior do que 25, ele será substituído pelo resto da 
divisão deste inteiro por 26. Como o resto da divisão é um dos inteiros 0, 1, 2, ..., 25, este 
procedimento sempre fornece um inteiro com equivalente alfabético. Assim, em ( )1 substitui-
se 59 por 7, que é o resto da divisão de 59 por 26 e obtém-se o texto cifrado GQ da Tabela 1 
para NO. 
Para codificar o par IT: 
 
L
Q






=





=











12
17
38
69
20
9
12
31
 
 
Para codificar o par EE 
 
O
T






=











15
20
5
5
12
31
 
Para codificar o par SC: 
O
D






=





=











15
4
41
82
3
19
12
31
 
Para codificar o par UR: 
H
W






=





=











8
23
60
75
18
21
12
31
 
Para codificar o par AA: 
C
D






=











3
4
1
1
12
31
 
Coletando os pares, obtém-se a mensagem cifrada completa GQ QL TO DO WH que seria 
normalmente transmitida como uma única cadeia sem espaços: GQQLTODOWH 
Como o texto comum foi agrupado em pares e criptografado por uma matriz 22 × , 
diz-se que a Cifra de Hill dos exemplos acima é uma 2-Cifra de Hill. Em geral, agrupar o 
texto comum em conjuntos de n letras e codificar com uma matriz codificadora nn × de 
entradas inteiras esta cifra é chamada n-Cifra de Hill. 
 
 
6 
 
Pode-se, também, encontrar de outra maneira a matriz codificada, é o que se vê a 
seguir: 
Problema: um batalhão do Exército resolveu codificar suas mensagens através da 
multiplicação de matrizes. 
Solução: primeiramente, associa as letras do alfabeto aos números, segundo a 
correspondência abaixo considerada: 
 
A 1 F 6 L 11 Q 16 V 21 
B 2 G 7 M 12 R 17 W 22 
C 3 H 8 N 13 S 18 X 23 
D 4 I 9 O 14 T 19 Y 24 
E 5 J 10 P 15 U 20 Z 25 
Dessa forma, supõe-se que o batalhão deseja enviar a mensagem “PAZ”, pode-se 
tomar uma matriz 22 × , da forma 





−Z
AP
, a qual, usando-se a tabela acima, será dada por 






=
025
115
M . Tomando-se uma matriz-chave C para o código, isto é: 





=
21
32
C , 
transmite-se a mensagem “PAZ” através da multiplicação das matrizes M e C , ou seja: 
 






=





⋅





=⋅
7550
4731
21
32
025
115
CM ou através da cadeia de números 31 47 50 75. 
Nos problemas anteriores, substituem-se os inteiros maiores que 25 pelo resto da 
divisão dele por 26. Esta técnica de trabalhar com os restos é a base de uma parte da 
Matemática chamada aritmética modular. Devido à sua importância em criptografia podemos 
defini-la por: supõe-se dado um inteiro positivo m , chamado módulo, considere-se “iguais” 
ou “equivalentes” em relação ao módulo, quaisquer dois inteiros cuja diferença é um múltiplo 
inteiro do módulo. Ou seja, 
 
 
Exemplos: 7 ≡ 2 (mod 5 ) ; 19 ≡ 3 (mod 2) ; 12 ≡ 0 (mod 4) 
 
Dado um módulo m , pode-se provar que qualquer inteiro a é equivalente, módulo m , a 
exatamente um dos inteiros: 0, 1, 2, ..., m -1. Este inteiro é chamado o resíduo de a módulo 
 
 
7 
 
m e nós escrevemos ( )1,,2,1,0 −= mZm L para denotar o conjunto dos resíduos de a 
módulo m . 
Se a é um inteiro não-negativo, então seu resíduo módulo m é simplesmente o resto da 
divisão de a por m . Para encontrar um a arbitrário, faz-se uso do seguinte teorema: 
 
Teorema 11.16.1 – Dados um inteiro a e um módulo m, quaisquer, se 
m
a
R de resto= , então 
o resíduo r de a módulo m é dado por 
 





=<
≠<
≥
−=
0 e 0 se
0 e 0 se
0 se
 
0 Ra
Ra
a
Rm
R
r 
De fato, para encontrar os resíduos módulo 26 de 
( )
( )
( ) 26 
 38 
 87 
−
−
c
b
a
, faz-se: 
Solução ( )a : 
m
a
R de resto= 
 Como 0>a , tem-se: Rr = 
26
87
 de resto 
26
87
 de resto ==R , dividindo-se 87 por 26 dá um resto de 9=R , ou seja, 9=r . 
Assim, ( )26mod987 = 
Solução ( ) :b 
m
a
R de resto= 
Como 0<a e 0≠R tem-se: Rmr −= 
26
38
 de resto 
26
38
 de resto =
−
=r , dividindo-se 38 por 26 dá um resto 12=R ou seja, pelo 
Teorema obtém-se 141226 =−=r . Assim, ( )26mod1438 =− 
Solução ( )c : 
m
a
R de resto= 
Como 0<a e 0=R temos: 0=r . 
 
 
8 
 
26
26
 de resto 
26
26
 de resto =
−
=R , dividindo-se 26 por 26 obtém-se um resto 0=R . Assim, 
( )26mod026 =− . 
Na Aritmética usual, cada número não-nulo a tem um recíproco, ou inverso 
multiplicativo, denotado por 1−a , tal que 111 == −− aaaa . 
Já, na Aritmética modular, tem-se o seguinte conceito correspondente: 
Definição: Dado um número a em mZ , diz-se que um número 
1−
a em mZ é um recíproco, 
ou inverso multiplicativo de a módulo m se ( )maaaa mod111 ≡= −− . 
Pode ser provado que se a e m não têm fatores primos comuns, então a tem um único 
recíproco módulo m ; analogamente, se a e m têm um fator primo comum, então a não tem 
recíproco módulo m . 
Para uma referência futura, fornece-se a seguinte tabela de recíprocos módulo 26: 
 
Tabela 2 – Recíprocos Módulo 26 
 
a 1 3 5 7 9 11 15 17 19 21 23 25 
1−
a 1 9 21 15 3 19 7 23 11 5 17 25 
 
Cada cifra útil deve possuir um procedimento para decifrar. Para decifrar as Cifras de 
Hill, usa-se a inversa (mod 26) da matriz codificadora. Ou seja, se m é um inteiro positivo, 
pode-se dizer que uma matriz A com entradas em mZ é invertível módulo m se existir uma 
matriz B com entradas em Zm tal que ( )mIBAAB mod≡= 
Suponha-se agora que 






=
2221
1211
aa
aa
A é invertível módulo 26 e que esta matriz é usada para uma 2-Cifra de Hill. Se 






=
2
1
p
p
p é um vetor comum, então pAc ⋅= é o correspondente vetor cifrado e cAp 1−= . 
Assim, cada vetor comum pode ser recuperado do correspondente vetorcifrado pela 
multiplicação à esquerda por ( )26mod1−A . 
Em Aritmética Modular, uma matriz quadrada é invertível se, e somente se, 0det ≠A 
ou, equivalentemente, Adet tem um recíproco. 
(2) 
 
 
9 
 
A inversa de ( )26moddet A é dada por ( ) ( )26mod11 





−
−
−=
−−
ac
bd
bcadA . 
Então, para se encontrar a inversa de 





=
27
19
A módulo 26, faz-se: 
117181729det =−=⋅−⋅=−= bcadA , de modo que, pela Tabela 2, 
( ) ( )26mod1911 11 ≡=− −−bcad 
Assim, por ( )2 , 
( )26mod
1523
712
171133
1938
97
12
191 





=





−
−
=





−
−
=
−A 
Conferindo, 






=





=











=
−
10
01
79130
78131
1523
712
27
191AA 
Analogamente, ( )26mod1 IAA ≡− 
Para decifrar uma Cifra de Hill, que foi criptografada como, por exemplo, a matriz 
acima, basta multiplicar-se cada vetor cifrado pela inversa de A e, assim, obtém-se os 
equivalentes alfabéticos destes vetores que fornecem a mensagem já decifrada. 
Com o advento da revolução industrial, a criptografia evoluiu no sentido de 
mecanização e automatização. O uso de códigos secretos, até então quase de uso exclusivo de 
militares e diplomatas, foi-se gradualmente difundindo e o campo das suas utilizações 
estende-se hoje a fichas médicas em hospitais, a empresas, cuja intenção é preservar 
informações técnicas da sua laboração e dos seus equipamentos, às atividades bancárias, ao 
tratamento e circulação de dados científicos bem como a salvaguarda de informações em 
redes informáticas. Tudo isso faz com que a criptografia seja hoje uma disciplina científica, 
ativamente estudada por matemáticos, especialistas em estatística e cientistas ligados a 
sistemas informáticos. 
 
Conclusão 
O uso da criptografia consiste em evitar violações dos sistemas eletrônicos e proteger 
informações sigilosas, garantindo de uma maneira mais segura que informações transmitidas 
não serão copiadas, modificadas ou falsificadas. Hoje em dia, o principal impulso para o 
desenvolvimento de códigos seguros é dado pelas comunicações confidenciais entre 
computadores, em telecomunicações, utilizando a Teoria dos Números e a Álgebra Linear. 
Com este trabalho, observa-se a importância tanto do conteúdo de operações modulares 
 
 
10 
 
(Teoria dos Números) como do produto de matrizes (Álgebra Linear) bem como, a 
Matemática Discreta para codificar e decodificar informações sigilosas. A criptografia é hoje 
considerada uma ciência no campo das Ciências Exatas, sendo a Teoria dos Números, 
Álgebra Linear e a Matemática Discreta as responsáveis por toda a sua parte teórica. 
 
Referências Bibliográficas 
 
COUTINHO,S.C.1997 Números Inteiros e Criptografia RSA.Rio de Janeiro:IMPA, 
SBM. 
HOWARD,A.e RORRES,C.2001.Álgebra Linear com Aplicações. 8ª ed. Porto Alegre: ed. 
Bookmann. 
MARCACINI, A. T. R. 2002 Direito e Informática – Uma abordagem jurídica sobre 
criptografia. Rio de Janeiro: ed. Forense.