Universidade do Estado do Pará
Centro de Ciências Sociais e Educação
Departamento de Matemática, Estatística e Informática
Licenciatura em Matemática
Alexandre Ferreira da Silva
Renato Marinho Martins
Criptografia: aspectos históricos e matemáticos
Belém – PA
2011
Alexandre Ferreira da Silva
Renato Marinho Martins
Criptografia: aspectos históricos e matemáticos
Trabalho de Conclusão de Curso apresentado como
requisito parcial para a obtenção do grau de
Licenciatura em Matemática, Universidade do Estado
do Pará.
Orientador: Prof. Dr. Pedro Franco de Sá
Belém – PA
2011
Dados Internacionais de Catalogação na publicação
Biblioteca do Centro de Ciências Sociais e Educação da UEPA
Silva, Alexandre Ferreira da
Criptografia: aspectos históricos e matemáticos. / Alexandre Ferreira da Silva, Renato
Marinho Martins. Belém, 2011.
Trabalho de Conclusão de Curso (Licenciatura em Matemática) – Universidade do Estado
do Pará, Belém, 2011.
Orientação de: Pedro Franco de Sá.
1. Teoria dos números 2. Matemática – História 3. Criptografia 4. Algoritmos I. Martins,
Renato Marinho II. Sá, Pedro Franco de (Orientador) III. Título.
CDD: 21 ed. 512.7
Alexandre Ferreira da Silva
Renato Marinho Martins
Criptografia: aspectos históricos e matemáticos
Trabalho de Conclusão de Curso apresentado como
requisito parcial para do grau de Licenciatura em
Matemática, Universidade do Estado do Pará.
Data: _____/______/______
Banca Examinadora
____________________________________ - Orientador
Prof. Pedro Franco de Sá
Dr. em Educação
Universidade do Estado do Pará
____________________________________
Prof. Fábio José da Costa Alves
Dr. em Geofísica
Universidade do Estado do Pará
____________________________________
Profª. Rosineide de Sousa Jucá
Ms. Em Educação
Belém – PA
2011
AGRADECIMENTOS
Bem, se não fosse Deus, possivelmente não estaríamos aqui. Então, quero
agradecer primeiro a Ele, por nos dar essa oportunidade. É meio clichê, mas
realmente devo agradecer, por segundo, aos meus pais, Guilherme Carvalho e
Regina Ferreira, principais responsáveis pela minha educação e por muito do que eu
sou hoje em dia. Não posso deixar de agradecer também a várias pessoas que, às
vezes sem saber, contribuíram bastante na minha vida pessoal, acadêmica e
profissional: meu irmão Lucas, companheiro, inteligente e amigo; a Franci, por ser
uma espécie de segunda mãe, na minha casa; meus camaradas do Rêgo Barros,
responsáveis por alguns dos melhores anos da minha vida; meus amigos da
instituição IFPA, o antigo Cefet, que proporcionou meu primeiro emprego e a minha
linda namorada, que eu amo muito, a Nayara.
Há também alguns professores que trilharam meu caminho e me ajudaram,
de alguma forma, a ser o profissional que hoje sou, como o Luís Otávio e a Deusélia
Nogueira, quando eu ainda estudava no Rêgo Barros; o Arthur, que muito me ajudou
quando eu estagiava na EMATER, em Marituba; a professora Márcia Santos, amiga
e companheira da monitoria da UEPA; o nosso professor e orientador Pedro Sá, que
é uma grande referência e um exemplo a ser seguido, (obrigado pela paciência!);
além do professor Adenílson Camelo, professor que me acompanhou durante o
estágio, no Rêgo Barros.
Não posso terminar sem citar os amigos que fiz na UEPA, que muito me
ajudaram em vários momentos difíceis, mesmo que talvez às vezes nem tivessem
dimensão que estavam me ajudando. São muitos, entre os futuros pedagogos,
secretários trilingues, cientistas da religião, biólogos e matemáticos. Infelizmente,
esse espaço não permite falar de todos. Porém, destaco os caras que eu considero
como verdadeiros irmãos pra mim: André, Itamar, Renato, Saulo e Walmi (vulgos
Ranger, Ítalo, Nattinho, Saulão e Tico), e a nossa mascotinha, a Mayara. Por último
ao Clube do Remo, que não tem me dado muita alegria, mas faz parte da minha vida
e eu tenho fé de que tudo há de melhorar.
Sinceramente, muito obrigado a todos, de coração!
ALEXANDRE FERREIRA DA SILVA
AGRADECIMENTOS
Primeiramente a Deus por me dar ombros mais fortes sempre que precisei
carregar fardos mais pesados.
À UEPA pela qualidade de ensino que permite formar profissionais de
qualidade.
Ao meu orientador, professor Pedro Sá, pelas orientações para a conclusão
deste trabalho e por ser um exemplo de profissional e fonte pessoal de inspiração
para seguir a carreira docente.
Aos meus amigos de UEPA dos cursos de Ciências da Religião, em especial
duas baixinhas que sempre me fazem sorrir, Narah e Monique, e Pedagogia, em
especial à Ellen Cristina pelo companheirismo; e a todos que tornaram meu tempo
nesta instituição mais agradável.
Aos meus amigos de UEPA, de curso, e de vida, em especial Alexandre,
André, Itamar, Saulo, Mayara e Walmi, pelas suas prazerosas companhias durante
todo o curso e por tudo de grandioso que fizemos juntos.
Por fim, aos meus pais. À minha mãe, principal responsável por eu está aqui,
a quem dedico tudo que consegui até hoje.
RENATO MARINHO MARTINS
“Não há fatos eternos, como não há verdades absolutas.”
Nietzsche
“Queima a ponte que acabaste de atravessar.
Para quem não pode recuar só resta avançar.
Até o rato, quando encurralado, ataca o gato.”
Masaharu Taniguchi
RESUMO
No presente trabalho apresenta os resultados de uma pesquisa bibliográfica sobre o
desenvolvimento e principais conceitos da Criptologia, ciência que estuda os
acontecimentos acerca das trocas e interceptações de mensagens sigilosas através
dos tempos. O objetivo do estudo é mostrar como ocorreu o avanço desta ciência
através da história, que remonta os tempos dos antigos faraós até os dias de hoje,
no século XXI, bem como, as suas relações com a matemática, entre cifras antigas e
atuais, até o advento da criptografia de chaves assimétricas. Como principal
exemplo desta, temos a cifra RSA, responsável por garantir formas de comunicação
seguras pela internet. São apontados os elementos matemáticos básicos da cifra,
como as diferentes formas de se obter e verificar números primos, além da
aritmética modular. Também há uma breve discussão sobre as consequências da
segurança proporcionada por esta cifra, assim como a expectativa quanto ao futuro
da Criptologia. Por fim, conclui-se que a criptografia foi e continua sendo de suma
importância à confidencialidade de informações, o que se deve, em grande parte, a
inúmeros matemáticos que dedicaram suas vidas a essa ciência e, às vezes, à suas
nações, atitudes essas decisivas para importantes acontecimentos que contribuíram
para a história da humanidade.
Palavras chave: Criptografia; História da Matemática; Criptologia; criptografia RSA;
Números Primos.
ABSTRACT
The present work presents results from a bibliographic research about the
development and main ideas of Cryptology, a science which studies events about
secret messages exchange and interception through ages. The objective of this
study is to show how this science advanced through history, dating back from the
ancient pharaohs until present time, on century XXI, as well as its interactions with
mathematics, amongst past and present ciphers, until the advent of asymmetric keys
cryptography. As a prime example of asymmetric keys cryptography there is the RSA
cipher, responsible for assuring secured means of communication through Internet.
The cipher’s basic mathematic elements have been pointed out, such as its different
ways for obtaining and checking prime numbers, and also modular arithmetic. In
addition, there is a brief discussion about the consequences of security provided by
RSA cipher and the expectations for the future of Cryptology. Finally, it is possible to
conclude that Cryptology was and still is of great importance to information
confidentiality, most thankfully to innumerous mathematicians who have dedicated
their lives to this science, sometimes to their countries, taking critical decisions
toward important happenings which contributed for the human history.
Key words: Cryptography; history of mathematics; Cryptology; RSA Cryptography;
prime numbers.
LISTA DE FIGURAS
FIGURA 01: Esquema de ramificações da Criptologia ...................................................................... 20
FIGURA 02: O alfabeto hebreu e suas cifras....................................................................................... 23
FIGURA 03: Scytale Espartano ............................................................................................................. 25
FIGURA 04: Cifrante dos Templários ................................................................................................... 30
FIGURA 05: Execução de Maria Stuart, rainha da Escócia ............................................................... 32
FIGURA 06: Disco de Alberti ................................................................................................................. 33
FIGURA 07: Tabula Recta de Johannes Trithemius ........................................................................... 34
FIGURA 08: Máquina de Diferenças nº 2 de Babbage ........................................................................ 39
FIGURA 09: Máquina Enigma................................................................................................................ 42
FIGURA 10: Bomba de Turing............................................................................................................... 46
FIGURA 11: Computador Colossus ..................................................................................................... 49
FIGURA 12: Relógio Analógico............................................................................................................. 53
FIGURA 13: Esquema para obtenção de uma chave sem a necessidade de um encontro físico . 54
FIGURA 14: Gráfico da quantidade de números primos até 100 ...................................................... 67
FIGURA 15: Gráfico da quantidade de números primos até 100.000 ............................................... 68
FIGURA 16: Gráfico de comparação da quantidade real de números primos e os de Gauss ....... 68
LISTA DE TABELAS
TABELA 01: Alfabeto da Cifra de César .............................................................................................. 26
TABELA 02: 10 primeiros números da fórmula polinomial para números primos .......................... 60
TABELA 03: Seis primeiros números de Fermat ................................................................................. 62
TABELA 04: Números primos gerados pela fórmula fatorial ............................................................. 63
TABELA 05: Crescimento do número de primos, por Gauss ............................................................ 66
TABELA 06: Atribuição de números para as letras do alfabeto ........................................................ 72
TABELA 07: Tempo de operação de operações necessárias para fatorar
................................... 77
TABELA 08: Letras e números correspondentes ................................................................................ 85
TABELA 09: Usando uma chave com a Cifra de Vigenère ................................................................. 88
SUMÁRIO
1. INTRODUÇÃO .................................................................................................................................... 14
2. HISTÓRIA E DESENVOLVIMENTO DA CRIPTOGRAFIA ...................................................................... 16
2.1. CONCEITOS BÁSICOS .................................................................................................................. 16
2.2. IDADE ANTIGA ............................................................................................................................ 20
2.3. IDADE MÉDIA.............................................................................................................................. 25
2.4. IDADE MODERNA ....................................................................................................................... 30
2.5. IDADE CONTEMPORÂNEA .......................................................................................................... 36
2.5.1. Popularização da Criptografia e a quebra da Cifra de Vigenère ....................................... 36
2.5.2. O surgimento da Criptografia mecânica ............................................................................ 39
2.5.3. As contribuições de Bletchley Park e Alan Turing ............................................................. 43
2.5.4. O código Navajo.................................................................................................................. 46
2.5.5. O surgimento da Criptografia computadorizada ............................................................... 47
3. CRIPTOGRAFIA RSA........................................................................................................................... 50
3.1. NECESSIDADES E DESAFIOS DA CRIPTOGRAFIA NA DÉCADA DE 70 ........................................... 50
3.2. NÚMEROS PRIMOS..................................................................................................................... 58
3.2.1. Fórmula Polinomial ............................................................................................................ 59
3.2.2. Números de Mersenne ....................................................................................................... 60
3.2.3. Método de Fermat (em relação aos números de Mersenne) ........................................... 60
3.2.4. Números de Fermat............................................................................................................ 61
3.2.5. Primos de Shophie Germain............................................................................................... 62
3.2.6. Fórmulas Fatoriais .............................................................................................................. 62
3.2.7. Crivo de Eratóstenes........................................................................................................... 63
3.2.8. A pergunta de Gauss .......................................................................................................... 64
3.3. ALGORITMO RSA ........................................................................................................................ 70
3.4. SEGURANÇA ............................................................................................................................... 75
3.4.1. Algoritmo de fatoração de Richard Schroeppel ................................................................ 75
3.4.2. Assinatura Digital ............................................................................................................... 76
3.5. CONSEQUÊNCIAS DA CIFRA RSA ................................................................................................ 77
3.5.1. Liberdade total ou controlada? ......................................................................................... 77
3.5.2. Física Quântica e a Criptologia ........................................................................................... 79
4. CONSIDERAÇÕES FINAIS ................................................................................................................... 82
REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................................................ 84
APÊNDICE A........................................................................................................................................... 88
P á g i n a | 14
1. INTRODUÇÃO
Criptografia. Muitas pessoas já ouviram falar nesse termo, porém a maioria
delas não sabe ao certo o que significa. Alguns se arriscam a dizer que se trata de
algo sigiloso, que apenas poucas pessoas têm acesso a esse tipo de informação; já
outros imaginam se tratar de um assunto exclusivamente relacionado a hackers,
daqueles que “roubam nosso dinheiro e contas de redes sociais pela internet”, como
diria um amigo próximo.
Essas opiniões, movidas pelo senso comum, de certa forma não deixam de
ser verdade. A criptografia realmente está ligada a assuntos bastante confidenciais,
assim como hoje em dia possui estreita relação com muitas utilidades e aplicações
da informática, principalmente no que diz respeito à internet. No entanto, a arte de
estabelecer comunicação de forma a conseguir certa confidencialidade não tem
origem no nosso atual mundo cibernético. Pelo contrário, remonta a tempos em que
computadores e demais máquinas não eram sequer sonhados. Também, não é
válido dizer que ela só é usada por um grupo seleto de pessoas, já que suas
utilidades atingem todos aqueles que possuem uma conta de correio eletrônico, ou
que usam o celular, por exemplo.
Este trabalho tem como objetivo apresentar como ocorreu a evolução e
consolidação desta ciência, que tem origem nos tempos dos grandes faraós, até
chegar à segunda metade do século XX, quando surge a criptografia de chaves
assimétricas, além de justificar matematicamente o porquê de a cifra RSA ser
considerada tão segura quando relacionada às telecomunicações. Portanto, essa
análise, feita através de pesquisa bibliográfica, não ocorre de forma apenas
histórica, mas privilegia principalmente a incorporação da matemática na produção
de conhecimentos científicos que visam privacidade nas telecomunicações em geral,
com o objetivo de potencializá-la e produzir, assim, maior segurança nesse ato.
Essa pesquisa torna-se importante, pois verificamos que existe pouco
material na língua portuguesa sobre a ciência, principalmente no que diz respeito a
explicar como ocorreram e as consequência dos acontecimentos ligados a ela.
Veremos também que a criptografia gerou uma ciência chamada Criptoanálise,
responsável por quebrar as cifras e códigos criados, e que as duas, são vertentes de
outra ciência, que é chamada de Criptologia.
P á g i n a | 15
Este trabalho está dividido em quatro seções, sendo a primeira delas esta
introdução. A segunda contém explicações sobre alguns termos e estrutura básica
destas ciências. Há nele um resumo histórico dividido por eras: Idade Antiga e a
Cifra de César; Idade Média e o surgimento da criptoanálise, Idade Moderna e o
desenvolvimento das cifras polialfabéticas; e Idade Contemporânea, que tem como
marco a criação da criptografia computacional a partir da Segunda Guerra Mundial,
e a invenção do tipo de cifragem que utiliza chaves assimétricas. Faz parte desse
período também a evolução da Criptografia Quântica, porém, esse será abordado no
final da seção seguinte.
Na terceira seção é a vez de analisar a fundo aquela que garante grande
parte da estabilidade e privacidade no ato de se comunicar pela internet nos dias de
hoje: a Cifra RSA. Números primos, Teoria dos números e demais tópicos
matemáticos são destacados para explicar e justificar a importância dessa inovação
tecnológica da segunda metade do século XX. Na quarta seção, apresentamos as
considerações finais.
Adentre conosco nesse fabuloso mundo onde as teorias conspiratórias
parecem ganhar lugar de destaque, em que guerras e a concorrência entre grandes
empresas são cenários, no qual fica claro que o futuro da humanidade está em
mãos não apenas de políticos, empresários ou soldados armados, mas
principalmente de matemáticos altamente qualificados em desenvolver e/ou quebrar
cifras.
P á g i n a | 16
2. HISTÓRIA E DESENVOLVIMENTO DA CRIPTOGRAFIA
Nesta seção são apresentados alguns conceitos básicos para o entendimento
do trabalho, além da evolução da Criptologia desde o surgimento até meados do
século XX.
2.1. CONCEITOS BÁSICOS
Para que possamos entender o que será discutido ao longo do trabalho,
precisamos saber o significado de alguns conceitos básicos do assunto.
Começamos
então
diferenciando
os
termos
Criptologia,
Criptoanálise
e
Criptografia.
A Criptologia é a ciência que engloba os dois ramos: a Criptografia e a
Criptoanálise. Segundo Couto (2008, p. 18) “a Criptologia é uma disciplina científica
que estuda os conhecimentos e as técnicas necessárias para a realização da
criptoanálise (ou seja, da solução das mensagens criptografadas) e da própria
criptografia (que é a codificação da escrita)”.
Considerando que cripto vem do grego antigo kriptó (κρύπτω) e graphein que
significam “oculto” e “escrita”, respectivamente, a criptografia trata da criação de
diversas formas de se transmitir mensagens ou dados de forma secreta, confidencial
e autêntica ao receptor correto através de códigos ou cifras (SINGH, 2001). Já a
criptoanálise é responsável por analisar e quebrar os mais variados tipos de cifras
e códigos criados sob a ótica da criptografia.
A partir destes três conceitos cruciais para o entendimento deste trabalho,
podemos perceber que a criptologia é a ciência que serve de alicerce para as outras
duas ciências e, ainda, o quanto ela é utilizada e importante em alguns contextos da
sociedade.
A criptografia vem sendo utilizada desde a antiguidade basicamente em três
tipos de contexto:
 Comunicação privada
 Arte e religião
 Uso militar e diplomático.
