CRIPTOGRAFIA
Waldizar Borges de Araújo França1
RESUMO
A Criptografia é a ciência que oculta o significado de uma mensagem e tem como ferramenta os recursos
matemáticos para cifrar e decifrar mensagens. O ato de cifrar consiste em transformar um texto normal em
texto secreto, e o ato de decodificar é a operação inversa, consiste em transformar um texto cifrado em texto
normal. Veremos os conceitos históricos da criptografia, suas definições e aplicações matemáticas.
Palavra-chave: criptografia; matemática; cifra.
1.
INTRODUÇÃO
Este artigo mostra as diferentes formas em que a matemática é aplicada na criptografia para
o desenvolvimento de códigos, cifras e técnicas para mascarar uma mensagem de modo que
só pessoa autorizada possa ter acesso ao seu conteúdo.
Desde os primórdios que o homem tem sentido a necessidade de guardar segredos. Sejam
segredos familiares, segredos sentimentais, segredos pessoais, segredos religiosos, ou
segredos militares e governamentais. Tão forte quanto a necessidade nata da espécie
humana de guardar segredo sobre determinados assuntos é a vontade dos mesmos humanos
de desvendar esses segredos. Seja por dinheiro, poder, vingança, curiosidade, arrogância,
ou qualquer outro sentimento essa tem sido uma batalha que, ao longo dos anos vem sendo
travada entre aqueles que querem guardar segredos e os que querem desvendar esses
segredos.
Com o avanço cada vez maior dos poderes das Redes de Computadores, o mundo tende a
ficar menor, perder fronteiras, encurtar distâncias. Hoje, com um simples apertar de teclas,
pode-se intercambiar informações através dos cinco continentes em questão de minutos ou
até segundos.
Este avanço faz com que a informação e o controle sobre ela sejam estratégicos para os
governos e para as empresas. E, quanto maior o fluxo de informações em redes de
telecomunicações, ou maior a quantidade de informação armazenada em meios
computacionais, maior é a necessidade de empresas, governos e até de pessoas físicas de se
protegerem contra uma nova ameaça que está crescendo proporcionalmente ao
desenvolvimento da informática. Trata-se do furto de informação sigilosa e estratégica,
armazenada em meios computacionais, ou da adulteração de transações através do poder
das telecomunicações.
Pensando na necessidade de se criar ferramentas capazes de proteger a informação e de
prover segurança aos dados armazenados e transmitidos pelas organizações através do
mundo, veio a motivação para se estudar Criptografia. Sendo que através desta disciplina
podem-se criar aplicações que dêem maior segurança às informações digitais.
1
Licenciando do Curso de Matemática da Universidade Católica de Brasília – UCB – DF.
Na palavra criptografia, “Cripto" vem do grego "kryptos" e significa oculto, envolto,
escondido. Também do grego, "graphos" significa escrever, "logos" significa estudo,
ciência e "analysis" significa decomposição. É também uma ciência matemática que se
dedica ao estudo de métodos de comunicação secreta. É composta pelas disciplinas de
criptografia e criptoanálise. A criptografia estuda os métodos para cifrar ou codificar uma
mensagem de modo que só o destinatário legítimo é capaz de interpretar o conteúdo da
mensagem sendo ilegível para terceiros e intrusos. Os procedimentos inversos, chamados
de decifragem, são os objetivos de estudo da criptoanálise. Decodificar é o procedimento
que o usuário legítimo do código realiza quando recebe uma mensagem codificada e quer
lê-la. Já decifrar é o procedimento feito para ler uma mensagem codificada sem ser um
destinatário legítimo. O principal propósito da criptografia é permitir a transmissão de
mensagem por canais não seguros empregando técnicas matemáticas para tornar o conteúdo
da mensagem restrita ao destinatário legítimo. Esta ciência é tão antiga quanto a própria
escrita, porém somente depois da Segunda Guerra Mundial, com a invenção do computador
e o desenvolvimento da teoria da informação, a criptografia realmente floresceu.
2.
HISTÓRIA
Cerca de 1900 a.C. acontece o primeiro relato da historia da criptografia. Numa vila egípcia
perto do rio Nilo chamada Menet Khufu. Khnumhotep II era um arquiteto do faraó
Amenemhet II. Ele construiu alguns monumentos para o faraó, os quais precisavam ser
documentados. Nem é preciso dizer que estas informações, escritas em tabletes de argila,
não eram para cair no domínio público. O escriba de Khnumhotep II teve a idéia de
substituir algumas palavras ou trechos de texto destes tabletes. Caso o documento fosse
roubado, o ladrão não encontraria o caminho que o levaria ao tesouro - morreria de fome,
perdido nas catacumbas da pirâmide. Pode ser considerado o primeiro exemplo
documentado da escrita cifrada.
A história da criptografia aconteceu em três fases distintas, a criptografia manual, a
criptografia por máquinas e a criptografia em rede.
2.1
A criptografia manual.
A criptografia manual são os algoritmos considerados clássicos. Podemos chamar assim a
todos os sistemas de criptografia anteriores à 2ª Guerra Mundial. Estas técnicas têm em
comum o fato de poderem ser empregadas usando-se apenas lápis e papel, e poderem ser
decifradas praticamente da mesma forma. Atualmente com a ajuda dos computadores, as
mensagens criptografadas empregando-se estes algoritmos são facilmente decifradas, por
isso caíram rapidamente em desuso. Podemos citar como exemplos:
Exemplo 1: O código de César que apesar da criptologia2 estar bastante avançada na época,
em 50 a.C. usava um sistema de substituição. Suetônio, escritor romano que viveu no início
2
Disciplina científica que reúne e estuda os conhecimentos (matemáticos, computacionais, psicológicos,
filológicos, etc.) e técnicas necessários à criptoanálise (solução de criptogramas) e à criptografia (escrita
codificada).
da era cristã (69 d.C.), em Vida dos Césares, escreveu a biografia dos imperadores romanos
de Júlio César a Domiciano. Conta que Júlio César usava na sua correspondência particular
um código de substituição muito simples no qual cada letra da mensagem original era
substituída pela letra que a seguia em três posições no alfabeto: a letra A era substituída por
D, a B por E, e assim até a última letra Z, que é cifrada com a letra C (veja a tabela abaixo).
Tabela 1: Código de 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
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
Hoje em dia, porém, se denomina de código de César qualquer cifra na qual cada letra da
mensagem original seja substituída por outra deslocada um número fixo de posições, não
necessariamente três. Um exemplo é o código que, ainda segundo Suetônio, era usado por
Augusto, onde a letra A era substituída por B, a B por C e assim sucessivamente. Como o
alfabeto romano possui 26 letras, são possíveis 26 códigos de César, dos quais um (o do
deslocamento zero) não altera a mensagem original. Uma simples criptoanálise estatística,
baseada na característica estatística da língua, é suficiente para decifrar o texto.
Exemplo 2: O cifrário de Francis Bacon, que foi um filósofo, escritor e político inglês, por
volta do século XVI, detalhou seu sistema de substituição usando um alfabeto de 24 letras
onde I=J e U=V. Para cada uma das letras do alfabeto é atribuído um grupo de 5 caracteres
compostos pelas letras "a" e "b". Como são utilizadas apenas duas letras para a formação
dos grupos, considera-se esta cifra como binária. Como os grupos são formados por 5
letras, considera-se a cifra como sendo de 5 bits e cada caractere possui duas possibilidades
poderíamos gerar 25 = 32 grupos e consequentemente representar 32 letras distintas.
A formação dos grupos segue uma seqüência lógica de fácil de memorizar. Além disso, os
"a" e "b" podem ser substituídos por 0 e 1. Analise a tabela abaixo:
Tabela 2: Cifrário de Francis Bacon
Letra Grupo Binário
Letra
A
aaaaa 00000
N
B
aaaab 00001
O
C
aaaba 00010
P
D
aaabb 00011
Q
E
aabaa 00100
R
G
aabba 00110
T
H
aabbb 00111
U/V
I/J
abaaa 01000
W
K
abaab 01001
X
L
ababa 01010
Y
M
ababb 01011
Z
Grupo
abbaa
abbab
abbba
abbbb
baaaa
baaba
baabb
babaa
babab
babba
babbb
Binário
01100
01101
01110
01111
10000
10010
10011
10100
10101
10110
10111
Exemplo 3: O Código Braille3 criado por Louis Braille (1809-1852), educador francês, que
ficou cego aos 3 anos de idade. Interessou-se por um sistema de escrita, apresentado na
escola Charles Barbier, no qual uma mensagem codificada em pontos era cunhada em
papel-cartão. Aos 15 anos de idade trabalhou numa adaptação, escrita com um instrumento
simples que é um sistema de símbolos onde cada caractere é formado por uma matriz de 6
pontos dos quais pelo um se destaca em relação aos outros. Temos então a possibilidade de
representar 26 − 1 caracteres distintos.
Tabela 3: Relação entre letra e símbolo do código Braille.
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
Hoje em dia existem vários dispositivos para escrita em Braille, desde muito simples até
sofisticados dispositivos eletrônicos. O mais simples é uma lousa com uma régua perfurada
onde, com o auxílio de um estilete, é possível produzir os pontos em relevo. Existem
também uma máquina de escrever especial, impressoras ligadas a computador que
produzem os relevos desejados, dispositivos com voz artifical que "lêem" braille, teclados
de computador especiais e "anotadores" eletrônicos associados a máquina de calcular,
calendário, etc.
2.2
A criptografia por máquinas.
Na criptografia por máquinas, uma tabela predeterminada era usada em conjunto com uma
máquina, onde o operador desta, usando a tabela e manipulando a máquina podia enviar
uma mensagem criptografada. Como exemplo de máquina de criptografia, podemos citar:
Exemplo 4: O código Morse4: Samuel Morse (1791-1872) em 1840 desenvolve o código
que recebeu o seu nome. Originalmente, Morse imaginou numerar todas as palavras e em
transmitir seus números através do telégrafo. O receptor, usando um enorme "dicionário",
decifraria a mensagem onde as letras do alfabeto foram definidas pelo padrão "ponto e
traço". Este novo código reconhecia quatro estados: voltagem-ligada longa (traço),
voltagem-ligada curta (ponto), voltagem-desligada longa (espaço entre caracteres e
palavras) e voltagem-desligada curta (espaço entre pontos e traços). Cada caractere (letras,
números, sinais gráficos) possui seu próprio conjunto único de pontos e traços.
3
4
Não tem finalidade de esconder mensagem, pelo contrário, mas é um bom exemplo de criptografia manual.
Idem. Só que aqui temos um bom exemplo de criptografia de máquina.
Tabela 4: Código Morse original:
a •—
l •—••
x
b —•••
m ——
y
c —•—• n —•
z
d —••
o — — — ch
e •
p •——• w
——•
f ••—•
q
ä
—
g ——•
r •—•
é/ë
h ••••
s •••
ï
i
j
k
••
•——
—
—•—
t
—
ñ
u
••—
ö
v
•••—
ü
—••—
—•——
——••
————
•——
1 •————
2 ••———
3 •••——
4 ••••—
5 •••••
•—•—
6
—••••
••—••
7 ——•••
—••—— 8 ———••
——•—
9 ————•
—
————
———• 0
—
••——
Podemos traduzir os termos utilizados para os dias de hoje para significarem condições
binárias de "1" (ponto) e "0" (traço). O alfabeto Morse é um código baseado em 5 posições,
ou seja, não precisa mais do que 5 posições para que todas as letras e números sejam
padronizados.
Na realidade, o aspecto mais importante quando se fala de Morse não é o código e sim a
possibilidade de transmitir informações à distância. Através dos fios correm sinais elétricos
que, devidamente concatenados, representam mensagens.
Exemplo 5: O Código Enigma5: código gerado pela Máquina Enigma, usada pelos alemães
na Segunda Guerra Mundial, que consistia de um teclado ligado a uma unidade
codificadora. O codificador tinha três rotores separados e as posições dos rotores
determinavam como cada letra no teclado seria codificada. O que tornava o código da
Enigma tão difícil de quebrar era o enorme número de modos nos quais a máquina podia
ser regulada. Em primeiro lugar, os três rotores na máquina eram escolhidos de uma seleção
de cinco que podia ser mudada e trocada para confundir os adversários. Em segundo lugar,
cada rotor podia ser posicionado em 26 modos diferentes. Isto significava que a máquina
podia ser regulada em milhões de modos diferentes. E além das permutações permitidas
pelos rotores, as conexões no quadro de chaveamento, na parte detrás da máquina, podiam
ser mudadas manualmente para fornecer um total de 150 trilhões de regulagens possíveis. E
para aumentar ainda mais a segurança, os três rotores mudavam de oritentação
continuamente, de modo que, cada vez que a letra era transmitida, a regulagem da máquina,
e portanto o código, iria mudar de uma letra para outras. Assim se alguém digitasse
“DODO” no teclado iria gerar a mensagem “FGTB”, por exemplo – o “D” e o “O” eram
transmitidos duas vezes, mas codificados de modo diferente a cada vez.
O grande salto em direção à decodificação do Código Enigma aconteceu quando se
percebeu que a máquina Enigma não podia codificar uma letra nela mesma, isto é, se o
5
Código “quebrado” pela equipe chefiada pelo matemático inglês Alan Turing.
emissor, por exemplo, teclasse a letra “B”, então, independente do ajuste, a máquina
poderia transmitir todo tipo de letra, exceto “B”.
2.3
A criptografia em rede.
Os sistemas de criptografia clássicos perderam sua eficácia devido à facilidade com que
atualmente são decodificados/criptanalizados empregando-se qualquer computador
doméstico, mas que foram empregados com êxito até princípios do século XX. Hoje em em
dia a criptografia que oferece maiôs segurança é a em rede.
Na criptografia em rede, a mensagem é criptografada usando-se algoritmos, gerando
diversos códigos que executam a criptografia. Podemos citar também que com o advento da
internet e sua popularização a criptografia em rede tem sido responsável pelo surgimento
do comércio eletrônico, visto que esta é essencial para que uma empresa virtual possa ter a
confiança de seus clientes na hora de comprar. Podemos citar como exemplos:
Exemplo 6: Algoritmo DES6 que utiliza a Criptografia simétrica que é conhecida como
“Criptografia Convencional”. O poder da cifra é medido pelo tamanho da chave (Num
sistema de encriptação, corresponde a um nome, uma palavra, uma frase, etc, que permite,
mediante o algoritmo de encriptação, cifrar ou decifrar uma mensagem.), geralmente as
chaves de 40 bits são consideradas fracas e as de 128 bits ou mais, as mais fortes. Os
algoritmos simétricos podem ser divididos em cifras de fluxo ou seqüenciais e em cifras de
bloco. As cifras de fluxo encriptam um texto claro bit a bit, ao passo que as cifras de bloco
usam conjuntos com um número fixo de bits (geralmente 64 bits nas cifras modernas) como
unidades de cifragem.
Esta cifra utiliza uma única chave secreta, logo antes de duas entidades estabelecerem um
canal seguro, é preciso que ambos, tanto o emissor quanto ao receptor, compartilhem suas
chaves respectivas.
Apesar de sua simplicidade, existem alguns problemas nesta cifra, pois cada par necessita
de uma chave secreta para se comunicar de forma segura. Portanto, estas devem ser
trocadas entre as partes e armazenadas de forma segura, o que nem sempre é possível de se
garantir. A criptografia simétrica não garante a identidade de quem enviou ou recebeu a
mensagem. A quantidade de usuários em uma rede pode dificultar o gerenciamento das
chaves.
Exemplo 7: No algoritmo RSA7 as cifras já são chamadas de cifras assimétricas ou de
algoritmos de chave pública, permitem que a chave seja de domínio público - pode até ser
publicada em jornais ou revistas. Qualquer pessoa pode, então, cifrar mensagens utilizando
a chave, mas apenas o destinatário e real proprietário da chave será capaz de decifrar o
texto porque é o único que conhece a chave decifrante. A chave cifrante também é chamada
6
Data Encryption Standart (DES): algoritmo de criptografia desenvolvido na década de 70 pelo National
Bureau of Standarts com ajuda da National Security Agency (USA).
7
O Código leva as iniciais dos sobrenomes de seus criadores: Ronald L. Rivest, Adi Shamir e Leonard M.
Adleman.
de chave pública e a chave decifrante de chave privada ou chave secreta.
Para contornar os problemas da criptografia convencional surgiram os algoritmos que
utilizam chave pública e privada. A idéia é que a criptografia de uma mensagem seja feita
utilizando a chave pública e sua decriptografia com a chave privada, ou vice-versa. Os
algoritmos de chave pública e privada exploram propriedades específicas dos números
primos e, principalmente, a dificuldade de fatorá-los, mesmo em computadores rápidos.
3
DESENVOLVIMENTO
Algumas aplicações matemáticas são freqüentemente abordadas quando tratamos de
assuntos como a criptografia. A seguir serão abordados tópicos matemáticos, que são vistos
a título de ensino médio, relacionado à criptografia.
3.1
Análise combinatória.
Uma das grandes aplicações da análise combinatória na criptologia, e talvez a primeira que
nos ocorre, é o número de alfabetos cifrantes possíveis. Se considerarmos o alfabeto
ocidental da atualidade, com 26 letras, quantos alfabetos cifrantes podem ser obtidos?
Sabemos que um alfabeto cifrante não pode ter letras repetidas e precisa conter todas as
letras do alfabeto original. Se apenas as posições das letras são alteradas, sabemos que se
trata de uma permutação simples. Então vamos ao cálculo das possibilidades:
P26 = 26!
P26 = 26 · 25 · 24 · ... · 3 · 2 · 1
P26 = 403.291.461.126.605.635.584.000.000
Ou seja, o número de alfabetos cifrantes possíveis é maior que espantosos 400 septilhões!
Se alguém quiser encontrar um determinado alfabeto cifrante através da "força bruta", ou
seja, tentando cada uma das possibilidades, e gastar apenas 1 minuto para cada
possibilidade, precisaria de pelo menos... a eternidade para encontrar o alfabeto cifrante
correto.
403.291.461.126.605.635.584.000.000 min = 6.721.524.352.110.093.926.400.000 horas
6.721.524.352.110.093.926.400.000 horas = 280.063.514.671.253.913.600.000 dias
280.063.514.671.253.913.600.000 dias = 9.335.450.489.041.797.120.000 meses
9.335.450.489.041.797.120.000 meses = 777.954.207.420.149.760.000 anos
Se considerarmos que a solução seja encontrada a "meio do caminho", ainda restam cerca
de 390 quatrilhões (388.977.103.710.074.880) de milênios!
3.2
Aritmética modular
Quando 15+15 são 6? Se analisarmos esta soma sem questionar, falaremos sem medo que
nunca. Agora, se pensarmos em horas, esta conta está correta, pois 15 horas mais 15 horas,
a partir de 0 hora, são 6 horas. Qualquer fenômeno cíclico como este, vai se tornar uma
aritmética distinta da que conhecemos no segundo grau. Esta aritmética é conhecida como
aritmética modular. Voltemos novamente ao exemplo do relógio. Como contamos o tempo
de 12 em 12 horas, o conjunto de cifras para expressar as horas são 12 (vão de 0 a 11). Se o
conjunto de cifras disponíveis no mostrador é limitado, sabemos imediatamente que
estamos lidando com a aritmética modular e que o relógio trabalha com módulo 12.
Ver as horas no mostrador é um procedimento imediato: mostrador no 3 indica que são 3
horas; mostrador no 8 indica que são 8 horas. Mas quando o mostrador chega nas 11 horas,
a próxima hora será 0. Que conta é esta? Somamos 11 + 1. Agora apliquemos o módulo 12:
11 + 1 = 12 e 12 ÷ 12 = 1 com resto 0. Da mesma forma, 11 + 5 = 16 e 16 ÷ 12 = 1 com
resto 4. Ou seja, sempre que o resultado da soma ultrapassar o maior valor do conjunto
(maior que 11), aplicamos o módulo 12. Por exemplo, 5 + 3 = 8 não precisa de ajuste.
Sabemos também que uma divisão nada mais é do que uma sucessão de subtrações. Veja o
exemplo: 36 ÷ 12 = 3 com resto 0 ou 36 - 12 = 24, 24 - 12 = 12 e 12 - 12 = 0. Fizemos três
subtrações até obtermos um número menor do que 12, ou seja, o resto. Parece bobagem,
mas é muito importante e, principalmente, muito prático.
Nos exemplos acima sempre somamos horas. Se, por exemplo, quisermos subtrair 15 de 3
horas, teríamos o seguinte cálculo: 3 - 15 = -12. Novamente caímos fora do conjunto de 0 a
11, portanto, precisamos aplicar um ajuste: -12 ÷ 12 = -1 com resto 0. Agora considere
subtrair 17 de 3 horas, ou seja, 3 - 17 = -14 e -14 ÷ 12 = -1 com resto -2, o que nos deixa
novamente fora do conjunto de 0 a 11. É neste ponto que é importante entender o
complemento de 12 (porque estamos trabalhando com módulo 12). Observe a tabela 5:
Tabela 5: Módulo 12.
Conjunto das Cifras 0
Complemento
12
Módulo 12
12
1
11
12
2
10
12
3
9
12
4
8
12
5
7
12
6
6
12
7
5
12
8
4
12
9
3
12
10
2
12
11
1
12
Analisando a tabela dos complementos verificamos que o complemento de 0 é 12, de 1 é 11
e assim sucessivamente. Ao mesmo tempo podemos notar que, subtraindo o complemento
do módulo 12, obtemos a cifra do conjunto correspondente, ou seja: 12 - 12 = 0, 12 - 11 =
1, etc, ou seja, o processo é reversível. Se quisermos encontrar a cifra correspondente a -2
no módulo 12, basta calcular 12 - 2 = 10.
Considerando que o número de caracteres disponíveis para se escrever (e cifrar) uma
mensagem seja finito, já entramos no ramo da aritmética modular. O alfabeto latino
completo possui 26 letras, portanto, vamos trabalhar com módulo 26. Numerando as letras
de 0 a 25, qualquer cálculo que se queira efetuar segue as mesmas regras explicadas para o
relógio. Imagine que você queira "subtrair" F de J: J corresponde a 9 e F a 5, então J - F = 9
- 5 = 4 que corresponde a E. Da mesma forma, T + 10 será 19 + 10 = 29 e 29 ÷ 26 = 1 com
resto 3, que corresponde ao D. Ou então T + 38 = 57 e 57 - 26 = 31 - 26 = 5, que
corresponde ao F. C - 10 será 2 - 10 = -8 e a letra correspondente será 26 - 8 = 18 (pelo
complemento) que é o S.
3.3
Estatística
A estatística também está relacionada com a criptografia nas cifras por substituição uma
simples análise estatística, baseada na característica da língua, é suficiente para decifrar o
texto. Na freqüência da ocorrência de letras no português do Brasil, temos algumas tabelas
ilustradas a seguir:
Histograma por Ordem alfabética .
Histograma por Ordem de Freqüência.
Figura 1: histograma da freqüência da ocorrência de letras no português do Brasil.
Tabela 6: freqüências das letras em percentuais.
Letra
A
B
C
D
E
F
G
H
I
J
K
L
M
Freq.%
14.63
1.04
3.88
4.99
12.57
1.02
1.30
1.28
6.18
0.40
0.02
2.78
4.74
Letra
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Freq.%
5.05
10.73
2.52
1.20
6.53
7.81
4.34
4.63
1.67
0.01
0.21
0.01
0.47
Tem-se como característica do português do Brasil o comprimento médio das palavras que
é de 4.53 letras e quando as letras são ordenadas pela freqüência, formam grupos bem
definidos:
Tabela 7: freqüência das letras divididas por grupos.
Letras
6 vogais: A, E, I, O, U, (Y)
20 consoantes
5 de frequência alta: S, R, N, D, M
10 de frequência média: T, C, L, P, V, G, H, Q, B, F
6 de frequência baixa: Z, J, X, K, W
Freq.
48.75 %
49.12 %
21.03 %
1.10 %
100.00 %
As vogais A, E, I, O, U e as consoantes S, R, N, D, M formam mais de 3/4 dos textos em
Português e a média de vogais a cada 10 letras é de 4.88.
3.4
Matrizes
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.
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 Z será atribuído
o valor zero, pois estaremos interessados em trabalhar com aritmética módulo 26.
Tabela 8: Relação de letras com 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 0
Para transformarmos um texto em texto cifrado seguiremos os seguintes procedimentos:
Passo 1. Escolha uma matriz 2x2.
A=
a11
a 21
a12
a 22
Com entradas inteiras para efetuar a codificação.
Passo 2. Agrupe letras sucessivas de 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; substitua
cada letra de texto de texto comum por seu valor numérico
Passo 3. Converta cada par sucessivo p1 p 2 de letras de texto comum em um vetor-coluna
p=
p1
p2
E forme o produto A.p .Nós chamamos p de vetor comum e A.p o correspondente vetor
cifrado.
Passo 4. Converta cada vetor cifrado em seu equivalente alfabético.
Exemplo 8: Cifra de Hill de uma mensagem.
Use a matriz:
1 2
0 3
Para obter a cifra de Hill da mensagem de texto comum WALDIZAR. Agrupa-se o texto
comum em pares de letras, temos:
WA
LD
IZ
Ou, equivalentemente, usando a tabela 8: 23 1
AR
12 4
Para codificar o par WA efetua-se o produto matricial:
90
1 2
0 3
⋅
23
1
1 18
=
25
3
Que fornece o texto cifrado DC, usando a tabela 8.
Para codificar o par LD efetua-se o produto matricial:
1 2 12
20
⋅
=
0 3
4
12
Que fornece o texto cifrado IL, usando a tabela 8.
Para codificar o par IZ efetua-se o produto matricial:
1 2 9
9
⋅
=
0 3 0
0
Que fornece o texto cifrado IZ, usando a tabela 8.
E finalmente para codificar o par AR efetua-se o produto matricial:
1 2
1
37
⋅
=
0 3 18
54
(1)
Aqui temos um problema, pois os números 37 e 54 não possuem equivalências alfabéticas
com a tabela 8. para resolver este problema utilizaremos o resto da divisão euclidiana
destes números por 26 e como o resto da divisão é um dos números 0, 1, 2, ..., 25, este
procedimento sempre fornece um inteiro com equivalente alfabético.
Assim em (1), deve se substituir 37 por 11 e 54 por 2, que equivale na tabela 8 com KB.
Coletando os pares obtêm-se a mensagem cifrada completa:
DC
IL
IZ
ZB
Seria transmitida como uma única cadeia sem espaços: DCILIZZB
Como o texto foi agrupado em pares e criptografado por uma matriz 2x2, dizemos que a
cifra de Hill é uma matriz 2-cifra de Hill. É possível criptografar com uma matriz 3x3 com
entradas inteiras. Em geral, para n-cifra de Hill agrupamos o texto comum em conjuntos de
n letras e codificamos com uma matriz codificadora nxn de entradas inteiras.
Para decifrar as cifras de Hill, usamos a inversa (mod 26) da matriz codificadora. Neste tipo
de criptografia é importante saber quais matrizes são invertíveis módulo 26. Em geral, uma
matriz quadrada A é invertível se, e somente se, det(A) ≠ 0 (pois nos números reais basta o
número ser diferente de zero para ter inverso multiplicativo). Na aritmética módulo 26, o
det(A) deverá ter inverso módulo 26, pois na fórmula da inversa de A, aparece o inverso do
determinante. Agora, um número n terá inverso módulo 26 se e somente se mdc (n, 26)=1,
ou seja, n e 26 são co-primos (não têm fatores em comum). Assim, só existirá inversa
módulo 26 se o det(A) não for divisível por 2 ou 13. Veja tabela 9 abaixo.
a b
, podemos obter a inversa de A (mod 26) com
c d
det(A)=ad - bc não divisível por 2 ou 13, pela expressão:
Sendo assim, dada uma matriz A =
A−1 = (ad − bc )−1
d −b
−c a
(mod 26)
Onde (ad − bc ) é o inverso multiplicativo de det(A). Para referencia futura, abaixo temos
a seguinte tabela com os inversos multiplicativos módulo 26 que, por exemplo, para
encontramos o inverso multiplicativo do número 3 teremos que encontrar o número x que
satisfaz a equação módular 3x = 1 (mod 26), que obteríamos como resposta o número 9.
−1
Tabela 9: inversos multiplicativos módulo 26
a
1
3
5
7
9
11
a −1
1
9
21
15
3
19
15
17
19
21
23
25
7
23
11
5
17
25
Exemplo 9: Decifrando uma cifra de Hill.
5 6
, primeiramente
2 3
obteremos a inversa de A (mod 26). Det(A)= 3 e pela tabela 9 o inverso multiplicativo de 3
é igual a 9. Sendo assim:
Temos a mensagem EOAF que foi codificada pela matriz A =
A−1 = 9
3 −6
27 − 54
1 24
=
=
(mod 26) .
−2 5
− 18 45
8 19
Pela tabela 8, o equivalente numérico do texto cifrado é: 5
15
1
6
Para obter os pares de texto comum, nós multiplicamos cada vetor pela inversa de A.
1 24 5
365
1
=
=
(mod 26)
8 19 15
325
13
1 24 1
145
15
=
=
(mod 26)
8 19 6
122
18
Obtemos a seqüência numérica 1 13 15 18, que pela tabela 8, os equivalentes alfabéticos
destes números fornecem a palavra AMOR.
3.5
Funções
O principio básico da criptografia é encontrar uma transformação (função) bijetiva f entre
um conjunto de mensagens escritas em um determinado alfabeto (letras, números) para um
conjunto de mensagens codificadas. Como f é inversível existe a garantia de o processo ser
reversível, o que vai possibilitar a revelação das mensagens pelos destinatários. O grande
segredo da criptografia está justamente em esconder de maneira eficiente o processo
(chave) para a inversão de f. Abaixo temos um diagrama que ajuda a entender a idéia do
processo criptográfico: Aqui podemos dar um exemplo didático: para começar criamos uma
tabela que relaciona números com letras do nosso alfabeto:
Tabela 10: Relação de letras com 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
Agora, escolhemos uma função f(x) que vai receber o valor da letra que queremos
transmitir e gerar um outro valor através de f(x). Ou seja, a imagem de f é que será
transmitida. Vamos supor que f seja a função f(x) = 3x + 5, que é também chamada de
função cifradora. O emissor vai transmitir a palavra MONOGRAFIA. Então, conforme as
tabelas acima têm a seguinte correspondência:
M = 13
O = 15
N = 14
O = 15
G=7
R = 18
A=1
F=6
I=9
A=1
=>
=>
=>
=>
=>
=>
=>
=>
=>
=>
f (M) = f (13) = 44
f (O) = f (15) = 50
f (N) = f (14) = 47
f (O) = f (15) = 50
f (G) = f (7) = 26
f (R) = f (18) = 59
f (A) = f (1) = 8
f (F) = f (6) = 23
f (I) = f (9) = 32
f (A) = f (1) = 8
A palavra M O N O G R A F I A ao passar pela função cifradora será transformada na
seqüência de números 31 50 47 50 26 59 8 23 32 8, que é a mensagem que o receptor
receberá. O receptor ao receber a mensagem codificada (seqüência numérica), realizará a
( x − 5)
(8 − 5)
operação inversa f −1 ( x) =
. Por exemplo, o receptor recebeu 8, f −1 (8) =
=1
3
3
= f (1) = f (A) , logo 8 (destino) = A (origem), e assim sucessivamente até recompor
totalmente a mensagem original.
4,
COSIDERACOES FINAIS
Os resultados obtidos nesse artigo revelam a importância da criptografia, e que ela não
poderia ser tão bem desenvolvida sem a presença da matemática, pois nota-se maior
confiabilidade em ocultar uma mensagem quando usamos essa ciência. Os ramos da
matemática que são aplicados à criptografia são diversos é notamos quanto maior o grau de
dificuldade que os aplicamos melhor ocultará a mensagem.
Durante este artigo tive um grande crescimento como professor e educador, pois no ensino
fundamental e médio diariamente somos questionados sobre a aplicação de diversos ramos
da matemática, podendo então agora usar os conhecimentos obtidos com as aplicações da
matemática na criptografia em sala de aula.
5.
REFERÊNCIA BIBLIOGRAFICAS
ANTON, RORRES; Álgebra linear com aplicações. 8ª ed. Porto alegre: Bookman, 2001.
COUTINHO, Severino; Números inteiros e criptografia RSA. 2. ed. Rio de Janeiro:
IMPA, 2003.
DOMINGUES, Hygino H.; IEZZI, Gelson. Álgebra moderna. 2. ed. São Paulo: Atual,
1992.
ROUTO, Terada. Segurança de dados - criptografia em redes de computador. Ed. E.
Blücher, 2000.
SINGH, Simon. O último teorema de Fermat: a história do enigma que confundiu as
maiores mentes do mundo durante 358 anos. Rio de Janeiro: Record, 1998.
TKOTZ,
Viktoria,
Historia
da
<http://www.numaboa.com.br/criptologia>.
criptografia.
Disponível
em