UNIVERSIDADE FEDERAL DE SAO CARLOS
CENTRO DE CIENCIAS EXATAS E DE TECNOLOGIA
LICENCIATURA EM MATEMATICA
Criptologia: uma abordagem historica e matematica
Diego Felipe Silveira Seabra
Sao Carlos – SP
Perıodo: marco a novembro de 2010
UNIVERSIDADE FEDERAL DE SAO CARLOS
CENTRO DE CIENCIAS EXATAS E DE TECNOLOGIA
LICENCIATURA EM MATEMATICA
Trabalho de Conclusao de Curso A
e Trabalho de Conclusao de Curso B
Criptologia: uma abordagem historica e matematica
Diego Felipe Silveira Seabra, R.A. 282421
Dissertacao apresentada ao
Departamento de Matematica
da UFSCar como parte dos
requisitos para a obtencao
do tıtulo de Licenciado em
Matematica.
Orientador: Prof. Dr. Joao Carlos Vieira Sampaio
Sao Carlos – SP
marco a novembro de 2010
A minha famılia e ao meu padrinho
Jose Maria.
Resumo
A historia dos codigos e seus decifradores em suas eternas batalhas acompanha a
propria historia humana. Ao longo do tempo, codigos, cifras e mensagens secretas
estiveram presentes nas mais diversas situacoes onde desempenharam papel essencial
decidindo resultados de guerras e o destino de pessoas e civilizacoes inteiras.
Nos mais diversos setores sociais e tipos de atividades humanas, a crip-
tografia interferiu diretamente. Em assuntos polıticos e diplomaticos, atividades
civis ou militares, onde se fez necessaria a transmissao de informacoes de maneira
segura e secreta ela esteve presente e a consciencia das consequencias de uma men-
sagem interceptada por maos erradas fez com que as nacoes criassem departamentos
especıficos para a criacao e implementacao de codigos cada vez mais seguros.
Nesse contexto a ciencia da Criptologia foi colocada num patamar de grande
importancia e muita atencao lhe foi dispensada no sentido em que fosse cada vez
mais desenvolvida e implementada.
Se de um lado temos os criadores de codigos, do outro estao os decifradores
em suas arduas e incessantes batalhas por organizar o aparente caos e encontrar o
verdadeiro significado por tras de sequencias misteriosas de letras e sımbolos. E uma
batalha intelectual constante e contınua cujos resultados interferem diretamente no
dia-a-dia das pessoas e em todo o contexto social.
Conforme o tıtulo deste trabalho, atraves de uma abordagem historica e
matematica da Criptologia farei uma viagem pela historia dos codigos e sua in-
fluencia na sociedade humana bem como um estudo mais detalhado da matematica
4
5
envolvida na criacao e quebra de codigos e cifras. Serao utilizados resultados da
Teoria dos Numeros e outros que eventualmente sejam necessarios.
Neste trabalho, a enfase e dada a parte historica e ao conteudo matematico
que sera necessario ao estudo mais detalhado de topicos da Criptologia, particular-
mente o sistema RSA, foco do trabalho de graduacao B.
Palavras-chave: criptologia, criptografia, aritmetica modulo m, funcao ϕ
de Euler.
Sumario
I Trabalho de Conclusao de Curso A 10
1 Um pouco de historia 13
1.1 A evolucao da escrita secreta . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Ramos da criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 Transposicao . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.2 Substituicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.3 Cifras de substituicao atraves de aritmetica modular . . . . . 19
1.3 Os criptoanalistas arabes . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 Criptoanalise de um texto cifrado . . . . . . . . . . . . . . . . . . . . 27
2 Elementos da teoria dos numeros 34
2.1 Inteiros modulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Inteiros modulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 A funcao ϕ de Euler 44
II Trabalho de Conclusao de Curso B 51
4 A criptografia de chave publica 54
6
7
4.1 O nascimento da criptografia de chave publica . . . . . . . . . . . . . 56
5 Teoria dos numeros para RSA 58
5.0.1 Algoritmo Euclidiano para o calculo de mdc . . . . . . . . . . 60
5.0.2 Calculando inteiros r e s tais que mdc(a, b) = ra+ sb . . . . . 61
5.1 Uma aplicacao interessante . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Implementacao de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.3 Exemplo numerico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6 Metodos de fatoracao 70
6.1 Teste de fatoracao de Fermat . . . . . . . . . . . . . . . . . . . . . . 71
6.2 Metodo Pollard p− 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Lista de Figuras
1.1 Primeiro aparelho criptografico militar, o citale espartano. . . . . . . 17
1.2 O relacionamento entre algoritmo e chave. . . . . . . . . . . . . . . . 18
1.3 Tabela de frequencias baseada em passagens extraıdas de jornais e ro-
mances cuja amostragem consistia em 100.362 caracteres do alfabeto.
Tabela compilada por H. Beker e F. Piper. . . . . . . . . . . . . . . . 26
1.4 Analise de frequencia da mensagem cifrada. . . . . . . . . . . . . . . 28
1.5 Dados referentes ao comportamento das letras em estudo. . . . . . . . 29
1.6 Dados referentes a letra O. . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7 Nosso alfabeto cifrado parcial. . . . . . . . . . . . . . . . . . . . . . . 32
1.8 Alfabeto cifrado completo. . . . . . . . . . . . . . . . . . . . . . . . . 33
8
Lista de Tabelas
1.1 Alfabeto cifrado deslocado um determinado numero de casas (neste
caso, tres) em relacao ao alfabeto original. . . . . . . . . . . . . . . . 19
1.2 A cifra de Cesar aplicada a uma mensagem curta. . . . . . . . . . . . 19
1.3 Os numerais equivalentes para as letras. . . . . . . . . . . . . . . . . 20
1.4 A correspondencia entre as letras para a Cifra de Cesar . . . . . . . . 20
1.5 A correspondencia entre as letras para cifra com C ≡ 7P +10 (mod 26). 23
5.1 Lista dos numeros 1 ≤ x ≤ 51 coprimos com 51. . . . . . . . . . . . . 63
5.2 Correspondencia alfa numerica . . . . . . . . . . . . . . . . . . . . . . 67
9
Parte I
Trabalho de Conclusao de Curso A
10
Introducao
A criptografia esta presente no cotidiano das pessoas mesmo que muitas vezes elas
nao tenham consciencia/conhecimento disso. Uma simples mensagem trocada via
e-mail, uma compra realizada atraves do cartao de credito ou mesmo o envio e rece-
bimento de mensagens de texto por celular, em todas essas situacoes esta presente a
criptografia. E se tudo isso hoje e possıvel e e feito com velocidade impressionante
e porque ao longo da historia houve quem se dedicasse a Criptologia e em meio as
batalhas entre criadores e decifradores de codigos tivessemos grandes avancos em
diversas areas e ciencias diretamente ligadas a tematica. Certamente devemos a
historia dos codigos por tamanho desenvolvimento cientıfico e tecnologico nos dias
atuais.
Varios assuntos entram em pauta quando o assunto e criptografia. Manu-
tencao da lei e seguranca nacional, direitos civis e privacidade individual, atividades
civis e militares. Em todo esse conjunto a criptografia exerce papel central e gera al-
gumas questoes que para serem respondidas exigem que sejam considerados diversos
aspectos. Vejamos. Ha tempos os servicos policiais fazem uso de escuta telefonica
para fins de investigacao e/ou coleta de informacoes que servirao como provas con-
tra criminosos e recentemente com o desenvolvimento de codigos ultra-resistentes o
grampo ve sua funcionalidade ameacada.
No tocante a privacidade individual ha uma corrente que defende o uso
generalizado da criptografia de tal forma que tenhamos esse direito assegurado e
mantido. Paralelamente temos aqueles que trabalham com negocios e necessitam da
criptografia e de codigos seguros para a manutencao de suas atividades comerciais.
11
12
Ao mesmo tempo encontramos as forcas da lei na defesa de um uso mais restrito da
criptografia.
Nesse contexto, onde interesses individuais e coletivos entram em choque
temos a criptografia sendo utilizada com as mais diversas finalidades, mas desem-
penhando sempre um papel importante e ocupando posicao central.
A historia da Criptologia e extremamente vasta e rica em episodios inter-
essantes e que por muitas vezes mudaram o rumo de acontecimentos importantes
da historia humana. Sao comuns as situacoes onde o destino de reis, rainhas, civi-
lizacoes e tramas de assassinato dependeram da manutencao ou quebra de mensagens
secretas. No entanto, algumas partes ficarao de fora deste trabalho em virtude da
necessidade de escolha daquilo que esteja mais fortemente ligado ao que estamos
estudando por conta de espaco e foco.
Capıtulo 1
Um pouco de historia
1.1 A evolucao da escrita secreta
Um dos primeiros relatos acerca de escrita secreta data de Herodoto, que escreveu
As historias e narrou os conflitos entre Grecia e Persia, ocorridos no seculo V a.C.
A escrita secreta desempenhou um papel essencial ao evitar que a Grecia
fosse conquistada por Xerxes, o despota lıder dos persas. Xerxes comecara a con-
struir a cidade de Persepolis que seria a nova capital de seu reino. Vindos de todas
as regioes do imperio e de estados vizinhos, tributos comecaram a chegar com a
excecao de Atenas e Esparta que nada enviaram.
Impulsionado por tal atitude, Xerxes resolve se vingar e comeca a montar
secretamente a maior forca de combate vista ate entao. Contando com o elemento
surpresa, em 480 a.C ele estava pronto para lancar seu ataque. O que o lıder Persa
desconhecia, no entanto, era que seus preparativos tinham sido testemunhados por
Demarato, um exilado grego que apesar de ter sido expulso de sua terra natal ainda
nutria algum sentimento de lealdade para com a Grecia.
Demarato entao decide enviar uma mensagem secreta de advertencia aos
espartanos sobre as intencoes de Xerxes. No entanto, havia um problema a ser
solucionado. Como enviar a tal mensagem aos gregos sem que fosse interceptada
13
CAPITULO 1. UM POUCO DE HISTORIA 14
pelos guardas?
Sobre tal episodio, escreveu Herodoto: O perigo de ser descoberto era
grande; havia apenas um modo pelo qual a mensagem poderia passar: isso foi feito
raspando a cera de um par de tabuletas de madeira, e escrevendo embaixo o que
Xerxes pretendia fazer, depois a mensagem foi coberta novamente com cera. Deste
modo, as tabuletas pareceriam estar em branco e nao causariam problemas com os
guardas ao longo da estrada. Quando a mensagem chegou ao seu destino, ninguem
foi capaz de perceber o segredo, ate que, pelo que entendi, a filha de Cleomenes,
Gorgo, que era casada com Leonidas, adivinhou e contou as outros que se eles ras-
passem a cera encontrariam alguma coisa escrita na madeira. Isto foi feito, reve-
lando a mensagem, entao transmitida para os outros gregos.
Xerxes perdia dessa forma o elemento surpresa e os gregos puderam se
preparar para o latente ataque persa. Em 23 de Setembro de 480 a.C, a frota persa
aproximando-se da baıa de Salamina encontrou uma marinha grega preparada e
postada estrategicamente para a batalha. Os gregos, que apesar de estarem em
menor numero, atraindo os navios persas para dentro da baıa puderam lutar da
forma como queriam. Instaurou-se o panico entre as forcas persas, com navios
se chocando e completa desorganizacao estrategica. O ataque coordenado grego
humilhou a numericamente maior forca persa no decorrer de um dia.
Vimos nesse episodio que a comunicacao secreta foi alcancada por Demarato
atraves da ocultacao da mensagem. Quando isso ocorre, chamamos esteganografia,
nome cuja origem esta nas palavras gregas steganos, que significa coberto, e graphein,
que significa escrever.
A tıtulo de exemplo, temos formas alternativas de ocultacao de mensagens
que foram usadas nos mais diversos momentos da historia. Os antigos chineses es-
creviam suas mensagens em seda fina que entao era amassada para formar uma
pequena bola e coberta com cera. Tal bolinha era engolida pelo mensageiro re-
sponsavel pela entrega da mensagem.
Substancias presentes em plantas tambem foram usadas como tinta invisıvel.
CAPITULO 1. UM POUCO DE HISTORIA 15
Apesar do aparente desaparecimento da escrita, por conta da transparencia, o sim-
ples aquecimento do local queima a tinta deixando a escrita com um tom de cor
proximo ao marrom que possibilita a sua leitura.
Analisando o nıvel de seguranca que a esteganografia confere vemos que ela
sofre de uma fraqueza fundamental. Como a mensagem e apenas escondida e facil
concluir que se o mensageiro for revistado e a mensagem descoberta, seu conteudo
esta prontamente revelado.
A questao principal e que quando se faz uso de esteganografia o simples fato
de a mensagem ser interceptada e suficiente para que o conteudo da mensagem possa
ser obtido por maos erradas. Claro que existe a necessidade de que a mensagem seja
descoberta de fato, mas uma simples revista feita ja com a intencao de encontrar
objetos suspeitos de carregar mensagens, por exemplo, ja e suficiente para que em
muitos casos conteudos secretos sejam revelados.
Como a historia da Criptologia e uma luta evolutiva, ao lado da es-
teganografia tivemos o desenvolvimento da criptografia, derivada da palavra grega
Kriptos, que significa “oculto”. Diferentemente do que ocorre na esteganografia,
a criptografia tem por objetivo esconder o significado da mensagem e nao a men-
sagem em si. Tal processo de ocultar o significado de mensagens e conhecido como
encriptacao e segue um protocolo especıfico que e previamente combinado entre
emissor e receptor.
Veremos mais adiante diversas formas de misturar a mensagem que foram
utilizadas ao longo dos tempos e alguns episodios marcantes onde tivemos sua uti-
lizacao. Ressalto neste ponto a vantagem da criptografia sobre a esteganografia
no sentido em que uma mensagem criptografada mesmo que seja interceptada por
maos erradas nao tera prontamente seu conteudo revelado e sera necessario todo um
processo para eventualmente tornar a mensagem compreensıvel.
A fim de atingir um nıvel maior de seguranca e possıvel combinar es-
teganografia e criptografia. Temos um exemplo desta aplicacao nos anos em que
o mundo viveu os horrores da Segunda Guerra Mundial. Uma pratica comum entre
CAPITULO 1. UM POUCO DE HISTORIA 16
os agentes alemaes era a utilizacao do microponto, que consistia em reduzir fotografi-
camente uma pagina de texto ate torna-la um ponto cujo diametro nao ultrapassasse
um milımetro. Em seguida esse microponto era oculto sobre o ponto final de uma
carta que nao levantasse maiores suspeitas.
O primeiro microponto so foi descoberto pelo FBI em 1941 e daı pra frente
os americanos puderam ler as informacoes contidas na maioria dos micropontos in-
terceptados, com excecao dos casos onde os alemaes combinaram esteganografia e
criptografia, ou seja, alem de esconder a mensagem tomaram o cuidado de crip-
tografa-la. Dessa forma, mesmo que os americanos interceptassem os micropontos
havia mais uma barreira a ser vencida ate que se pudesse chegar a informacao de
fato.
1.2 Ramos da criptografia
A criptografia pode ser dividida em dois ramos, a saber: transposicao e substituicao.
1.2.1 Transposicao
Neste caso temos o rearranjo das letras da mensagem de tal forma que tenhamos na
realidade anagramas como resultado. Analisando o nıvel de seguranca percebemos
que para mensagens muito curtas este metodo e muito inseguro ja que e limitado o
numero de possibilidades de rearranjo para poucas letras. Vejamos o caso de uma
palavra com tres letras. Ela pode ser rearranjada de apenas seis maneiras diferentes,
o que confere um nıvel muito baixo de seguranca.
A medida que o numero de letras aumenta, no entanto, o numero de re-
arranjos possıveis cresce assustadoramente, fazendo com que a tarefa de chegar a
mensagem original torne-se impossıvel quando nao se conhece o processo pelo qual
as letras foram misturadas.
Considerando os numeros astronomicos que envolvem esse tipo de trans-
CAPITULO 1. UM POUCO DE HISTORIA 17
posicao, fica claro que sua viabilidade depende de um conhecimento previo tanto do
emissor quanto do receptor do sistema utilizado para misturar as letras. Evidente-
mente tal sistema nao pode chegar ao conhecimento do inimigo.
Uma forma alternativa de utilizacao da transposicao encontramos no
primeiro aparelho criptografico militar, o citale espartano, que remonta ao seculo
cinco antes de Cristo.
Consiste em um bastao de madeira onde e enrolado um pergaminho ou
mesmo uma tira de couro. O emissor entao escreve a mensagem ao longo das linhas
que se formam no citale, conforme pode ser visto na figura 1.1, pagina 17, e ao ser
desenrolada a tira, esta parece conter uma serie de letras aleatorias e sem significado
aparente. Continuando o processo, a tira e entregue ao mensageiro responsavel por
fazer chegar ao destinatario desejado a mensagem secreta.
Neste ponto, fazemos a observacao de que e possıvel fazer uso combinado da
criptografia com a esteganografia que vimos ha pouco, de tal forma que o mensageiro
pode esconder a tira de diversas formas, mesmo porque seu formato permite isso. O
destinatario desejado ao receber a mensagem criptografada simplesmente enrola a
tira em um citale de mesmo diametro daquele utilizado pelo emissor. Naturalmente
e essencial que os diametros sejam os mesmos.
Figura 1.1: Primeiro aparelho criptografico militar, o citale espartano.
CAPITULO 1. UM POUCO DE HISTORIA 18
Ao tratarmos de uma cifra devemos levar em consideracao duas partes im-
portantes que sao o algoritmo e a chave. As relacoes entre ambas estao esquemati-
zadas na figura 1.2, pagina 18.
De maneira geral, se a mensagem e interceptada pelo inimigo ele apesar
de poder suspeitar qual foi o algoritmo utilizado para cifrar a mensagem se nao
dispuser da chave correta nao tera acesso a mensagem. A importancia da chave e
descrita pelo linguista holandes Auguste Kerckhoff Von Nieuwenhof, em seu livro La
Cryptographie Militaire. E o chamado Princıpio de Kerckhoff: “A seguranca de um
criptossistema nao deve depender da manutencao de um criptoalgoritmo em segredo.
A seguranca depende apenas de se manter em segredo a chave.”
Figura 1.2: O relacionamento entre algoritmo e chave.
Para que um sistema de codigo seja realmente seguro, alem da manutencao
em segredo da chave utilizada para encifrar a mensagem, e importante que haja
um numero amplo de chaves em potencial para que o trabalho de um interceptador
indesejado nao seja facilitado e mais, torne-se praticamente inviavel.
1.2.2 Substituicao
Uma alternativa para a transposicao e a substituicao. Julio Cesar fazia uso com
frequencia de escrita secreta e uma das formas de cifra de substituicao utilizadas
por ele consistia em substituir cada letra na mensagem por outra que estivesse tres
CAPITULO 1. UM POUCO DE HISTORIA 19
Alfabeto original a b c d e f g h i j k l m
Alfabeto cifrado D E F G H I J K L M N O P
Alfabeto original (continuacao) n o p q r s t u v w x y z
Alfabeto cifrado (continuacao) Q R S T U V W X Y Z A B C
Tabela 1.1: Alfabeto cifrado deslocado um determinado numero de casas (neste caso,
tres) em relacao ao alfabeto original.
Texto original veni vidi vici
Texto cifrado Y H Q L Y L G L Y L F L
Tabela 1.2: A cifra de Cesar aplicada a uma mensagem curta.
casas a frente no alfabeto. Observemos na tabela11.1, pagina 19 como fica o alfabeto
cifrado atraves da cifra de substituicao de Cesar e um exemplo de aplicacao para
uma frase curta na tabela 1.2, pagina 19.
A seguir, um estudo a respeito da cifra de substituicao de Cesar atraves de
aritmetica modular.
1.2.3 Cifras de substituicao atraves de aritmetica modular
Para tais sistemas de sigilo, inicialmente traduzimos letras em numeros. Tomamos
o alfabeto padrao de letras do Ingles e o traduzimos em inteiros de 0 a 25, como e
mostrado na tabela 1.3 abaixo.
Naturalmente devemos utilizar a serie de inteiros adequada ao alfabeto que
estivermos usando. Discutiremos sistemas de sigilo que sao baseados na trans-
formacao de cada letra da mensagem original para uma letra diferente de tal forma
1Foi convencionado em Criptologia que o alfabeto original deve ser escrito em letras minusculas
e o criptografado em maiusculas. Da mesma forma, o texto original e grafado em letras minusculas
e a mensagem cifrada em maiusculas.
CAPITULO 1. UM POUCO DE HISTORIA 20
Letra A B C D E F G H I J K L M N O
Numeral equivalente 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Letra (continuacao) P Q R S T U V W X Y Z
Numeral equivalente (cont.) 15 16 17 18 19 20 21 22 23 24 25
Tabela 1.3: Os numerais equivalentes para as letras.
que produzamos o texto cifrado. Tais cifras onde cada letra e substituıda individual-
mente por outra sao chamadas “cifras monograficas”. Temos no total 26! caminhos
possıveis para produzir uma transformacao monografica.
Para descrever a cifra de substituicao de Cesar atraves de aritmetica modu-
lar, seja P o numeral equivalente a letra no texto original e C o numeral equivalente,
de acordo com a correspondencia, ao texto cifrado. Entao:
C ≡ P + 3 (mod 26), 0 ≤ C ≤ 25
A correspondencia entre o texto original e o texto cifrado e dada na Tabela
1.4 abaixo.
Texto original A B C D E F G H I J K L M N O
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Texto cifrado 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
D E F G H I J K L M N O P Q R
Texto original(continuacao) P Q R S T U V W X Y Z
15 16 17 18 19 20 21 22 23 24 25
Texto cifrado(continuacao) 18 19 20 21 22 23 24 25 0 1 2
S T U V W X Y Z A B C
Tabela 1.4: A correspondencia entre as letras para a Cifra de Cesar
Para cifrar uma mensagem usando esta transformacao, nos primeiro a tro-
camos por sua equivalente numerica e agrupamos as letras em blocos de cinco. Tal
CAPITULO 1. UM POUCO DE HISTORIA 21
agrupamento tem por objetivo prevenir o sucesso de uma criptoanalise2, baseada no
reconhecimento de particularidades das palavras. Ilustramos o procedimento inicial
encifrando a mensagem a seguir:
TRABALHO DE CONCLUSAO DE CURSO
Fazendo os grupos de cinco letras, teremos:
TRABA LHODE CONCL USAOD ECURS O
Agora convertemos as letras em seus equivalentes numericos, resultando:
19 17 0 1 0 11 7 14 3 4 2 14 13 2 11 20 18 0 14 3 4 2 20 17 18 14
Lancando mao da transformacao de Cesar C ≡ P + 3 (mod 26), isto se
torna:
22 20 3 4 3 14 10 17 6 7 5 17 16 5 14 23 21 3 17 6 7 5 23 20 21 17
Traduzindo de volta para letras, nos temos:
W U D E D O K R G H F R Q F O X V D R G H F X U V R
E esta e a mensagem que nos enviamos.
O receptor decifra isto da seguinte maneira. Inicialmente, as letras sao
convertidas para numeros. Entao, a relacao P ≡ C − 3 (mod 26), 0 ≤ P ≤ 25 e
usada para trocar o texto cifrado de volta para a versao numerica do texto original
e finalmente a mensagem e convertida para letras.
Utilizamos a mensagem abaixo cifrada pela Cifra de Cesar para ilustrar o
procedimento de decifracao descrito acima.
2criptoanalise e a ciencia da deducao do texto original a partir do texto cifrado, sem o conhec-
imento da chave. O assunto e tratado com maior riqueza de detalhes em 1.3, pagina 24.
CAPITULO 1. UM POUCO DE HISTORIA 22
G H S D U W D P H Q W R G H P D W H P D W L F D
Trocando estas letras por suas equivalentes numericas, temos:
6 7 18 3 20 22 3 15 7 16 22 17 6 7 15 3 22 7 15 3 22 11 5 3
Continuando, fazemos a transformacao P ≡ C−3 (mod 26) para voltarmos
ao texto original, e obtemos:
3 4 15 0 17 19 0 12 4 13 19 14 3 4 12 0 19 4 12 0 19 8 2 0
Traduzimos entao estes numeros de volta as letras e recuperamos assim a
mensagem original
DEPAR TAMEN TODEM ATEMA TICA
Combinando apropriadamente as letras em palavras, encontramos o que a
mensagem diz:
DEPARTAMENTO DE MATEMATICA
A Cifra de Cesar e uma da famılia de cifras similares conhecidas por “trans-
formacoes por substituicao”.
C ≡ P +K (mod 26), 0 ≤ C ≤ 25
Onde “K” e a “chave” que representa o tamanho do salto entre as letras
no alfabeto. Existem 26 transformacoes diferentes deste tipo, incluindo o caso em
que temos K ≡ 0 (mod 26), onde as letras nao sao alteradas, ja que neste caso
C ≡ P (mod 26). Mais geralmente, nos iremos considerar transformacoes do tipo
C ≡ aP + b (mod 26), 0 ≤ C ≤ 25 (1.1)
CAPITULO 1. UM POUCO DE HISTORIA 23
onde a e b sao inteiros com (a, 26) = 1. Essas sao chamadas “transformacoes afins”.
Dessa forma, transformacoes por substituicao sao transformacoes afins com a = 1.
Nos precisamos que (a, 26) = 1, assim P percorre um sistema completo de resto
modulo 26, incluindo C. Existem ϕ(26) = 12 opcoes para a e 26 opcoes para b dando
um total de 12 · 26 = 312 transformacoes desse tipo (uma delas e C ≡ P (mod 26)
obtido quando a = 1 e b = 0). Se a relacao entre texto original e texto cifrado e
descrita por (1.1), pagina 22 entao a relacao inversa e dada por
P ≡ a(C − b) (mod 26), 0 ≤ P ≤ 25
quando a e um inverso de a (mod 26).
Como um exemplo de tal cifra, vamos tomar a = 7 e b = 10, assim C ≡7P +10 (mod 26). Portanto, P ≡ 15(C − 10) ≡ 15C +6 (mod 26), desde que 15 e o
inverso de 7 modulo 26. A correspondencia entre letras e dada na tabela 1.5 abaixo:
Texto original A B C D E F G H I J K L M N O
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Texto original(continuacao) P Q R S T U V W X Y Z
15 16 17 18 19 20 21 22 23 24 25
Texto cifrado 10 17 24 5 12 19 0 7 14 21 2 9 16 23 4
K R Y F M T A H O V C J Q X E
Texto cifrado(continuacao) 11 18 25 6 13 20 1 8 15 22 3
L S Z G N U B I P W D
Tabela 1.5: A correspondencia entre as letras para cifra com C ≡ 7P +10 (mod 26).
Para ilustrar como nos obtivemos esta correspondencia, observe que a letra
original L com seu numeral equivalente 11 corresponde a letra J do texto cifrado,
desde que 7 · 11 + 10 = 87 ≡ 9 (mod 26) e 9 e o numeral equivalente de J.
CAPITULO 1. UM POUCO DE HISTORIA 24
Para ilustrar como encifrar, observe que
PLEASE SEND MONEY
e transformado em
L J M K G M G M F Q E X M W
Observe tambem que o texto cifrado
F E X E N Z M B M K J N H M G M Y Z M N
corresponde ao texto original
D O N O T R E V E A L T H E S E C R E T
ou combinando apropriadamente as letras
DO NOT REVEAL THE SECRET.
1.3 Os criptoanalistas arabes
Por volta do ano 661, o Isla havia se espalhado de tal forma que metade do mundo
conhecido encontrava-se sob o domınio muculmano. A civilizacao islamica alcancou
um nıvel muito alto de desenvolvimento, nas mais diversas esferas; social, cultural
e das ciencias em geral. Tal desenvolvimento deu-se atraves de uma sociedade rica
e pacıfica centrada na organizacao e menos interessada em conquistas.
Nesse contexto, temos dentro da historia da criptografia uma mencao hon-
rosa aos arabes por conta da descoberta da criptoanalise, a ciencia que permite
decifrar uma mensagem desconhecendo sua chave. Veremos que os criptoanalistas
CAPITULO 1. UM POUCO DE HISTORIA 25
arabes obtiveram sucesso ao encontrar um metodo para quebrar a cifra de substi-
tuicao monoalfabetica que por seculos permanecera invulneravel.
Para que a criptoanalise pudesse se desenvolver foi necessario um nıvel con-
sideravel de desenvolvimento em areas tais como matematica, linguıstica e estatıstica
e a civilizacao muculmana serviu perfeitamente para este fim.
Em grandes escolas de teologia que foram fundadas, teologos examinavam
minuciosamente as revelacoes de Maome contidas no Corao. Havia o interesse em
estabelecer a cronologia das revelacoes e a forma encontrada para atingir tal final-
idade foi estabelecer a frequencia com que cada palavra aparecia nas revelacoes. A
ideia por tras desse procedimento era a de que algumas palavras haviam surgido
mais recentemente e assim uma maior frequencia de tais palavras em determinada
revelacao implicaria que esse texto pertenceria a uma parte posterior da cronologia.
Os estudiosos analisavam tambem o Hadith, ou seja, os pronunciamentos
diarios do profeta e buscavam demonstrar que cada declaracao era de fato de Maome.
Nesse sentido, era feita uma analise etimologica das palavras e uma comparacao com
os padroes linguısticos do profeta.
Como consequencia ate natural deste tipo de trabalho, descobriram partic-
ularidades muito interessantes das letras. A tıtulo de exemplo, perceberam que as
letras “a” e “l” sao mais comuns no idioma arabe, boa parte devido ao artigo definido
al-, enquanto que outras letras aparecem com frequencias varias vezes menor. Essa
observacao, a primeira vista ingenua e sem importancia, levaria ao primeiro grande
avanco dentro da criptoanalise.
Nao se sabe ao certo quem foi o primeiro a ter a percepcao de que a
frequencia das letras poderia ser utilizada com a finalidade de quebrar codigos, mas
a mais antiga descricao conhecida desta tecnica remonta a um cientista do seculo IX,
Abu Yusef Ya’qub ibn Is-haq ibn as-Sabbah ibn omran ibn Ismail al-Kindi. Al-Kindi
foi autor de centenas de livros das mais diversas areas do conhecimento. Seu maior
tratado, no entanto, so foi redescoberto no ano de 1987, no Arquivo Otomano Su-
laimaniyyah em Istambul e leva o tıtulo “Um manuscrito sobre a decifracao de men-
CAPITULO 1. UM POUCO DE HISTORIA 26
sagens criptograficas”. Apesar de tratar detalhadamente outros aspectos, o sistema
revolucionario de criptoanalise aparece sucintamente descrito em dois paragrafos, a
seguir:
Um meio de se decifrar uma mensagem codificada, quando conhecemos seu
idioma, e encontrar um texto diferente, na mesma lıngua, suficientemente longo
para preencher uma pagina. Entao contamos a frequencia com que cada letra
aparece. A letra que aparecer com maior frequencia chamamos de “primeira”, en-
quanto a segunda mais frequente recebe o nome de “segunda”, a terceira em ordem
de frequencia vira “terceira” e assim por diante, ate contarmos todas as letras difer-
entes no texto. Em seguida examinamos o criptograma que desejamos decifrar e
tambem classificamos os seus sımbolos. Descobrimos qual o sımbolo que aparece
com maior frequencia e o transformamos na “primeira” letra do texto que usamos
como amostra. O segundo sımbolo mais comum e transformado na “segunda” letra,
enquanto o terceiro sımbolo mais frequente vira a “terceira” letra e assim por diante,
ate convertermos todos os sımbolos do criptograma que desejamos decifrar.
Temos na tabela 1.3 a frequencia das letras para o alfabeto ingles.
Figura 1.3: Tabela de frequencias baseada em passagens extraıdas de jornais e ro-
mances cuja amostragem consistia em 100.362 caracteres do alfabeto. Tabela com-
pilada por H. Beker e F. Piper.
CAPITULO 1. UM POUCO DE HISTORIA 27
O procedimento descrito por al-Kindi, conhecido em criptografia como
analise de frequencia, resolveu um problema que ha muito intrigava os envolvidos
na tentativa de quebra de codigos, particularmente a cifra de substituicao monoal-
fabetica, que ate entao parecia invulneravel ao ataque de receptores indesejados.
A tecnica revolucionaria mostrava ser desnecessaria a verificacao de cada
uma das bilhoes de chaves em potencial. Estava provada a possibilidade de revelar
o conteudo de uma mensagem atraves da simples analise de frequencia de seus
caracteres.
Vale, no entanto, fazer uma observacao. Nao e possıvel fazer uso incondi-
cional da tecnica descrita por al-Kindi, ja que a lista padrao das frequencias de-
scrita na Tabela 1.3 oferece apenas uma media e nao deve corresponder fielmente as
frequencias de todo e qualquer texto.
De maneira geral, textos muito curtos tem maior chance de apresentar
desvios significativos enquanto que textos mais longos apresentam maior proba-
bilidade de fidelidade as frequencias tidas como padrao.
1.4 Criptoanalise de um texto cifrado
Vejamos agora um exemplo de aplicacao da analise de frequencia para decifrar um
texto. Suponhamos que interceptamos a seguinte mensagem e que sabemos que
ela foi misturada com uma cifra de substituicao monoalfabetica desconhecendo, no
entanto, a chave utilizada. Sabemos tambem que o texto original esta escrito em
ingles.
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ
LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV
OPVOV LBO LXRO CI SX’XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV
ZOICJO BYS, KXUYPD: ’DJOXL EYPD, ICJ X LBCMKXPV XPV CPO
PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL
CAPITULO 1. UM POUCO DE HISTORIA 28
XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV
XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?’
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK
Naturalmente uma pesquisa de todas as chaves possıveis nao e nada pratico.
Lancamos mao entao da analise de frequencia. O primeiro passo e ate mesmo a
reacao natural de qualquer criptoanalista frente a uma mensagem cifrada desse tipo
e fazer uma analise da frequencia com que cada letra ocorre na mensagem cifrada.
Temos entao a tabela 1.4, na pagina 28.
Figura 1.4: Analise de frequencia da mensagem cifrada.
Evidentemente a frequencia das letras varia bastante e neste caso temos
um texto relativamente curto, o que faz com que uma aplicacao simples e direta da
tecnica de analise de frequencias nao produza os resultados esperados.
Vejamos, a aplicacao incondicional resultaria que a primeira palavra, ou
seja, PCQ fosse decifrada como aov, o que nao faz nenhum sentido. Partindo por
outro caminho, percebemos que tres letras: O, X e P aparecem mais de trinta vezes
no texto cifrado. Vamos trabalhar com elas!
CAPITULO 1. UM POUCO DE HISTORIA 29
E razoavel supor que estas tres letras representam as tres letras mais comuns
do alfabeto ingles, mas existe a possibilidade de que nao estejam mantendo a ordem
correta. Sendo assim, podemos ter:
O = e, t ou a, X= e, t ou a, P= e, t ou a.
Prosseguindo, vamos incrementar nossa analise atentando a frequencia com
que nossas tres letras aparecem ao lado das outras letras.
Vejamos o caso da letra O. Ela aparece antes ou depois de varias letras
ou apresenta tendencia a ficar ao lado de algumas letras em especial? Esse tipo de
analise nos possibilitara saber se temos uma vogal ou consoante. SeO for uma vogal,
ela tera um comportamento mais amigavel com as outras letras, aparecendo antes
e depois da maioria delas. No caso de ser uma consoante existira uma tendencia a
evitar a maioria das letras.
Temos na tabela abaixo as informacoes quanto ao comportamento das letras
que estamos estudando quanto a frequencia com que aparecem antes ou depois das
demais.
Figura 1.5: Dados referentes ao comportamento das letras em estudo.
Percebemos que as letras O e X sao bem sociaveis, tendo evitado apenas
algumas letras. A letra P, no entanto, e bem menos amistosa ao evitar 15 letras!
Isso nos sugere que O e X representam vogais, enquanto que P e uma consoante.
A partir daqui resta-nos saber que vogais sao representadas por O e X.
Uma boa suposicao, naturalmente, e que sao e e a, as duas vogais mais populares
do idioma ingles. Mas ainda ha um problema a ser solucionado: O = e e X = a ou
CAPITULO 1. UM POUCO DE HISTORIA 30
O = a e X = e?
Neste ponto, uma observacao pertinente e que muito nos ajudara e a
seguinte. Na analise do texto cifrado, podemos perceber que a combinacao OO
aparece por duas vezes, enquanto que XX nao aparece nenhuma vez. Sabemos
tambem que as letras ee aparecem juntas muito mais frequentemente do que aa em
textos em ingles, e portanto, e muito provavel que tenhamos O = e e X = a.
Ate aqui conseguimos identificar com confianca duas letras do texto cifrado.
Um fato observado que apoia a conclusao de que X = a e o fato de que a e uma das
duas unicas palavras do ingles formadas por uma unica letra. Neste ponto, notamos
tambem que so uma outra letra aparece sozinha no texto cifrado e esta e o Y. Isso
supoe que ela representa a outra palavra inglesa de uma letra so, ou seja, o i.
Vale destacar que esse procedimento de focar a atencao em palavras de uma
so letra e padrao dentro da criptoanalise, mas neste caso particular, funciona porque
nosso texto cifrado manteve os espacos entre as palavras, o que frequentemente nao
ocorre, ja que os criptografos removem todos os espacos justamente para dificultar
a vida dos interceptadores inimigos.
Continuando, lancaremos mao de um truque que funciona mesmo nos casos
em que o texto cifrado esta unido numa linha contınua de caracteres.
O que se segue e um procedimento que nos permite identificar a letra h de-
pois de termos identificado a letra e. Fundamentamos-nos na seguinte constatacao.
No idioma ingles a letra h aparece com frequencia antecedendo a letra e (como em
the, then, they, etc.), mas muito raramente ocorre depois do e.
A tabela abaixo, que nos fornece dados referentes a frequencia com que
o O, que pensamos representar o e, aparece antes e depois de todas as letras do
texto cifrado nos sugere que o B representa o h, ja que ele aparece antes do O em
nove ocasioes, mas nunca depois dele. Observe que nenhuma outra letra na tabela
apresenta esse comportamento assimetrico com o O.
CAPITULO 1. UM POUCO DE HISTORIA 31
Figura 1.6: Dados referentes a letra O.
Vejamos o que temos, por ora. Identificamos com confianca quatro letras,
a saber: O = e, X = a, Y = i e B = h. Passemos entao a substituicao de algumas
das letras do texto cifrado por suas equivalentes no texto original mantendo as letras
do texto cifrado em maiusculas e as letras do texto decodificado em minusculas.
PCQ VMJiPD LhiK LiSe KhahJaWaV haV ZCJPe EiPD KhahJiUaJ LhJee
KCPK. CP Lhe LhCMKaPV aPV IiJKL PiDhL, QheP Khe haV ePVeV Lhe LaRe
CI Sa’aJMI, Khe JCKe aPV EiKKev Lhe DJCMPV ZelCJe hiS, KaUiPD: ’DJeaL
EiPD, ICJ a LhCMKaPV aPV CPe PiDhLK i haNe ZeeP JeACMPLiPD LC UCM
Lhe IaZReK CI FaKL aDeK aPV Lhe ReDePVK CI aPAiePL EiPDK. SaU i SaEe
KC ZCRV aK LC AJaNe a IaNCMJ CI UCMJ SaGeKLU?’
eFiRCDMe, LaReK IJCS Lhe LhCMKaPV aPV CPe PiDhLK
Com esse passo simples, podemos avancar em nosso trabalho observando
particularidades que nos possibilitam adivinhar algumas palavras. Por exemplo, as
palavras de tres letras mais comuns no ingles sao the e and, e elas sao facilmente
localizadas; Lhe, que aparece seis vezes e aPV, que aparece outras cinco. Portanto,
L provavelmente representa t, enquanto que P provavelmente representa n e V
representa d. Facamos novamente a substituicao das letras conhecidas.
nCQ dMJinD thiK tiSe KhahJaWad had ZCJne EinD KhahJiUaJ thJee KCnK.
Cn the thCMKand and IiJKt niDht, Qhen Khe had ended the taRe CI Sa’aJMI,
Khe JCKe and EiKKed the DJCMnd ZeICJe hiS, KaUinD: ’DJeat EinD, ICJ a
CAPITULO 1. UM POUCO DE HISTORIA 32
thCMKand and Cne niDhtK i haNe Zeen JeACMntinD tC UCM the IaZReK CI
FaKt aDeK and the ReDendK CI anAient EinDK. SaU i SaEe KC ZCRd aK tC
AJaNe a IaNCMJ CI UCMJ SaGeKtU?’
eFiRCDMe, taReK IJCS the thCMKand and Cne niDhtK
Quando chegamos neste estagio, onde algumas letras ja foram determinadas,
o processo de criptoanalise avanca muito rapidamente.
Atentemos a palavra que inicia a segunda frase, que e Cn. Sabemos que
toda palavra tem uma vogal, de tal forma que C deve ser uma vogal. Ate agora
so nao identificamos duas vogais, u e o; mas o u nao se encaixa, portanto C deve
estar representando o o. Tambem temos a palavra Khe, o que implica que o K
deve representar t ou s. Agora, sabemos que L = t e, portanto, K = s.
Apos a identificacao dessas duas letras e sua insercao no texto cifrado, vimos
o surgimento da frase thoMsand and one niDhts. Um palpite bastante razoavel
e de que se trata do tıtulo thousand and one nights(Mil e uma noites), e parece
provavel que a ultima linha esteja nos dizendo que se trata de uma passagem de
Tales from the Thousand and One Nights. Isto nos leva ao seguinte: M = u, I = f,
J = r, D = g, R = I e S = m.
Neste ponto, e conveniente ao inves de continuarmos palpitando a respeito
das outras letras, observarmos o que sabemos a respeito de ambos os alfabetos;
original e cifrado. Esses dois alfabetos formam a chave e ao identificarmos a identi-
dade de algumas letras no texto cifrado nos obtivemos detalhes do alfabeto cifrado.
Vejamos, a seguir, o que temos ate o momento.
Figura 1.7: Nosso alfabeto cifrado parcial.
CAPITULO 1. UM POUCO DE HISTORIA 33
Examinando o alfabeto cifrado parcial, ja e possıvel completar a crip-
toanalise, baseando-nos na observacao da sequencia VOIDBY que sugere a uti-
lizacao de uma frase-chave por parte do criptografo como base para o seu codigo.
Um simples trabalho de suposicao e suficiente para sugerir que a frase-chave
pode ser A VOID BY GEORGES PEREC, que e reduzida a AVOIDBYGER-
SPC apos a remocao dos espacos e repeticoes. Depois as letras continuam em ordem
alfabetica, omitindo-se qualquer uma que tenha aparecido na frase-chave.
Observamos ainda, neste caso particular, o cuidado por parte do criptografo
de nao comecar a frase-chave no inıcio do alfabeto cifrado, e sim tres letras depois do
comeco. Isto e possıvel porque a frase-chave comeca com a letra A e o criptografo
quis evitar codificar a como A. Finalmente, tendo em maos o alfabeto cifrado com-
pleto, decodificamos todo o texto cifrado e chegamos ao conteudo da mensagem.
Figura 1.8: Alfabeto cifrado completo.
Now during this time Shahrazad had borne King Shahriyar three sons. On the
thousand and first night, when she had ended the tale of Ma’aruf, she rose and
kissed the ground before him, saying:’Great King, for a thousand and one nights I
have been recounting to you the fables of past ages and the legends of ancient
Kings. May I make so bold as to crave a favour of your majesty?’
Epilogue, Tales from the Thousand and One Nights.
Capıtulo 2
Elementos da teoria dos numeros
Neste e no proximo capıtulo estaremos estudando elementos de teoria dos numeros
que sao pre-requisitos ao desenvolvimento futuro deste trabalho de conclusao de
curso.
2.1 Inteiros modulo m
Para entendermos as operacoes modulo m em Z, temos que comecar com a definicao
de divisibilidade.
Sejam a, b ∈ Z e b 6= 0. Dizemos que b divide a quando existe um inteiro
c tal que
a = bc.
E nesse caso escreveremos b | a. Se b nao divide a escreveremos que b - a.
Dizemos que a e divisıvel por b se b dividir a. Por exemplo, (−2) | 8, pois8 = (−2)(−4).
Observe que zero e sempre divisıvel por todos os inteiros nao nulos b, pois
sempre temos 0 = b× 0.
Os divisores positivos que chamaremos de divisores de um inteiro na-
34
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 35
tural a sao todos os inteiros positivos que dividem a. Se b e um divisor de a, entao
existe um inteiro positivo c tal que a = bc. E nesse caso c tambem e um divisor de
a.
Por exemplo, os divisores de 24 sao
1, 2, 3, 4, 6, 8, 12, 24.
Os divisores de zero sao os numeros naturais. O numero 1 tem um unico
divisor que e o proprio numero 1.
Teorema 2.1 Sejam a,a′,b numeros inteiros.
1. Se b | a e b | a′, entao
b | (a+ a′), b | (a− a′), b | (a′ − a), b | (aa′).
2. Se k | b e b | a, entao k | a.
3. Se b | a, entao b | at para qualquer inteiro t.
Demonstracao: Pela suposicao existem inteiros c e c′ tal que a = bc e
a′ = bc′, respectivamente. Entao, a + a′ = b(c + c′). Logo, b | (a + a′). Tambem
temos aa′ = bbcc′ = b2cc′. Portanto, b | (aa′). Similarmente poderemos demonstrar
as outras propriedades do item 1.
Para demonstrar o item 2, observamos que pela suposicao b = kd e a = bc.
Logo, a = (kd)c = k(dc). Entao k | a.
A demonstracao do item 3 e simples, pois quando b | a temos que a = bc.
Apos multiplicar os lados dessa igualdade por t, teremos que at = bct. Daı, at = b(ct)
que mostra b | at. Isso completa a demonstracao do teorema.
2.2 Inteiros modulo m
Seja m um inteiro natural.
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 36
Definicao 2.1 Dizemos que dois inteiros a e b sao congruentes modulo m se e
somente se
m | (a− b), ou m | (b− a).
Observe que se m | (a− b), naturalmente m | (b− a), pois
a− b = (−1)(b− a).
Portanto, para verificar se dois inteiros a, b sao congruentes modulo m e
suficiente verificar uma das condicoes da definicao. Quando m | (a−b), dizemos que
a e congruente com bmodulom e no casom | (b−a) dizemos que b e congruente
com a modulo m. Pela observacao acima, a e congruente com b modulo m se e
somente se b for congruente com a modulo m.
Quando a e b forem congruentes modulo m, escreveremos
a ≡ b (mod m).
Para um dado inteiro b, existem infinitos inteiros a congruentes com b
modulo m. Por exemplo, se m = 6 e b = 2, entao a pode assumir um dos muitos
numeros como:
2, 8, 14, 20, ...,−4,−10,−16,−22, ...
Usando o conceito a ≡ b (mod m) poderemos ver que a forma geral dos
inteiros a congruentes com 2 modulo 6 e
a = 2 + 6k,
em que k varia sobre todos os inteiros nao negativos, ou seja, k = 0, 1, 2, 3, .... Se
permitimos que k assuma todos os valores inteiros, teremos a forma geral dos inteiros
a congruentes com 2 modulo 6, como demonstra o exemplo acima.
O seguinte teorema leva-nos ao sistema de operacoes de numeros modulo
m.
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 37
Teorema 2.2 As seguintes propriedades sao verdadeiras:
1. a ≡ b (mod m) se e somente se b ≡ a (mod m).
2. Se a ≡ b (mod m) e c ≡ d (mod m) entao
(a+ c) ≡ (b+ d) (mod m), e
(a− c) ≡ (b− d) (mod m).
3. Se a ≡ b (mod m) e c ≡ d (mod m) entao
ac ≡ bd (mod m).
4. Se a ≡ b (mod m) entao ay ≡ by (mod m) para todo y ∈ Z.
Demonstracao: No item (1) apresentam-se duas formas de escrever que
m | (a − b), que e verdadeira de acordo com a nossa observacao explicitada na
propriedade acima.
O item (2) e consequencia direta do item (1), do teorema anterior.
O item (4) e consequencia direta do item (3), do teorema anterior.
Para demonstrar o item (3), vamos reescrever os dados do teorema na
seguinte forma
a = b+ km, c = d+ lm
para certos inteiros k e l. Agora, vamos respectivamente multiplicar os dois lados
dessas igualdades. Isso nos dara
ac = bd+ blm+ dkm+ klm2
= bd+m(bl + dk + klm)
Portanto, m | (ac − bd). Isso mostra que ac ≡ bd (mod m). Esta completa a
demonstracao do teorema.
O exemplo precedente permite-nos perceber que os numeros a congruentes
com 2 modulo 6 sao da forma a = 2 + 6k. Em outras palavras, a pode ser visto
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 38
como forma geral de todos os inteiros a, para os quais o resto da divisao por 6 e 2.
Por exemplo, suponhamos que estamos procurando um numero inteiro x para que
um numero dado a seja congruente com x modulo m. Para fazer isso, na pratica
aplicamos a divisao de Euclides.
Teorema 2.3 (Divisao de Euclides) Sejam a, b ∈ N dois inteiros naturais.
Entao, existem unicos inteiros q e r tais que
a = bq + r, 0 ≤ r < b. (2.1)
Quando a propriedade (2.1) esta satisfeita, dizemos que r e o resto da
divisao(de Euclides) de a por b. E chamaremos q de quociente.
Agora, voltamos para a pergunta anterior e suponhamos que a = 23141512,
e m = 121. Entao para achar x podemos igualmente procurar r da identidade (2.1).
Apos a divisao teremos que
23141512 = 121× 191252 + 20
Daı
23141512− 20 = 121× 191252
Essa propriedade pode ser escrita da seguinte forma
23141512 ≡ 20 (mod 121).
Logo, x = 20 e uma resposta.
Agora, o teorema precedente leva-nos ao seguinte resultado.
Teorema 2.4 Para um dado inteiro natural a e um inteiro natural m, existe um
unico inteiro positivo (natural) x com 0 ≤ x < m tal que
a ≡ x (mod m). (2.2)
Pelo teorema da divisao de Euclides e obvio que x e o resto da divisao de a
por m. Por exemplo, se a = 141, m = 10, entao x = 1.
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 39
Para definir operacoes modulo m, precisaremos de definir o conjunto dos
inteiros modulo m.
A cada inteiro positivo b, podemos associar um subconjunto infinito dos
inteiros a ser chamado classe de b modulo m ou numero b (mod m).
A classe associada ao numero b e exatamente o conjunto dos inteiros que
sao congruentes com b modulo m. Duas classes b (mod m) e d (mod m) sao iguais
se e somente se m | (b− d), ou igualmente
b (mod m) = d (mod m) ⇔ b− d ≡ 0 (mod m). (2.3)
Por exemplo, para b = 2 e m = 9, temos
2 (mod 9) = {...,−25,−16,−7, 2, 11, 20, ...}.
Se b = 3, entao
3 (mod 9) = {...,−24,−15,−6, 3, 12, 21, ...}.
Se b = 4, entao
4 (mod 9) = {...,−23,−14,−5, 4, 13, 22, ...}.
Pelas operacoes modulo m, entendemos as operacoes aritmeticas – adicao
e multiplicacao no conjunto de classes modulo m.
Agora vamos definir as operacoes aritmeticas de soma e multiplicacao para
classes modulo m.
Se b (mod m) e d (mod m) sao duas classes modulo m entao, definiremos a
soma modulo m e o produto modulo m delas, da seguinte maneira, respectiva-
mente,
b (mod m) + d (mod m) := b+ d (mod m), (2.4)
em que a soma do lado direito e a classe de b+ d modulo m.
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 40
E definiremos o produto(multiplicacao) por
b (mod m) · d (mod m) := bd (mod m), (2.5)
no qual o produto do lado direito e a classe modulo m do produto do b e d em Z.
Por exemplo, para b = 2 e d = 3 e m = 9, temos
2 (mod 9) + 3 (mod 9) = 5 (mod 9)
2 (mod 9) · 3 (mod 9) = 6 (mod 9)
Notemos que a troca de representantes das classes a (mod m) e b (mod m)
nao afeta a soma e nem a diferenca das classes, pois se a (mod m) = a′ (mod m) e
b (mod m) = b′ (mod m), entao a ≡ a′ (mod m) e b ≡ b′ (mod m).
Teremos entao a+ b ≡ a′ + b′ (mod m) e a · b ≡ a′ · b′ (mod m).
Portanto a+ b (mod m) = a′ + b′ (mod m) e ab (mod m) = a′b′ (mod m).
Da mesma forma que no conjunto Z existem os numeros zero (0) e um (1)
satisfazendo
0 + a = a, 1a = a, para todo a ∈ Z,
no conjunto das classes modulo m tambem existem as classes zero e um. A classe
zero e 0 (mod m) e a classe um e a classe 1 (mod m), assim temos
0 (mod m) + b (mod m) = b (mod m)
1 (mod m) · b (mod m) = b (mod m).
para todas as classes b (mod m).
Seja b (mod m) uma classe modulo m. Se existir uma classe modulo m como
d (mod m) tal que
b (mod m) · d (mod m) = 1 (mod m) (2.6)
dizemos que d (mod m) e a inversa de b (mod m). Quando numa classe existe a
inversa, dizemos que ela e inversıvel.
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 41
Agora, podemos nos perguntar quando uma classe e inversıvel.
Para responder a essa pergunta invocamos a seguinte proposicao. Mas antes
relembremos o conceito de maximo divisor comum, a seguir:
Definicao 2.2 Dados dois inteiros a e b, chama-se maximo divisor comum de a e
b ao inteiro d satisfazendo:
1. d = 0, se a = b = 0
2. Se a 6= 0 ou b 6= 0, d e caracterizado pelas seguintes duas propriedades:
(a) d | a e d | b
(b) ∀x ∈ Z, x | a e x | b ⇒ x ≤ d
Observacao 2.1 Se d e o maximo divisor comum de a e b, denotamos
d = mdc(a, b)
De acordo com a notacao estabelecida acima, simbolicamente temos:
1- mdc(0, 0) = 0
2- Se a 6= 0 ou b 6= 0, entao
mdc(a, b) = max{x ∈ Z | x | a e x | b}
Agora sim, veremos a proposicao.
Proposicao 2.1 Sejam a, b, c ∈ Z. Entao existem inteiros x, y tal que
ax+ by = c
se e somente se mdc(a, b) | c.
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 42
Por exemplo, se a = 2, b = 4 e c = 3, nunca existira x, y ∈ Z, tais que
2x+ 4y = 3. A razao disso e que o mdc(2, 4) = 2 e que 2 - 3.
Agora podemos responder a pergunta acima.
Proposicao 2.2 Seja b 6= 0 um numero inteiro. Entao a classe b (mod m) tem
inversa (e inversıvel) se e somente se mdc(b,m) = 1.
Demonstracao: Primeiro, suponhamos que a classe b (mod m) tenha inversa, e
que sua inversa seja a classe d (mod m). Entao, pela identidade (2.6), pagina 40
temos
bd (mod m) = 1 (mod m).
Pela identidade (2.3) temos
bd− 1 ≡ 0 (mod m).
Logo, bd − 1 = ym para algum inteiro y. Portanto, bd − ym = 1. Isso
pode ser escrito na forma bd + (−y)m = 1. Entao, pela proposicao anterior temos
o mdc(b,m) = 1. Agora, suponhamos que o mdc(b,m) = 1, e dessa forma provare-
mos que a classe b (mod m) tem inversa. Para fazer isso, novamente, usaremos
a proposicao anterior que garante, sob a condicao mdc(b,m) = 1, que a equacao
bx+my = 1 tem solucao.
Portanto, existem numeros inteiros x = x0 e y = y0 tal que
bx0 +my0 = 1.
Essa equacao pode ser escrita assim,
bx0 − 1 ≡ 0 (mod m).
E essa congruencia pode ser escrita dessa forma
CAPITULO 2. ELEMENTOS DA TEORIA DOS NUMEROS 43
bx0 = 1 (mod m).
Daı, a classe x0 (mod m) e a inversa da classe b (mod m) e a demonstracao
fica completa.
Capıtulo 3
A funcao ϕ de Euler
A funcao ϕ de Euler tem a propriedade que seu valor em um inteiro n e o produto dos
valores da funcao nas potencias de primos que ocorrem na fatoracao de n. Funcoes
com essa propriedade sao chamadas funcoes multiplicativas.
O objetivo neste capıtulo e mostrar que a funcao ϕ de Euler e multiplicativa
e a partir daı chegarmos a uma formula para seus valores baseada na fatoracao em
primos.
A funcao ϕ de Euler calcula a quantidade de numeros inteiros positivos
relativamente primos com n e que sao menores que n. Por ora, vejamos algumas
definicoes que nos serao uteis no decorrer deste capıtulo e do estudo que faremos.
Definicao 3.1 Uma funcao aritmetica e uma funcao que e definida para todos os
inteiros positivos.
Definicao 3.2 Uma funcao aritmetica f e chamada multiplicativa se f(mn) =
f(m)f(n) sempre que m e n sao inteiros positivos relativamente primos. Ela e
chamada completamente multiplicativa se f(mn) = f(m)f(n) para todos os inteiros
positivos m e n.
Exemplo 3.1 A funcao f(n) = 1 para todo n e completamente multiplicativa, e
portanto tambem e multiplicativa, pois f(mn) = 1, f(m) = 1 e f(n) = 1, de tal
44
CAPITULO 3. A FUNCAO ϕ DE EULER 45
forma que f(mn) = f(m)f(n). Similarmente, a funcao g(n) = n e completamente
multiplicativa, e por isso multiplicativa, pois g(mn) = mn = g(m)g(n).
Se f e uma funcao multiplicativa, nos podemos encontrar uma formula
simples para f(n) dada a fatoracao em potencias de primos de n.
Definicao 3.3 Um inteiro positivo p 6= 1 e chamado “primo” se os seus unicos
divisores sao 1 e p.
Um numero inteiro positivo diferente de 1 e “composto” quando nao e primo.
Definicao 3.4 Dados a e b inteiros, dizemos que a e b sao relativamente primos ou
primos entre si se mdc(a, b) = 1,ou seja, se a e b nao tem fatores positivos comuns
alem da unidade.
Teorema 3.1 Se p e primo, entao ϕ(p) = p−1. Reciprocamente, se p e um inteiro
positivo com ϕ(p) = p− 1, entao p e primo.
Demonstracao: Se p e primo entao todos os inteiros positivos menores
que p sao relativamente primos com p. Como existem p − 1 desses inteiros, temos
ϕ(p) = p − 1. Reciprocamente, se p e composto, entao p tem um divisor d com
1 < d < p, e, e claro, p e d nao sao relativamente primos. Como sabemos que pelo
menos um dos p− 1 inteiros 1, 2, ..., p− 1, nomeado de d, nao e relativamente primo
com p, ϕ(p) ≤ p− 2. Portanto, se ϕ(p) = p− 1, entao p deve ser primo.
Definicao 3.5 (A funcao ϕ de Euler) Seja m ∈ N. Seja
E(m) = {x ∈ N | x ≤ m e mdc(x,m) = 1}.
Usando o sımbolo #E para denotar o numero de elementos do conjunto (finito) E,
nos definimos:
ϕ : N −→ N
ϕ(m) = #E(m)
ou seja,
CAPITULO 3. A FUNCAO ϕ DE EULER 46
ϕ(m) = #{x ∈ N; x ≤ m e mdc(x,m) = 1}.
Exemplo 3.2 1. Seja m = 5, entao E(5) = {1, 2, 3, 4} e assim temos que
ϕ(5) = 4.
2. ϕ(1) = 1, ϕ(2) = 1 e estes sao os dois unicos naturais com esta propriedade.
3. Se p e primo, entao ϕ(p) = p− 1.
Agora vamos encontrar os valores da funcao ϕ para potencias de primos.
Teorema 3.2 Seja p um primo e a um inteiro positivo. Entao ϕ(pa) = pa − pa−1.
Demonstracao: Os inteiros positivos menores que pa que nao sao relativa-
mente primos com pa sao aqueles inteiros nao excedendo pa que sao divisıveis por
p. Estes sao os inteiros da forma kp onde 1 ≤ k ≤ pa−1. Como ha exatamente pa−1
desses inteiros, ha pa − pa−1 inteiros menores que pa que sao relativamente primos
com pa. Portanto, ϕ(pa) = pa − pa−1.
Exemplo 3.3 Usando o teorema 3.2, nos encontramos que ϕ(53) = 53 − 52 = 100,
ϕ(210) = 210 − 29 = 512, ϕ(112) = 112 − 11 = 110.
Definicao 3.6 Um conjunto de inteiros {r1, ..., rs} e chamado um ‘sistema reduzido
de resıduos modulo m’ se
1. (ri,m) = 1, para todo i ∈ {1, 2, ..., s}.
2. ri 6≡ rj (mod m) se i, j ∈ {1, 2, ..., s} e i 6= j.
3. Para todo n ∈ Z satisfazendo (m,n) = 1, existe i ∈ {1, ..., s} tal que n ≡ri (mod m).
Com um pequeno abuso de notacao indicaremos um sistema completo de resıduos
modulo m por Z/mZ (utilizamos esta notacao para indicar o conjunto de todas as
classes de equivalencia da congruencia modulo m) e um sistema reduzido de resıduos
modulo m por (Z/mZ)∗.
CAPITULO 3. A FUNCAO ϕ DE EULER 47
Teorema 3.3 Sejam m,n ∈ N tais que mdc(m,n) = 1. Entao ϕ(m · n) =
ϕ(m)ϕ(n).
Demonstracao: Sejam x1, ..., xϕ(n) e y1, ..., yϕ(m) sistemas reduzidos de
resıduos modulo n e m respectivamente. Nossa intencao e mostrar que o conjunto
B das combinacoes lineares
bij = xim+ yjn
i = 1, ..., ϕ(n) e j = 1, ..., ϕ(m)
forma um sistema reduzido modulo mn, o que completaria a demonstracao. Para
isto precisamos mostrar:
1. bij 6= bkl se i 6= k ou j 6= l;
2. se mdc(a,mn) = 1 entao existe bij ∈ B tal que a ≡ bij (mod mn).
Comecemos pelo item (1), assumindo que
mxi + nyj ≡ mxk + nyl (mod mn),
entao
m(xi − xk) ≡ n(yl − yj) (mod mn).
Como m divide mn, temos que
n(yl − yj) ≡ 0 (mod m),
logo m | n(yl − yj).
Como m e n sao primos entre si, m divide yl − yj e portanto
yl ≡ yj (mod m).
Isto implica que j = l pois os y′is formam um sistema reduzido modulo m. Similar-
mente vemos que i = k.
CAPITULO 3. A FUNCAO ϕ DE EULER 48
Vamos entao asssumir que mdc(a,mn) = 1 e provar o item(2). Observe que
como mdc(m,n) = 1 existem inteiros r, s tais que rm+ sn = 1.
Logo existem x, y tais que a = xm+ yn.
Como mdc(a,mn) = 1 teremos mdc(a,m) = mdc(a, n) = 1, concluımos
que mdc(m, y) = mdc(n, x) = 1. Portanto x e y sao inversıveis modulo m, e assim
existem ındices i, j tais que
y ≡ yj (mod m) e x ≡ xi (mod n).
Logo
ny ≡ nyj (mod mn) e mx ≡ mxi (mod mn),
e entao temos
a = mx+ ny ≡ mxi + nyj = bij (mod mn)
como querıamos demonstrar.
Teorema 3.4 (Euler) Sejam a ∈ Z, m ∈ N tais que mdc(a,m) = 1. Entao
aϕ(m) ≡ 1 (mod m)
Demonstracao: Seja {r1, ..., rϕ(m)} um sistema reduzido de resıduos
modulo m. Vamos primeiramente verificar que o conjunto ar1, ..., arϕ(m) e tambem
um sistema reduzido de resıduos modulo m (Ver Definicao 3.6).
Seja A = {x ∈ Z | 1 ≤ x ≤ m − 1,mdc(x,m) = 1}. Notemos que A tem
ϕ(m) elementos.
Temos entao que A = {x (mod m) | x ∈ A} e o conjunto de inteiros modulo
m, que sao inversıveis na multiplicacao modulo m.
Vamos enumerar
A = {x1, x2, ..., xϕ(m)}
A = {x1 (mod m), ..., xϕ(m) (mod m)}
Tome a ∈ Z com mdc(a,m) = 1;
CAPITULO 3. A FUNCAO ϕ DE EULER 49
Demonstraremos a seguir que
B = {ax1 (mod m), ax2 (mod m), ..., axϕ(m) (mod m)} = A
Consideremos a funcao f : A −→ A
definida por f(x (mod m)) = ax (mod m).
f e injetora:
Suponhamos
ax (mod m) = ay (mod m)
Como mdc(a,m) = 1, a (mod m) tem um inverso b (mod m).
Sendo ax (mod m) = ay (mod m), teremos entao
bax (mod m) = bay (mod m)
logo
ba (mod m) · x (mod m) = ba (mod m) · y (mod m)
e assim, como ba (mod m) = 1 (mod m),
x (mod m) = y (mod m)
Sendo f injetora, como A e finito, f e sobrejetora e, portanto, B = A.
Assim,
ax1 · ax2 · · · axϕ(m) (mod m) = x1 · x2 · · · xϕ(m) (mod m)
e portanto
aϕ(m)x1x2 · · · xϕ(m) (mod m) = x1x2 · · · xϕ(m) (mod m)
Cancelando-se os varios xi’s, teremos
aϕ(m) ≡ 1 (mod m)
ou seja,
aϕ(m) (mod m) = 1 (mod m)
Referencias Bibliograficas
[1] ROSEN, KENNETH H., Elementary Number theory and its Applications. Read-
ing(MA): Addison-Wesley Publishing Co.2003.
[2] SINGH, SIMON., O livro dos codigos ; traducao de Jorge Calife. – 4aed. – Rio
de Janeiro: Record, 2004.
[3] SHOKRANIAN, SALAHODDIN., Criptografia para iniciantes / Salahoddin
Shokranian. – Brasılia: Editora Universidade de Brasılia, 2005.
[4] SHOKRANIAN, SALAHODDIN., Teoria dos numeros / Salahoddin Shokra-
nian; Marcus Soares, Hemar Godinho. – Brasılia: Editora Universidade de
Brasılia, 1994.
[5] SAMPAIO, JOAO CARLOS., Introducao a teoria dos numeros: um curso breve
/ Joao Carlos Vieira Sampaio, Paulo Antonio Silvani Caetano. – Sao Carlos:
EdUFSCar, 2008.
50
Parte II
Trabalho de Conclusao de Curso B
51
Resumo
Este trabalho apresenta-se como continuidade do estudo da Criptologia iniciado em
Trabalho de Conclusao de Curso A. Estudaremos aqui a chamada “criptografia de
chave publica”, tendo como foco a “criptografia RSA”.
Veremos alguns resultados da Teoria dos Numeros que possibilitaram e im-
pulsionaram o seu desenvolvimento, bem como algumas de suas caracterısticas prin-
cipais e implicacoes ao mundo dos negocios e ao nosso cotidiano de maneira geral.
Considerando a importancia da questao da fatoracao de numeros dentro do
sistema RSA, sao apresentados ainda dois metodos, a saber, Teste de fatoracao de
Fermat e Metodo Pollard p− 1.
Palavras-chave: criptologia, criptografia de chave publica, aritmetica
modulo m, pequeno teorema de Fermat.
52
Introducao
A historia da Criptologia caracteriza-se como uma luta evolutiva, no sentido em
que ha uma constante batalha entre os criadores e os decifradores de codigos. A
consequencia desse embate intelectual e a necessidade sempre presente do desen-
volvimento de novas formas de criptografia, cada vez mais seguras e de viavel im-
plementacao. Com o passar dos anos surgem novos problemas e desafios a serem
vencidos pelos criptografos, que encontram na matematica um campo muito fertil
para novas ideias e teorias.
As primeiras formas de criptografia, conforme visto no Trabalho de Con-
clusao de Curso A, sao aquelas conhecidas na area como criptografias de chave
privada, onde uma mesma chave e utilizada tanto para encifrar quanto decifrar as
mensagens. Naturalmente, essa chave precisa ser mantida em segredo entre as fontes
que trocarao as mensagens ja que sua interceptacao por maos erradas comprometeria
de imediato a seguranca da comunicacao dando acesso ao seu conteudo.
Toda essa logıstica necessaria para o processo da troca de mensagens e o
nıvel de seguranca que essa forma de criptografia oferece mostraram-se incompatıveis
com as exigencias cada vez maiores advindas do desenvolvimento tecnologico com
o passar dos anos. Com o advento da internet e todas as suas possibilidades no
tocante a troca de informacoes e formas de atividades comerciais, fez-se essencial o
desenvolvimento de uma criptografia segura e que pudesse otimizar os procedimentos
que garantiriam a seguranca das comunicacoes realizadas.
Nesse contexto surge a criptografia de chave publica, que estudaremos neste
trabalho.
53
Capıtulo 4
A criptografia de chave publica
Um dos problemas essenciais enfrentados por qualquer um que quisesse enviar men-
sagens secretas atraves de algum sistema criptografico e a questao da chave. Con-
forme visto no Trabalho de Conclusao de Curso A, havia sempre a necessidade do
conhecimento por ambas as fontes envolvidas no processo, ou seja, fonte A (emissor)
e fonte B (receptor), da chave utilizada para encifrar as mensagens.
A tıtulo de exemplo e fazendo alusao a metodos ja vistos anteriormente,
temos o caso do citale espartano, onde era necessario o conhecimento do diametro
do citale por ambas as partes ou ainda o numero “k” na cifra de Cesar, que conforme
visto, determinava o tamanho do salto entre as letras no processo de encifracao.
Esse empecilho esteve presente durante toda a historia da criptografia de-
safiando os criadores de codigos e dificultando muito o processo de envio e rece-
bimento de mensagens secretas. O problema persistiu ate chegarmos a epoca dos
negocios via internet e neste ponto imaginemos a situacao.
A logıstica necessaria para que as transacoes comerciais pudessem ser rea-
lizadas era uma barreira enorme a ser vencida, ja que numa situacao hipotetica em
que quisessemos realizar uma compra com cartao de credito, via internet, haveria
a necessidade de recebermos da empresa responsavel pela pagina virtual, cartas
confidenciais contendo as informacoes e dados sobre como codificar os dados.
54
CAPITULO 4. A CRIPTOGRAFIA DE CHAVE PUBLICA 55
Considerando a inviabilidade deste metodo, que justifica-se pelo enorme
tempo necessario para o desenvolvimento do processo e mais, sua inseguranca prove-
niente dos dados que estariam em circulacao, tornou-se necessario o desenvolvimento
de um sistema criptografico adequado a era emergente de rapida comunicacao global.
Mais uma vez entrariam em cena, como protagonistas desta batalha intelectual, os
matematicos, que atraves da criacao de novos codigos forneceram as bases para o
nascimento e desenvolvimento do que hoje e conhecido como criptografia de chave
publica.
Uma analogia entre o processo de codificacao e decodificacao com o pro-
cedimento de trancar e destrancar uma porta e bastante sugestiva. Em uma porta
comum, a mesma chave e usada tanto para abri-la como para fecha-la e nesse caso,
quanto maior for a distancia entre emissor e receptor maior tambem sera a logıstica
necessaria para o envio da chave utilizada para trancar e destrancar a mensagem.
No sistema de criptografia de chave publica, no entanto, existe uma
diferenca fundamental. Continuando com nossa analogia, neste caso terıamos uma
porta com duas chaves diferentes: uma chave X para trancar a porta e uma chave
diferente Y para destranca-la. Assim, nao ha mais a necessidade da manutencao de
confidencialidade em relacao a chave X.
Levando o que foi apresentado ha pouco para o contexto das transacoes
comerciais realizadas atraves da internet, veremos o gigantesco passo a frente que
foi dado quando da descoberta da criptografia de chave publica.
Imaginemos que uma porta guarda a entrada da secao segura da pagina
virtual de uma empresa. Como agora nao e mais imprescindıvel que a chave X,
usada para trancar a porta, seja mantida em segredo, a empresa pode distribuir
copias da chave para seus clientes que visitam a pagina e desejam enviar mensagens
seguras, como o numero de um cartao de credito, por exemplo.
Deve-se notar que, embora todos usem uma mesma chave para a codificacao
dos dados – trancando a porta e protegendo o segredo -, ninguem consegue ler as
mensagens codificadas dos demais e somente a empresa administradora da pagina
CAPITULO 4. A CRIPTOGRAFIA DE CHAVE PUBLICA 56
virtual possui a chave Y, usada para destrancar a porta e conseguintemente obter
acesso aos numeros dos cartoes de credito.
4.1 O nascimento da criptografia de chave publica
A criptografia de chave publica foi proposta inicialmente no ano de 1976, em um
artigo intitulado “Novos caminhos na criptografia”, escrito por dois matematicos da
Universidade de Stanford, na California. Whit Diffie e Martin Hellman publicaram o
artigo e defendiam a ideia de que a criptografia nao fosse um assunto discutido ape-
nas atras de portas fechadas do governo, mas que suas ideias se tornassem publicas.
O artigo prenunciou uma nova era da comunicacao eletronica segura e secreta.
A ideia por tras da criptografia de chave publica parecia revolucionaria
e excelente, mas ainda havia uma questao essencial a ser respondida: haveria a
possibilidade de coloca-la em pratica atraves da criacao de um novo codigo que
funcionasse obedecendo seus princıpios?
O desafio estava lancado e muitos anos depois, apos varias tentativas
frustradas, alguns criptografos ja comecavam a duvidar de que fosse possıvel cons-
truir tal codigo. Foi quando surgiu a figura de Ron Rivest, do Instituto de Tecnologia
de Massachussetts (MIT), que nutria grande interesse por questoes complexas en-
volvendo matematica e ciencia da computacao. Ao ser apresentado ao artigo da
dupla de Stanford ficou fascinado imediatamente por seu conteudo que envolvia
computacao, logica e matematica. Percebeu que era um problema com claras im-
plicacoes praticas no mundo real, mas que tinha tambem ligacoes diretas com as
preocupacoes teoricas que tanto ocupavam seu pensamento.
Rivest notou que para que nao fosse facil quebrar um determinado codigo,
ele teria de ser baseado em algum problema matematico cuja solucao fosse difıcil
de calcular e dedicou-se entao a criar um sistema de criptografia de chave publica
explorando todo tipo de problema que os computadores sabidamente levariam um
longo tempo para resolver.
CAPITULO 4. A CRIPTOGRAFIA DE CHAVE PUBLICA 57
Aderiram a empreitada de Rivest dois matematicos, Leonard Adleman e
Adi Shamir, razao pela qual temos as iniciais RSA, e juntos comecaram a buscar
ideias que permitissem implementar o sonho de Diffie e Hellman. A medida em que
exploravam diversos problemas matematicos considerados difıceis, foram aos poucos
se aproximando cada vez mais das ideias oriundas da Teoria dos Numeros. Varios
sistemas criptograficos embrionarios surgiram e foram posteriormente descartados
ate que algo lhes chamasse verdadeiramente a atencao.
Numa noite em que o trio foi convidado para um jantar na casa de um aluno
em celebracao a noite da Pascoa judaica, Rivest vislumbrou uma ideia que viria a
mudar radicalmente o rumo de suas vidas e da criptografia. Eles ja vinham ha algum
tempo considerando em seus estudos o difıcil problema da fatoracao de numeros e
sabiam que nao existiam boas propostas de programas que conseguissem decompor
numeros em seus blocos de construcao primos. Rivest, ao que tudo indicava, havia
encontrado uma maneira de utilizar esse problema na implementacao de seu novo
codigo.
Seguiram-se estudos para descobrir se a fatoracao era realmente tao difıcil,
considerando a restrita literatura acerca do assunto e a dificuldade na epoca em
se fazer boas estimativas sobre o tempo que os algoritmos existentes levariam para
realiza-la.
Martin Gardner, um especialista no assunto e colunista da Scientific Ameri-
can, ficou intrigado com a proposta de Rivest e publicou um artigo sobre tal ideia. A
enorme repercussao do artigo deu ao trio uma prova da grandiosidade daquilo com
que estavam trabalhando. Apesar de na epoca nao existir muito desenvolvimento
quanto ao comercio eletronico, havia a percepcao das implicacoes e da forca contida
naquela ideia.
Capıtulo 5
Teoria dos numeros para RSA
Teorema 5.1 (Pequeno Teorema de Fermat) Seja p um numero primo. Se a
e um numero inteiro tal que mdc(p, a) = 1, entao
ap−1 ≡ 1 (mod p)
Esse teorema e uma consequencia direta do seguinte teorema de Euler (a demons-
tracao encontra-se na monografia de Trabalho de Conclusao de Curso A).
Teorema 5.2 (Teorema de Euler) Sejam a,m inteiros com m > 0 tal que
mdc(a,m) = 1. Entao
aϕ(m) ≡ 1 (mod m)
Para verificarmos que, de fato, o pequeno teorema de Fermat (Teorema 5.1)
e uma consequencia do teorema de Euler (Teorema 5.2) basta supor que m = p.
Nesse caso as condicoes do Teorema 5.1 estao satisfeitas. Por outro lado, temos
ϕ(p) = p− 1. Portanto, o teorema de Euler nos fornece
ap−1 ≡ 1 (mod p)
que e exatamente a afirmacao do teorema de Fermat.
58
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 59
Teorema 5.3 Suponhamos que:
1. p e q sao numeros primos distintos;
2. e ∈ N e um inteiro tal que mdc(e, ϕ(pq)) = 1;
3. T ∈ Z e um inteiro tal que T 6≡ 0 (mod p) e T 6≡ 0 (mod q);
4. C ∈ Z e um inteiro definido por C ≡ T e (mod pq);
5. d ∈ Z e um inteiro definido pelas duas condicoes
ed ≡ 1 (mod ϕ(pq)), 1 ≤ d < (p− 1)(q − 1).
Entao
T ≡ Cd (mod pq).
Lema 5.1 Sejam a, b e c inteiros positivos tais que a e b sao relativamente primos.
1. Se b | ac entao b | c.
2. Se a | c e b | c, entao ab | c.
Demonstracao.
1. Sejam a e b inteiros relativamente primos, isto e, tal que mdc(a, b) = 1. Agora,
sendo a e b dois inteiros, a e b sao primos entre si se, e somente se, existirem
inteiros m e n satisfazendo
m · a+ n · b = 1
Multiplicando esta expressao por c, obtemos
m · ac+ n · bc = c
E obvio que b | nbc. Mas, por hipotese b | ac. Logo b | (m · ac+ n · bc) = c.
Portanto, b | c.
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 60
2. Pode ser provado a partir de (1). De fato, se a | c, pode-se escrever c = at,
para algum inteiro t. Mas, b | c, e como mdc(a, b) = 1, segue da afirmacao (1)
que b | t. Assim, t = bk para algum inteiro k. Portanto,
c = at = a(bk) = (ab)k
e divisıvel por ab, o que prova a afirmacao (2).
Usaremos agora o lema 5.1 para demonstrar uma propriedade muito impor-
tante dos numeros primos. Vejamos.
Propriedade Fundamental dos Numeros Primos: Seja p um numero
primo e a e b inteiros positivos. Se p | ab, entao p | a ou p | b.
Demonstracao. Se p | a, a prova esta concluıda. Supomos entao que p - a.
Como p e primo, entao mdc(a, p) = 1 e pelo lema 5.1, item (1), segue que p | b.
5.0.1 Algoritmo Euclidiano para o calculo de mdc
Recordaremos agora o algoritmo euclidiano para o calculo de mdc(a, b), no caso em
que a e b sao inteiros ambos nao nulos. O algoritmo e realizado atraves de uma
sequencia finita de divisoes euclidianas e ilustra-lo-emos atraves de um exemplo.
Queremos calcular mdc(91, 35) e para comecar fazemos a seguinte divisao
91 35
21 2
Consideramos entao o divisor 35 e o resto 21 dessa primeira divisao e efe-
tuamos a divisao euclidiana de 35 por 21.
35 21
14 1
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 61
Agora repetimos o processo iniciado acima, isto e, tomamos, na proxima
divisao, 21 como dividendo e 14 como divisor:
21 14
7 1
Finalmente, chegamos a divisao exata
14 7
0 2
Tendo chegado a um resto igual a zero, o algoritmo termina. O ultimo
resto nao nulo, das divisoes sucessivas realizadas, e o mdc procurado, ou seja,
mdc(91, 35) = 7.
5.0.2 Calculando inteiros r e s tais que mdc(a, b) = ra+ sb
Veremos agora como o algoritmo euclidiano, do calculo do mdc de dois inteiros, pode
ser usado para obtermos o mdc como uma combinacao linear desses inteiros.
Vimos acima que mdc(91, 35) = 7. Para expressar 7 como combinacao linear
de 91 e 35, consideramos as divisoes euclidianas usadas no calculo de mdc(91, 35),
91 35
21 2
35 21
14 1
21 14
7 1
14 7
0 2
Lembremo-nos de que o ultimo resto nao nulo, das divisoes sucessivas realizadas, e
o mdc procurado.
As tres primeiras divisoes estabelecem
91 = 35 · 2 + 21
35 = 21 · 1 + 14
21 = 14 · 1 + 7
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 62
E entao, isolando os restos, temos
21 = 91− 35 · 2
14 = 35− 21 · 1
7 = 21− 14 · 1
de onde entao obtemos, passo a passo, cada um dos tres restos como combinacao
linear de 91 e 35:
21 = 91− 35 · 2, conforme ja estabelecido.
14 = 35− 21 · 1
= 35− (91− 35 · 2)
= (−1) · 91 + 3 · 35
e finalmente
7 = 21− 14 · 1
= (91− 35 · 2)− [(−1) · 91 + 3 · 35] · 1
= 2 · 91 + (−5) · 35
ou seja,
7 = 2 · 91 + (−5) · 35
obtendo-se assim 7 = mdc(91, 35) como combinacao linear r · 91 + s · 35, com r e s
inteiros.
5.1 Uma aplicacao interessante
Os dois teoremas, Teorema 5.1 e Teorema 5.2, tem uma aplicacao interessante, ja
que podem ser usados para verificar se um dado inteiro positivo NAO E PRIMO.
Por exemplo, consideremos o numero n = 51. Veremos a seguir que esse numero
nao e primo. Inicialmente, facamos uma lista (Tabela 5.1) dos numeros 1 ≤ x ≤ 51
coprimos com 51, isto e mdc(x, 51) = 1. Isso nos mostra que ϕ(51) = 32.
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 63
1 2 4 5 7 8 10 11 13 14 16 19 20 22 23 25
26 28 29 31 32 35 37 38 40 41 43 44 46 47 49 50
Tabela 5.1: Lista dos numeros 1 ≤ x ≤ 51 coprimos com 51.
Agora, observamos que n = 51 e um numero ımpar e portanto coprimo com
2. Se 51 fosse primo, a seguinte congruencia deveria ser verdadeira:
251−1 ≡ 1 (mod 51)
mas apos calcular o lado esquerdo da congruencia acima (usando o programa Maple,
por exemplo) podemos ver que
251−1 = 250 = 1125899906842624
e
250 − 1 = 1125899906842623
que nao e divisıvel por 51. Portanto, 51 nao e primo.
Observacao 5.1 Tambem poderia ser usado o fato de que ϕ(51) 6= 51 − 1 = 50,
mostrando igualmente que 51 nao e primo. O objetivo desse exemplo nao era real-
mente verificar o fato trivial que 51 nao e primo, mas usar o pequeno teorema de
Fermat para chegar a esse fato.
5.2 Implementacao de RSA
Se um dos sistemas de cifra descritos e estudados no Trabalho de Conclusao de
Curso A, ou seja, aqueles conhecidos como sistemas de criptografia de chave privada
e usado para estabelecer comunicacoes seguras dentro de uma rede, entao cada par
de comunicantes deve empregar uma chave de encifracao que e mantida em segredo
para os outros indivıduos na rede, ja que se essa chave de encifracao e conhecida, a
chave de decifracao pode ser encontrada usando um pequeno tempo computacional.
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 64
Consequentemente, para manter secretas as chaves de encifracao elas precisam ser
transmitidas atraves de um canal de comunicacoes secretas.
Com o intuito de evitar essa necessidade da atribuicao de uma chave para
cada par de indivıduos e que deve ser mantida secreta do resto da rede, um novo
tipo de sistema de cifra, chamado sistema de cifra de chave publica, foi introduzido.
Neste tipo de sistema, chaves de encifracao podem ser tornadas publicas desde que
um tempo extraordinariamente grande e exigido para encontrar a transformacao de
decifracao atraves da transformacao de encifracao.
Para usar um sistema de cifra de chave publica para estabelecer comu-
nicacoes secretas em uma rede de “n” indivıduos, cada indivıduo produz uma chave
do tipo especificado pelo sistema de cifra, retendo certas informacoes privadas que
entraram na construcao da cifra de encifracao E(k), obtida da chave “k” de acordo
com uma regra especificada. Entao um diretorio com as “n” chaves k1, k2, ..., kn e
publicado. Quando o indivıduo “i” deseja enviar uma mensagem para o indivıduo
“j”, as letras da mensagem sao traduzidas para suas equivalentes numericas e com-
binadas em blocos de tamanho especıfico. Entao para cada bloco T da mensagem
um correspondente bloco C de texto cifrado, C = Ekj(T ), e computado usando a
tranformacao de encifracao Ekj . Para decifrar a mensagem, o indivıduo “j” aplica a
transformacao de decifracao Dkj para cada bloco de texto cifrado C para encontrar
T , isto e,
Dkj(C) = Dkj(Ekj(T )) = T
Desde que a transformacao de decifracao Dkj nao possa ser encontrada em
uma quantidade realista de tempo por ninguem a nao ser o indivıduo “j”, nenhum
indivıduo sem autorizacao pode decifrar a mensagem, mesmo que ele conheca a
chave kj .
O sistema de cifra RSA, inventado por Rivest, Shamir e Adleman nos anos
setenta, e um sistema de cifra de chave publica baseado em exponenciacao modular
onde as chaves sao pares (e, n), consistindo em um expoente e e um modulo n que e
o produto de dois primos grandes, isto e, n = p ·q, onde p e q sao primos grandes, de
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 65
forma que mdc(e, ϕ(n)) = 1. Para encifrar a mensagem, nos primeiro traduzimos as
letras em seus equivalentes numericos e entao formamos blocos do maior tamanho
possıvel. Para encifrar um bloco T da mensagem, nos formamos um bloco C de
texto cifrado por
E(T ) = C ≡ T e (mod n), 0 < C < n
O procedimento de decifracao requer o conhecimento de um inverso d de e
modulo ϕ(n), que existe ja que mdc(e, ϕ(n)) = 1. Para decifrar o bloco C de texto
cifrado, nos encontramos
D(C) ≡ Cd = (T e)d = T ed = T kϕ(n)+1 ≡ (Tϕ(n))kT ≡ T (mod n)
onde ed = kϕ(n)+1 para algum inteiro k, ja que ed ≡ 1 (mod ϕ(n)), e pelo teorema
de Euler, nos temos Tϕ(n) ≡ 1 (mod n), quando mdc(T, n) = 1. O par (d, n) e a
chave de decifracao. Desse modo, produzimos aqui, ainda que informalmente, uma
demonstracao do Teorema 5.3, enunciado na pagina 59.
A seguir mostraremos como usar o teorema 5.3 e implementar o sistema
de criptografia RSA. Observe que nesse sistema a questao tambem e como escrever
cifras e decifra-las. Nas discussoes a seguir T denota o texto da mensagem, esta
escrito em numeros (usando por exemplo alfabeto digital) e C as cifras, usadas para
encriptar a mensagem.
Definicao 5.1 Chamaremos o numero n = pq de modulo, o numero e de
potencia de encifracao, d de potencia de decifracao e a tripla (n, e, d) de
a chave do sistema RSA.
Definicao 5.2 O par (n, e) e a chave publica do sistema RSA e o par (n, d)
e a chave privada do sistema RSA.
A comunicacao entre as fontes A e B esta baseada no uso das chaves publica
e privada. A chave publica (n, e) da fonte A deve ser conhecida por B e a chave
publica (n′, e′) da fonte B deve ser conhecida por A. Neste caso, B e A podem trocar
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 66
mensagens secretas no sistema RSA. Para que B consiga enviar mensagens para A
as etapas sao:
1. B deve saber da chave publica (n, e) de A.
2. B traduz a mensagem x no alfabeto digital T (esse alfabeto deve ser conhecido
pelas mesmas fontes).
3. B escreve T em blocos numericos T1, T2, · · · , Tr. Os numeros T1, T2, · · · , Tr
nao devem ultrapassar o numero n = pq e devem ser primos com p e com q.
4. B encripta os blocos T1, T2, · · · , Tr usando a condicao (4) do teorema 5.3 e
assim estabelece as cifras C1, C2, · · · , Cr. Logo
C1 ≡ T e1 (mod n), C2 ≡ T e
2 (mod n), · · · , Cr ≡ T er (mod n).
Relembre que os Ci devem ser escolhidos de tal forma que Ci < n para todo
i = 1, · · · , r.
5. B transmite as cifras C1, C2, · · · , Cr para A.
6. Ao receber a cifra, a fonte A decifra as cifras C1, C2, · · · , Cr usando o resultado
do teorema 5.3, que diz que
Ti ≡ Cdi (mod n), i = 1, 2, · · · , r
usando a chave privada (n, d), onde na verdade somente d e privada para A e
somente A sabe esse numero.
7. Uma vez que T1, T2, · · · , Tr sao conhecidos por A, ele/ela pode usar o alfabeto
digital e transformar esses blocos numericos na mensagem original x. E o
processo esta completo.
5.3 Exemplo numerico
Ilustraremos a seguir, atraves de um exemplo numerico, como funciona o sistema
RSA. Sejam p = 59 e q = 101 dois numeros primos (menores do que os numeros
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 67
primos grandes que seriam realmente utilizados). Segue que n = p · q = 59 · 101 =
5959 e o modulo. Tomemos e = 13 como sendo nosso expoente para a cifra RSA.
Note que estamos satisfazendo a condicao (2) do Teorema 5.3, pagina 59, ja que
temos mdc(e, ϕ(n)) = mdc(e, (p−1)(q−1)) = mdc(13, 58·100) = mdc(13, 5800) = 1.
Neste ponto, lancando mao do algoritmo euclidiano para o calculo do mdc, visto no
Capıtulo 2, mostraremos que de fato mdc(13, 5800) = 1. Vejamos.
Comecamos fazendo
5800 13
2 446
Consideramos entao o divisor 13 e o resto 2 dessa primeira divisao e efetu-
amos a divisao euclidiana de 13 por 2.
13 2
1 6
Repetimos o processo iniciado acima, isto e, tomamos, na proxima divisao,
2 como dividendo e 1 como divisor:
2 1
0 2
Tendo chegado a um resto igual a zero, o algoritmo termina. O ultimo
resto nao nulo, das divisoes sucessivas realizadas, e o mdc procurado, ou seja,
mdc(13, 5800) = 1.
Continuando nosso exemplo, seja o seguinte alfabeto digital.
A B C D E F ...
01 02 03 04 05 06 ...
Tabela 5.2: Correspondencia alfa numerica
Queremos encifrar a mensagem “AB”
T = AB
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 68
e para isso, nos primeiro traduzimos as letras em seus equivalentes numericos e, em
seguida, os agrupamos em blocos de quatro. Segue
T = AB = 0102
Continuando com o algoritmo, nos enciframos cada bloco do texto da men-
sagem usando a relacao
C ≡ T e (mod pq)
No exemplo que estamos considerando, quando enciframos o bloco 0102,
obtemos o seguinte bloco de texto cifrado
C ≡ T e (mod pq) ⇔ C ≡ 10213 (mod 5959) ⇔ C = 3233
Devemos encifrar todos os blocos da mensagem, obtendo assim a mensagem
cifrada. Para decifra-la, temos de encontrar um inverso de e modulo ϕ(n), ou seja,
d tal que d = e−1 (mod ϕ(n)). Calculos usando o algoritmo euclidiano nos pos-
sibilitam escrever o mdc de dois numeros inteiros como combinacao linear entre eles
(Vide Capıtulo 2). Isso nos leva a descoberta de que d = 2677 e o inverso de 13
modulo ϕ(n) = 5800. Vejamos.
Vimos ha pouco que mdc(13, 5800) = 1. Para expressarmos 1 como com-
binacao linear de 13 e 5800 consideramos as sucessivas divisoes realizadas no algo-
ritmo euclidiano utilizado para encontrar o mdc e temos as seguintes igualdades:
5800 = 13 · 446 + 2 (5.1)
13 = 2 · 6 + 1 (5.2)
2 = 1 · 2 + 0 (5.3)
Considerando a igualdade 5.1, teremos:
5800 = 13 · 446 + 2 ⇔ 2 = 5800− 446 · 13 (5.4)
Considerando a igualdade 5.2, teremos:
13 = 2 · 6 + 1 ⇔ 1 = 13− 6 · 2 (5.5)
CAPITULO 5. TEORIA DOS NUMEROS PARA RSA 69
e relacionando 5.4 em 5.5
1 = 13−6(5800−446 ·13) ⇔ 1 = 13−6 ·5800+2676 ·13 ⇔ 1 = −6 ·5800+2677 ·13
e, portanto, d = 2677 e o inverso de 13 modulo ϕ(n) = 5800.
Consequentemente, para decifrar os blocos de texto cifrado C, nos usamos
a relacao
T ≡ C2677 (mod 5959), 0 ≤ T ≤ 5959
que e valida porque
C2677 ≡ (T e)d ≡ T ed ≡ T 1+k·ϕ(n) ≡ T (Tϕ(n))k ≡ T · 1k (mod n) = T
e mdc(T, n) = 1.
Em realidade, na criptografia RSA, p e q devem ser tomados bem grandes,
de modo a garantir que mdc(T, p) = mdc(T, q) = 1 para cada bloco a ser cifrado.
No nosso caso, sendo n = 59 · 101, a palavra T = AA e representada por 0101, que
nao e primo com n. Assim, a encifracao de AA pode nao funcionar.
Capıtulo 6
Metodos de fatoracao
O sucesso da criptografia RSA reside no fato de que, pelo menos no panorama da
Matematica computacional atual, nao ha algoritmos computacionais eficazes para
fatorar numeros inteiros que sejam produtos de fatores primos enormes. No entanto,
ao longo da historia, matematicos destacados dedicaram-se a desenvolver algoritmos
de fatoracao de inteiros. Neste capıtulo delineamos os elementos matematicos de dois
algoritmos famosos, sendo um deles de autoria de Fermat, e outro de autoria de John
Pollard, inventado em 1974.
A partir do teorema fundamental da aritmetica, nos sabemos que todo in-
teiro positivo pode ser escrito unicamente como produto de numeros primos. Neste
capıtulo, discutimos o problema da determinacao desta fatoracao. A maneira mais
direta para encontrar a fatoracao do inteiro positivo n e a seguinte.
Lembremos do teorema que nos diz que n e primo, ou entao tem um fator
primo nao superior a√n. Consequentemente, quando dividimos n pelos primos
2, 3, 5... sucessivamente nao excedendo√n, ou encontramos um fator primo p1 de n
ou entao podemos concluir que n e primo.
Se localizamos um fator primo p1 de n, olhamos entao para um fator primo
de n1 = n/p1, comecando a nossa pesquisa com o primo p1, uma vez que n1 nao
tem fator primo menor que p1, e qualquer fator de n1 e tambem um fator de n.
70
CAPITULO 6. METODOS DE FATORACAO 71
Continuamos, se necessario, determinando se qualquer um dos numeros primos nao
superiores a√n1 divide n1. Continuamos desta forma, procedendo iterativamente,
para encontrar a fatoracao prima de n.
Exemplo 6.1 Seja n = 42833. Notamos que n nao e divisıvel por 2, 3 ou 5, mas
que 7 | n. Temos:
42833 = 7 · 6119
Divisoes triviais mostram que 6119 nao e divisıvel por nenhum dos primos 7, 11, 13, 17, 19
ou 23. No entanto, vemos que
6119 = 29 · 211
Ja que 29 >√211, sabemos que 211 e primo. Nos concluımos que a fatoracao prima
de 42833 e 42833 = 7 · 29 · 211.
6.1 Teste de fatoracao de Fermat
Descrevemos aqui uma tecnica de fatoracao interessante, muito embora nao seja
sempre eficiente. Esta tecnica e conhecida como fatoracao de Fermat, por ter sido
descoberta pelo matematico frances Pierre de Fermat no seculo 17. O metodo e
baseado no seguinte lema.
Lema 6.1 Se n e um inteiro positivo ımpar , entao ha uma correspondencia um-
para-um entre fatoracoes de n em dois numeros inteiros positivos e a diferenca de
dois quadrados que e igual a n.
Demonstracao. Seja n um inteiro positivo ımpar e n = ab uma fatoracao de n em
dois numeros inteiros positivos. Entao n pode ser escrito como a diferenca de dois
quadrados, pois
n = ab = s2 − t2
onde s = (a+b)/2 e t = (a−b)/2 sao ambos inteiros ja que a e b sao ambos ımpares.
CAPITULO 6. METODOS DE FATORACAO 72
Por outro lado, se n for a diferenca de dois quadrados, digamos n = s2− t2,
entao podemos fatorar n observando que n = (s− t)(s+ t).
Para realizar o metodo de fatoracao de Fermat, buscamos solucoes da
equacao n = x2 − y2 procurando por quadrados perfeitos da forma x2 − n. As-
sim, para encontrar fatoracoes de n, buscamos um quadrado entre a sequencia de
numeros inteiros
t2 − n, (t+ 1)2 − n, (t+ 2)2 − n, ...
onde t e o menor inteiro maior que√n. Este procedimento e garantido, uma vez
que a fatoracao trivial n = n · 1 leva a equacao
n =
(
n+ 1
2
)2
−(
n− 1
2
)2
Exemplo 6.2 Iremos fatorar o numero 6077 utilizando o metodo de fatoracao de
Fermat. Como 77 <√6077 < 78, nos olhamos para um quadrado perfeito na
sequencia
782 − 6077 = 7
792 − 6077 = 164
802 − 6077 = 323
812 − 6077 = 484 = 222
Uma vez que 6077 = 812 − 222, vemos que 6077 = (81− 22)(81 + 22) = 59 · 103.
Infelizmente, o metodo de fatoracao de Fermat pode ser muito ineficiente.
Para fatorar n usando esta tecnica, pode ser necessario verificar (n + 1)/2 − √n
inteiros para determinar se eles sao quadrados perfeitos. A fatoracao de Fermat
funciona melhor quando e utilizada para fatorar inteiros que tem dois fatores de
tamanho similar. Apesar de o metodo de fatoracao de Fermat ser raramente usado
para fatorar inteiros grandes, ele e a base para muitos dos algoritmos de fatoracao
mais poderosos usados extensivamente em calculos de computador.
CAPITULO 6. METODOS DE FATORACAO 73
6.2 Metodo Pollard p− 1
O pequeno teorema de Fermat e a base de um metodo de fatoracao inventado por
J. M. Pollard em 1974. Esse metodo, conhecido como metodo Pollard p − 1, pode
encontrar um fator nao trivial de um inteiro n, quando n tem um fator primo p tal
que os numeros primos que dividem p− 1 sao relativamente pequenos.
Para ver como esse metodo funciona, supoe-se que se deseja encontrar um
fator do inteiro positivo n. Alem disso, supoe-se que n tem um fator primo p tal
que (p − 1) divide k!, onde k e um inteiro positivo que nao seja grande demais, ou
seja, deseja-se que p − 1 tenha apenas fatores primos pequenos. Por exemplo, se
p = 2269, entao p− 1 = 2268 = 22347, de modo que p− 1 divide 9!, mas nao divide
nenhum valor menor da funcao fatorial.
O motivo pelo qual se quer que p− 1 divida k! e para que se possa aplicar o
pequeno teorema de Fermat. Pelo pequeno teorema de Fermat sabemos que 2p−1 ≡1 (mod p). Agora, como p− 1 divide k!, k! = (p− 1)q para algum inteiro q. Assim
2k! = 2(p−1)q = (2p−1)q ≡ 1q = 1 (mod p)
o que implica que p divide 2k!−1. Agora, seja M o menor resıduo positivo de 2k!−1
modulo n, de modo que M = (2k!−1)−nt para algum inteiro t. Vemos que p divide
M , uma vez que p divide 2k! − 1 e n.
Agora, para encontrar um divisor de n, precisamos apenas calcular o maior
divisor comum de M e n, d = mdc(M,n). Isso pode ser feito rapidamente, usando
o algoritmo de Euclides. Para este divisor d ser um divisor nao trivial, e necessario
que M seja nao nulo. Este e o caso quando o proprio n nao divide 2k! − 1, o que e
provavel quando n tem divisores primos grandes.
Para usar este metodo, deve-se calcular 2k! onde k e um inteiro positivo.
Isso pode ser feito eficientemente via exponenciacao modular. Para encontrar o
menor resto positivo de 2k! modulo n fixa-se r1 = 2 e usa-se a seguinte sequencia de
calculos:
r2 ≡ r21 (mod n), r3 ≡ r32 (mod n), ..., rk ≡ rkk−1 (mod n).
CAPITULO 6. METODOS DE FATORACAO 74
Nos ilustramos esse procedimento no exemplo seguinte:
Exemplo 6.3 Para encontrar 29! (mod 5157437), realizamos a seguinte sequencia
de calculos:
r2 ≡ r21 = 22 ≡ 4 (mod 5157437)
r3 ≡ r32 = 43 ≡ 64 (mod 5157437)
r4 ≡ r43 = 644 ≡ 1304905 (mod 5157437)
r5 ≡ r54 = 13049055 ≡ 404913 (mod 5157437)
r6 ≡ r65 = 4049136 ≡ 2157880 (mod 5157437)
r7 ≡ r76 = 21578807 ≡ 4879227 (mod 5157437)
r8 ≡ r87 = 48792278 ≡ 4379778 (mod 5157437)
r9 ≡ r98 = 43797789 ≡ 4381440 (mod 5157437)
Segue que 29! ≡ 4381440 (mod 5157437).
O exemplo seguinte ilustra o uso do metodo Pollard p − 1 para encontrar
um fator do inteiro 5157437.
Exemplo 6.4 Para fatorar 5157437 usando o metodo Pollard p − 1, encontramos
sucessivamente rk, o menor resıduo positivo de 2k! modulo 5157437, para k =
1, 2, 3, ...,. Calculamos mdc(rk − 1, 5157437) em cada etapa. Para encontrar um
fator de 5157437 precisamos de nove etapas, porque mdc(rk − 1, 5157437) = 1 para
k = 1, 2, 3, 4, 5, 6, 7, 8,, mas mdc(r9 − 1, 5157437) = (4381439, 5157437) = 2269.
Disso resulta que 2269 e um divisor de 5157437.
O metodo Pollard p − 1 nao funciona sempre. No entanto, ja que nada no
metodo depende da escolha de 2 como base, podemos estender o metodo e encontrar
o fator de mais inteiros usando inteiros que nao 2 como base. Na pratica, o metodo
Pollard p− 1 e utilizado apos tentativas de divisoes por numeros primos pequenos,
mas antes que a artilharia pesada de metodos, como o crivo quadratico e o metodo
de curvas elıpticas, seja usada.
Referencias Bibliograficas
[1] DU SAUTOY, MARCUS, 1965- A musica dos numeros primos: a historia de
um problema nao resolvido na matematica/Marcus du Sautoy; traducao, Diego
Alfaro. – Rio de Janeiro: Jorge Zahar Ed., 2007.
[2] ROSEN, KENNETH H., Elementary Number theory and its Applications. Read-
ing(MA): Addison-Wesley Publishing Co.2003.
[3] SINGH, SIMON., O livro dos codigos ; traducao de Jorge Calife. – 4aed. – Rio
de Janeiro: Record, 2004.
[4] SHOKRANIAN, SALAHODDIN., Criptografia para iniciantes / Salahoddin
Shokranian. – Brasılia: Editora Universidade de Brasılia, 2005.
[5] SHOKRANIAN, SALAHODDIN., Teoria dos numeros / Salahoddin Shokra-
nian; Marcus Soares, Hemar Godinho. – Brasılia: Editora Universidade de
Brasılia, 1994.
[6] SAMPAIO, JOAO CARLOS., Introducao a teoria dos numeros: um curso breve
/ Joao Carlos Vieira Sampaio, Paulo Antonio Silvani Caetano. – Sao Carlos:
EdUFSCar, 2008.
75
Recommended