Só na metade do século XX que a criptografia foi utilizada em outros setores
da sociedade como comércio e computação. Toda essa evolução está intimamente
P á g i n a | 17
ligada com a evolução tecnológica. Mas antes de entrarmos na história dessa
interessante ciência, vamos introduzir mais alguns conceitos e contextos
imprescindíveis a sua familiarização.
Como vimos, a criptografia é uma ciência que desenvolve vários métodos
para cifrar ou codificar mensagens a fim de transmiti-las com segurança. Mas existe
também outra técnica que permite o estabelecimento de comunicação de forma
particular, chamada esteganografia. Ela é um ramo particular da criptografia que
consiste em camuflar alguma informação, mascarando sua presença. A princípio
criptografia e esteganografia podem parecer o mesmo tipo de ciência/técnica, porém
a grande diferença consiste que a esteganografia propriamente dita não altera a
mensagem de alguma forma, apenas a esconde em algum lugar previamente
combinado para que a pessoa que deve recebê-la a encontre sem mais problemas,
enquanto que a criptografia altera a disposição de escrita da mensagem mas não se
importa em tentar esconder o fato de que há uma troca de informações entre
pessoas ou instituições diferentes (COUTO, 2008).
Podemos entender, portanto, que a esteganografia faz parte da criptografia
como sendo um caso de um total de três. As outras duas vertentes são as Cifras e
os Códigos. Segundo Singh (2001, p. 47) “tecnicamente um código é definido como
uma substituição de palavras ou frases, enquanto a cifra é definida como uma
substituição de letras”. Tkotz (2005a) define código:
Um código é um método de se obter um criptograma tratando palavras ou
conjuntos de palavras do texto claro como unidades da cifragem. Neste
caso, o número de substitutos pode chegar a alguns milhares e costumam
ser listados em dicionários, conhecidos como nomenclaturas.
(TKOTZ, 2005a)
Já as cifras, como já foi dito, focam seus esforços em substituir letras
individualmente. Na verdade, elas se dividem em duas categorias: as Cifras de
Substituição e as Cifras de Transposição. As de transposição são aquelas que
mantêm o mesmo texto, no entanto trocam apenas a ordem das letras. Por exemplo,
a frase “Eu gosto de Matemática” poderia ser escrita como “aMetámitac ed ogtso
uE”, ou seja, mantivemos as letras originais e trocamos a ordem delas. Veremos
mais exemplos no próximo tópico. As Cifras de Substituição se dividem em três
grupos; Monoalfabéticas, Polialfabéticas e Homofônicas.
P á g i n a | 18
As Cifras Monoalfabéticas utilizam apenas um alfabeto cifrante, como a
Cifra de César, por exemplo, que veremos mais adiante. As Cifras Polialfabéticas
usam vários alfabetos cifrantes na mensagem, tendo como exemplo a cifra de
Vigenère, que é a principal cifra polialfabética já criada, a qual abordaremos mais
tarde. Por último ainda temos as Cifras Homofônicas, cujo nome deriva de homo e
fonos, que significam “igual” e “som” em grego, respectivamente. Singh (2001)
explica como é o funcionamento dessa cifra:
Nela cada letra é substituída por uma variedade de substitutivos, seu
número potencial sendo proporcional à frequência da letra. Por exemplo, a
letra a corresponde a 8 por cento de todas as letras que aparecem num
texto em inglês, assim criamos oito símbolos para representá-la. Cada vez
que aparecer um a no texto original, ele será substituído no texto cifrado por
um dos oito símbolos escolhidos ao acaso, de maneira que, ao ser
concluída a cifragem, cada símbolo corresponderá a 1 por cento do texto.
[...] Esse processo de usar símbolos numéricos para agirem como
substitutos de cada letra continua por todo o alfabeto até chegarmos ao z,
uma letra tão rara que apenas um símbolo pode agir como substitutivo.
(SINGH, 2001, p. 70 e 71)
Por sua vez, as cifras de substituição monoalfabéticas se dividem em três
subgrupos. Teoricamente, as polialfabéticas e as homofônicas também podem ter
essas subdivisões, no entanto, não existem cifras desse tipo, na prática. Vejamos
cada uma delas:

Substituição Monogrâmica: o significado da palavra deriva dos termos
“mono” e “grama” que significam “um” e “caractere”, respectivamente. Dessa
forma, esse tipo de cifra tem a característica de cada símbolo ser substituído
por apenas um outro. O comprimento do texto original e o comprimento do
texto cifrado são iguais. Além disso, o cifrante possui o mesmo número de
símbolos e caracteres que o alfabeto utilizado para escrever o texto claro,
pois para cada símbolo do texto claro existe um símbolo cifrante (TKOTZ,
2005a).

Substituição Poligrâmica: a palavra “poli” dá a ideia de “muitos”, portanto,
nesse tipo de cifra vários símbolos substituem vários outros, ou seja, cada
caractere cifrante pode cifrar vários caracteres diferentes, assim como cada
um pode ser cifrado por vários diferentes. Assim como no caso anterior, o
comprimento do texto original é o mesmo do cifrado, da mesma forma da
quantidade de símbolos.
P á g i n a | 19

Substituição Tomogrâmica: “tomo” em grego significa “cortar”. Assim, nesse
tipo de cifra os caracteres são cortados em dois ou mais, fazendo com que
cada caractere do texto original possa ser trocado por vários diferentes.
Então, dessa vez, a extensão do texto cifrado é maior do que a do texto
original.
Para
simplificar
todas
as
classificações
da
criptologia,
vejamos
o
organograma seguinte:
Figura 01 – Esquema de ramificações da Criptologia
Adaptado de Tkotz (2005a)
Não podemos esquecer uma técnica chamada Supercifragem. Ela é a
mistura de diferentes técnicas de cifragem, por exemplo, cifra-se um texto com uma
cifra monoalfabética e depois cifra com a mesma técnica ou com outra. Existem,
porém, outros tipos de classificações de cifras, no que diz respeito às chaves: os de
algoritmos simétricos, que possuem chave secreta e os assimétricos, com chaves
públicas e privadas.
Vamos nos deter primeiramente nos simétricos. Nesse caso usa-se uma
única chave que serve tanto para cifrar como revelar o texto original. Podemos
P á g i n a | 20
dividir esse método de utilização de chaves em Cifras de Bloco e Cifras de Fluxo.
Couto (2008, p. 238) explica a diferença entre as duas:
A diferença destas cifras [de fluxo] para as de bloco está no modo como
operam. As de bloco operam em grandes blocos de dígitos com uma
transformação fixa. Já as de fluxo são executadas numa velocidade maior
que as de bloco e possuem uma complexidade menor. Porém são mais
suscetíveis a sérios problemas de segurança caso sejam usadas de
maneira incorreta.
(Couto, 2008, p. 238)
Um exemplo de cifra de bloco é o DES (Data Encryption Standard ou Padrão
de Cifragem de Dados), e um de cifra de fluxo é o One-Time-Pad (Bloco de Uso
Único ou Bloco de Cifras de uma única vez, em tradução literal). Essas duas cifras
são exemplos modernos, que ainda podem ser usadas até hoje, sobretudo, nas
comunicações de governos e grandes corporações, via internet.
Uma das grandes revoluções da criptologia foi o advento da criptografia
assimétrica. Ela consiste na obtenção de chaves públicas e privadas através de
funções matemáticas chamadas de Mão Única, na qual, segundo Tkotz (2007a), “a
cifragem é feita através de uma chave pública e a decifração é feita através de uma
chave privada que não pode ser calculada com base na chave pública”. Como
exemplo, destacamos a Cifra RSA, principal objeto de estudo deste trabalho. Essa
cifra envolve elementos matemáticos como números primos e a aritmética modular.
Veremos mais sobre esse assunto na sessão nº IV. Por fim, quanto à criptografia, há
uma divisão entre Clássica e Moderna. A primeira vai dos primórdios da criptologia
até a metade do século XX, quando surge a chamada Teoria da Informação (ou
Teoria
Matemática
da
Comunicação)
que
fornece
base
sólida
para
o
desenvolvimento de uma nova criptografia.
Dispondo desses conceitos básicos, vejamos agora como se deu o
desenvolvimento da criptologia através dos tempos.
2.2. IDADE ANTIGA
O surgimento da criptografia aconteceu de forma bastante rudimentar e até
mesmo sem propósito. Historiadores datam de 2000 a.C., o uso de hieróglifos
“criptografados”, que tinham a função de deixar a mensagem mais “pomposa”.
Algum escriba anônimo, no século XX a.C., em uma cidade chamada Menet Khufu,
P á g i n a | 21
às margens do rio Nilo, na incumbência de contar a história da vida de seu senhor,
deu início também a história registrada da criptologia (KAHN, 1967).
Obviamente o sistema utilizado por ele nem de longe se compara com os
métodos modernos ou contemporâneos. Na verdade, o sistema do escriba era mais
simples, pois ele não usou nenhum código totalmente desenvolvido de substituições
de símbolos hieroglíficos. Ele substituiu hieróglifos comumente utilizados em
mensagens ordinárias por hieróglifos incomuns e raros. Com isso, Kahn (1967, p.
65, tradução nossa) afirma: “Deste modo a inscrição não foi escrita secreta, mas
incorporou um dos principais elementos considerados essenciais da criptografia:
uma transformação deliberada da escrita. É o mais antigo texto conhecido a fazê-lo”.
Conforme o tempo foi passando essa prática ficou mais complexa e ao mesmo
tempo mais comum, no mundo egípcio.
E nesta pequena atividade, quase que de entretenimento, compondo as
idéias de sigilo e transformação de palavras que surgiu a criptografia. Obviamente a
criptologia se desenvolveu, assim como muitas ciências, de forma independente nas
mais variadas civilizações, porém consideraremos o Egito como o berço dessa
ciência.
Muitos séculos depois, manuscritos que viriam a fazer parte da Bíblia foram
escritos contendo algumas cifras simples. O trecho criptografado pode ser
encontrado em Jeremias 25:26 e 51:41. A palavra Sheshach aparece no lugar de
Babel ("Babilônia"). Outra transformação pode ser encontrada em Jeremias 51:1,
onde temos as palavras Leb Kamai ("coração do meu inimigo") no lugar de Kashdim
("caldeus") (KAHN, 1967). Essas duas modificações surgiram da utilização da cifra
Atbash, que juntamente com as cifras Albam e Atbah, são três das cifras hebraicas
mais conhecidas, tendo sido utilizadas no período compreendido entre 600 e 500 a.
C. Eram usadas principalmente em textos religiosos, e baseavam-se no sistema de
substituição monoalfabética (COUTO, 2005).
Couto (2005) ainda classifica as cifras utilizadas pelos hebreus foram em três
categorias: Atbash, Albam e Atbah.
Na cifra Atbash, a encriptação se dá através sucessivas trocas no alfabeto
hebreu, a primeira letra (Aleph) pela última (Taw), a segunda (Beth) pela penúltima
(Shin) e assim sucessivamente e vice-versa. O nome dessa cifra vem justamente
destas primeiras substituições: Aleph, Taw, Beth, Shin = ATBASH.
P á g i n a | 22
Na cifra Albam, as substituições se dão da seguinte maneira: a primeira letra
(Aleph) pela décima segunda letra (Lamed), a segunda (Beth) pela décima terceira
(Mem) e assim sucessivamente e vice-versa. Surge assim o nome da cifra: Aleph,
Lamed, Beth, Mem = ALBAM.
Na cifra Atbah, a substituições são um pouco mais complexas. A primeira
letra (Aleph) é substituída pela oitava letra (Teth), a segunda (Beth) pela sétima
(Heth). E o nome desta cifra surgiu da mesma fora que as outras: Aleph, Teth, Beth,
Heth = ATBAH. Abaixo o quadro (adaptado) com as cifras:
1
1
2
1
3
1
4
1
Figura 02 – O alfabeto hebreu e suas cifras
Fonte: <http://www.quadibloc.com/crypto/ppen01.htm>. Acesso em 02/01/2012.
Em 1 temos o alfabeto hebreu original e seus símbolos de letras. Em 2 temos
este alfabeto já encriptado com a cifra Atbash. Em 3, encriptado com a cifra Atbam.
E em 4 com a cifra Atbah.
P á g i n a | 23
Por volta do ano 300 a.C., um livro chamado Artha-sastra, produzido na Índia,
recomendava o uso da criptografia. Ele refere-se a várias cifras e recomenda a
quebra de cifras para obtenção de relatórios de espionagem, indicados para
diplomatas (COUTO, 2005).
Sua escrita é atribuída à Kautilya. Já o famoso Kama-Sutra, escrito no século
4 d.C. por Vatsyayana, recomenda que suas mulheres devem estudar 64 artes,
incluindo culinária, vestiário, etc., e algumas menos óbvias como magia, xadrez,
carpintaria, etc. A arte número 45 na lista é a mlecchita-vikalpa, a arte da escrita
secreta justificada de modo a ajudar as mulheres a esconder os detalhes de seus
relacionamentos. Uma das técnicas recomendadas envolve o emparelhamento ao
acaso de letras do alfabeto, e depois substituir cada letra na mensagem original com
o seu parceiro (SINGH, 2001).
Quando o assunto é Antiguidade, não podemos deixar de falar de uma grande
civilização, a qual desenvolveu e até mesmo criou diferentes e variados ramos das
ciências: a Grécia. Como não podia deixar de ser, na Grécia também foram
desenvolvidas alguns tipos de mensagens criptografadas. Uma das primeiras
referências se encontra na Iliada de Homero, assim como alguns casos envolvendo
esteganografia.
Um método antigo foi atribuído ao general Histiaeus, o qual se baseava em
raspar a cabelo de um escravo e tatuar uma mensagem em sua cabeça. Uma vez
que o cabelo já estivesse grande o suficiente para camuflar essa mensagem, o
escravo era enviado ao destinatário para que a mensagem pudesse ser entregue
(GIL et al. 2008). Enéas, o Tático (Aeneas Tacticus), cujo nome era Éneas de
Stymphalus, foi um cientista militar que desenvolveu outros dois métodos
esteganográficos, por volta do século IV a. C. O primeiro, conhecido como Astrogal,
era basicamente uma madeira composta por vários furos, em que cada furo
representava uma letra do alfabeto. Para que uma mensagem pudesse ser enviada,
era necessário passar um barbante entre os furos, de maneira a formar a mensagem
propriamente dita. Logo, o receptor deveria acompanhar as ligações de pontos feitas
com o barbante para que a mensagem pudesse ser decodificada. (CHIRIGATI, et al
2006).
Tkotz (2005b) descreve outro método desenvolvido por Enéas, o tático:
P á g i n a | 24
[Ele] inventou um telégrafo hidro-ótico, um sistema de comunicação à
distância. Dois grupos, separados por uma distância em que ainda era
possível reconhecer a luz de uma tocha e que quisessem enviar mensagens
deviam possuir dois vasos iguais. Os vasos tinham um abertura no fundo,
fechada por uma rolha, e eram preenchidos com água. Um bastão, que
tinha mensagens inscritas, era colocado em pé dentro do vaso. Ao sinal de
uma tocha, as rolhas eram retiradas simultaneamente. Quando o nível da
água estivesse na altura da mensagem que se queria transmitir, outro sinal
luminoso era enviado para que as rolhas fossem recolocadas.
(Tkotz, 2005b)
Os gregos são responsáveis também pelo primeiro registro conhecido do uso
da criptografia para fins militares: o Scytale ou bastão de Licurgo, que foi produzido
pelos espartanos. A invenção consistia em um bastão de madeira com uma tira
estreita de couro ou pergaminho enrolada em volta, na qual era escrita a mensagem
no sentido do comprimento do bastão, e após isso, desenrolada a tira do bastão, a
mensagem ficava desconexa, só se revelando ao receptor portador da chave que
era o bastão e algoritmo que seria enrolar a tira neste bastão. Segundo Couto
(2005), ainda, complementando o registro, a primeira noticia de seu uso foi com o
General Parasius, o qual recebia as ordens codificadas com este instrumento, a
mando de Tucídides. Abaixo um scytale:
Figura 03 – Scytale Espartano
Fonte: Wikipédia, disponível em <http://en.wikipedia.org/wiki/File:Skytale.png>.
Acesso em 02/01/2012.
Por fim, em relação aos gregos, ainda temos a menção de um método de
cifragem pelo historiador grego Políbio (204 a.C. a 122 a.C.), no seu livro Histórias,
que seria um código poligrâmico e cuja autoria do mesmo foi atribuída aos seus
contemporâneos Cleoxeno e Democleto. Sua importância na história da criptografia
P á g i n a | 25
reside no fato de que serviu de base para outros métodos de cifragem como a Cifra
Playfair e a Cifra Campal Germânica (ADFGX), usada na Primeira Guerra Mundial.
A principal invenção criptográfica da Idade Antiga, porém, ainda estaria por
vir: o escritor Suetônio, registra em sua obra Vida dos Césares, que Júlio César
escrevia, em correspondências particulares, em uma cifra de substituição, a qual
substituía as letras do alfabeto comum por letras desse mesmo alfabeto em três
posições depois da substituída. Utilizando o alfabeto moderno de 26 letras teríamos
D por A, E por B, F por C, e assim sucessivamente. Até hoje, qualquer cifra baseada
em um deslocamento fixo de posições é considerada “Cifra de César”, ou seja,
mesmo que não inicie com a letra D (KAHN, 1967; COUTO, 2005). A Tabela 01
mostra como seria a Cifra de César, em vermelho, com o nosso alfabeto de 26
letras, em preto:
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
Tabela 01 – Alfabeto da Cifra de César
Para mais informações sobre a Cifra de César, ver o Apêndice A.
2.3. IDADE MÉDIA
Oficialmente esse período histórico tem o seu início no ano de 476 d.C.,
marcado pelo fim do Império Romano do Ocidente e seu término em 1453 d.C., ano
do fim do Império Romano do Oriente, simbolizado pela tomada da cidade de
Constantinopla (atual Istambul, Turquia) pelo Império Octomano. Porém, para a
criptologia essa era começa mesmo por volta do ano 800 d.C., época em que os
mulçumanos alcançaram um estágio intelectual bastante significativo para a época
(SINGH, 2001).
Vários fatores contribuíram para que o mundo islâmico pudesse ultrapassar o
europeu com relação a avanços científicos, entre eles o fato dos mulçumanos
valorizarem bastante a ciência, o que os fez criar a Bait al-Hikmah (Casa da
Sabedoria), a qual era um importante centro de produção de conhecimento, em
Bagdá. Outro aspecto interessante é que pessoas estrangeiras não eram vistas com
maus olhos e tinham suas ideias bastante toleradas. A chamada Idade de Ouro
islâmica (750 d.C. até 1258 d.C.) proporcionou avanços em várias áreas, como nas
P á g i n a | 26
Artes, na Medicina e na Matemática. Dessa última destacamos os progressos feitos
na Trigonometria e na Combinatória, além do desenvolvimento da álgebra (nome
oriundo do termo al-jabr) e dos números indo-arábicos (SINGH, 2001).
Para a criptologia, os mulçumanos ficaram marcados por serem os
responsáveis pela criação da Criptoanálise. Isso foi possível por dois fatores:
primeiro porque a criptografia era bastante utilizada no dia a dia desse povo, já que
ela era amplamente usada nas correspondências de cunho administrativo do
Estado, as quais possuíam alguns manuais que explicavam conceitos e técnicas,
como o Adab al-Kuttab; segundo porque os estudos científicos desse povo incluíam
as escrituras sagradas, como o Alcorão, em busca das revelações de Maomé, o que
possibilitou aos estudiosos perceberem que algumas letras apareciam no texto com
mais frequência que outras, no idioma árabe. Tudo isso gerou o surgimento de uma
técnica chamada Análise de Frequências, na qual verifica-se um texto cifrado e
observa-se a frequência com que as letras aparecem. Logo após substituí-se as
letras cifradas por aquelas que apresentam frequência semelhante, e assim obtémse o texto original ou pelo menos bem semelhante, de modo que ele possa ser
deduzido (SINGH, 2001).
Várias pessoas se destacaram na evolução criptológica entre os mulçumanos.
O filósofo, cientista e matemático al-Kindi é conhecido como o “filósofo dos árabes” e
o “bisavô da estatística”. Ele é responsável por 290 livros de diversos assuntos,
porém seu maior tratado, que foi redescoberto apenas em 1987 no Arquivo
Sulaimaniyyah Ottoman em Istambul, na Turquia, é intitulado "Um Manuscrito sobre
Decifração de Mensagens Criptográficas". Ou seja, não se sabe de fato se ele foi o
primeiro a conceber a análise de frequência, no entanto, é de autoria dele o livro
mais antigo que se tem conhecimento sobre a técnica (TKOTZ, 2005c).
Outro destaque é uma pessoa que nasceu antes de al-Kindi, o autor do Kitab
al Mu'amma (Livro das mensagens criptográficas), chamado al-Khalil. Essa obra,
que fora escrita em grego para o então imperador bizantino, solucionava um antigo
criptograma com o uso de uma técnica chamada “Método da Palavra Provável”. Ele
sabia que qualquer texto da época iniciava com a frase “Em nome de Deus”, e com
isso pôde elaborar uma “cola”, a qual lhe fornecia informações bastante úteis de
como a cifra havia sido elaborada, ajudando-o, assim, a decifrá-la. (KANH, 1996;
POMMERENING, 1985).
P á g i n a | 27
Outros
estudiosos
árabes
contribuíram
para
o
desenvolvimento
da
criptografia. Ibn Dunainir (1187 – 1229) escreveu uma obra intitulada Maqasid alFusul al-Mutarjamah an Hall at-Tarjamah (Explicações claras para a solução de
mensagens secretas). O livro contém uma inovação importante: cifras algébricas, ou
seja, a substituição de letras por números que podem ser transformados aritmeticamente (POMMERENING, 1985). O poeta e professor Ibn Adlan (1187 – 1268) era
bastante conhecido por sua inteligência e foi considerado uma figura de destaque na
literatura. Talvez essas características o tenham qualificado para ser perito em
charadas e criptoanálise, no qual se destacou e para o qual ele dedicou mais de um
livro, entre eles o Al-Mu'allaf lil-Malik al-Ashraf, que fora escrito para o Rei al-Ashraf,
com explicações detalhadas do assunto (MRAYATI, ALAM e TAYYAN, 2003a;
POMMERENING, 1985).
Um polímata árabe chamado Ibn Khaldun (1332 – 1406) escreveu o
Muqaddimah, um importante relato da história que cita o uso de "nomes de
perfumes, frutas, pássaros ou flores para indicar letras, ou [...] sobre formas
diferentes das formas das letras aceitas" como um código usado entre escritórios
militares e de controle de impostos. Ele também inclui uma referência à
criptoanálise, observando que "escritos conhecidos sobre o assunto estão em poder
do povo". (KAHN, 1996). Para completar a lista de estudiosos árabes temos o
professor Ibn Ad-Duraihim (1312 – 1361), famoso por sua engenhosidade em
aritmética, criptoanálise, e em resolver enigmas e caça-palavras. Ele também tinha
conhecimento em al-'awfaq (uma ciência antiga lidar com números: em especial
combinações, valores e características secretas), e nas letras do alfabeto e suas
estatísticas e propriedades fonéticas. Ad-Duraihim escreveu muitas obras nestas
áreas (MRAYATI, ALAM E TAYYAN, 2003b). Ele é o autor do livro Miftah al-Kunuz fi
Idah al-Marmuz (Chaves para a Elucidação de Mensagens Secretas) que contém
uma classificação das cifras, análises de frequência em várias línguas, uma tabela
semelhante à de Vigenère (na verdade de Trithemius, como veremos a seguir) e
grades de transposição. Al-Qalqashandi (1355-1418), um matemático egípcio,
escreveu em 1412 a Subh al-sha’, uma enciclopédia de 14 volumes em árabe, na
qual incluiu uma seção de Criptologia. Ele refere Ibn ad-Duraihim como o autor das
informações e cujos escritos sobre criptologia foram perdidos. A lista de cifras nesta
obra inclui tanto a substituição quanto a transposição e, pela primeira vez, uma cifra
com múltiplas substituições para cada letra do texto original. Também é atribuída a
P á g i n a | 28
ibn ad-Duraihim uma explicação com exemplo de criptoanálise, inclusive o uso de
tabelas de frequência de letras e conjuntos de letras que podem ocorrer juntas numa
palavra (KAHN, 1996).
Apesar de viverem em uma época em que as evoluções tecnológicas não
eram muito incentivadas, os europeus da Idade Média deram alguns importantes
passos nesse período em relação à criptografia, o que refletiu na sua enorme
contribuição para esta ciência algum tempo depois, já na Idade Moderna. Há relatos
do uso de cifragem de mensagens vindo deles, porém considerados formas
rudimentares quando comparados aos árabes. Aparentemente a maioria absoluta
dos europeus que tinha algum conhecimento em criptografia não sabia das técnicas
de criptoanálise, portanto suas cifras não tinham um nível de segurança considerado
alto. Essa situação só viria começar a mudar depois do início do período que ficaria
conhecido como “Renascimento no século XII” (COUTO, 2005).
Temos conhecimento de que inicialmente a criptografia na Europa era
utilizada por reis que não queriam que seus inimigos soubessem de seus segredos;
por alquimistas que tinham receio de que o significado de seus estudos caísse nas
mãos da Igreja Católica e fossem parar na fogueira; além de alguns próprios clérigos
desta instituição, que estudavam a bíblia e procuravam mensagens ocultas nela, na
qual a cifra Atbash foi encontrada em várias passagens (VISSIÈRE, 2009).
Uma cifra de destaque foi criada pelos membros da Ordem dos Pobres
Cavaleiros de Cristo e do Templo de Salomão, mais conhecida como a Ordem dos
Cavaleiros Templários. Essa organização, fundada em 1118, tinha como objetivo
inicial a proteção dos peregrinos que buscavam chegar à chamada Terra Santa,
Jerusalém, cuja quantidade crescia cada vez mais, visto que muitos naquela época
acreditavam que o fim dos tempos estava próximo. Os Templários ganharam
bastante respeito pelos europeus, inclusive por Papas, entre eles Balduíno II e
Inocêncio II. Com isso, passaram a ter poderes econômico, militar e religioso de
proporções imensas, e assim se espalharam por toda a Europa.
Dessa forma, passaram a ter a necessidade de cifrar suas mensagens para
esconder seu significado para seus inimigos. Encontramos em Tkotz (2005d) o
cifrante usado pelos Cavaleiros Templários. Ele foi extraído da cruz chamada "das
oito beatitudes", que constituía o emblema da ordem. Essa cifra apresenta apenas
uma substituição simples onde cada letra é substituída por um símbolo especial,
como podemos ver na figura a seguir:
P á g i n a | 29
Figura 04 – Cifrante dos Templários
Fonte: Adaptada de Tkotz (2005d)
Como podemos ver, os Templários utilizavam uma cifra de substituição
monoalfabética que era eficiente na Europa, mas que poderia ser facilmente
quebrada pelos árabes.
A partir do século XIII alguns personagens entram de forma individual nessa
história. O frade franciscano inglês Roger Bacon (1214 – 1294), conhecido também
como "Doctor mirabilis" (Doutor admirável, em latim) dava, em seus estudos da
natureza, bastante ênfase ao empirismo e ao uso da matemática, além de contribuir
em áreas importantes como a Mecânica, a Filosofia, a Geografia e principalmente a
Ótica. Além de tudo isso, Bacon exercia em segredo atividades de cunho alquimista.
Os alquimistas acreditavam que, ao aprender a manipular os elementos da natureza,
seria possível transformar metais ordinários em ouro e aperfeiçoar o espírito
humano. Como essa prática era vista como bruxaria, eles poderiam ser condenados
e mortos na fogueira. Dessa forma, esses estudiosos desenvolveram sistemas de
cifragem e decifragem. No campo da codificação, eles usavam símbolos para
designar substâncias químicas, como o lobo para representar o antimônio e o leão
verde para o vitríolo verde (VISSIÈRE, 2009).
Durante o período que ficou conhecido como “Cisma de Avignon”, o antipapa
Clemente VII decidiu unificar o sistema de cifras da Itália Setentrional, tornando
Gabriele de Lavinde o responsável de coordenar a tarefa. Lavinde juntou várias
cifras num manual, do qual o Vaticano conserva uma cópia de 1379. Com isso ele
pôde unir a cifra de substituição a um código com listas de palavras, sílabas e
nomes equivalentes que foi usado por volta de 450 anos, por diplomatas e alguns
P á g i n a | 30
civis europeus e americanos (KAHN, 1996). Esse fato é importante porque
demonstra o crescente interesse dos europeus em cifras, a ponto de uma das
maiores autoridades da Igreja Católica se importar de unificar o sistema de
encriptação. Outra demonstração disso é que em 1392, Geoffrey Chaucer,
considerado o melhor poeta inglês antes de Shakespeare, no seu "The Equatorie of
the Planetis", um suplemento da sua obra "Treatise on the Astrolabe", incluiu seis
passagens escritas em cifras (TKOTZ, 2005e).
Para finalizar esse período, temos indícios de que já se concebia uma ideia
de que as cifras monoalfabéticas poderiam ser quebradas através da análise de
freqüências. Em 1401, Simeone de Crema usou uma chave na qual cada vogal do
texto original possuía vários equivalentes. Não há razão para que ele tenha feito isso
se não soubesse que os outros modos de encriptação não eram mais seguros. Mais
tarde, em 1411, Michele Steno, doge de Veneza, nos dá um dos primeiros exemplos
de cifras homofônicas: escolhia um dos muitos símbolos para cada caractere, além
de utilizar nulos e caracteres especiais para certas palavras de uso freqüente
(KAHN, 1996).
2.4. IDADE MODERNA
Não foi possível conter a evolução da criptografia na Europa por muito tempo.
Os segredos de estado dependiam cada vez mais de cifras confiáveis. Para atender
as suas necessidades os governos começaram a não mais perseguir e matar os
criptógrafos e criptoanalistas. Agora eles eram recrutados para trabalhar para o
estado (VALDEVINO, 2006).
Em Singh (2001), observa-se que não se tem certeza acerca de como se deu
esse avanço criptológico na Europa, mas é possível que ele tenha ocorrido de forma
independente ao que havia ocorrido na parte oriental do mundo. O Renascimento
possibilitou a produção do conhecimento necessário ao desenvolvimento da
Criptologia ocidental.
Um dos casos mais emblemáticos das mudanças ocorridas na concepção de
segurança na comunicação dessa época é o da condenação e morte da rainha da
Escócia, Maria Stuart, em 1587. A mandante da execução foi a também rainha
Elizabeth I, da Inglaterra, que era prima de Maria. A situação toda fora conseqüência
de disputas internas entre Católicos e Protestantes na Inglaterra. Elizabeth temia
P á g i n a | 31
que sua prima pudesse roubar-lhe o trono por ela ser considerada a herdeira
legítima, pela parte católica do país. Por isso a manteve presa por quase duas
décadas, até o seu primeiro-secretário, Francis Walsingham, contratar um espiãoduplo para contrabandear cartas de simpatizantes de Maria para ela própria e a
resposta dela para eles. As cartas, que eram cifradas, continham detalhes da
armação que estava sendo arquitetada para um suposto o assassinato de Elizabeth
e a libertação de Maria. No entanto, por ser um nomenclator, sua decifração era
bastante fácil através de uma análise de frequência, e a Inglaterra já dispunha nessa
época de criptoanalistas trabalhando para a Corte Real. Dessa forma, Walsingham
pôde comprovar que Maria compactuava com as ideias de seus simpatizantes,
fornecendo assim provas suficientes para que ela pudesse ser executada. Em 8 de
fevereiro de 1587, depois de alguns dias de julgamento e decisão, a rainha da
Escócia foi decapitada para uma platéia de 300 pessoas.
Figura 05 – Execução de Maria Stuart, rainha da Escócia, em 1587, autor desconhecido.
Fonte: Galeria Nacional Escocesa, disponível em
<http://www.nationalgalleries.org/collection/artists-a-
z/U/5600/artistName/Unknown/recordId/3237>. Acesso em 01/01/2012.
A Idade Moderna é bem mais rica de situações em que a criptografia era
usada, no entanto, para não nos prolongarmos, nos deteremos apenas nos detalhes
P á g i n a | 32
relacionados à maior evolução desta ciência nesse período: o surgimento das cifras
polialfabéticas. Vários estudiosos contribuíram para que uma cifra polialfabética
consistente pudesse ser criada.
Tudo começa quando Leon Battista Alberti (1404 – 1472), uma das maiores
figuras da renascença italiana (TKOTZ, 2005f), escreveu um ensaio sobre esse
assunto, apresentando o que ele acreditava ser uma nova forma de cifra. Lá, ele
propõe o uso de dois ou mais alfabetos cifrados que, quando usados
alternadamente, confundiriam os criptoanalistas (SINGH, 2001).
Seu sistema de encriptação usava dois discos concêntricos de metal, cujas
circunferências eram divididas e 24 partes iguais (COUTO, 2008). Foi também o
inventor de uma técnica chamada “sobrecodificação codificada”, que reforçava o
segredo das palavras-chave. Esses dois mecanismos, realmente novos, tornaram
inútil qualquer tentativa de decodificação baseado na análise da frequência com que
as letras e palavras eram utilizadas (VISSIÈRE, 2009).
Figura 06 – Disco de Alberti
Fonte: Fincatt (2010, p. 33)
Alberti não conseguiu aperfeiçoar suas ideias, porém, elas serviram como
base para outros estudiosos. Em 1518 foi publicado o que seria o primeiro livro
impresso sobre criptologia, cujo autor era o abade e ocultista alemão Johannes
Trithemius (1462 – 1516) (COUTO, 2008). Esse, que é considerado o seu maior
tratado, foi chamado de Poligraphia, terminado em 1508 e ficando à disposição do
público em seis livros apenas depois da sua morte. Ele também escreveu, embora
não tenha publicado, um livro chamado Steganographia, onde apresenta uma cifra
intitulada Ave Maria, na qual supostamente escrevia uma oração, mas na verdade
era uma mensagem esteganográfica, já que cada letra era representada por uma
P á g i n a | 33
frase da oração (TKOTZ, 2007b). Em Couto (2008) vemos que sua maior invenção,
porém, foi outra:
A tabela de Trithemius, chamada de Tabela Reta (tabula recta), é um
quadro onde cada linha substitui a anterior com um deslocamento de um
caractere para a esquerda. O abade usava a tabula recta para definir uma
cifra polialfabética equivalente à do Disco de Alberti.
(COUTO, 2008, p. 78)
Abaixo a tabela inventada por Trithemius:
Figura 07 – Tabula Recta de Johannes Trithemius
Fonte: Wikipédia, disponível em <http://pt.wikipedia.org/wiki/Ficheiro:Vigenere-square.png>.
Acesso em 02/01/2012.
Apesar de ser de autoria de Trithemius, a Tábua Reta ficou mais conhecida
com outro nome e como sendo de outra pessoa. Logo mais voltaremos a falar desse
assunto, por ora vamos nos deter ao matemático e filósofo italiano Girolamo
Cardano (1501 – 1576). Ele inventou um método esteganográfico que é conhecido
como Grelha de Cardano, que foi adaptada e usada pelo cardeal Richelieu,
conselheiro da rainha regente da França. Sua contribuição para o sistema
P á g i n a | 34
polialfabético de cifras foi ser o inventor do primeiro método a usar uma auto-chave,
mesmo que esse sistema seja considerado imperfeito (TKOTZ, 2005g).
No ano de 1563 o polímata italiano Giambattista Della Porta, que já dava
atenção à criptografia em outra obra anterior, publica o livro De furtivis literarum notis
- vulgo de ziferis, o qual segundo Toktz (2005h):
É composto por quatro volumes que tratam, respectivamente, de cifras da
antiguidade, de cifras modernas, da criptoanálise e das características
linguísticas que facilitam a decifração. A obra representa a soma dos
conhecimentos criptológicos da época.
(TKOTZ, 2005h)
De acordo com Vissière (2009), nesse livro há a introdução de uma cifra que
funcionava sob um sistema de substituição bigramática, para o qual Della Porta
criara “uma grade formada por um alfabeto disposto em um eixo horizontal e outro
em um eixo vertical; cada casa dessa grade correspondia a um par de letras (AA,
AB, AC etc.), simbolizado por um caractere diferente”.
Como pudemos ver, Alberti, Trithemius, Cardano e Della Porta deram suas
contribuições para o desenvolvimento da cifra polialfabética. No entanto a pessoa
que ficou conhecida como quem organizou e simplificou os avanços desses
estudiosos foi Blaise de Vigenère (1523 – 1596). Precisamos, porém, tomar cuidado
com essa afirmação. Vigenère, como falamos, ficou conhecido como o responsável
pela versão final da cifra, mas o verdadeiro autor dessa façanha foi Giovanni Battista
Bellaso (1549 - desconhecido). Fato é que Vigenère produziu uma cifra polialfabética
mais robusta que a de Bellaso, porém essa segunda é que foi a mais utilizada após
ser criada, por ser mais simples. Equivocadamente essa cifra foi atribuída à
Vigenère, sendo reconhecida até hoje como de sua autoria. A cifra que foi realmente
criada por Vigenère é a cifra de Autochave.
Independente de quem tenha criado, a grande importância do surgimento e
desenvolvimento das cifras polialfabéticas é que elas foram as primeiras a causar
um desafio realmente notável para os criptoanalistas da época. A cifra criada por
Bellaso foi considerada indecifrável por quase dois séculos. Por isso que ela é
conhecida também como “Le chiffre Indéchiffrable”. Para mais informações sobre
essa cifra, ver o Apêndice A.
Eram os criptógrafos levando a melhor novamente depois de alguns séculos
de soberania dos criptoanalistas. A dificuldade de quebra da cifra consistia no fato
P á g i n a | 35
dela, aparentemente, ser imune à análise de frequência. Como era usado mais de
um alfabeto, cada letra da mensagem original poderia ser substituída por mais de
um tipo de letra na mensagem cifrada. Além disso, a ideia do uso de chaves préestabelecidas para a cifra a potencializou muito mais.
Pode parecer, portanto, que todos aqueles que queriam esconder suas
mensagens a partir daquela época passaram a usar a cifra, porém, não foi o que
aconteceu. Em Singh (2001) descobrimos que elas foram ignoradas por quase dois
séculos. Isso porque as cifras polialfabéticas eram consideradas muito complexas e
inapropriadas para serem usadas em guerras, por exemplo. Nesse tipo de situação
a agilidade e rapidez no envio de mensagens são essenciais. Além do mais, ainda
existiam casos que não era tão necessário o seu uso, como proteger o significado
de informações de funcionários, vizinhos, cônjuges ou demais pessoas que não
tinham conhecimento de como decifrá-las. Dessa forma, o uso de mensagens
monoalfabéticas ainda era justificável.
Nas guerras a solução criptográfica foi o uso de cifras de substituição
homofônicas. Uma bastante conhecida é a Grande Cifra, desenvolvida Antoine
Rossignol e seu filho Bonaventure em 1619. Essa cifra era tão forte que só foi
quebrada no fim do século XIX. Elaborada para guardar os segredos do rei Luís XIV
da França, a cifra dispunha de 587 números diferentes, e continha várias formas de
armadilhas, para eventuais criptoanalistas. A dificuldade de decifração era grande
porque Rossignol atribuiu números para sílabas, e não para letras individuais. Além
disso, quando os criadores faleceram, as regras de decifração foram rapidamente
perdidas (SINGH, 2001).
As cifras monoalfabéticas só foram definitivamente abandonadas após o início
do século XVIII, com a criação das chamadas Câmaras Escuras. Segundo Couto
(2008) elas consistiam em “grupos ligados aos governos que se dedicam ao estudo
e aplicação dos métodos criptográficos”. A mais famosa delas é Geheime
Kabinettskanzlei de Viena, que era liderada pelo barão Ignaz Von Koch. Ela recebia
diariamente centenas de cartas, às 7 da manhã, que deveriam ser entregues às
embaixadas da cidade. Até as dez da manhã todas elas eram copiadas e seladas
novamente, de forma a chegar a seus destinos finais. A partir daí começava a
decifração das mensagens pela equipe de criptoanalistas profissionais. As
informações descobertas serviam tanto para o governo austríaco como para outras
nações dispostas a pagar pelo valioso significado delas.
P á g i n a | 36
A França já dispunha de suas câmaras escuras desde 1680, os Cabinet Noir,
enquanto que a Inglaterra criou sua primeira Black Chamber em 1701. Esses grupos
foram mantidos apenas até o ano de 1850, porque os seus respectivos governos
não mais acharam que era necessário que eles fossem mantidos em forma de
plantão, o que culminou nas suas dissoluções (COUTO, 2008). Além desse, outros
fatores contribuíram para que o uso das cifras polialfabéticas passasse a ser cada
vez maior.
O
principal
deles foram os
avanços tecnológicos
da
Idade
Contemporânea.
2.5. IDADE CONTEMPORÂNEA
2.5.1. Popularização da Criptografia e a quebra da Cifra de Vigenère
A invenção do Telégrafo elétrico revolucionou as formas de se comunicar, no
século XIX. Ou seja, a criptografia precisava evoluir junto, já que a necessidade de
comunicação sigilosa só aumentava cada vez mais. O uso das cifras polialfabéticas
se consolidou com o surgimento dessa tecnologia porque a criptoanálise tornava-se
cada vez mais profissional e era preciso se precaver quanto à troca de mensagens,
que se tornou mais rápida e ao mesmo tempo mais suscetível a ser descoberta.
O Telégrafo ajudou ainda a popularizar a criptografia, visto que pessoas
comuns que necessitavam utilizar a tecnologia precisavam aprender formas simples
de criptografar suas mensagens, para escondê-las pelo menos dos telegrafistas.
Com isso o interesse por esse tipo de conhecimento aumentou bastante entre essas
pessoas, que tinham interesse de esconder seus segredos de pessoas próximas,
como pais, familiares ou cônjuges. É claro que um profissional da quebra de cifras
poderia desvendar a maioria absoluta das mensagens enviadas, mas o objetivo
principal era que pessoas conhecidas não as descobrissem.
Essa popularização pode ser vista claramente na Inglaterra Vitoriana, período
que vai de 1837 a 1901, onde casais (que eram proibidos de expressar o seu amor
em público) mandavam mensagens cifradas através dos jornais de grande
circulação nacional. Também compartilhavam dessa prática pessoas que queriam
criticar o governo ou organizações (SINGH, 2001). Além disso, tendo despertado o
interesse das pessoas em geral, alguns romances envolvendo essa temática foram
produzidos em meados do século XIX. Júlio Verne, com as suas obras Viagem ao
P á g i n a | 37
centro da Terra e Mathias Sandrof; Edgar Allan Poe com O Escaravelho de Ouro;
Arthur Connan Doyle, criador do detetive mais famoso do mundo, o Sherlock
Holmes, produziu O Vale do Terror e A aventura dos Homenzinhos Dançantes.
Nessa época, porém, outra grande (e talvez mais importante, para a
criptologia) revolução estava acontecendo: a quebra da cifra de Vigenère. Isso
aconteceu no ano de 1854, mas só veio à tona em 1863. O responsável por essa
façanha foi Charles Babbage (1791 – 1871), que hoje é considerado o pai do
computador moderno.
Esse cientista tem em seu currículo várias invenções, como o velocímetro; o
limpa-trilhos, estrutura que ficava localizada na parte dianteira dos trilhos para liberar
o caminho de possíveis obstáculos; o sistema que oferece um preço único por carta,
independente do destino, por ter provado que o cálculo do preço que cada uma
dessas cartas teria, caso ele variasse de acordo com o destino final, era maior que o
custo da postagem em si. Ele foi também o primeiro a perceber que a largura dos
anéis de crescimento das árvores dependia do clima em determinado ano,
deduzindo assim que se poderia determinar climas de eras passadas estudando
árvores antigas. Além disso, produziu um conjunto de tabelas de mortalidade que
são ferramentas básicas das companhias de seguro, na atualidade.
No entanto, sua contribuição mais importante para a ciência em geral foi a
idealização do precursor dos computadores modernos. Com dinheiro público tentou
construir a sua “Máquina de Diferenças” (ou “Motor de Subtração”), que consistia em
uma calculadora de 25 mil peças, que possuía rodas dentadas em eixos que uma
manivela fazia rolar. Caso essa invenção fosse concluída, ela seria capaz de
computar e imprimir extensas tabelas científicas. 17 mil Libras e 10 anos depois,
Babbage abandonou o seu projeto em busca de realizar um mais ambicioso, o que
ele chamou de “Máquina de Diferenças nº2”. Infelizmente, o governo britânico
resolveu não mais financiar os experimentos do cientista alegando que ele não
chegara a um resultado significativo depois de tanto dinheiro investido (TKOTZ,
2005h).
Singh (2001, p. 82) define esse acontecimento como “uma tragédia científica”.
Tudo isso porque a nova máquina de Babbage seria a primeira da história da
humanidade com a capacidade de ser programável. Couto (2008, p. 110) afirma que
o próprio Babbage relata que sua nova invenção serviria “não apenas para
P á g i n a | 38
solucionar um tipo de problema matemático, mas para executar uma ampla gama de
tarefas de cálculo, de acordo com instruções fornecidas por seu operador”.
Figura 08: Máquina de Diferenças nº 2 de Babbage, construída em 1991 pelo Museu de Ciência
e Tecnologia de Londres.
Fonte: Livraria de Imagens da Ciência e Sociedade de Londres. Disponível em
<http://www.scienceandsociety.co.uk/results.asp?image=10324907&itemw=4&itemf=0005&itemstep=
1&itemx=6>. Acesso em 02/01/2012.
Tragédias a parte, Charles Babbage foi a primeira pessoa a conseguir
quebrar a cifra de Vigenère. Ele percebeu que uma cifra polialfabética se tratava de
nada mais que um conjunto de diferentes cifras monoalfabéticas organizadas em
uma sequência, e que, dessa forma, poder-se-ia aplicar também a técnica conhecida
como análise de frequências. Portanto, Babbage tinha acabado com um paradigma
que já durava havia séculos.
Porém, o cientista parece não ter dado a devida atenção para a sua própria
descoberta. Na verdade, só no século XX, ou seja, depois da sua morte, é que
estudiosos descobriram o feito de Babbage, ao examinarem suas anotações. De
qualquer forma, nove anos após o cientista inglês, que era general do exército
prussiano, chamado Friedrich Wilhelm Kasiski encontrou, de forma independente do
P á g i n a | 39
primeiro, as falhas da cifra de Vigenère. Assim, a técnica de decifragem relacionada
a essa cifra polialfabética ficou conhecida como Teste de Kasiski.
2.5.2. O surgimento da Criptografia mecânica
O final do século XIX e início do XX ficaram marcados por muita confusão
entre os criptógrafos, que tentavam a todo custo inventar uma cifra forte o suficiente
para re-estabelecer as comunicações secretas pelo mundo. Várias cifras novas
surgiram, porém, eram quebradas pouco tempo depois, por serem variações de
antigas cifras. Algo novo precisava ser inventado (SINGH, 2001).
Enquanto isso, outra descoberta mudaria o rumo da história: a possibilidade
de comunicação via rádio. O físico italiano Guglielmo Marconi desenvolveu um
sistema no qual poderia enviar mensagens entre longas distâncias sem a
necessidade de um fio que ligasse emissor e receptor. Uma vez tendo provada a
eficiência da tecnologia, Marconi encantou os militares que viam o sistema como um
excelente aliado durante a Primeira Guerra Mundial. No entanto, a facilidade de
comunicação por rádio tinha como consequência a facilitação de interceptação das
mensagens. Portanto, era vital que uma cifra realmente segura fosse criada.
Os alemães criaram a ADFGVX, que era considerada imbatível por eles, e
que foi usada no ano de 1918. Couto (2008, p. 102) define a cifra como sendo
“baseada em substituição por meio de uma matriz com chave seguida de
fracionamento e transposição das letras fracionadas”. Para a infelicidade dos
alemães, um francês chamado Georges Painvin, após perder por volta de 15 quilos,
conseguiu quebrar a cifra (SINGH, 2001).
Nesse ponto da história, mais especificamente entre os anos 1917 a 1918,
houve vários outros acontecimentos interessantes no ponto de vista da criptologia:
Couto (2008, p. 101) aponta que em 1917 o criptologista “Willian Frederick
Friedman, que será conhecido como ‘pai da criptoanálise dos EUA’ e criador do
termo ‘criptoanálise’ começa a trabalhar nesse cargo no Riverbank Laboratories, que
também presta serviços ao governo norte-americano”; ainda em 1917, o engenheiro
Gilbert Stanford Vernam cria uma máquina cifrante que usa uma chave totalmente
randômica e que nunca se repete. Ele ainda cria uma cifra baseada na Cifra de
Vigenère que leva seu nome; também nesse ano o chamado “Telegrama de
Zimmermann”, de autoria alemã, é interceptado e lido pelos ingleses, na chamada
P á g i n a | 40
Sala 40; no ano seguinte, em 1918, o general norte-americano Joseph Oswald
Mauborgne aperfeiçoa a cifra de Vernam, que fica conhecida como One-Time Pad;
nesse ano o engenheiro elétrico Arthur Scherbius cria uma máquina de cifragem
chamada Enigma, considerada a maior máquina de códigos de todos os tempos
(SINGH, 2001; COUTO, 2008).
Todos esses acontecimentos são bastante importantes para o rumo da
história, porém vamos nos deter em dois: a criação do One-Time-Pad e da Enigma.
Singh (2001, p. 134) define a cifra como “o Santo Graal da criptografia”. De fato, em
teoria, a cifra oferece segurança absoluta. Isso porque ela consiste em usar a cifra
de Vigenère com chaves tão grandes quanto a própria mensagem a ser cifrada, o
que acabava com a possibilidade da quebra cifra através da análise de frequência.
Isso, claro, só garante realmente a segurança se cada chave puder ser usada uma
única vez. Daí deriva o nome One-Time-pad (Bloco de Uso Único ou Bloco de Cifras
de uma única vez, em tradução literal). Além disso, é indispensável que essa chave
seja formada de uma sequência de letras completamente aleatórias, para garantir
que o criptoanalista não tenha qualquer chance de decifrar a mensagem.
O grande problema dessa cifra era o uso dela na prática, pois se na teoria
tudo era perfeito, como criar chaves tão grandes quanto o texto em uma guerra, na
qual eram enviados centenas de mensagens num único dia? Talvez se todas elas
fossem previamente criadas para depois serem distribuídas em grandes blocos para
todo o exército e marinha, pudesse dar certo, porém, se uma única delas caísse em
mãos inimigas, todo sistema de comunicação estaria comprometido (SINGH, 2001).
Portanto, a cifra One-Time-Pad era perfeita para a teoria, mas não para a
prática, que envolvia lápis e papel para cifrar e decifrá-la. Era preciso algo mais
eficiente. Desse pensamento surgiu a máquina Enigma. Essa invenção, como já foi
dito, ocorreu em 1918 por Arthur Scherbius, mas somente fora utilizada pelo exército
alemão em 1926.
O funcionamento da máquina é um tanto quanto complexo, e sua descrição
aqui neste trabalho seria inviável. Precisamos apenas entender que ela dispunha de
um instrumento que era conhecido como misturador, “a parte mais importante da
máquina” (SINGH, 2001, p. 146). As três unidades dessa peça garantiam a mistura
das 26 letras do alfabeto de forma aleatória, ou seja,
possibilidades.
Além disso, os misturadores poderiam mudar de ordem multiplicando esse valor
acima por seis, já que
. Sem contar um painel de tomadas que fazia uma
P á g i n a | 41
simples troca das letras (em formato monoalfabético), mas que garantia mais
possibilidades. Multiplicando tudo, temos:
Como podemos ver, era virtualmente impossível descobrir uma mensagem
cifrada pela Enigma, a não ser que se soubesse a disposição dos misturadores no
início da cifragem. Tentando pelo método da força bruta, um criptoanalista levaria
quase que a totalidade de tempo da duração do universo, caso verificasse cada
chave por minuto (SINGH, 2001). Surgiram outras máquinas semelhantes na época,
mas que não obtiveram sucesso por diferentes motivos, como as criadas pelo
holandês Alexander Koch, o Sueco Arvid Damm e o Americano Edward Hebern.
Figura 09 – Máquina Enigma
Fonte: Livraria de Imagens da Ciência e Sociedade de Londres. Disponível em
<http://www.scienceandsociety.co.uk/results.asp?image=10305535&itemw=4&itemf=0003&itemstep=
1&itemx=32>. Acesso em 02/01/2012.
O governo alemão começou a usar a Enigma em 1926. A partir daí, o mundo
todo ficou impossibilitado de ler as mensagens trocadas pelos militares alemães.
Singh (2001, p.163) é preciso ao dizer que “a Alemanha tinha agora a rede de
P á g i n a | 42
comunicações mais segura do mundo”. Isso aconteceu também devido à falta de
empenho por meio das maiores potências em quebrar essa cifra. A maioria achou
simplesmente que era impossível quebrá-la, por se tratar de uma máquina, e não
fizeram grandes esforços pra provar o contrário.
Havia, porém, uma nação emergente que dependia da interceptação e quebra
das mensagens alemãs: a Polônia. Localizado entre a então União Soviética e a
Alemanha, esse país tinha um potencial muito grande de ser invadido e, portanto,
necessitava de todas as armas possíveis para evitar esse acontecimento. O governo
polonês dispunha de um departamento de cifras chamado Biuro Szyfrów, o qual
demonstrava bastante competência na decifragem de mensagens estrangeiras. Em
1929, o capitão Maksymilian Ciezki, o encarregado de decifrar as mensagens
alemãs, tratou de recrutar matemáticos de uma universidade de uma parte do país
que fazia parte da Alemanha antes da primeira guerra mundial, por eles falarem
alemão fluentemente (COUTO, 2008; SINGH, 2001).
A pessoa de maior destaque foi Marian Rejewski, “um homem tímido de 33
anos que usava óculos” (SINGH, 2001, p. 169). Nota-se aí uma mudança no
recrutamento de pessoas para trabalhar com cifras, que passou a dar mais
credibilidade para matemáticos, em detrimento dos peritos em linguagens. O
brilhante Rejewski aproveitou-se do fato do governo francês ter obtido documentos
sobre o funcionamento da Enigma, através de um alemão descontente com seu
país, chamado Hans-Thilo Schmidt. De posse deles, Rejewski batalhou por mais de
um ano para conseguir ler as mensagens alemãs.
Para dar o merecido mérito, esse cientista conseguiu perceber padrões
através da interceptação de mensagens e daí traçou estratégias para diminuir o
número de tentativas, até um número razoavelmente pequeno, que pudesse ser
verificado pelo seu grupo de criptoanalistas. Pode não estar muito claro para o leitor,
mas, de fato, esse foi um salto extraordinário no que diz respeito à criptoanálise.
Singh (2001, p. 176), que explicou como Rejewski quebrou o código da Enigna em
seis páginas do seu livro, escreve ao final da análise: “A Enigma é uma máquina de
cifragem muito complicada e decifrá-la exigiu um imenso poder intelectual. Minhas
simplificações não devem levá-lo a subestimar a extraordinária conquista de
Rejewski”.
Quando os alemães fizeram algumas mudanças na Enigma, Rejewski
respondeu com a criação da chamada Bomba, uma máquina de decifragem da
P á g i n a | 43
Enigma. Com isso a Polônia foi capaz de ler as mensagens alemãs por boa parte da
década de 30. No entanto, os militares germânicos foram cada vez mais
aprimorando sua máquina cifrante deixando o número de possibilidades novamente
muito alto, o suficiente para que Rejewski e seus comandados não tivessem
recursos e capacidade técnica suficientes para verificar todas elas. A Polônia, que
havia chegado ao ápice de interceptações e decifragens de mensagens em 1938, se
viu completamente atordoada em 1939 com as modificações da Enigma.
Desesperados com a invulnerabilidade da máquina cifrante e com a
estratégia de blitzkrieg (guerra relâmpago) de Hitler, o governo polonês resolveu
divulgar seus avanços intelectuais e tecnológicos para os países Aliados. Singh
(2001, p. 180 e 181) relata o acontecimento da seguinte forma:
No dia 24 de julho, importantes criptoanalistas franceses e britânicos
chegaram ao quartel-general do Biuro, sem saber o que esperar. Langer (...)
puxou o pano, revelando dramaticamente uma das bombas de Rejewski. A
platéia ficou assombrada ao saber como Rejewski estivera decifrando a
Enigma havia anos. Os poloneses estavam uma década à frente do mundo.
Os franceses ficaram particularmente admirados, porque o trabalho dos
poloneses se baseara em resultados da espionagem francesa. Eles tinham
entregue as informações de Schmidt para os poloneses porque acreditavam
que elas não tinham nenhum valor, mas os poloneses mostraram que
estavam errados.
(SINGH, 2001, p. 180 e 181)
A Polônia, definitivamente, mudou o curso da história. Não fossem eles, os
Aliados não teriam obtidos métodos de quebra da Enigma tão cedo. Além disso, a
decisão de revelar suas conquistas ocorreram na hora certa: algumas semanas
depois, em 1º de setembro, Hitler invadiu o país.
2.5.3. As contribuições de Bletchley Park e Alan Turing
A partir daí, a decifração da Enigma estava nas mãos de outros países, de
maior recurso e capacidade técnica pra executar as tarefas necessárias. E isso
aconteceu, sobretudo, em Bletchley Park, a sede da Escola de Cifras e Códigos do
Governo (GC&CS) da Inglaterra. Inicialmente o local contava com duzentas
pessoas, mas em cinco anos esse número subiu para sete mil. Estudiosos de todo
tipo habitavam a grande mansão que ficava no centro da cidade, entre matemáticos,
linguistas, especialistas em xadrez, em palavras cruzadas, entre outros. Nos
primeiros meses, por terem mais recursos humanos, os habitantes de Bletchley Park
P á g i n a | 44
aplicaram as mesmas técnicas usadas por Rejewski e obtinham êxito. Além disso,
eles começaram a criar se próprios métodos de decifração da Enigma e perceberam
que algumas falhas humanas estavam deixando a segurança da cifra mais fraca, e
puderam explorar isso ao máximo (SINGH, 2001).
Muitos importantes estudiosos passaram por Bletchley Park, porém seu mais
ilustre morador chegou um mês depois: Alan Turing (1912 – 1952). Segundo Singh
(2001, p. 186) esse cientista foi “quem identificou a maior fraqueza da Enigma e a
explorou sem piedade. Graças a Turing tornou-se possível quebrar a cifra da
Enigma mesmo sob as circunstâncias mais difíceis”. Esse cientista, que fora
professor da Universidade de Cambridge anos antes, já era bastante respeitado aos
seus 26 anos, após o lançamento do seu trabalho mais influente, o “Sobre os
números computáveis”. Nele, Turing entra no debate proposto pelo lógico Kurt
Gödel, sobre a indecidibilidade, o qual propunha que nem tudo poderia ser provado
na matemática através da lógica. Turing, além de comprovar a teoria, forneceu aos
cientistas uma sólida base teórica para a construção dos primeiros computadores,
ressuscitando assim o conceito da Máquina de Diferenças nº 2 de Babbage.
Em Bletchley Park, Turing empenhou-se em achar outras fraquezas da cifra
da Enigma, pois os britânicos imaginavam que os alemães corrigiriam as que eles
estavam usufruindo, até então. Por várias semanas o cientista pensou em como
poderia realizar essa tarefa, analisando arquivos antigos de mensagens decifradas
da Enigma. Notou então que o modo de uso da máquina possuía certos padrões que
facilitavam a sua quebra, como mensagens mandadas diariamente, no mesmo
horário, com informação sobre o clima, por exemplo. Elas poderiam ser usadas
como cola, porque como eram comunicações militares, obrigatoriamente seguiam
um padrão, e certas palavras como “tempo” sempre estariam localizadas em locais
específicos. Também descobriu que os alemães nunca usavam os misturadores nas
mesmas posições do dia anterior, o que reduzia pela metade as possibilidades para
o próximo dia, além de que uma letra nunca poderia ser cifrada por ela mesma ou
pelas duas seguintes. Ou seja, a letra “d” não poderia ser cifrada por “d”, “e” ou “f”.
Os alemães acreditavam estar dificultando o trabalho dos Aliados com essas
medidas, no entanto estavam na verdade tornando suas cifras mais vulneráveis
(SINGH, 2001).
Com as suas descobertas, criou uma versão melhorada das Bombas de
Rejewski, que levaram o seu nome, dessa vez. Não tendo sucesso na primeira
P á g i n a | 45
versão da sua máquina, a segunda atendeu prontamente os ensejos de Turing e
todos de Bletchley Park. Ele, que era considerado um verdadeiro gênio por seus
colegas de trabalho, ganhara tanto prestígio que, desobedecendo a ordens de seu
superior direto, enviou, junto a outros cientistas, uma carta para o primeiro-ministro
inglês solicitando mais recursos para Bletchley Park, sendo atendido prontamente.
Figura 10: Bomba de Turing
Fonte: Livraria de Imagens da Ciência e Sociedade de Londres. Disponível em
<http://www.scienceandsociety.co.uk/results.asp?image=10307387&itemw=4&itemf=0003&itemstep=
1&itemx=4>. Acesso em 02/01/2012.
O último grande desafio da inteligência inglesa foi a quebra da cifra da
Enigma da marinha alemã, que usava uma versão da máquina bem mais sofisticada
e segura, além deles não cometerem os mesmos erros que os seus compatriotas em
terra estavam cometendo. As mensagens trocadas pela frota naval eram
consideradas impossíveis de serem decifradas. No entanto, os britânicos tinham
como exemplo o caso da Polônia, que apelara para a espionagem, na tentativa de
facilitar sua missão. Como os Aliados estavam visivelmente perdendo a batalha nos
mares, corriam sérios riscos de perderem também a guerra.
Como os navios alemães passavam muito tempo em mar, todos eles
possuíam livros-código a serem usados por mês, então se um fosse roubado, os
P á g i n a | 46
Aliados poderiam decifrar as suas mensagens durante igual período. E assim foi
feito: uma série de ataques a navios e submarinos alemães foi realizada e, dessa
forma, foram obtidos os livros. De posse deles, os Aliados puderam reverter a
situação da guerra marítima. Em contrapartida, os alemães começaram a suspeitar
que houvesse espiões Aliados entre eles, pois com o aumento repentino de ataques
a seus navios e submarinos só poderia ser explicado dessa forma, uma vez que “a
quebra da Enigma era considerada impossível e inconcebível” (SINGH, 2001, p.
207).
Depois de vencida a guerra, os heróis dos campos de batalha puderam contar
seus trunfos e histórias, ao contrário dos criptoanalistas que assinaram termos de
sigilo de suas funções durante a guerra. Isso acarretou em muitos dos intelectuais,
que foram tão importantes quanto os soldados que pegavam em armas, não
receberem os méritos por suas contribuições ainda em vida. Um dos casos mais
emblemáticos é o do próprio Alan Turing. Uma vez considerado gênio, cometeu
suicídio em uma cadeia, após ter sido acusado de “alta indecência”, por ser
homossexual. Lá, fora forçado a consultar um psiquiatra e a tomar hormônios que o
deixaram obeso e impotente. Em 7 de junho de 1954 comeu uma maçã que ele
havia mergulhado em uma solução de cianeto. O sigilo só acabou na década de 70,
quando a Enigma deixou de ser usada definitivamente (SINGH, 2001).
2.5.4. O código Navajo
Ainda durante a Segunda Guerra Mundial, não podemos esquecer da
contribuição dos índios Navajos para os Aliados. Como vimos, os alemães usaram a
máquina Enigma para cifrar suas mensagens, no entanto, ainda não mencionamos
que os ingleses e americanos também tinham suas máquinas de cifragem: a Typex
e SIGABA, respectivamente. Elas eram mais complexas que a Enigma, e
funcionaram perfeitamente, já que eram usadas corretamente por suas nações,
sendo assim consideradas indecifráveis durante a guerra. Porém elas não eram
práticas, como a Enigma, que poderia ser usada em campo de batalha, pois cada
mensagem que precisava ser cifrada e decifrada tinha que ser anotada no papel,
primeiramente, e depois ser passada para a máquina, além de elas serem
relativamente lentas, o que acarretava em muitos prejuízos, no calor da batalha.
P á g i n a | 47
Portanto, os Aliados precisavam de um método mais prático. Foi quando, em
1942, Philip Johnston, um engenheiro de Los Angeles, propôs o recrutamento de
nativos americanos, cuja língua própria era desconhecida para os próprios
americanos. Depois de uma pesquisa, foram escolhidos os Navajos, por ser o único
povo no qual os alemães não tiveram contato antes da guerra. Nesse mesmo ano,
29 navajos passaram por um treinamento de oito semanas, no qual foram
apresentados a alguns termos em inglês para objetos que não existiam no seu
cotidiano, como aviões, navios e submarinos. Esses termos foram substituídos para
nomes de pássaros e peixes, por exemplo (COUTO, 2008).
Dessa forma, os nativos ajudaram e muito os Aliados a vencerem a guerra,
porque uma mensagem que levaria quase uma hora pra ser cifrada e decifrada pela
SIGABA levava menos de cinco minutos pelos navajos. Esse código continuou
inquebrável por muito tempo. Infelizmente, assim como Alan Turing, os navajos só
obtiveram reconhecimento muitos anos depois de terminada a guerra, pelo sigilo em
que foram obrigados a manter. Apenas em 1982 eles foram homenageados pelo
governo americano, ao batizar o dia 14 de agosto como “Dia Nacional dos
codificadores navajos”.
2.5.5. O surgimento da Criptografia computadorizada
Como podemos perceber, as máquinas foram decisivas na Segunda Guerra
Mundial. Algumas delas que tinham como função a cifragem de mensagens, e
outras a decifragem. Apesar da Enigma ser a mais conhecida, a Alemanha dispunha
de outra máquina: a Lorenz SZ40. Ela responsável pela comunicação direta de Hitler
e seus generais, e sua cifra era mais complexa que a da Enigma.
A quebra dessa cifra não era páreo para as bombas de Turing, pois exigiam
certa flexibilidade para as sutilezas da Lorenz. Foi então que o matemático Max
Newman projetou um mecanismo de decifragem da máquina de Hitler, baseando-se
no conceito criado por Alan Turing. Tratava-se de um computador programável.
Depois de ser rejeitado, primeiramente, o projeto foi iniciado quando o engenheiro
Tommy Flowers decidiu levar as plantas para o centro de pesquisa dos correios, no
norte de Londres. Em 8 de dezembro de 1943 ele entregou em Bletchley Park a
máquina Colossus, o primeiro computador da história. Ela usava 1500 válvulas
P á g i n a | 48
eletrônicas, o que aumentava bastante sua velocidade com relação às outras
existentes, e tinha a incrível capacidade de ser programável.
Figura 11 – Computador Colossus
Fonte: Livraria de Imagens da Ciência e Sociedade de Londres. Disponível em
<http://www.scienceandsociety.co.uk/results.asp?image=10307367&itemw=4&itemf=0003&itemstep=
1&itemx=9>. Acesso em 02/01/2012.
A partir daí a evolução dos computadores só fez crescer, e com isso, a
criptografia e, consequentemente, a criptoanálise também. Os computadores
ampliaram e muito a concepção dessas ciências, criando muitas novas
possibilidades. Porém, nessa época ainda estavam presas aos militares, pois não
era qualquer um que tinha computadores. Situação que começou a mudar no início
da década de 50, com a invenção dos transistores, que tornaram as máquinas mais
baratas e passíveis de serem comercializadas. Porém, revolução mesmo ocorreu no
final dessa década, quando foram inventados os circuitos integrados, que
potencializava ainda mais a comercialização dos computadores.
Com muito mais empresas podendo adquirir e manter uma máquina dessas, a
cifragem de suas comunicações, como negociações comerciais ou transferência de
dinheiro também aumentou. O grande problema era que cada empresa tinha seu
próprio sistema de cifragem, o que confundia a todos. Até que na década de 70, o
P á g i n a | 49
Bureal nacional de padrões norte-americano propôs a criação de um sistema único
de cifragem, e pediu sugestões para cientistas. Primeiramente, nenhuma proposta
foi feita. Na segunda tentativa apareceu o DES (Data Encryption Standard ou
Padrão de Cifragem de Dados). Desenvolvido pela IBM em 1970, através de um
grupo liderado por Horst Feistel, o DES tornou-se o sistema de cifragem padrão dos
Estados Unidos por décadas. Antes passou por algumas modificações, como o
nome, que era chamado de sistema Lucifer, e o tamanho da chave. Com relação a
esse último item, quem fez a proposta de redução foi a NSA (Nacional Security
Agency ou Agência de Segurança Nacional). Singh (2001, p. 273) a define da
seguinte forma:
(...) a organização responsável pela manutenção da segurança das
comunicações militares e do governo, que também tenta interceptar e
decifrar as comunicações estrangeiras. A NSA emprega mais matemáticos,
compra mais equipamentos de computação e intercepta mais mensagens
do que qualquer outra organização do mundo. É a líder mundial no que se
refere a escuta.
(SINGH, 2001, 273)
A NSA propôs a redução do tamanho da chave, que era de 64 bits para uma
de 56 bits, para que a segurança nas comunicações fosse mantida, mas que ela
ainda pudesse ser capaz de decifrar as mensagens, pois se fosse mantido o
tamanho original da chave, a cifra era tão segura que nem a própria agência poderia
quebrar.
O DES, que transforma as letras em números binários, é altamente eficaz
porque embaralha todos esses números em 16 rodadas de manipulação, algo que
tornava os computadores da época incapazes de verificar todas as possibilidades
existentes, tornando-a assim extremamente segura.
Com o DES, o problema da padronização foi resolvido. No entanto, havia
outro: com o crescente uso da criptografia por mais organizações, como lidar com a
distribuição de chaves, de modo a garantir a segurança de milhares de negócios,
que geralmente envolviam muito dinheiro? É o que vamos ver na próxima seção.
P á g i n a | 50
3. CRIPTOGRAFIA RSA
Nesta seção apresentamos a necessidade de resolução do problema da
distribuição de chaves, o que gerou o modelo de criptografia com chaves
assimétricas, tendo com sua principal exemplo a cifra RSA.
3.1. NECESSIDADES E DESAFIOS DA CRIPTOGRAFIA NA DÉCADA DE 70
O grande problema da criptografia ao longo da história e principalmente no
século XX era a troca de chaves de forma segura, pois para duas partes se
comunicarem entre si, era preciso uma terceira para o transporte das chaves ou
encontros periódicos para a troca delas.
Com a criação de um projeto de computadores conectados batizado de
ARPAnet, criado em 1969 que, mais tarde, em 1982, deu origem à internet,
Whitifield Diffie(1944 -), um matemático e criptógrafo norte-americano, motivado pela
sua visão de mundo conectado, se interessou pelo envio de informações de forma
confidencial, mas esbarrou no problema das trocas de chaves de forma segura
(ARAUJO e SOUZA, 2010).
Você deve estar pensando que se duas pessoas querem trocar mensagens
de forma confidencial ente si, uma solução seria eles marcarem encontros
periódicos para trocar chaves suficientes para um mês todo; mas o que aconteceria
se uma delas, por motivo de doença, por exemplo, fosse impossibilitada de ir ao
encontro? Nesse caso, seria preciso uma terceira pessoa para o envio de
mensagens.
Na década de 1970 os bancos tentaram distribuir chaves usando viajantes
que estavam entre os empregados de maior confiança da empresa. Esses
estafetas percorriam o mundo com valises trancadas, distribuindo
pessoalmente as chaves pra todos os que receberiam mensagens do banco
na semana seguinte. Mas à medida que as redes de negócios aumentavam
em complexidade, mais mensagens eram enviadas e mais chaves tinham
que ser entregues. Os bancos logo descobriram que esse processo de
distribuição tornara-se um horrível pesadelo logístico, e os custos ficaram
proibitivos.
(SINGH, 2001, p. 275)
Costuma-se usar para ilustrar os problemas de criptologia três personagens
fictícios em uma determinada situação. Os personagens são Alice, Bob e Eva onde
P á g i n a | 51
Alice e Bob querem trocar mensagem de forma confidencial em um lugar onde as
empresas de troca de mensagens não são confiáveis, e Eva tenta interceptá-la.
Diffie começou a pensar em formas de Alice e Bob trocarem chaves sem a
necessidade que se encontrassem e, ainda de forma segura, para que Eva não
conseguisse descobrir tais chaves. Uma solução para o caso seria Alice e Bob
contratarem mensageiros para entregar as mensagens, mas como os mensageiros
não são confiáveis, essa não seria uma boa idéia. Diffie pensou na seguinte
situação: Alice envia sua mensagem em um baú e tranca-o com cadeado que só ela
tem a chave; o mensageiro leva o baú até Bob que põem outro cadeado que
somente ele tem a chave; então o mensageiro volta até Alice que destranca o
cadeado que ela colocou e reenvia o baú para Bob, apenas com o cadeado dele
(SINGH, 2001).
Esse sistema garante que a mensagem tenha sido enviada com sigilo, mas
não era muito funcional na prática, pois o fato de que a mensagem passasse duas
vezes por Bob e por Alice e o uso do mensageiro aumentaria os custos. No entanto,
este modelo serviu como base para que Diffie e Martin Hellman, outro criptógrafo
nascido em 1945, procurassem um método prático para solucionar o problema de
distribuição de chaves, já que o modelo de cifragem dupla não requer a troca de
chaves.
Então Diffie e Hellman, que mais tarde receberam a ajuda de Ralph Merkle
(um intelectual que também se interessava pelo problema das trocas de chaves), se
empenharam na tarefa de encontrar funções matemáticas de mão única, pois a
maioria delas é considerada de mão dupla, ou seja, que apresentam facilidade pra
criptografar e descriptografar ao mesmo tempo. Por exemplo, uma função que
representa as letras do alfabeto como sendo número, como A
etc., cuja fórmula é
. Se usarmos
,B
,C
,
, ou seja, a letra A
passaria a ser a letra E. Esse é um método fácil de criptografar, e isso é positivo. No
entanto, para descriptografar, o processo é inverso e, portanto, apresenta certa
facilidade, já que devemos apenas subtrair
e dividir por
. Já os processos
considerados de mão única são aqueles irreversíveis ou então quase impossíveis de
serem revertidos, que Singh (2001, p. 286) usa como exemplo o ato de “misturar
tinta amarela com tinta azul para produzir tinta verde” pela facilidade em misturar as
tintas, mas ser quase impossível desfazer a mistura.
P á g i n a | 52
Nessa procura por funções de mão única encontraram a aritmética modular,
que é um campo rico em funções desse tipo. Para explicar melhor como funciona
uma função modular, usamos uma comparação com o relógio analógico, onde as
horas são apresentadas de maneira circular. Por exemplo, suponha que o ponteiro
pequeno marque 2 horas em ponto. Daqui a três horas o ponteiro marcará 5 horas,
porém, passadas mais dez horas, o relógio não marcará 15 horas, mas sim 3 horas.
Figura 12 – Relógio Analógico
Fonte: Própria
Na aritmética modular dizemos que 15 é congruente à 3 módulo 12
. Os cálculos e os valores estão em função do valor do módulo, pois todo
número pode ser representado pelo valor do resto da divisão dele mesmo pelo valor
do módulo. Primeiro os cálculos são realizados usando a aritmética normal. Depois,
para saber a resposta em
, a dividimos por
, encontrando o quociente
inteiro e anotamos o resto. Por exemplo, para achar o valor de
primeiro efetuamos a operação
; depois dividimos o resultado por
:
, com resto igual a
É importante ressaltar que as propriedades de funções exponenciais se
mantém quando contidas na função modular.
Em 1976, depois de passarem dois anos estudando a aritmética modular e as
funções de mão única, Hellman descobriu uma solução para o problema da troca de
chaves. A ideia dependia de uma função de mão única da forma
esquema, Alice e Bob escolhem inicialmente os valores de
. Nesse
e , sendo que esses
P á g i n a | 53
valores não são secretos, ou seja, eles podem trocar essas informações sem se
preocupar que Eva descubra esses valores.
Vamos ilustrar o procedimento com um exemplo:
Alice e Bob escolhem primeiramente os
valores de Y e P, que poderiam ser, por
exemplo, 5 e 13, respectivamente.
Alice escolhe um número que
vamos chamar de A, digamos 7, e
o mantém em segredo.
Alice introduz o 7 na função de mão
única e o resultado de
:
Bob escolhe um número que
vamos chamar de B, digamos 4, e
o mantém em segredo.
Bob introduz o 4 na função de mão
única e o resultado de
:
Alice chama o resultado dos
Bob chama o resultado dos
cálculos de e envia o seu
resultado para Bob.
cálculos de e envia o seu
resultado para Alice.
Normalmente este seria um momento crucial porque Alice e
Bob estão trocando informações e, portanto, esta é uma
oportunidade para Eva escutar e descobrir os detalhes da
informação transmitida.
Contudo, Eva pode ouvir sem comprometer a segurança final
do sistema. Alice e Bob podem usar a mesma linha telefônica
através da qual escolheram os valores de e , e Eva pode
interceptar esses números que estão sendo trocados, ou
seja, 5 e 4. Contudo esses números não são a chave, e por
isso não importa que Eva os conheça.
Alice pega o resultado do Bob e
calcula a solução de
:
Bob pega o resultado do Alice e
calcula a solução de
:
Miraculosamente Alice e Bob
terminaram com o mesmo número
1. Esta é a chave!
Figura 13 – Esquema para obtenção de uma chave sem a necessidade de um encontro físico.
Fonte: Adaptado de Singh (2001, p.290).
Singh (2001, p. 291) compara este processo com a seguinte situação:
P á g i n a | 54
(...) vamos presumir que todos, incluindo Alice, Bob e Eva, possuam um
frasco de três litros contendo um litro de tinta amarela. Se Alice e Bob
desejam obter uma chave secreta, eles acrescentam um litro da cor secreta
de cada um ao seu próprio frasco. Alice pode colocar um tom peculiar de
púrpura, enquanto Bob pode colocar vermelho. E cada um envia seu frasco
de tinta misturada para o outro. Finalmente Alice pega a mistura de Bob e
acrescenta um litro de sua própria cor secreta. Ao mesmo tempo Bob pega
a mistura de Alice e acrescenta um litro de sua própria cor secreta. Ambos
os frascos agora devem apresentar a mesma cor, porque ambos contêm um
litro de amarelo, um litro de púrpura e um litro de vermelho. E é esta cor
exata dos frascos, duplamente contaminados, que será usada como chave.
Alice não tem ideia de qual foi a cor colocada por Bob e Bob não tem ideia
da cor acrescentada por Alice, mas ambos obtiveram o mesmo resultado.
Enquanto isso, Eva está furiosa.
(SINGH, 2001, p. 291)
No entanto, mesmo que esse sistema conhecido pelo nome Diffie-HellmanMerkle fosse um grande salto, não era perfeito, pois para Alice cifrar sua mensagem,
ela precisa escolher uma chave juntamente a Bob. E pra que essa troca seja feita é
preferível que os dois estejam conectados ao mesmo tempo, pois o estabelecimento
da chave exige uma troca mútua de informações, e isso prejudica a espontaneidade
do envio de mensagens.
Ainda havia outro problema no sistema Diffie-Hellman-Merkle, pois além de
não resolver totalmente o problema da distribuição de chaves, como vimos, ele não
era muito prático. Imagine que Alice queira trocar mensagens cifradas com um
número muito grande de pessoas. Primeiramente ela teria que estabelecer contato
com todas as pessoas para escolher o valore
e
e estabelecer a chave, logo isso
poderia levar algum tempo e não poderia ser feito simultaneamente, a não ser que
todos, inclusive Alice, adotem o uso de valores padrões para a chave. Porém isso
prejudicaria muito a segurança do método, uma vez que dependeria da
responsabilidade de cada um guardar os valores da chave, pois, se de alguma
forma, Eva esteja infiltrada entre os remetentes de Bob e Alice, ela teria acesso à
chave e poderia decifrar todas as mensagens cifradas. Portanto quanto maior o
número de remetentes de Alice, menor a segurança da cifragem.
Mas o problema da troca de chaves foi finalmente superado com a ideia que
Diffie elaborara: nele incorporava-se a chave assimétrica. O grande problema do
sistema anterior era que as chaves que eram usadas para cifrar e decifrar eram as
mesmas, e sistemas assim são chamados de simétricos. Todos os sistemas de
cifragem até então era simétricos. Em um sistema assimétrico, as chaves de
P á g i n a | 55
cifragem e de decifragem são diferentes, logo, se Alice souber a chave cifrante, ela
pode cifrar a mensagem, mas não pode decifrá-la, para isso precisaria da chave de
decifragem. “Esta distinção entre a cifragem e decifragem é o que torna a cifra
assimétrica tão especial” (SINGH, 2001, p. 294).
Nesse contexto, podemos imaginar que a chave de cifragem de Alice é um
número e a chave de decifragem é outro número. Assim, Alice mantém em segredo
a sua chave que é responsável por decifrar e pode distribuir a sua chave cifrante
para todos que quiserem lhe enviar mensagem possam saber sem comprometer a
confidencialidade da mensagem. É por isso que esta chave é comumente chamada
de chave pública. Assim, se Bob deseja envia uma mensagem para Alice, basta
procurar a chave pública dela, que poderia estar em uma lista como a telefônica, por
exemplo. Bob então usa a chave pública para cifrar a mensagem e enviar para Alice,
que poderá decifrá-la com sua chave particular. Singh (2001, p. 295) afirma que “a
grande vantagem desse sistema é que não há envios e recepções de números como
no sistema de troca de chaves de Diffie-Hellman-Merkle, [...] além disso, cifra
assimétrica elimina o problema de distribuição de chaves”.
Agora Bob não precisa esperar que Alice lhe envie informações antes de
cifrar e mandar a mensagem para ela, ele só precisa obter a chave de cifragem
pública usada por ela; e Alice não precisa se preocupar em enviar a chave de
cifragem em segurança, ao contrário, ela tem interesse em divulgar a chave pública
para um número cada vez maior de pessoas para que possam lhe enviar
mensagens em segurança.
Esse método de cifragem proposto por Diffie é o inverso da cifra simétrica
tradicionalmente usada, onde a chave usada para cifragem era igual a usada para
decifragem, de modo que Alice e Bob precisariam tomar muito cuidado para que
esta chave não caia nas mão de Eva. A ideia de método de cifragem assimétrico
pode ser comparada ao ato de fechar e abrir um cadeado, onde qualquer pessoa
pode fechar (cifrar) o cadeado simplesmente apertando o fecho no lugar, mas
somente quem tem a chave do cadeado (chave particular) pode abri-lo (decifrar). É
como se Alice enviasse cadeados para todos que quisessem lhe enviar mensagem,
assim, Bob pode escrever uma mensagem, colocar dentro de um baú e enviar para
Alice, e somente Alice tem a chave para abrir o cadeado (SINGH, 2001).
É importante ressaltar que, embora Diffie tivesse elaborado a idéia de uma
cifra assimétrica, ele não tinha uma que servisse de exemplo. O sistema parece
P á g i n a | 56
simples quando explicados em analogias a chaves e cadeados, mas encontrar uma
função matemática que faça a mesma coisa é um trabalho longe de ser banal. No
verão de 1975, Diffie publicou um resumo da sua idéia, o que fez com que muitos
cientistas procurassem por uma função de mão única apropriada que se adequasse
aos critérios de uma cifra assimétrica.
Em 1976 a equipe Diffie, Hellman e Merkle revolucionaria a criptografia.
Primeiro porque criaram o sistema que solucionaria o problema da distribuição de
chaves, o sistema de troca de chaves Diffie-Hellman-Merkle, que era imperfeito, mas
que poderia ser operado; em seguida por propor o sistema de cifragem assimétrica,
que era perfeito, mas até então, não funcionava.
A descoberta de uma função de mão única que pudesse ser usada em um
sistema de criptografia assimétrico veio de outro trio, dois cientistas computacionais
e um matemático: Ronald Rivest e Adi Shamir e Leonard Adleman, respectivamente.
Após muitas tentativas e fracassos, onde os cientistas eram responsáveis por criar
um possível sistema que solucionaria o problema e o matemático se encarregava de
encontrar falhas, em um determinado dia, Adleman não encontrou uma falha sequer
no sistema proposto por Rivest. Deu-se origem então ao sistema que seria chamado
a partir das iniciais dos nomes de seus criadores, o sistema RSA (Rivest, Shamir,
Adleman), que se tornou a cifra mais influente da criptografia moderna (TKOTZ,
2005i).
O sistema RSA depende de uma função modular de mão única que pode ser
usada para cifrar a mensagem, mas que para decifrá-la esta pessoa precisaria de
uma informação especial. De forma geral, nesse sistema, precisamos de três
informações¸ dois números primos
e
multiplicação dos dois primos. O valor de
e o número
que é o resultado a
é uma informação pública, que será
aplicada a função junto com a mensagem para cifrá-la, mas para decifrá-la é preciso
conhecer
e , e como
é um valor flexível, cada pessoa pode ter sua própria
chave. Assim, podemos pensar em
como a chave pública, informação disponível
para qualquer pessoa e necessária para cifrar as mensagens; já
e
são a chave
particular, informação necessária para decifrar a mensagem.
Você pode estar pensando que não deve ser tão difícil encontrar
conhecendo
uma vez que
é resultado de
e
e . Em primeiro lugar, pelo teorema
da fatoração única, enunciado primeiramente por Gauss no seu livro Disquisitiones
P á g i n a | 57
arithmetiae, este produto tem a forma única
e
, onde
suas multiplicidades. Portanto os únicos primos que geram
única forma de obtê-los através de
são fatores primos
são
e
e a
é a fatoração. Como os matemáticos têm tido
grande dificuldade em encontrar um método rápido e eficiente para descobrir quais
foram os números primos usados para gerar outros números, se
for um número
suficientemente grande, será praticamente impossível deduzir os valores de
e .É
baseada nisso que a segurança da criptografia RSA é tida como plenamente
satisfatória.
Por exemplo, digamos que Alice tenha criado
, para obter
a partir dos primos
basta multiplicar, com qualquer calculadora, os valores de
e encontrar o valor de
descobrir os valores de
, que é
e
e
e
. Entretanto se em vez disso tentássemos
a partir do valor
não seria uma tarefa tão
fácil, pois os métodos de fatoração conhecidos não são tão eficientes. É isso que faz
a função ser considerada como de mão única (SINGH, 2001).
Em 1903, Frank Nelson Cole, professor de matemática da Universidade de
Columbia, em Nova York, deu uma palestra curiosa em um encontro da
Sociedade Norte-Americana de Matemática. Sem dizer uma palavra,
escreveu um dos números de Mersenne em um quadro-negro e, no quadro
ao lado, escreveu a multiplicação de dois números menores. No meio,
colocou um sinal de “igual”, e então se sentou.
A platéia ficou em pé e aplaudiu — uma efusão rara em uma sala cheia de
matemáticos. Mas seria tão difícil multiplicar dois números, mesmo para
matemáticos da virada do século? Na verdade, Cole havia feito o oposto. Já
se sabia desde 1876 que
, um número de Mersenne de 20
algarismos, não era primo, sendo o produto de dois números menores.
Porém, ninguém sabia quais eram esses números. Cole precisou gastar as
tardes de domingo durante três anos seguidos para “decifrar” os dois
componentes primos desse número.
(SATOY, 2007 p. 240)
Para o caso de ainda não estar convencido da dificuldade de fazer a
operação inversa ou de encontrar números primos grandes, tente encontrar o
valores primos que deram origem ao número
de
e
. Para deduzir os valores
precisamos calcular os valores que se multiplicados um pelo outro, geram
, e a única maneira é fatorar.
A fatoração é um processo trabalhoso e que exige muito tempo, pois todas
envolvem, essencialmente, verificar cada número primo para ver se ele divide
. Se
P á g i n a | 58
tentarmos primo a primo, começaremos por
que é primo, mas não divide
deixar resto, então passamos para o número
que é primo mas também não divide
e assim por diante até chegarmos no número primo
da sequência, e um fator de
valor, é fácil encontrar o segundo
sem
que é o de numero
. Depois de encontrar o primeiro
. Se usássemos uma calculadora que
verificasse quatro números por minuto, levaríamos 500 minutos para encontrar, ou
seja, mais de oito horas. Mas para gerar o valor de
multiplicando
e
, não
precisaríamos de mais que um minuto com uma calculadora.
O nível de segurança, nesse caso, não é muito grande, mas se escolhermos
primos maiores, que resultassem em
na casa de
, Singh (2001 p. 303) afirma
que “os esforços combinados de cem milhões de microcomputadores levariam mais
de mil anos para quebrar esta cifra. Com valores suficientemente grandes de
e ,
a RSA é invencível”.
Antes de continuarmos, é importante analisarmos alguns dos métodos e
fórmulas que foram criados para encontrar ou estimar números primos, ao longo da
história.
3.2. NÚMEROS PRIMOS
Como sabemos, a segurança da criptografia RSA depende de sermos
capazes de escolher dois primos grandes, na casa dos 60 ou mais algarismos cada.
Os números primos sempre foram objeto de estudo dos matemáticos durante toda a
história, e existem grandes dificuldades em encontrar e traçar fórmulas para
descobrir números primos. Mostraremos, nessa sessão, algumas tentativas.
Muitos matemáticos tentaram descobrir padrões para o aparecimento de
números primos na sequência de números inteiros e assim, gerar fórmulas que
determinem números primos. Por muito tempo, nenhuma tentativa foi bem sucedida.
Todas elas acabam por classificar esses números de acordo com o seu
comportamento, ou seja, de acordo com a fórmula ou método pelo qual é possível
encontrá-lo. Dentre essas classificações e formulas podemos citar a fórmula
polinomial, o Teorema de Fermat e o método de Gauss, por exemplo. Vejamos,
então, essas e mais algumas.
P á g i n a | 59
3.2.1. Fórmula Polinomial
A fórmula polinomial é uma das mais simples para encontrar primos, pois ela
nos diz que um polinômio na forma
onde os coeficientes
condição “
são números inteiros que satisfazem a
é primo, para todo o inteiro positivo
”.
Vamos calcular os valores do polinômio para os dez primeiros inteiros
positivos no polinômio de segundo grau
.
Tabela 02 – 10 primeiros números da fórmula polinomial para números primos.
É possível notar que quando
exceto para
é impar,
, ou seja, só é possível ser primo se
é par e, portanto não é primo,
for par, mas
que é
composto, logo este polinômio está longe de nos dar a fórmula para números
primos.
Entre essas tentativas de encontrar formulas para encontrar números
podemos destacar duas de grande importância histórica, são elas as de Mersene e
Fermat.
P á g i n a | 60
3.2.2. Números de Mersenne
Números de Mersenne são os números da forma
, e determinar
quais desses números são primos é uma questão herdada da Grécia. Marin
Mersenne era um frade matemático amador do século XVII, que se correspondia
com muitos matemáticos da sua época, entre eles¸ Fermat. Ele afirmou que os
números da forma
e
seriam primos quando
; e compostos para os outros valores primos menores que
Os valores de
teriam que ser primos, pois, caso contrário,
composto. É fácil provar este fato se
Portanto se
divide
.
será
é composto, então
então
divide
, mas como o enunciado indica,
nem todo primo resultará em outro primo, pois
é composto, pois,
Mersenne não apresentou nenhuma justificativa para estes resultados, como
era muito comum na época. Posteriormente foram encontrados alguns erros na lista,
o primeiro foi encontrado por Persvusin e Seelhof em 1886, descobriram que
é primo, outros erros foram encontrados depois. Além de
e
e inclui os compostos
e
, a lista omite
.
De acordo com Dias (2008, p. 37), “ainda hoje existem questões abertas
sobre a infinitude dos números primos e compostos de Mersenne. O maior primo de
”.
Mersenne conhecido até agora é:
Fermat desenvolveu um método para encontrar fatores para os números de
Mersenne tais que
seja primo com
um número primo.
3.2.3. Método de Fermat (em relação aos números de Mersenne)
Seja
um número e
um fator primo de
. Então
para
algum inteiro positivo . Vamos usar este método para achar um fator de
. Temos que qualquer fator primo de
é da forma
. Vamos
P á g i n a | 61
atribuir valores a
e testar em cada caso se temos fator. Sabemos que se
composto, então tem um fator
for
. Logo
como
então
Quando
,
. Logo só temos que tentar
Mersene conhecido é
. O maior primo de
.
3.2.4. Números de Fermat
Outra fórmula conhecida para encontrar primos é de autoria de Fermat, em
uma carta para um matemático amador, o cavalheiro Frenicle, onde Fermat
enumerou os elementos da forma
, para os valores inteiros de
e , que apresentamos na tabela a seguir:
Tabela 03 – Seis primeiros números de Fermat.
entre
P á g i n a | 62
Assim, conjecturou que todos os números desta forma são primos. Mas essa
conjectura foi refutada por Leonhard Euler em 1732, quando mostrou que
era
composto.
3.2.5. Primos de Shophie Germain
Alguns números primos podem ser encontrados na forma
, e os
chamamos de primos Shophie Germain. São exemplos destes números os primos ,
, ,
e
. O maior número primo conhecido na forma de Shophie Germain é o
número
.
3.2.6. Fórmulas Fatoriais
Coutinho (2000) diz que dado
um primo positivo, construiremos uma função
semelhante ao fatorial, só que apenas os primos são multiplicados. Vamos chamar
de
o produto de todos os primos menores ou iguais a . Por exemplo
, estamos interessados em números da forma
, veremos o porquê abaixo:
Tabela 04 – Números primos gerados pela fórmula fatorial
Note que todos os números da terceira coluna são primos, mas se fizermos
teriamos
, que é composto. Essa formula não é
uma das melhores para encontrar primos. Sua importância não está na
determinação de números primos, afinal, são conhecidos apenas 16 primos, sendo
que o maior corresponde a
. Porém, essa formula é importante, pois
permite concluir o seguinte teorema: Existem infinitos números primos.
Uma das demonstrações mais importante desses teoremas é a de Euler em
1737, em que ele considera o produto
P á g i n a | 63
onde temos que para cada número primo. Se houvesse uma quantidade finita
de números primos, esse produto seria igual a um número real positivo. Assim, por
contradição, é preciso mostrar que isto não é verdade. Euler verificou primeiro que
é igual à soma
Esta soma tende a se elevar cada vez mais, então não há dificuldade para
mostrar que ela é divergente. Logo, não pode haver uma quantidade finita de
números primos.
3.2.7. Crivo de Eratóstenes
Eratóstenes foi um matemático, historiador, filósofo, astrônomo e geógrafo
grego que nasceu em Cirene por volta de 275 a.C e morreu em Alexandria em 194
a.C. Foi o criador de um dos mais antigos métodos para encontrar números primos,
o chamado “crivo de Eratóstenes”, que não envolve nenhuma fórmula matemática
explicita (COUTINHO, 2004).
O crivo funciona como uma espécie de peneira que só deixa passar os
números primos, ele determina todos os primos até certo inteiro positivo
Começamos listando os números impares de
primo par). Digamos que
a
(ímpares porque
.
é o único
, então teremos os números
Depois de formada a lista, procedemos da seguinte maneira: o primeiro
número da lista é o
, então riscamos os números de três em três, assim serão
riscados todos os números múltiplos de .
P á g i n a | 64
Fazemos o mesmo com o número
e assim com os próximos números, até
riscarmos todos o números que são múltiplos que outros
Podemos parar na terceira passagem (de 7 em 7), pois a lista continua a
mesma se riscarmos os múltiplos de 11.
Isto garante que os números restantes não sejam múltiplos de nenhum dos
números anteriores, logo os números primos menores que 39 são os listados acima.
Como podemos notar, no crivo de Erastóstenes há números que são riscados
mais de uma vez, o 21, por exemplo, que já havia sido riscado como múltiplo de 3,
foi riscado também como múltiplo de 7. Existem formas de amenizar esse problema
de riscar um número mais de uma vez, porém não de eliminá-lo totalmente.
Coutinho (2000, p. 65) afirma que “não podemos creditar isso como um defeito;
afinal, o objetivo do algoritmo é achar todos os primos até , e isto não é razoável se
tiver
algarismos”.
3.2.8. A pergunta de Gauss
Em 1792, aos 15 anos de idade, Gauss adotou uma estratégia diferente. Um
ano antes, ele havia ganhado um livro de logaritmos onde, na contracapa, havia uma
tabela de números primos. Gauss, conhecido pela facilidade em encontrar
regularidades, percebeu, após cálculos extensos, uma relação entre assuntos
aparentemente desconexos.
Os números primos fascinavam Gauss porque eram totalmente aleatórios, e
não existe nenhuma maneira de prever quando esperar o primeiro primo depois do
número 1000. Mas Gauss, tinha uma pergunta diferente sobre os números primos, e
a tentativa de responder essa pergunta foi a responsável pelo grande avanço dele.
Em vez de tentar encontrar primos, ele buscou descobrir quantos primos haveria
P á g i n a | 65
entre os 100 primeiros números, depois entre os 1000, entre os 10000 e assim por
diante. Assim, se pegarmos um número
quantos números primos existem entre
, poderíamos fazer uma estimativa que
e ?
Se analisarmos, veremos que existe 25 números primos entre 1 e 100, isso
significa que temos 25% de chance de encontrar um número primo se escolhermos
um número qualquer nesse intervalo. Mas o que acontece se aumentarmos essa
proporção, entre 1 e 1000000, por exemplo? Analisando-a na tentativa de responder
essa pergunta, Gauss notou um padrão à medida que a contagem se elevava,
apesar de toda a aleatoriedade. Vejamos a tabela a seguir:
Número de primos de 1 a
,
frequentemente chamado de
.
Em média quantos números
precisamos contar até atingir um
número primo.
10
4
2,5
100
25
4,0
1.000
168
6,0
10.000
1.229
8,1
100.000
9,592
10,4
1.000.000
78.498
12,7
10.000.000
664.579
15,0
100.000.000
5.761.455
17,4
1.000.000.000
50.847.534
19,7
10.000.000.000
455.052.511
22,0
Tabela 05 – Crescimento do número de primos, por Gauss.
Fonte: Sautoy (2007, p. 57)
Esta tabela demonstra mais claramente a regularidade que ele descobriu. Se
observarmos a ultima coluna, na primeira linha, temos a chance de encontrar um em
cada quatro. Para
maior que 10000, essa última coluna parece estar aumentando
em aproximadamente 2,3 em cada etapa. Portanto, para cada potencia de 10,
devemos acrescentar cerca de 2,3 à razão entre o números primos e a quantidade
de números no intervalo. A proporção de primos aumentava de 2,3, e não de 1,
enquanto a quantidade de números aumentada em potências, isso porque os
números primos seguem um logaritmo cuja base não é uma potencia de 10.
P á g i n a | 66
O que Gauss descobriu foi o fato de que os primos podem ser contados
usando-se logaritmos cuja base é um número chamado
aproximado de
O número
, que tem o valor
, ocorre em toda parte no mundo
matemático, e é por isso que os logaritmos na base e são chamados “naturais”. “A
tabela que Gauss descobriu aos 15 anos de idade o levou à seguinte conjectura:
entre os números
a
, aproximadamente um em cada
denota o logaritmo de
número de primos entre
e
na base
será primo (onde
). Assim, Gauss podia estimar que o
era de aproximadamente
” (SAUTOY, 2007, p.
58). Mas é importante ressaltar que Gauss afirmava que essa não era a fórmula que
indicaria o número exato de primos até
¸ e sim, que era uma estimativa com um
bom grau de precisão. Enquanto os matemáticos estiveram a procura de fórmulas
para prever a localização precisa do próximo primo, Gauss tentou encontrar um
padrão entre eles, fazendo uma pergunta mais ampla: queria saber qual a
quantidade de primos entre um e um milhão em vez de localizar os primos entre
esses dois números.
Para ilustrar a força do padrão descoberto por Gauss, podemos observar um
gráfico da função
, contando o número de primos de
a
, com
. O
gráfico conta a quantidade cumulativa de primos até o número 100:
:
Figura 14: Gráfico da quantidade de números primos até 100.
Fonte: Sautoy (2007, p. 29)
Agora observe a função ao analisarmos a mesma função em uma escala
maior, calculando
ao longo de uma faixa muito mais ampla de números, por
exemplo, até 100.000:
P á g i n a | 67
Figura 15: Gráfico da quantidade de números primos até 100.000.
Fonte: Sautoy (2007, p. 60)
A revelação de que o gráfico parece subir tão suavemente, embora os primos
sejam tão imprevisíveis, é um dos grandes milagres da matemática, e representa um
ponto alto na história dos primos (SAUTOY, 2007 p. 60).
Mais tarde verificou-se que a curva desviava gradualmente do numero real de
primos à medida que
se tornava elevado. A figura abaixo mostra a comparação:
Figura 16: Gráfico de comparação da quantidade real de números primos e os de Gauss.
Fonte: Sautoy (2007, p. 63)
Por fim, encontramos “a formula que dá todos os números primos e somente
esses” (WATANABE, 1998, p. 19). A fórmula encontrada em Honsberger (1976), diz
o seguinte:
P á g i n a | 68
Sejam
e
números naturais com
;e
. Então
é primo.
Agora atribuiremos valores para
e
, então
Se
e
então
Se
e
então
Se
e
então
e
e
para verificarmos os resultados. Com
P á g i n a | 69
Como vimos a escolha dos valores para
e
não é tão simples, pois não
basta apenas atribuir valores ao par ordenado para obtermos como resultado
números primos. Mas com a escolha de pares ordenados adequados ela nos
fornece todos os números primos, por exemplo:
Para acharmos os pares acima, devemos partir dos primos, por exemplo, para
encontramos o par ordenado que tem como resultado o número primo 13, devemos
aplicar na seguinte fórmula:
e
Assim para
temos
Como podemos observar, a formula não apresenta grande praticidade e,
embora possamos encontrar todos os primos a partir de determinados pares
ordenados, para determinar esse pares, precisamos partir do primo associado a
eles.
P á g i n a | 70
3.3. ALGORITMO RSA
Para tentar expor a segurança do sistema RSA, que é chamado de sistema
de chave pública, dividimos o processo de criptografar uma mensagem pelo método
RSA nas seguintes etapas:
ETAPA 1: Escolher dois números primos grandes ( e ). Segundo Fincatti
(2010, p. 49), para aumentar a segurança da chave, basta escolher números primos
tão grandes como
ETAPA 2: Calcular o valor de
ETAPA 3: Encontrar o valor de
que seja primo relativo com
, ou seja,
ETAPA 4: Separar a chave que criptografa a mensagem
.
ETAPA 5: Realizar a pré-criptografia do texto e depois separar a sequência
de números em blocos.
ETAPA 6: Criptografar os blocos separadamente pela função
O primeiro passo para usar a criptografia RSA é converter a mensagem em
uma sequência de números. Para tornar mais simples, usaremos um exemplo que
não contenha números, mas somente as letras que formarão as palavras e pelos
espaços entre as palavras. Chamaremos isso de 1ª fase da codificação, pois ainda
não será o método de codificação propriamente dito.
Para substituir as letras e espaços por números, faremos correspondências
desses com números de dois algarismos. É importante que a correspondência seja
feita com números de dois algarismos para evitar ambigüidades como, por exemplo,
se fizermos correspondência da letra A com o número 1, da letra B com o número 2
e assim sucessivamente, o número 21 poderia ser tanto BA como a letra U.
P á g i n a | 71
A
B
C
D
E
F
G
H
I
J
K
L
M
10 11 12 13 14 15 16 17 18 19 20 21 22
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
23 24 25 26 27 28 29 30 31 32 33 34 35
Tabela 06 – Atribuição de números para as letras do alfabeto.
Substituiremos o espaço entre as palavras por 99, dessa forma, a frase
“Belém do Pará” será convertida para o número
Agora usaremos como parâmetros dos primos distintos
e
tal que
,e
por fim, quebramos este longo número em blocos com números menores que
evitando os blocos que comecem em zero. Por exemplo, se
e
,
então
e, neste caso, a conversão acima ficaria dividida da seguinte maneira
Note que os blocos não correspondem a nenhuma unidade linguística, isto
torna muito difícil a decodificação por análise de frequência. Encerramos assim a
nossa 1ª fase e passamos pra fase de codificação propriamente dita.
Para codificar a mensagem precisamos de
e de um inteiro positivo
tal que
.
O par
é chamado de chave de decodificação, ou chave pública, do
sistema RSA que estamos usando. Vejamos como ficaria a codificação se
, logo
, nesse caso, o menor valor de
e
nas condições
dadas é 7, o menor primo que não divide 120.
Agora codificaremos cada bloco separadamente e a mensagem passará a ser
a sequência dos blocos codificados. É importante que os blocos codificados não
sejam novamente reunidos de modo a formar um longo número, caso contrário será
impossível decodificar a mensagem.
P á g i n a | 72
Para decodificar um bloco b precisaremos da chave de codificação
.
Lembre-se que b é um inteiro positivo menor que .
Denotaremos o bloco codificado por
, a codificação será dada pela
fórmula:
Pela aritmética modular, obviamente que usaremos
na forma reduzida.
Assim, o bloco 111 da mensagem anterior é codificado como o resto da divisão de
por
. Fazendo as contas:
Como e
Para os outros valores, temos:
temos que
P á g i n a | 73
Codificando toda a mensagem, obtemos a seguinte sequência de blocos:
Chamaremos cada um desses novos blocos da mensagem codificada de
Vejamos agora como decodificar esses blocos. Para tal, precisaremos de
inverso de
no módulo de
, que chamaremos de
é a chave de decodificação. Seja
denotaremos por
e o
. Logo o par
um bloco da mensagem codificada, então
o resultado da decodificação, que será a seguinte fórmula.
Note que é fácil decodificar a cifra desde que
conhecidos, porém a chave pública é
necessário fatorar
.
onde
e
sejam
. Logo, para obtê-los é
para decodificar a mensagem. Mas isto não é estritamente
verdadeiro, pois além do próprio , só precisamos conhecer o inverso
de
módulo
.
Em nosso exemplo estamos usando a chave de codificação. Temos que
e
encontraremos
. Para calcular
basta aplicar o algoritmo euclidiano estendido que
. Assim, para decodificar o primeiro bloco da mensagem,
calculamos a forma reduzida de
módulo 143.
P á g i n a | 74
O método RSA consiste em duas chaves, uma de codificação (pública) e
outra de decodificação (privada), então ele só será útil se, decodificando um bloco
codificado
, obtemos de volta o bloco correspondente a mensagem original .
Basta observar que em um sistema RSA de parâmetros
com a chave de codificação igual à
precisamos verificar que seja
e , e a de decodificação serão
um inteiro tal que
Ou provar apenas que
e . Apenas
então
.
, pois isto é suficiente porque tanto
quanto b estão no intervalo que vai de
modulo
e , com
a
, logo só podem ser congruentes
se são iguais. É por isso que precisamos escolher
menor que
, e é,
também, por isso que temos que manter os blocos separados, mesmo depois da
codificação (COUTINHO, 2000, p. 184).
De acordo de como definimos
Porém
é inverso de
e ,
módulo
, logo
; para algum .
Disto resulta
Agora vamos a decodificação das mensagens cifradas:
P á g i n a | 75
Que nos dá de volta a mensagem original, e basta juntar e consultar a tabelas
para encontrar a mensagem.
3.4. SEGURANÇA
Como o RSA é um método de chave pública, a chave de codificação
é
acessível a qualquer pessoa, logo, a segurança do RSA depende da dificuldade de
calcular o valor de
quando
e
conhecendo
são conhecidos. Na prática, só podemos calcular
, e a única forma de encontrar os valores
e
é,
segundo Coutinho (2000, p. 186), fatorando .
No caso de
ser um número muito grande, o problema da fatoração se torna
muito complexo. Mostraremos um dos métodos para fatorar um número muito
grande.
3.4.1. Algoritmo de fatoração de Richard Schroeppel
O método permite fatorar
em aproximadamente:
P á g i n a | 76
Silva (2006) nos dá a seguinte tabela que mostra o número de operações
necessárias para fatorar
e o tempo requerido em cada operação supondo que se
leva um microsegundo para cada dígito decimal do numero .
Dígitos
Número de Operações
Tempo
50
horas
70
horas
100
anos
200
anos
300
anos
500
anos
Tabela 07 – Tempo de operação de operações necessárias para fatorar .
3.4.2. Assinatura Digital
O método RSA também é comumente usado para verificar a originalidade de
uma mensagem, ou seja, para saber se a mensagem é realmente de uma pessoa
que conheça a chave privada.
Para usar o sistema de assinaturas digitais com RSA, o usuário que possui
uma chave privada d, poderá assinar uma mensagem dada, cifrada em blocos,
,
através da seguinte expressão:
De fato, é difícil descobrir s sem o conhecimento de d. Portanto, uma
assinatura digital descrita acima é dificilmente forjada. O receptor recupera a
mensagem utilizando a chave pública e do emissor e, dessa forma:
Assim, o receptor poderá validar a assinatura do emissor calculando
(SILVA, 2006, p. 25).
Com isso é possível identificar a assinatura como sendo única.
P á g i n a | 77
3.5. CONSEQUÊNCIAS DA CIFRA RSA
3.5.1. Liberdade total ou controlada?
Um debate sobre o uso maciço da criptografia vem tomando grande destaque
nas últimas duas décadas. Um dos fatores que contribuíram para isso foi quando o
norte-americano Phil Zimmermann, um cientista da computação engajado
politicamente, resolveu criar o Prety Good Privacy (PGP; “Uma Ótima Privacidade”,
em português), na década de 90.
Zimmermam percebeu que, apesar de todo o sucesso da cifra RSA e demais
algoritmos modernos, como o DES, por exemplo, apenas uma parcela muito
pequena da sociedade desfrutava dessa segurança, por ser preciso o uso de
computadores rápidos e a dificuldade de utilização das cifras. Os usuários comuns
cifravam suas mensagens de modo bem menos seguro, isso quando ainda usavam
algum tipo de cifragem. Portanto, o principal objetivo da criação do PGP foi oferecer
a qualidade de segurança proposta pela cifra RSA e o IDEA (uma cifra de bloco
criada no início da década de 90), de forma que usuários comuns pudessem usufruílos (SINGH, 2001).
Phil resolveu o problema usando o algoritmo RSA para cifrar uma chave do
algoritmo IDEA, que precisava de muito menos recursos tecnológicos para ser
rodado com eficiência. Ele tinha resolvido assim o problema da velocidade. Em seu
programa, ainda, o usuário não precisaria se preocupar com nada em termos de
matemática: tudo era feito automaticamente ao simples clique e movimento do
mouse.
Dessa forma, em 1991, o cientista disponibilizou o programa na internet.
Inicialmente, nada revolucionário. No entanto, aos poucos várias pessoas e
entidades passaram a copiá-lo. Mais adiante, artigos em revistas de grande
circulação passaram estampar artigos sobre o PGP em suas páginas. O programa
virara um fenômeno. No entanto, para a infelicidade de Phil, dois grandes problemas
começaram a assolar sua vida. O primeiro se tratava de a RSA Security, a empresa
que gerenciava a cifra, não autorizou que o cientista usasse seu algoritmo em um
programa, mesmo ele não ter tido qualquer tipo de retorno financeiro, classificando
assim o PGP como um programa pirata. Segundo que, em 1993, o governo norteamericano o acusou de contrabando de armas, já que programas de cifragem estão
P á g i n a | 78
inclusos na categoria de munições, e o mesmo deveria ter pedido uma autorização
para que o programa fosse exportado (SINGH, 2001).
A partir dá originou-se uma série de debates que tinham como tema central a
privacidade na troca de informações pela internet. De um lado, defensores da
liberdade de cifragem argumentavam que o governo não poderia limitar o uso da
criptografia para os cidadãos comuns. Do outro, agentes federais preocupados com
a utilização cada vez maior da criptografia por parte de criminosos, como terroristas,
contrabandistas, pedófilos e traficantes. A grande questão é que o PGP tinha
oferecido uma segurança muito grande para uma quantidade imensa de pessoas,
fazendo com que a NSA não pudesse ser capaz de investigar suas vidas através da
internet, caso fosse necessário. Por outro lado, grupos de defesa da liberdade de
privacidade e as grandes empresas de segurança na internet argumentavam que o
governo já havia cometido muitos abusos através escutas de telefone ilegais, por
exemplo. Antigos presidentes dos EUA haviam coletado ilegalmente informações de
seus adversários políticos para desacreditá-los ou ganhar vantagem na votação e
aprovação de alguma lei (SINGH, 2001).
Entre as propostas feitas pelo governo, está a criação da chamada chave de
depósito, que consiste em o governo permitir o uso indiscriminado da criptografia,
desde que ele tenha acesso às chaves das pessoas. Teoricamente, as pessoas
comuns teriam suas trocas de mensagem protegidas de pessoas de má-índole, mas
caso fosse necessário, o governo teria como investigar possíveis criminosos. A
utilização de uma chave não depositada que fosse usada para o estabelecimento de
comunicação seria considerada ilegal.
Obviamente a ideia não foi bem aceita pelos defensores da liberdade de
privacidade. Eles argumentam considerando como poderia ser trágico se o governo
possuísse as chaves de nossas casas. Assim, o debate continua até os dias de hoje,
não tendo por enquanto previsão de término.
Zimmermann teve seu caso arquivado, já que o caso ganhara grande
repercussão e estimulara ainda mais o download do software. Como o dano era
irreversível e possivelmente o cientista seria absolvido, o polícia americana resolveu
devolver a sua liberdade. A RSA security também entrou em acordo e cedeu
autorização para que o PGP fosse veiculado livremente, permitindo que Phil
vendesse o programa para uma empresa chamada Network Associates, tornando-se
um dos sócios majoritários.
P á g i n a | 79
Singh (2001, p. 340) termina dizendo que a decisão sobre essa questão não
precisa ser definitiva. A opinião das pessoas vai variar da situação em que se
encontram os seus países: caso a liberdade do uso da criptografia vença, e por um
acaso uma série de atrocidades venham a acontecer, rapidamente o governo terá a
oportunidade de restrição de mensagens criptografadas; depois disso, após alguns
anos de um suposto abuso do governo a partir do uso ilegal de suas escutas,
rapidamente o processo dará nova reviravolta. Ainda segundo o autor “o fator
decisivo vai ser de quem o público tem mais medo – dos criminosos ou do governo”
(SINGH, 2001, p. 340).
3.5.2. Física Quântica e a Criptologia
Como vimos, a criptografia RSA fornece atualmente uma segurança
considerada muito alta. Porém, tudo isso se baseia no atual estágio dos nossos
computadores, que levariam, literalmente, milênios para conseguir quebrara cifra.
Tudo depende da improvável descoberta de algum meio prático de fatorar números
gigantescos, ou o advento de uma nova tecnologia. É com essa segunda opção que
os atuais criptoanalistas estão trabalhando: a criação do computador quântico
(RIBEIRO, 2010).
Essa fascinante criação consiste em tudo o que há de mais moderno na
física. Não nos deteremos nos detalhes técnicos, porém para entendermos a grande
revolução que seria esse invento, vamos imaginar um computador moderno que
tenha como tarefa a realização de 64 processamentos. Nessa situação, caso o
computador precisasse de um segundo para realizar cada processo, levaria 64
segundos no total, isso porque ele processa um de cada vez. No computador
quântico, a pretensão é que ele possa fazer todos esses processamentos de uma só
vez, acabando a tarefa em apenas um segundo.
Couto (2008, p. 312) escreve:
Esse fenômeno significa em termos práticos que os computadores
quânticos teriam um poder inimaginável de processamento num dispositivo
‘do tamanho de uma xícara de chá’, para usar palavras dos pesquisadores.
Isso porque, enquanto os computadores normais trabalham com unidades
básicas de informação (os conhecidos bits) em formas de 1 ou 0, no
minúsculo universo quântico há os chamados bits quânticos ou quantum
bits (do qual usa-se a sigla qubit) que podem ser tanto 0 quanto 1 ao
mesmo tempo.
(COUTO, 2008, p. 312)
P á g i n a | 80
A vantagem criptoanalítica é que a cifra RSA ficaria completamente
comprometida, caso um computador tão rápido assim existisse. Porém, para a
infelicidade dos criptoanalistas, os criptógrafos estão utilizando a mesma física
quântica para a produção de um protocolo inviolável, chamado BB84.
Nele, a polarização de fótons pode ser usada como qubits. Ribeiro (2010, p.
30) especifica:
(...) o fóton é a menor quantidade de energia que se consegue extrair da
luz. A polarização é a direção em que o fóton – mais especificamente o
campo elétrico que o compõe – oscila à medida que ele se desloca. Essa
direção pode ser, por exemplo, vertical ou horizontal. (...) Com isso, a
informação pode ser codificada atribuindo o bit 1 à polarização vertical e o
bit 0 à polarização horizontal, por exemplo.
(RIBEIRO, 2010, p. 30)
A grande vantagem desse sistema é que a física prova, por meio de um
teorema, que é impossível interceptar os fótons sem causar erros na comunicação.
Portanto, antes da mensagem principal ser enviada, uma mensagem-teste seria
transmitida a fim de avaliar se ela fora comprometida no caminho. Se a taxa de erros
estiver dentro do padrão, avalia-se que é seguro a troca de informações. Caso não
seja, o envio é cancelado e a mensagem não poderá ser interceptada. Dessa forma,
o protocolo BB84 é considerado inviolável.
Poderemos, num futuro próximo, acabar com qualquer chance de privacidade
na internet, assim como garantir privacidade absoluta. A grande dificuldade ainda
reside em aprimorar ainda mais os conhecimentos nessa área, como aumentar a
capacidade dessa tecnologia a funcionar com eficiência há grandes distâncias, entre
outros. Há muito a ser feito, mas o que já foi feito revela um futuro promissor. Singh
(2001, p. 378) diz que “a criptografia quântica marcaria o fim da batalha entre
criadores de códigos e os quebradores, com os criadores de códigos saindo
vitoriosos”. Essa afirmação pode ser um tanto exagerada, visto que antigos
criadores também achavam o mesmo de suas cifras. Porém, o autor se baseia nas
propriedade da física quântica que “proíbem” a interceptação de mensagens sem
que Alice e Bob saibam que estão sendo vigiados.
P á g i n a | 81
Segurança absoluta remonta ao direito de privacidade dos cidadãos a à
possível proteção de criminosos. Não é só de segurança e tecnologia que vive a
criptografia, mas, sobretudo, de ética também.
P á g i n a | 82
4. CONSIDERAÇÕES FINAIS
Ao término do trabalho, é possível perceber que alcançamos os seus
objetivos iniciais, sendo eles: apresentar os principais acontecimentos históricos
ligados à criptologia; explicar como o ocorreu o desenvolvimento desta ciência,
desde o surgimento até a metade do século XX; fazer entender a entrada da
matemática na criptografia e criptoanálise; e explicitar matematicamente a
importância do surgimento cifra RSA para as telecomunicações em termos de
praticidade e segurança.
Ao longo do trabalho podemos ver que a necessidade de esconder
informações faz parte do cotidiano do ser humano há milênios. Com o passar do
tempo, as motivações mudaram, mas o desejo de ocultar saberes e obter privilégios
por causa deles, só fez crescer. Porém, como resposta natural a esse ato, sempre
existiram aqueles que tentavam desfrutar das oportunidades que surgiriam, caso
descobrissem o que tanto as outras pessoas tentavam esconder.
A informação é peça fundamental da estratégia. Com ela, os Aliados
reverteram a situação na Segunda Guerra Mundial; Elizabeth I pôde manter seu
reinado na Inglaterra, com a decapitação da sua prima, a rainha Maria Stuart da
Escócia; a NSA evita inúmeros atentados terroristas nos Estados Unidos, todos os
anos; a Polônia pôde descobrir que a Enigma tinha falhas e assim ler as mensagens
alemãs; os árabes presumiram que era possível quebrar a cifra de César. Enfim,
através dos tempos a posse ou não de determinados fragmentos de informação, por
parte de algumas pessoas ou organizações, ajudou a fazer o mundo do jeito que
conhecemos hoje.
Através do trabalho pudemos verificar também que, em aspectos históricos, a
Criptologia é muito importante para entendermos vários acontecimentos. Ela nos
traz uma abordagem contextual, em que talentos individuais e capacidade
tecnológica sempre estão envolvidos, tanto na criação quanto na quebra de códigos
e cifras. Através dela compreendemos o porquê do surgimento de algumas
tecnologias, como o Colossus, por exemplo, além de algumas cifras como a de
Vigenère, o DES e a RSA.
É notável também que o desenvolvimento da criptografia e da criptoanálise,
bem como das tecnologias em geral, aconteceu principalmente em épocas de
grandes guerras e conflitos, onde as instituições precisavam a todo custo
P á g i n a | 83
estabelecer comunicação de forma segura e ao mesmo tempo descobrir as
estratégias inimigas. Nesse ponto, grandes mentes brilhantes ajudaram a promover
esses avanços, seja trabalhando por suas nações, ou mesmo fazendo por puro
passatempo.
A partir do século XX é possível notar que os matemáticos passaram a se
tornar os maiores responsáveis pela criação de novidades, tanto na área da
criptografia quanto da criptoanálise. A contribuição deles para a criação de máquinas
que tinham a capacidade se serem programáveis mudou a concepção de criação e
quebra de novas cifras.
Por fim, a segunda metade do século XX e o início do XXI, com a
consolidação da Globalização, comprovaram ainda mais que a informação detém
valor inestimável, muitas vezes mais que armas ou recursos financeiros. Estamos na
era da informação, onde a internet tem se mostrado muito eficaz na transmissão de
dados. Internet, a nova fronteira entre a ética, a segurança e a criptografia. Melhor
os físicos se prepararem, logo mais eles precisarão, em massa, se juntar aos
matemáticos, para assim ajudarem a escrever os próximos capítulos dessa
fascinante história.
P á g i n a | 84
REFERÊNCIAS BIBLIOGRÁFICAS
ARAUJO, Diego da Costa; SOUZA, Thiago Gomes. Criptografia: conceitos, origens,
cifras e códigos. 2010. 50 f. Trabalho de Conclusão de Curso (Graduação em
Licenciatura em Matemática) – Universidade do Estado do Pará. Belém, 2010.
CHIRIGATI, Fernando Seabra; KIKUCHI, Rafael Shinji Aoki; GOMES, Talita Lopes.
Esteganografia. Universidade Federal do Rio de Janeiro, 2006.
COUTINHO, Severino Collier. Primalidade em tempo polinomial: uma introdução
ao algoritmo AKS. 1. ed. Rio de Janeiro: Sociedade Brasileira de Matemática, 2004.
v. 01. 105 p.
COUTINHO, Severino Collier. Números inteiros e Criptografia RSA. Rio de Janeiro (RJ):
Instituto Nacional de Matemática Pura e Aplicada, 2000. (Série de Computação e
Matemática)
COUTO, Sérgio Pereira. Decifrando a Fortaleza Digital. São Paulo (SP): Universo
dos Livros, 2005.
COUTO, Sérgio Pereira. Códigos & Cifras: da antiguidade à era moderna. Rio de
Janeiro (RJ): Novaterra, 2008.
DIAS, Ricardo Alexandre da Rocha. Algumas evidências computacionais da
infinitude dos números primos de Fibonacci e generalizações destes. 2008. 157
f. Monografia (Ciências da Computação) – Universidade Federal do Rio Grande do
Norte. Natal, 2008.
GIL, Fernando de O.; MALANDRIN, Leandro José A. A.; MORIGAKI, Roberto H.;
BARRETO, Paulo S. L. M. SEA - Sistema Esteganográfico de Arquivos. Anais do
VIII
Simpósio
Brasileiro
em
Segurança
da
Computacionais, Gramado, p. 401-410, set. 2008.
Informação
e
de
Sistemas
P á g i n a | 85
HONSBERGER, Ross. Mathematical Gems II. The Mathematical Association of
America, 1976.
KAHN, David. The Codebreakers: The Story of Secret Writing. New York:
The Macmillan Company, 1967.
KAHN, David. The Codebreakers: The Comprehensive History of Secret
Communication from Ancient Times to the Internet. New York: Scribner, 1996.
FINCATTI, Camila Ávila. Criptografia como agente motivador na aprendizagem
da matemática em sala de aula. 2010. 82 f. Trabalho de Conclusão de Curso
(Graduação em Licenciatura em Matemática) – Universidade Presbiteriana
Mackenzie, 2010.
MRAYATI, Mohamad; ALAM, Yahya Meer; TAYYAN, Muhammad Hassan at. Ibn
‘Adlan’s Treatise. Arábia Saudita: KFCRIS & KACST, 2003a. (Arabic Origins of
Criptology, v. 2)
MRAYATI, Mohamad; ALAM, Yahya Meer; TAYYAN, Muhammad Hassan at. Ibn
Ad-Durayhim’s Treatise. Arábia Saudita: KFCRIS & KACST, 2003b. (Arabic Origins
of Criptology, v. 3)
POMMERENING, Klaus. Affinity Chromatography. [S.I.] Marcel Dekker, 1985.
RIBEIRO, Paulo Henrique Souto. Criptografia Quântica: os desafios de gerar
códigos invioláveis. Ciência Hoje, São Paulo, v.47, n.277, p.26-31, dez. 2010.
SAUTOY, Marcus Du. A música dos números primos: a história de um problema
não resolvido na matemática. Rio de Janeiro (RJ): Jorge Zahar Editora, 2007.
SILVA, Elen Viviane Pereira da. Introdução à Criptografia RSA. 2006. 32 f.
Apresentação de Trabalho/Simpósio. 3º Simpósio Nacional/Jornada de Iniciação
Científica; Inst. promotora/financiadora: Instituto Nacional de Matemática Pura e
Aplicada-IMPA. Rio de Janeiro (RJ): 2006.
P á g i n a | 86
SINGH, Simon. O Livro dos Códigos: A ciência do sigilo – do antigo Egito à
criptografia quântica. Record, 2001.
TKOTZ, Viktoria. (2005a) Classificação das cifras. Disponível em: <
http://www.numaboa.com.br/criptografia/gerais/314-classificacao>. Acesso em: 28
dez. 2011.
TKOTZ, Viktoria. (2005b) A Linha do Tempo da Criptografia na Antiguidade.
Disponível em: <http://www.numaboa.com.br/criptografia/historia/157-antiguidade>.
Acesso em: 28 dez. 2011.
TKOTZ, Viktoria. (2005c) al-Kindi. Disponível em: <
http://www.numaboa.com.br/criptografia/historia/159-alkindi>. Acesso em: 28 dez.
2011.
TKOTZ, Viktoria. (2005d) A Cifra dos Templários. Disponível em: <
http://www.numaboa.com.br/criptografia/substituicoes/monoalfabeticas/simples/327templarios>. Acesso em: 28 dez. 2011.
TKOTZ, Viktoria. (2005e) A Linha do Tempo da Criptografia Medieval. Disponível
em:
<http://www.numaboa.com.br/criptografia/historia/316-medieval?start=1>.
Acesso em: 28 dez. 2011.
TKOTZ, Viktoria. (2005f) Leon Battista Alberti. Disponível em: <
http://www.numaboa.com.br/index.php?option=com_content&view=article&id=158&It
emid=100>. Acesso em: 28 dez. 2011.
TKOTZ, Viktoria. (2005g) Girolamo Cardano. Disponível em: <
http://www.numaboa.com.br/criptografia/historia/162-cardano>. Acesso em: 28 dez.
2011.
P á g i n a | 87
TKOTZ, Viktoria. (2005h) A máquina das Diferenças de Babbage. Disponível em:
<http://www.numaboa.com.br/informatica/museu/414-babbage>. Acesso em: 02 jan.
2012.
TKOTZ, Viktoria. (2005i) Algoritmo RSA. Disponível em: <
http://www.numaboa.com.br/criptografia/chaves/350-rsa>. Acesso em: 02 jan. 2012.
TKOTZ, Viktoria. (2007a) Comunicação usando chave pública. Disponível em:
<http://www.numaboa.com.br/criptografia/chaves/835-chave-publica>. Acesso em:
28 dez. 2011.
TKOTZ,
Viktoria.
(2007b)
Ave
Maria
de
Trithemius.
Disponível
em:
<
http://www.numaboa.com.br/index.php?option=com_content&view=article&id=613&It
emid=57>. Acesso em: 28 dez. 2011.
VALDEVINO, André. Criptografia Caótica. Artigo do Trabalho de Conclusão de
Curso.
Universidade
Católica
de
Brasília,
2006.
Disponível
em
<http://webcache.googleusercontent.com/search?q=cache:LR75LYXj0REJ:www.ucb.
br/sites/100/103/TCC/22006/AndreValdevino.pdf+Ibn+DUNAINIR&hl=pt-BR&gl=br>.
Acesso em: 28 dez. 2011.
VISSIÈRE, Laurent. Altamente Confidencial. In Revista História Viva, Ed. Duetto,
nº 70, 2009.
WATANABE, Renate G.. Uma formula para os números primos. Revista do
Professor de Matemática. n. 37. p. 19-21, 1998.
P á g i n a | 88
APÊNDICE A
Iremos abordar nesta seção as operações matemáticas envolvidas no
processo de cifragem de uma mensagem em alguns dos diferentes métodos de
criptografia, neles encontramos o uso de matrizes e funções modulares, entre
outros.
1. CIFRA DE CÉSAR
A cifra de César faz uma correspondência biunívoca entre as letras da
mensagem e sua imagem, ou seja, a mensagem é cifrada através de uma função
bijetora.
A função citada é a
codificação, e
assumir
onde
é a chave de
é valor ao qual cada letra corresponde na tabela abaixo, podendo
valores
A
B
C
D
E
F
G
H
I
J
K
L
M
0
1
2
3
4
5
6
7
8
9
10
11
12
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
13
14
15
16
17
18
19
20
21
22
23
24
25
Tabela 08 – Letras e números correspondentes
Usaremos esta tabela de correspondência para todas as próximas
criptografias que precisarmos daqui em diante.
Dessa forma, para criptografar a palavra “CRIPTOGRAFIA” usando a chave
, usaríamos a seguinte função
Criptografando a palavra acima teremos:
P á g i n a | 89
A palavra “CRIPTOGRAFIA” se transforma na palavra “NDTBFARDLQTL”.
Para decodificar, basta usar o inverso aditivo da chave utilizada para a
codificação, no caso, o inverso aditivo de
é
.
P á g i n a | 90
E obtemos a palavra inicial.
A desvantagem das cifras de substituição como a de César, é que elas
preservam a frequência das letras em cada língua, o que as torna relativamente fácil
de quebrar. Uma solução é criptografar o texto em grupos em vez de uma letra de
cada vez (ANTON, 2001).
2. CIFRA DE VIGENÈRE
Na cifra de Vigenère, fazemos a codificação de palavras através da
interseção das letras desta palavra com as letras da palavra que é a chave de
codificação, como vimos anteriormente. Para mostrar como esta codificação pode
ser feita algebricamente, temos que primeiramente fazer a correspondência destas
letras com os valores de acordo com a figura 07, de forma que a palavra
“CRIPTOGRAFIA” se transforme na sequência de números “2 – 17 – 8 – 15 – 19 –
14 – 6 – 17 – 0 – 5 – 8 – 0” e a chave que “BELEM” na sequência “1 – 4 – 11 – 4 12”.
P á g i n a | 91
A codificação vista algebricamente é feita ultilizando-se
onde
é o valor da letra a ser cifrada e
,
o valor da letra da chave e
o número de
caracteres, assim, a decodificação ficaria:
C
R
I
P
T
O
G
R
A
F
I
A
B
E
L
E
M
B
E
L
E
M
B
E
Tabela 09 – Usando uma chave com a Cifra de Vigenère
E assim obtemos a mensagem codificada “DVTTGPKDERJE”
P á g i n a | 92
Para decodificar, basta fazer o processo inverso utilizando
onde
é a letra da mensagem cifrada.
3. Cifra de Hill
Na Cifra de Hill separamos a mensagem que queremos criptografar em
blocos de duas letras e através de uma multiplicação de matrizs criptografamos a
mensagem. Faremos por etapas.
P á g i n a | 93
1ª etapa: escolhemos a matriz
2ª etapa: agrupamos as letras sucessivas do texto que queremos cifrar,
adicionando uam letra fictícia no ultimo par se o texto tiver um número impar de
letras, e substituímos cada letra pelos números correspondentes na tabela que
usamos na primeira cifra.
Decodificaremos as palavra “MATEMÁTICA”, para isso iremos dividi-la
MA – TE – MA – TI – CA
Fazendo a correspondência de acordo com a tabela:
12, 0 – 19, 3 – 12, 0 – 19, 8 – 2, 0
3ª etapa: convertemos cada par em um vetor coluna, multiplicamos pela
matriz dada na 1ª etapa e os resultados devem ser dados em
mensagem.
Codificação:
. Codificando a
P á g i n a | 94
A palavra codificada é transformada na seguinte:
Para decodificar a mensagem precisamos apenas fazer o mesmo processo
com a mensagem codificada usando a matriz inversa da usada para decodificar, a
idéia é muito simples, para codificar, multiplicamos uma matriz (dos números que
correspondem aos blocos da mensagem) pela matriz codificadora
para decodificarmos, basta multiplicarmos pela matriz inversa
facilitar os cálculos, uma vez que os resultados terão que pertencer à
a matriz inversa em
.
Calculando a inversa da matriz que usamos teríamos
, logo,
, e para
, usaremos
Universidade do Estado do Pará
Centro de Ciências Sociais e Educação
Travessa Djalma Dutra, s/n – Telégrafo
66113-200 Belém-PA
www.uepa.br