UNIVERSIDADE ESTADUAL DE MARINGÁ

CENTRO DE CIÊNCIAS EXATAS

DEPARTAMENTO DE MATEMÁTICA
PROGRAMA DE MESTRADO PROFISSIONAL EM
MATEMÁTICA
EM REDE NACIONAL – PROFMAT
(Mestrado)

DARCI DALA COSTA

A MATEMÁTICA E OS CÓDIGOS SECRETOS:

UMA INTRODUÇÃO À CRIPTOGRAFIA

Maringá – PR
2014
 DARCI DALA COSTA

A MATEMÁTICA E OS CÓDIGOS SECRETOS:

UMA INTRODUÇÃO À CRIPTOGRAFIA

Trabalho de Conclusão de Curso apresentado ao

Programa de Mestrado profissional em Matemática
em Rede Nacional – PROFMAT do Departamento
de Matemática, Centro de Ciências Exatas da
Universidade Estadual de Maringá, como requisito
parcial para obtenção do título de Mestre.
Área de concentração: Matemática.

Orientador: Prof. Dr. JOSINEY ALVES DE SOUZA

Maringá – PR
2014

III
Ficha Catalográfica
D136m Dala Costa, Darci
A Matemática e os códigos secretos: uma introdução à criptografia/
Darci Dala Costa.- Maringá: UEM/PROFMAT,2014.
xi, 67 p.: gráficos, tabelas.
Inclui bibliografia

Dissertação (mestrado) Universidade Estadual de Maringá, 2014

Orientador: Prof. Dr. Josiney Alves de Souza

1. Criptografia. 2. Criptografia – História. 3. Criptografia aplicada à

Matemática. 4. Criptografia – Método RSA. 5. Matemática. 6. Teoria dos números.
7. Linguagem codificada. I. Título
CDD 20ª ed. 005.82
512.7
513
Bibliotecária – Hebe Negrão de Jimenez -CRB 101/9
IV
 Dedico este trabalho à minha
Família: com amor, por tudo que
significam pra mim e com
gratidão, por suportarem os
momentos em que fui mais
estudante do que pai ou marido.

V
 Agradecimentos

Ao concluir este trabalho agradeço:

A CAPES, pela oportunidade e pelo fundamental apoio financeiro.
À minha esposa, Neiva, meus filhos Vitor e Thais pelo apoio e
compreensão.
Ao professor Josiney Alves de Souza, pela orientação e disponibilidade.
Aos meus colegas de Curso, especialmente a Graciele Muller, Reges
Gaieski, Maycon Pavei Boff e Vanderlei Veríssimo, o “Povo do Oeste” pelas
viagens divertidas.
A todos os professores que se dispuseram a ministrar aulas para nossa
turma.

VI
 Resumo

Neste trabalho buscamos mostrar, de forma sintetizada, a evolução da

criptografia desde a civilização grega até os dias atuais. Apresentamos as formas
de criptografar que tiveram algum destaque histórico, bem como algumas
sugestões de exercícios que podem ser trabalhados em aulas de Matemática
fazendo uso delas. Incluímos, também, alguns elementos da Teoria dos Números,
com o objetivo de auxiliar o entendimento de uma das formas de criptografia aqui
apresentadas: o Método RSA.
Palavras chave: Criptografia, Teoria dos Números, Criptografia RSA.

VII
 Abstract

In this work, we seek showing, in a synthetic form, the evolution of the

cryptography, from the Greek civilization until the present days. We introduce the
ways of encrypting that had some historic prominence, as well as some
suggestions of exercises which can be worked in the math classes doing the use of
them. We include, also, some elements of the Number Theory, with the purpose of
helping the understanding of one of the forms of encryption presented here: the
RSA method.

Key words: Cryptography, Number Theory, RSA Encryption.

VIII
“ A engenhosidade humana não pode arquitetar uma
escrita secreta que a própria engenhosidade humana
não possa resolver.”

Edgar Allan Poe

IX
 Sumário
Introdução . 1
1 Códigos Secretos Notáveis 3
1.1 Um pouco de História. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Quadrado de Polybius. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 4
1.3 Troca de César . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . 5
1.4 O Quadrado de Trithemius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 A cifra de Vigenère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Criptografia por Transposição. . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 A cifra ADFGX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Números Inteiros 15
2.1 Indução Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Elemento mínimo de um conjunto de inteiros. . . . . . . . 16
2.1.2 Princípio da Indução Finita . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Propriedade da Boa Ordem. . . . . . . . . . . . . . . . . . . . . . 17
2.2 Fatores e Números Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 Divisibilidade e propriedades . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Algoritmo da Divisão ou Divisão Euclidiana . . . . . . . . 19
2.2.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 20
2.2.4 Números Primos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.5 Como saber se um número é primo . . . . . . . . . . . . . . . . 23
2.2.6 Método da Fatoração de Fermat . . . . . . . . . . .. . . . . . . . 24
2.2.7 Formula de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.8 Fórmula de Euler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.9 Fórmula de Mersenne:. . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Congruências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.1 Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.4 Sistemas de Congruências Lineares . . . . . . . . . . . . . . . . . . . . . . . 36
2.5 Congruência e Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

X
 2.5.1 Cifra de César . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5.2 Cifra de Trithemius . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5.3 Cifra de Vigenère . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 42
3 A Teoria dos Números e a Criptografia RSA 45
3.1 O método de criptografia RSA. . . . . . . . . . . . . . . . .. . . . . . . . . . . 45
3.1.1 Descrição do método RSA . . . . . . . . . . . . . . . . . . . .. .. 47
3.1.2 Um exemplo de mensagem criptografada de
acordo com o método RSA . . . . . . . . . . . . . . . . . . . . . . 49
4 Sugestão de Atividade 60
4.1 Plano de Aula. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Conclusão 65
Referências Bibliográficas 67

XI
 Introdução
Você é capaz de entender o significado da mensagem abaixo?

Essa mensagem foi codi…cada, ou seja, o texto original foi substituído por
símbolos com o objetivo de di…cultar a leitura, ocultando, assim, o signi…-
cado.
A arte de usar símbolos diferenciados para representar mensagens é quase
tão antiga quanto a própria escrita. Atualmente, esse procedimento recebe o
nome de criptogra…a, termo cuja origem vem do grego kryptós (escondido)
e gráphein (escrita). De modo geral, essa técnica pode ser entendida como
o ato de aplicar um determinado código a …m de manter secreto o conteúdo
de certas informações.
Antes de existir os meios de comunicação atuais, os exércitos dependiam
de mensageiros para transmitir ordens e informações às tropas. Entretanto,
se o arauto fosse capturado e a mensagem caísse em mãos inimigas, dados
sigilosos poderiam ser revelados. Diante disso, era prudente que o conteúdo
estivesse codi…cado. Desse modo, os adversários permaneceriam alheios à
signi…cação.
Convém ressaltar que cifrar o texto era apenas uma maneira de di…cultar
a leitura, não uma garantia absoluta de segurança com relação ao envio da
mensagem. Os exércitos deveriam possuir uma rede e…ciente de envio de
informações, pois, se estas não chegassem ao destinatário, pouco importaria
o fato de estarem codi…cadas ou não.
Com a invenção do telégrafo, as mensagens poderiam percorrer grandes
distâncias rapidamente, sem a necessidade de um mensageiro. Contudo, emb-
ora fosse muito mais prático enviar um telegrama, não havia meios de garantir
que a linha estivesse imune a possíveis interceptações. Tal incerteza fez com
que surgissem maneiras próprias de comunicação – por meio de códigos –,
formadas por frases cifradas ou de sentido modi…cado.
Outra evolução importante foi o surgimento do telefone, o qual permitia
conversas a longas distâncias. Todavia, assim como o telégrafo, o telefone
também poderia ser grampeado, o que colocaria em risco conversas con…den-
ciais. Para contornar a situação, novamente entra em cena a linguagem em
código –neste caso, evidentemente, no nível da fala.
Nos tempos atuais, mesmo com o advento de toda a tecnologia relacionada
à Internet, a necessidade de o homem constituir novos sistemas semióticos
não se extinguiu. A…nal, os dados dos usuários são transmitidos via cabo
telefônico ou rádio, e as informações que viajam através desses meios estão
sujeitas aos mesmos perigos enfrentados em dispositivos como o telégrafo e

1
o telefone. Então, o remédio também é o mesmo: a utilização de mensagens
cifradas.
Em face do exposto, o trabalho ora aduzido almeja explorar, ainda que
nos limites de nossas possibilidades, o riquíssimo campo da criptogra…a.
Com efeito, apresentar-se-ão aqui alguns métodos semióticos desenvolvidos
no decorrer da História ocidental; métodos estes que se caracterizam pela uti-
lização, ora de letras do alfabeto latino, ora de números, como símbolos para
transmitir mensagens codi…cadas. Conseguintemente, o objetivo aqui pro-
posto é o de estabelecer uma base de pesquisa para professores que queiram
abordar o tema da criptogra…a em suas aulas.
Neste trabalho, analisaremos também a Teoria dos Números, ramo da
Matemática que contribuiu para o desenvolvimento do mecanismo criptográ-
…co que tornou mais seguras as transações comerciais via Internet: o método
RSA.
No Capítulo 1, destacaremos alguns processos de codi…car mensagens
usados antes do surgimento do computador. Para cada método apresentado,
elaboramos um exemplo de codi…cação, seguido da respectiva decodi…cação
–tudo isso, com modelos simples, de fácil entendimento.
No Capítulo 2, veremos alguns tópicos da Teoria dos Números. Focamos
a nossa atenção no estudo de números primos e congruências, apresentando
as principais proposições e teoremas que envolvem tais tópicos. Objetivamos,
com esse capítulo, formar uma base para o entendimento de um sistema de
criptografar muito empregado nos tempos atuais: o RSA.
No Capítulo 3, trabalharemos o funcionamento do método RSA. Para
tanto, destacaremos um exemplo de cifragem de palavra com o uso do mesmo.
No Capítulo 4, apresentaremos sugestões de atividades –desa…os ou ex-
ercícios de aplicação – para serem trabalhadas em aulas de Matemática.
Isso envolverá conteúdos como funções, matrizes, análise de frequência, pro-
priedades das potências e outros que, porventura, o leitor julgar exequível.

2
Capítulo 1

Códigos Secretos Notáveis

Neste capítulo, veremos as quatro maneiras mais comuns de criptografar –

segundo[7] –da era pré-computador.
i) substituição monoalfabética: cada letra do alfabeto é representada por
um símbolo diferente, que pode ser um número, uma letra ou uma …gura
qualquer;
ii) substituição polialfabética: cada símbolo representa uma letra difer-
ente de acordo com sua posição na mensagem;
iii) transposição: a mensagem é transformada em uma matriz e crip-
tografada pela matriz transposta
iv) combinação de substituição e transposição

1.1 Um pouco de História

No decorrer da História da humanidade, a criptogra…a sempre esteve pre-
sente. Tal prática persiste até os tempos atuais, seja em situações de caráter
pessoal –como, por exemplo, nos diários de adolescentes que não querem que
seus segredos sejam revelados –, seja numa conjuntura mais ampla, como a
que envolve informações sobre pessoas, empresas, nações, táticas de guerra
etc.
Um dos primeiros povos ocidentais a registrar uma maneira de codi…car
mensagens em guerras foi os gregos –mais precisamente, o exército espartano,
há mais de 2500 anos –(ver[5]).
A troca de mensagens se dava da seguinte forma: o remetente escrevia
a mensagem em uma faixa de pergaminho enrolada em espiral, ao longo de
um cilindro, chamado cítala –o texto deveria ser escrito no sentido do com-
primento desse objeto. Consequentemente, a mensagem tornar-se-ia clara se
o pergaminho fosse enrolado em outra cítala, de mesmo diâmetro.

3
 No caso dos espartanos, a cítala era como a "chave"do código, pois servia
tanto para ocultar a mensagem como para revelá-la. A chave, no caso citado,
era um objeto. No entanto, com o passar do tempo, ela foi, aos poucos,
substituída por outros elementos, tais como números, mudança de posição
de letras, símbolos associados a letras, entre outros.
Veremos agora algumas maneiras de codi…cação conhecidas na História
ocidental.

1.2 Quadrado de Polybius

De origem grega, esta cifra consiste em um quadrado 5x5 onde são distribuí-
das as letras do alfabeto, estando as letras I e J na mesma posição.
Para criptografar por esse método associamos a cada letra um número de
dois dígitos formado pela linha e coluna, nessa ordem, onde estava a letra,
conforme ilustra a Figura 1.1 abaixo.

Figura 1.1

Por exemplo a letra L é representada pelo número 31. O L está situado

no encontro da terceira linha com a primeira coluna. Continuando dessa
maneira ciframos a palavra

LÁPIS pelo número 3111352443

e
LÁPIS PRETO por 31113524433542154434:

O quadrado de Polybius apresentava uma maneira de associar letras e

números, mas não era …xo, senão não teria utilidade visto que todos que o
usassem uma vez sempre saberiam como decifrar as mensagens. As letras

4
poderiam ser colocadas no interior do quadro de maneira aleatória o que
daria inúmeras possibilidades de variação da cifra.

1.3 Troca de César

Os romanos, naturalmente, também …zeram uso de mensagens secretas . O
imperador romano Julio César, utilizava um artifício que consistia em se
trocar a letra original pela letra que se encontra a algumas posições a frente
pela ordem do alfabeto.
Por exemplo se ele deslocasse as letras da mensagem original duas unidades
teríamos a cifra ilustrada na Figura 1.2.

Figura 1.2

Nessa con…guração a letra B seria representada por D, a palavra

GUERRA …caria IWGTTC

e a frase
VIM, VI, VENCI …ca XKO XK XGPEK.

Com algumas variações, usando qualquer um desses sistemas podemos

criar muitas maneiras de cifrar uma mensagem. Independente da escolha, só
estamos mudando o símbolo que representa a letra. Esse procedimento faz
com que a frequência do símbolo associado a letra permaneça a mesma. Na
prática, continuamos com um alfabeto de 26 símbolos . Por exemplo, em
um texto criptografado pelo quadrado de Polyibius, con…gurado da maneira
como dispusemos, sempre que aparecer o número 31 ele vai representar a
letra L.
Códigos como estes são chamados de Códigos de Substituição Alfabética e
eram muito utilizados até o século IX. Neste século o cientista árabe Al-Kindi

5
descreveu uma maneira de decifrar mensagens de acordo com a frequência em
que os símbolos apareciam nas mesmas, (ver[7]). Esse método é conhecido,
hoje, como "análise de frequência". Ele realiza uma contagem de símbolos
da mensagem e associa a quantidade deles com a frequência de cada letra
nos textos escritos na língua em que a mensagem foi, supostamente, escrita.
A Figura 1.3 mostra qual é a porcentagem de frequência das letras num
texto em português.
Figura 1.3

Com o uso das informações contidas nele, podemos concluir que o símbolo
com maior frequência em um texto tem uma grande possibilidade de ser um
A, se o texto estiver em português.
Como o objetivo da criptogra…a é ocultar informações, uma simples sub-
stituição alfabética, com o passar do tempo, deixou de ser segura tornando
necessária a criação de novas maneiras de ocultar mensagens.

1.4 O Quadrado de Trithemius

Os textos criptografados por substituição monoalfabéticas se tornaram vul-
neráveis após Al-Kindi. Mesmo assim, perduraram por algum tempo pois
a troca de informações era muito lenta nessa época. No século XV, Leon
Battista Alberti escreveu um manuscrito propondo uma nova forma de crip-
togra…a, a substituição polialfabética, ou seja, um código que possui mais de

6
um alfabeto em sua estrutura de codi…cação. O método de criptogra…a apre-
sentado faz uso de um quadro formado por 26 linhas e 26 colunas contendo
todas as letras do alfabeto. Cada linha do quadro representa uma troca de
César em relação à primeira linha.
O primeiro livro impresso que continha a descrição dessa forma de crip-
tografar foi: «Polygraphiae libri sex, Ioannis Trithemii abbatis Peapolitani,
quondam Spanheimensis, ad Maximilianum Ceasarem» , traduzido, "Poligra…a
em seis livros por João Trithemius, abade de Würzburg, anteriormente de
Sponheim, dedicados ao Imperador Maximiliano". Devido a isso o quadro
usado por Alberti …cou conhecido como Qaudrado de Trithemius, (ver[7],[8]).
A Figura1.4 representa o Quadrado de Trithemius.

Figura 1.4

Cifrar uma mensagem usando esse sistema é simples. Deslocamos e sub-

stituímos as letras de acordo com a posição na mensagem. Sendo o desloca-
mento igual a uma unidade a menos que a posição. Consideramos o alfabeto
um ciclo e a ordem alfabética das letras como o sentido positivo de desloca-
mento.
A Figura 1.5 mostra como codi…car a palavra POLIGRAFIA.

Figura 1.5

7
 Assim: POLIGRAFIA torna-se PPNLKWGMQJ
Note que, o primeiro I é cifrado por L e o segundo I por Q. Apenas a
análise de frequência não é su…ciente para quebrar esse tipo de código.
Para decodi…car, basta fazer o deslocamento oposto ao da codi…cação,
como está apresentado na Figura 1.6.

Figura 1.6

O Quadrado de Trithemius serviu de base para outros tipos de substitu-

ição polialfabética, como veremos a seguir.

1.5 A cifra de Vigenère

Ao estudar Trithemius e outros autores, no …nal do século XVI, Blaise de
Vigenère escreveu Traité des chi¤res ou secrètes manières d’écrire: em que
descreve os modos de encriptação usados na época. Um dos método descrito
por Vigenère, no qual se utiliza o Quadrado de Trithemius e uma palavra
chave para cifrar mensagens, foi originalmente proposto por Giovan Batista
Belaso em seu livro "La cifra del. Sig. Giovan Batista Belaso", (ver[7], [8]).
Acompanhe, passo a passo, como codi…car a palavra LEITURA, uti-
lizando como chave a palavra: PRIMO.
Conforme a Figura 1.7, escrevemos a palavra chave sobre o texto a ser
cifrado, letra sobre letra e repetindo a mesma palavra até que este termine.

Figura 1.7

8
 Para cifrar, devemos ter nas mãos o Quadrado de Trithemius. Cada letra
da cifra é obtida pela interseção da linha iniciada pela letra da palavra chave
com a coluna iniciada pela letra do texto.
Na mensagem que estamos codi…cando a primeira letra é obtida pela
interseção da linha que inicia com "P"com a coluna que inicia com "L"que é
a letra "A". A segunda letra é obtida pela interceção da linha que começa com
"R"com a coluna que começa com "E"que é "V".Seguindo esse procedimento
obtemos a cifra ilustrada na …gura 1.8.

Figura 1.8

Dessa maneira: LEITURA é cifrada como AVQFIGR.

Para decifrar o receptor deve escrever o texto cifrado sob a chave, letra
com letra e deve utilizar o Quadrado de Trithemius. A Figura 1.9 ilustra
esse procedimento no caso da mensagem ser AVQFIGR.

Figura 1.9

Para obter a primeira letra da mensagem original, seguimos a linha que

inicia com "P"até encontrarmos a letra "A". A primeira letra da coluna
que contém esse "A"que, no caso é "L", é a primeira letra da mensagem.
Para a segunda letra, seguimos a linha que inicia em "R"até a coluna que
contém "V", a letra do topo dessa coluna, no caso "E"é a segunda letra da
mensagem. Procedendo dessa maneira para cada par de letras Chave/Cifra
encontramos o texto original.(Figura 1.10)

Figura 1.10

9
 Apesar de ter sido elaborada por Belaso essa cifra é chamada de Cifra de
Vigenère.
Além desse sistema, Vigenere propôs um esquema chamado cifra de auto
chave, onde a chave era a própria mensagem iniciada por uma letra, chamada
letra primária, previamente combinada entre remetente e receptor. As Fig-
uras 1.11 e 1.12 mostram como …caria a nossa mensagem usando como letra
primária o "S".

Figura 1.11

Como a maneira de codi…car é a mesma:

Figura 1.12

A mensagem codi…cada é : "DPMBNLR".

Para decifrar a mensagem, visto que não temos uma palavra chave, pro-
cedemos do seguinte modo:
Tabelamos a mensagem e a letra primária como mostra a Figura 1.13.

Figura 1.13

Como a letra primária é "S"e a primeira letra da mensagem é "D", deve-

mos determinar a primeira letra da coluna que cruza a linha que inicia com
"S"em "D". Dessa forma encontraremos o "L". Então "L"é a primeira letra
da mensagem e também a segunda letra da chave.(Figura 1.14)

Figura 1.14

10
 Agora repetimos esse procedimento com o "L"e o "P"para encontrar o
"E", que é a segunda letra da mensagem e a terceira letra da chave. Repeti-
mos o processo até o término da mensagem ilustrado na Figura 1.15.
Figura 1.15

A cifra de Vigenère foi uma campeã em segurança. Foram precisos 300

anos para que, em meados do século XIX, Charles Babbage (na Inglaterra)
e Friedrich Kasiski (na Alemanha) quebrassem a cifra, (ver[8]).

1.6 Criptogra…a por Transposição

A quebra da Cifra de Vigenère mostrou a vulnerabilidade das cifras de sub-
stituição voltando a atenção dos criptoanalistas para outras formas de en-
criptação. Uma dessas formas é embaralhar o terxto, ao invés de subtituir
as letras. Uma das maneiras de fazer isso é criptografar a mensagem por
transposição. A mais simples é a transposição geométrica, assim chamadas
por usar como base uma matriz retangular. O texto original é escrito dentro
da matriz no sentido das linhas, completando com X os espaços que sobram.
Feito isso, é feita a transposição da matriz. A mensagem criptografada é
obtida pelo conjunto de blocos de letras formados pelas linhas.
Observe como isto é feito com o comando:
ATACAREMOS AO NASCER DO SOL
Como a ordem é formada por 23 letras, vamos escrevê-la em uma matriz
de 4 por 6, conforme a Figura 1.16.
Figura 1.16

A transposta desta matriz é dada na Figura 1.17.

11
 Figura 1.17

Assim:
ATACAREMOS AO NASCER DO SOL
torna-se
AEND TMAO AOSS CSCO AAEL RORX
Para decodi…car a mensagem, os blocos são escritos em uma matriz de 6
por 4, cuja transposta é a mensagem original.

1.7 A cifra ADFGX

Apesar de muito simples, criptogra…a por transposição serviu de base para
outro algoritmo, que foi utilizado durante a Primeira Guerra Mundial
No século XIX, foi inventado o telégrafo trazendo um grande avanço nas
comunicações. Agora as mensagens viajariam grandes distâncias sem a ne-
cessidade de um mensageiro o que, teoricamente, era uma garantia maior de
sigilo entre remetente e receptor da mensagem.
A utilização do telégrafo para envio de mensagens trazia também alguns
inconvenientes, tais como: eram necessários operadores nos postos e estes
teriam acesso a mensagem enviada, a linha telegrá…ca poderia ser "gram-
peada"por alguém com o equipamento correto e assim a mensagem seria
interceptada. Isso representaria um perigo em tempos de guerra
Para contornar essa situação os alemães criaram uma nova cifra utilizando
o tabuleiro de Polybius, substituindo os números 12345 pelas letras ADFGX,
uma palavra chave e uma transposição.
Acompanhe como codi…car uma mensagem usando este sistema:
Inicialmente, criamos uma matriz parecida com o tabuleiro de Poly-
bius.(Figura 1.18)

12
 Figura 1.18

A maneira de cifrar a mensagem segue, de início, da forma já vista, apenas

trocando o par de números pelo par de letras. Se a mensagem fosse

CHEGAREI SÁBADO,

teríamos:
C=AF,H=DF,E=AX,G=DD,A=AA,R=GD,E=AX,I=DG,
S=GF,A=AA,B=AD,A=AA,D=AG,O=FG
que, agrupado, …ca

AFDFAXDDAAGDAXDGGFAAADAAAGFG

A próxima etapa é escolher uma palavra-chave, que pode ter qualquer

tamanho mas não ter letras repetidas. Neste caso vamos utilizar a palavra
CIFRA.
Montamos uma tabela com as letras da palavra-chave na primeira linha
e completamos a tabela com a mensagem cifrada, uma letra para cada célula
da tabela, conforme ilustra a Figura 1.19.

Figura 1.19

A tabela deve ser reorganizada de forma que as letras da palavra-chave

…quem em ordem alfabética, alterando nas colunas correspondentes as letras
de forma apropriada:(Figura 1.20)

13
 Figura 1.20

A mensagem cifrada é formada pelos grupos de cada coluna, excetuando

a linha da palavra-chave. Em nosso caso, a mensagem enviada pelo telégrafo
se torna:

AADAA AXGGAG DDAFAG FDDGDF FAXAA.

O código ADFGX, por sua vez, deu origem a outro, o ADFGVX, que
incluía os algarismos de 0 a 9 e foi utilizado pelo exército alemão no …nal
primeira guerra mundial.
Embora o número de grupamentos nos dão a quantidade de letras da
palavra chave, esse código foi difícil de ser quebrado, feito realizado por
Georges-Jean Painvin sem o auxílio de computadores. Estes são capazes de
realizar várias simulações por segundo, podendo "quebrar"a mensagem pelo
que é chamado "força bruta"que signi…ca testar todos os casos.
Mas se o método da "força bruta"pode "quebrar códigos"e decodi…car
mensagens, surge a necessidade de criar uma maneira de codi…cação que
mesmo os computadores não possam decifrar.
Um método usado atualmente que vem conseguindo realizar essa proeza
é o RSA. Para apresentá-lo vamos revisar alguns conceitos de Teoria dos
Números que servem como base para o mesmo.

14
Capítulo 2

Números Inteiros

Neste capítulo trataremos de alguns pontos da Teoria dos Números sem os

quais não poderemos entender o método RSA. Nossa atenção será focada nas
proposições e teoremas necessários para a compreensão do mesmo. Ao …nal
do capítulo utilizaremos um de seus tópicos para cifrar e decifrar de maneira
mais rápida alguns métodos de criptogra…a vistos no Capítulo 1. Pautamos
este capítulo nos trabalhos: [1], [3] e [4] .

2.1 Indução Matemática

As ciências naturais baseiam suas conclusões a respeito de determinados fenô-
menos por meio de um grande número de observações e posterior análise de
resultados semelhantes. Dessa maneira, se um fenômeno, observado várias
vezes, produz o mesmo resultado, é possível fazer conclusões sobre ele. Tal
fenômeno conduz a tal resultado.
Fazendo uma analogia com a matemática, os fenômenos são as proposições.
Lembrando que proposições são sentenças declarativas a…rmativas que po-
dem ser verdadeiras ou falsas. O fato de uma proposição ser verdadeira num
grande número de casos particulares não nos permitirá concluir que ela é vál-
ida. Uma a…rmação sobre números só é valida se for verdadeira para todos
os números aos quais ela se refere. Como não podemos veri…car a veracida
de uma proposição com todos os números, usamos testes que se baseiam
nas características dos conjuntos numéricos envolvidos. Um teste para a…r-
mações sobre números inteiros, que veremos a seguir, é o chamado método
de recorrência ou indução matemática([3]).

15
2.1.1 Elemento mínimo de um conjunto de inteiros
De…nição 2.1. Seja A um conjunto de inteiros. Chama-se elemento mín-
imo de A um elemento de A tal que a x para todo x 2 A.
Notação: minA; se lê: mínimo de A.
Teorema 2.2. Se a é elemento mínimo de A, então esse elemento é único.
Demonstração: Com efeito, se existisse um outro elemento mínimo b de A,
teríamos: a b, porque a = minA e b a, porque b = minA o que implica
em a = b.

O elemento mínimo de A, se existe, denomina-se também primeiro ele-

mento de A ou menor elemento de A.

2.1.2 Princípio da Indução Finita

O Princípio da Indução é um importante instrumento para provar teoremas
que envolvam números inteiros. Para demonstrá-lo, no entanto, precisamos
do seguinte axioma.
Axioma 1. Seja N o conjunto dos números inteiros positivos e S um subcon-
junto de N tal que
i) 0 2 S
ii) S é fechado com respeito à operação de "somar 1"a seus elementos,
ou seja, para todo elemento n 2 S implicar (n + 1) 2 S:
Então S = N:
Se A N e a 2 N; usaremo a seguinte notação: a + A = fa + x; x 2 Ag.
É imediato veri…car que: a + N = fm 2 N; m ag
Teorema 2.3. ( Princípio da Indução ) Seja N o conjunto dos números
inteiros positivos e P(n) uma proposição associada a cada inteiro positivo n
e que satisfaz às duas seguintes condições:
i) P(1) é verdadeira;
ii) para todo inteiro positivo k, se P(k) é verdadeira, então P(k + 1)
também é verdadeira.
Nestas condições, a proposição P(n) é verdadeira para todo inteiro positivo
n.
Demonstração: Seja V o subconjunto dos elementos de N para os quais
P (n) é verdade. Considere o conjunto

S = fm 2 N; a + m 2 V g;

16
que veri…ca trivialmente a + S V:Como, pela primeira condição, temos que
a + 0 = a 2 V , segue que 0 2 [Link] outro lado, se m 2 S; então a + m 2 V;
e por (ii), temos que a + m + 1 2 V; logo m + 1 2 S: Assim, pelo Axioma de
Indução, temos S = N. Portanto,

fm 2 N; m ag = a + N V;

o que prova o resultado.

2.1.3 Propriedade da Boa Ordem

A Propriedade ou Princípio da Boa Ordem é uma maneira de dispor os ele-
mentos de um subconjunto, não vazio, de números inteiros como se estes for-
massem uma …la. Assim como o Princípio da Indução, é de grande relevância
nas demonstrações de teoremas que envolvem Números Inteiros.

Teorema 2.4. Sendo N o conjunto dos números inteiros positivos todo sub-
conjunto não vazio de N possui um menor elemento.

Demonstração: Seja S um subconjunto não vazio de N e suponha, por

absurdo, que S não possui um menor elemento. Queremos mostrar que S é
vazio, conduzindo a uma contradição. Considere o conjunto T , complementar
de S em N:Queremos, portanto, mostrar que T = N. De…na o conjunto

In = fk 2 N; k ng;

e considere a sentença aberta

p(n) : In T:

Como 0 n para todo n;segue que 0 2 T; pois, caso contrário, 0 seria um

menor elemento de S: Logo p(0) é verdade. Supomha agora que p(n) seja
verdade. Se n + 1 2 S; como nenhum elemento de In está em S, teríamos
que n + 1 é um menor elemento de S, o que não é permitido. Logo,

In+1 = In [ fn + 1g T;

o que prova que para todo n, In T ; portanto N T N e, consequente-

mente, T = N:

17
2.2 Fatores e Números Primos
Nesta seção apresentamos algumas propriedades relativas à divisão de números
inteiros, os números primos e teoremas envolvendo números primos e divisibil-
idade. Citamos, também, algumas fórmulas de obtenção de números primos
e o Método de Fatoração de Fermat.

2.2.1 Divisibilidade e propriedades

De…nição 2.5. : Sejam a e b números inteiros, com a diferente de zero.
Dizemos que a divide b, e notamos ajb, se existe um único inteiro c tal que
b = ac.

Nos termos da de…nição2.5, podemos dizer que b é múltiplo de a, que a

é fator ou divisor de b e, ainda, se 1<a<b, a é um fator próprio de b. O
número c na de…nição acima é chamado de cofator de a em b.

Proposição 2.6. Sejam a; b; c 2 Z*:

i) 1jc, aja e aj0:

ii) Se ajb e bjc; então ajc.
iii) Se ajb e ajc; então aj(b c):
iv) Se ajb; então ajbc:
v) Se ajb e aj(b c); então ajc:
Demonstração: i) Vem das igualdades c = 1 c; a = 1 a e 0 = a 0:
ii) Como ajb e bjc;então, por de…nição, existem d e f 2 Z tais que
b = a d e c = b f: Subtituindo o valor de b da primeira equação na outra
temos:
c = b f = (a d) f = a (d f );
o que mostra que ajc.
iii) Como ajb e ajc; então, por de…nição, existem d e f 2 Z tais que
b = a d e c = a f: De modo que:

b c = (a d) (a f ) = a(d f)

Logo aj(b c):

iv) Sendo que ajb;por de…nição existe d 2 Z tal que b = a d , logo:

bc = (a d) c = a (d c):

Portanto, ajbc:

18
 v) Vamos considerar o caso (b + c). Como ajb e aj(b + c);então,
por de…nição, existem d e f 2 Z tais que b = a d e (b+c) = a f: Substituindo
b na segunda igualdade, temos:
b + c = (a d) + c = a f:
Subtraindo a d de ambos os lados da igualdade temos:
c=a f a d = a(f d);
o que mostra que ajc.

2.2.2 Algorítmo da Divisão ou Divisão Euclidiana

Proposição 2.7. ( Algorítmo da Divisão) Dados a; b 2 Z; com b > 1,
existem únicos q; r 2 Z tais que
a = bq + r e 0 r<b
onde q é o quociente e r é o resto da divisão de a por b:
Demonstração: Seja b 2 Z; com b > 1: Dado um número a 2 Z, temos
duas possibilidades:
i) a é múltiplo de b, ou seja, existe q 2 Z tal que a = bq.
ii) a está entre dois múltiplos de b, ou seja, existe q 2 Z tal que
bq < a < b(q + 1): (Essas possibilidades são chamadas de Propriedades de
Arquimedes).
Subtraindo bq na igualdade (ii), esta torna-se:
0<a bq < b:

Seja r 2 Z; tal que r = a bq e

0 < r < b;
é claro que se r = 0, então a = bq. Caso (i). Resta saber se r e q são
únicos. Para isso supomos que a = bq + r e a = bq1 + r1 com 0 r; r1 < b:
Consideremos r 6= r1 com r > r1 : Assim
bq + r = bq1 + r1 =) b(q1 q) = r r1 ;
donde, concluímos que q1 > q e r = r1 + b(q1 q): Como r1 > 0 e q1 q > 1,
temos, pela última igualdade, que r > b o que é um absurdo. Então r = r1
e q1 = q:

19
Exemplo 2.1. Na expressão 17 = 3 5 + 2 temos que na divisão de 17 por
5 o quociente q = 3 e o resto r = 2:

2.2.3 Máximo Divisor Comum e Mínimo Múltiplo Co-

mum

De…nição 2.8. Sejam os números a; b 2 Z:Um número inteiro d é chamado

de Máximo Divisor Comum de a e b (denota-se d = mdc(a; b)) se:
i) dja e djb
ii) Se, para algum c 2 Z; temos cja e cjb; então cjd:
Por (i) temos que d é divisor tanto de a quanto de b e por (ii) temos que
d é o maior divisor com a caraterística (i).

De…nição 2.9. Sejam os números a; b 2 Z:Um número inteiro m é chamado

de Mínimo Múltiplo Comum de a e b (denota-se m = mmc(a; b)) se:
i) ajm e bjm
ii) Se, para algum c 2 Z; temos ajc e bjc; então mjc:
En…m m é o menor dos múltiplos comuns de a e b.

Teorema 2.10. (Teorema de Bachet-Bézout)Dados dois inteiros a e b,

não conjuntamente nulos. Seja d = mdc(a; b), então existem x e y inteiros
tais que: d = ax + by, ou seja, d é uma combinação linear de a e b.
Demonstração: Considere o conjunto L = { ax + by, todas as combi-
nações lineares de a e b} e n = ax0 + by0 onde n é o menor elemento natural
de L. Suponha, por absurdo, que n - a, então: a = nq + r (i), para q e r
inteiros com 0 < r < n. Subtraindo nq de ambos os lados, a igualdade (i) se
torna r = a nq: Substituindo o valor de n, temos:
r=a (ax0 + by0 )q = a ax0 q + by0 q = a(1 x0 q) + b(y0 q).
Isto implica em r 2 L; o que é um absurdo, pois r > 0 e r < n e n é o menor
elemento de L. Portanto nja: Analogamente njb: Assim n é divisor comum
de a e b. Resta mostrar que n é o maior divisor comum de a e b, ou seja,
n = d: Como d = mdc(a; b), então:
dja implica que existe q1 2 Z tal que a = dq1 (ii)
djb implica que existe q2 2 Z tal que b = dq2 (iii)

20
Sendo n = ax0 + by0 , de (ii) e (iii), n = dq1 x0 + dq2 y0 : Isolamos d e temos
n = d(q1 x0 + q2 y0 ); donde concluímos que djn: Do fato n ser divisor comum
de a e b e d = mdc(a; b); vem n d e de djn temos d n, logo d = n;
consequentemente d = ax0 + by0 :

Uma consequência direta do Teorema de Bachet-Bézout é que se mdc(a; b) =

1 exitem inteiros s e r tais que:

a r + b s = 1.

De…nição 2.11. Dados a; b 2 Z f 1; 0; 1g se mdc(a; b) = 1 dizemos que

os números a e b são coprimos ou primos entre si.

2.2.4 Números Primos

De…nição 2.12. Um número inteiro p 2 é dito primo se seus únicos

divisores positivos são 1 e p, caso contrário p é um número composto.

Exemplo 2.2. O número 7 é primo, pois tem como divisores apenas o 1 e

o 7 enquanto que o número 6 é composto pois seus divisores são 1, 2, 3 e 6.

Proposição 2.13. Sejam a; b e p 2 Z, com p primo. Se pjab então pja ou

pjb:

Demonstração: Supõe-se que p - a. Então os divisores comuns de p e a são

apenas 1 e [Link]í o mdc(a; p) = 1:Logo, existem x, y 2 Z de maneira que

1 = ax + py

Portanto, multiplicando ambos os membros da igualdade por b, temos b =

(ab)x + p(by):Como pj(ab) existe um k 2 Z tal que ab = kp. Dado que pjp,
então
b = (kp)x + p(by) = p(kx + by):
Logo, pjb.

Corolário 2.14. Se p é um primo tal que pjp1 pn , então pjpi para algum
i = 1; :::::; n:

Demonstração: Usando Indução, a proposição é verdadeira para n =

1(imediato) e para n = 2 (pela Proposição 2.13 ). Supondo, pois, n > 2
e que, se p divide um produto com menos de n fatores, então p divide pelo

21
menos um dos fatores (hipótese de indução). Pela proposição..., se pjp1 pn ,
então pjpn ou pjp1 pn 1 . Se pjpn , a proposição está demonstrada, e se,
ao invés, pjp1 pn 1 , então a hipótese de indução assegura que pjpk , com
1 < k < n 1. Em qualquer dos casos, p divide um dos inteiros p1 ; p2 ; :::; pn .

Corolário 2.15. Se p; p1 ; :::; pn são números primos e se pjp1 pn , então

p = pi para algum i = 1; :::::; n:

Demonstração: De fato, pelo Corolário 2.14, existe um índice k, com

1 < k < n , tal que pjpk , como os únicos divisores positivos de pk são 1
e pk , porque pk é primo, segue-se que p = 1 ou p = pk . Mas, p > 1, porque p
é primo. Logo, p = pk .

Teorema 2.16. (Teorema Fundamental da Aritmética)Todo inteiro

maior do que 1 é primo ou pode ser representado de maneira única (a menos
da ordem dos fatores) como um produto de fatores primos.

Demonstração: Usaremos o Princípio da Indução. Se n = 2, o resultado

é óbvio pois 2 é primo. Suponhamos o resultado válido para todo número
natural menor do que n e vamos provar que vale para n. Se o número n é
primo, não há o que demonstrar. No caso de n ser composto, existem números
inteiros positivos n1 e n2 tais que n = n1 n2 , com 1 < n1 < n e 1 < n2 < n.
Pela hipótese de indução, temos que existem primos p1 ; p2 ; :::; pr e q1 ; q2 ; :::; qs
tais que n1 = p1 ; p2 ; :::; pr e n2 = q1 ; q2 ; :::; qs . Portanto,

n = p1 p2 pr q1 q 2 qs :

Suponha, agora, que n = p1 p2 p r = q1 q2 qs , onde os pi e os

qj são números primos. Como p1 jq1 q2 qs pelo corolário 2.14, temos
que p1 = qj para algum j s; que, ao reordenarmos os fatores q1 ; q2 ; :::; qs
podemos chamar de q1 :Portanto,

p2 p r = q2 qs

Como p2 pr < n; a hipótese de indução implica em r = s e os pi e qj

são iguais aos pares. Isso mostra a unicidade da fatoração de n.

Teorema 2.17. Existem in…nitos números primos.

22
Demonstração: Consideremos que a quantidade de números primos seja
…nita e P = fp1 ; p2 ; p3 ; ; pn g o conjunto de todos os primos. Seja R =
p1 p2 p3 pn + 1; notemos que R é maior que qualquer pi 2 P e nenhum el-
emento de P é fator de R: Como, pelo Teorema Fundamental da Aritmética,
ou R é primo ou possui algum fator primo, isto implica na existência de um
primo que não pertence P . Portanto P não pode ser um conjunto …nito.

2.2.5 Como saber se um número é primo

Como sabemos, um número primo p não possui divisores positivos diferentes
de 1 e ele mesmo. Quando precisamos veri…car se um dado número n é primo
ou não devemos tentar encontrar divisores primos de n efetuando as divisões
até obtermos um resto zero. Caso isto não ocorra: n é primo. Por sorte, de
acordo com a seguinte proposição, não precisamos efetuar todas as divisões.
p
Proposição 2.18. Se p é o menor fator primo de n então p n:

Demonstração: Denotaremos por D(n) o conjunto dos divisores positivos

de n diferentes de 1 ou n. Como n não é primo, temos que D(n) 6= ?. Pelo
Princípio da Boa Ordem, existe um elemento
p p 2 D(n) tal que, para todo
q 2 D(n) tem-se p q: Supondo p que p > n pe que q seja cofator de p em
2
relação a n temos q > p > p n: Disto n = ( n) < p q = n; isto é um
absurdo. Sendo assim p n:

Exemplo 2.3. Para determinar se o número 173 é primo basta tentarmos

dividí-lo pelos primos menores ou igual a 13 que é, aproximadamente, sua
raiz quadrada:

173 = 86 2 + 1 resto 1
173 = 57 3 + 2 resto 2
173 = 34 5 + 3 resto 3
173 = 24 7 + 5 resto 5
173 = 15 11 + 8 resto 8
173 = 13 13 + 4 resto 4
Logo, 173 é primo.
Esta proposição diminui a quantidade de cálculos necessário para deter-
minar se um número dado é primo. Mesmo assim o processo é pouco prático
e demorado. Por isso o método RSA baseia sua segurança no processo de
fatoração de números extremamente grandes. pois sua chave pública é for-
mada por um número composto n que é produto de primos p e q com mais

23
de 60 algarismos cada. Fatorar um número como esse, usando testes de di-
visibilidade toma muito tempo, questão de anos para os computadores mais
avançados.

2.2.6 Método da Fatoração de Fermat

Pierre de Fermat (1601-1665) foi um dos poucos matemáticos amadores
famosos. Filho de um rico comerciante de couro, pôde se dedicar comple-
tamente aos estudos. Por in‡uência de sua mãe, descendente de uma família
de juristas, estudou leis na Universidade de Orleans e formou-se em advoca-
cia. Trabalhou durante toda sua vida na corte de justiça de Toulouse. Foi
nomeado juiz e ocupava os seus momentos de folga em diversos lazeres, entre
os quais a poesia e a Matemática.
Seu interesse na teoria dos números surgiu após ler o livro Aritmética
de Diofanto (matemático grego, 200 A.C.) e alguns dos problemas propostos
por Fermat, nesta área, eram tão difíceis que somente muitos anos mais
tarde foram provados. Seu resultado mais famoso resistiu por mais de 350
anos e inspirou a publicação, em 1996, do bestseller O Último Teorema de
Fermat. Este teorema diz que “se n é um natural maior que 2, então não
existem números inteiros x, y e z que satisfaçam a equação xn + y n = z n ”.
Isto foi provado de…nitivamente, em 1994, pelo matemático inglês Andrew
Wiles (repare que no caso n = 2 o teorema é satisfeito por todos os ternos
pitagóricos, isto é, por inteiros que satisfaçam o Teorema de Pitágoras)[8].
Apresentamos, agora, uma idéia de reduzir a quantidade necessária de
cálculos para a fatoração de um número: o Método da fatoração de Fermat.

Proposição 2.19. Seja n > 1 um inteiro ímpar. Há uma correspondência

biunívoca entre a fatoração de n e a representação de n como diferença de
dois quadrados.

Demonstração: Se n = a b, e n ímpar, então a e b são ímpares. Logo a + b

e a b são pares, e a 2 b e a+b
2
são [Link]ão,
2 2
a+b a b
n=
2 2

expressa n como a diferença de dois quadrados. Reciprocamente, suponha

n escrito como a diferença de dois quadrados: n = s2 t2 , então n =
(s t) (s + t) é a forma fatorada de n. Você pode ver que esses dois pro-
cedimentos –da fatoração para a diferença e da diferença para a fatoração –
determinam uma relação biunívoca.

24
Algorítmo de Fermat
A proposição 2.19 nos permite descrever um algorítmo,pque é muito e…ciente
nos casos em que n tem um fator primo próximo de n. A ideia é tentar
achar números inteiros positivos x e y tais que n = x2 y 2 . Caso estes
números sejam encontrados, temos que:

n = x2 y 2 = (x + y) (x y):

Logo x y e x + y são fatores de n.

O caso mais fácil ocorre quando n é um quadrado perfeito; isto é, quando
existe algum inteiro r tal que n = r2 . Neste caso temos que x = r e y = 0.
Observe que se y > 0 então
p p
x = n + y2 > n

Tentamos encontrar x e y; onde (x y) e (x + y) são fatores de n; com o

seguinte procedimento: p p
Passo 1: Fazemos x = b nc (parte inteira de n); se n = x2 então x é
fator de n e podemos parar.
Passo
p 2: Caso contrário incrementamos x de uma unidade e calculamos
y = x2 n: Se y for inteiro, paramos.
Passo 3: Repetimos o Passo 2 até encontrarmos y inteiro ou até que x
seja igual a n+1
2
; neste caso n é primo.

Exemplo 2.4. Vamos usar o Algorítmo de Fermat parapencontrar dois fa-

tores do número n = 1297603. Iniciamos fazendo x = b 1297603c = 1139:
Como 11392 = 1297321 < 1297603, passamos a incrementar x de um em um
e calculamos y. Vamos dispor os cálculos em uma tabela.(Tabela 2.1)

Tabela 2:1

Obtivemos, assim um inteiro no terceiro laço. Portanto x = 1142 e y = 81

são os valores desejados. Os fatores correspondentes são (x + y) = 1223 e
(x y) = 1061:Logo, 1061 e 1223 são fatores de 1297603:

25
 Essa maneira de encontrar fatores de um númerop inteiro n é prática
quando, pelo menos um deles estiver próximo de n:Também não é muito
útil para números inteiros muito grandes. Uma saída para agilizar a fatoração
de números, seria encontrar uma fórmula simples que fornecesse todos os
números primos.
Ainda não existe uma fórmula aritmética simples e e…caz que forneça
somente primos. As seções seguintes fornecem algumas fórmulas, elaboradas
por grandes matemáticos, que geram uma certa quantidade deles.

2.2.7 Formula de Fermat

Fermat conjecturou que números da forma
n
Fn = 22 + 1

são primos.
Para n = 0; 1; 2; 3; 4 os números:
0
F0 = 22 + 1 = 3
F1 = 22 + 1 = 5
2
F2 = 22 + 1 = 17
3
F3 = 22 + 1 = 257
4
F4 = 22 + 1 = 65:537

são todos primos. Porém, Euler mostrou que:

5
F5 = 22 + 1 = [Link] = 641 6700417.

Portanto F5 não é primo.

Até o momento só são conhecidos estes cinco primos de Fermat, (ver[8]).

2.2.8 Fórmula de Euler

Leonhard Euler (1707 -1783) foi um matemático e físico de origem suíça.
Nasceu na Basiléia, …lho do pastor calvinista Paul Euler que, desprezando
seu prodigioso talento matemático, determinou que ele estudasse Teologia e
seguiria a carreira religiosa. Daniel e Nikolaus Bernoulli convenceram o pai
de Euler a permitir que seu …lho trocasse o hábito pelos números.
Durante sua vida resolveu enorme quantidade de problemas, da naveg-
ação às …nanças, da acústica à irrigação. A solução de tais problemas, que
atendiam aos reclamos do mundo prático, não o entediava, principalmente

26
porque cada novo trabalho inspirava-o para criar uma Matemática nova e
engenhosa. Era capaz de escrever vários trabalhos em um único dia com os
cálculos completos e prontos para serem publicados, (ver[3][8]).
Em 1772 Euler descobriu um polinômio tendo uma longa sucessão de
valores primos, dado por

F (n) = n2 + n + 41

que fornece primos para n = 1, 2, ..., 39. Entretanto, para n = 40 o valor é

composto. De fato:

F (40) = 402 + 40 + 41 = 40:(40 + 1) + 41

= 40:41 + 41 = 41:(40 + 1) = [Link]

2.2.9 Fórmula de Mersenne:

Marin Mersenne (1588 - 1648) em 1644 fez a seguinte a…rmação: “Todo
natural
Mp = 2p 1
é primo para os primos p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 e 257, e é
composto para todos os outros primos menores que 257”:
A formula de Mersene fornece uma série de números primos e os números
primos que são obtidos pela sua fórmula recebem o nome de primos de
Mersene.
Estudos posteriores mostraram que Mersene havia se equivocado ao fazer
a sua lista: Incluiu M67 e M257 na sua lista de primos e excluiu dessa lista
M61 , M89 , M107 .. Nos meados do século XX, 300 anos depois, a lista correta
p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 e 127 onde p < 257, …cou pronta,
(ver[3]).
Segundo o site [Link] [Link], até janeiro de 2014
já eram conhecidos, 48 primos de Mersene, para os primos p = 2, 3, 5, 7,
13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423,
9689, 9941, 1213 ,19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091,
756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917,
20996011, 24036583, 30402457, 32582657, 37156667, 42643801, 43112609
e 57885161. Esse último primo foi descoberto em janeiro de 2013 e tem
17.425.170 de dígitos, (ver[3] e [8]).

27
2.3 Congruências
A codi…cação e decodi…cação pelo método RSA é baseada em cálculos que en-
volvem congruências. Nessa parte de nosso estudo veremos algumas de…nições
e proposições a repeito da mesma.

De…nição 2.20. Seja m um número natural diferente de zero. Diremos

que dois números a e b são congruentes módulo m se os restos das divisões
euclidianas de a por m e de b por m forem iguais.

A representação de a e b são congruentes módulo m é

a b(mod m):

Exemplo 2.5. 23 31(mod 4); já que os restos das divisões de 23 e de 31

por 4 são iguais a 3.

Proposição 2.21. Dados três inteiros a, b e m; com m > 0, temos que

a b(mod m) se, e somente se, mj(b a).

Demonstração: Sejam a = mq + r, com jrj < jmj e b = mq0 + r0, com

jr0j < jmj as divisões euclidianas de a e b por m, respectivamente. Logo,
b a = m(q 0 q) + (r0 r) onde jr0 rj < jmj: Portanto, a b(mod m) se,
e somente se, r0 = r; o que equivale a dizer que mjb a.

Proposição 2.22. Sejam m 2 Z com m > 1: Para todo a; b; c; d 2 Z;tem-se

que

i) a a(mod m)
ii) se a b(mod m);então b a(mod m);
iii) se a b(mod m) e b c(mod m), então a c(mod m)
iv) se a b(mod m) e c d(mod m), então a + c b + d(mod m)
v) se a b(mod m) e c d(mod m), então a c b d(mod m)
vi) se a b(mod m);então an bn (mod m):
Demonstração: i) a a(mod m) pois mj(a a) = 0.
ii) Se a b(mod m), pela proposição2.22 que mj(b a) sendo assim,
existe um inteiro x tal que (b a) = xm; por outro lado, existe o inteiro x,
simétrico de x; tal que xm = (b a) = (a b): Donde concluímos que
mj(a b), ou seja b a(mod m):
iii) Se a b(mod m) e b c(mod m);então mj(b a) e mj(c b): Pela
proposição2.6 (iii) mj(b a) + (c b) que equivale a mj(b a + c b), ou
mj( a + c):Portanto a c(mod m):

28
 iv) Se a b(mod m) e c d(mod m); então mj(b a) e mj(d c):Pela
proposição2.6 (iii) mj(b a) + (d c) que é o mesmo que mj(b a + d c), ou
mj(b+d a c) ou, ainda, mj((b+d) (a+c)):Portanto a+c b+d(mod m):
v) Se a b(mod m) e c d(mod m); logo mj(b a) e mj(d c):Faça
bd ac = d(b a) + a(d c):Como mjd(b a) + a(d c) concluímos que
mjbd ac; portanto a c b d(mod m):
vi) Usando o Princípio da Indução, temos que para n = 1 é verdadeira.
Supondo que an bn (mod m) como verdadeira, temos, usando a propriedade
(v) a b(mod m) e an bn (mod m), então a an b bn (mod m) =) an+1
bn+1 (mod m):O que mostra que a propriedade é verdadeira.

Proposição 2.23. Sejam a; b; c; m 2 Z, com c 6= 0 e m > 1. Temos que

a+c b + c(mod m) se, e somente se, a b(mod m)

Demonstração: Suponhamos que a + c b + c(mod m). A propriedade

(i) nos garante que c c(mod m) isto impílica que (c c) (c + ( c))
0(mod m): Somando c a ambos os lados da igualdade temos:

a + c + ( c) b + c + ( c)(mod m) que implica a + 0 b + 0(mod m)

logo
a b(mod m).
Partindo de a b(mod m): Temos, por (i); c c(mod m). Usando a pro-
priedade (iv) temos a + c b + c(mod m):

Proposição 2.24. Sejam a; b; c; m 2 Z, com c 6= 0 e m > 1. Então

m
ac bc(mod m) se, e somente se a b(mod ).
mdc(c; m)
m c
Demonstração: Note que mdc(c;m) e mdc(c;m) são coprimos. Temos, então,
que ac bc(mod m) se, e somente se, mjc(b a) , dividimos ambos os termos
por mdc(c; m)
m c
j (b a)
mdc(c; m) mdc(c; m)
que é equivalente a
m
j(b a)
mdc(c; m)

29
ou seja
m
a b(mod ).
mdc(c; m)

Da Proposição 2.24 decorre que:

Sejam a; b; c e m números inteiros, com c 6= 0, m > 1 e mdc(c; m) = 1:
Temos que: ac bc(mod m) se, e somente se, a b(mod m) e existe um
0 0 0
inteiro c tal que c c 1(mod m): Sendo c chamado de inverso de c
módulo m:

Exemplo 2.6. a) 36 21(mod 5) como 36 e 21 são múltiplos de 3, podemos

escrever 12 3 7 3(mod 5) que, pela proposição2.24 se torna 12 7(mod 5)
pois mdc(3; 5) = 1:Note, também que 3 2 1(mod 5): Logo 2 é o inverso de
3 módulo 5.

Proposição 2.25. Se existir um fator primo comum entre a e m, então a

não admite inverso módulo m.

Demonstração: Digamos que m e a são inteiros positivos tais que 1 <

a < m e existe um inteiro p; tal que 1 < p, pja e pjm:Suponha que existe
um inteiro b tal que ab 1(mod m): Assim teremos um q inteiro tal que
ab 1 = qm ou 1 = qm ab:Por hipótese

pja; logo pjab

pjm; então pjqm

pela Proposição 2.6 (iii) pjqm ab o que implica em pj1 que é um absurdo
pois 1 < p. Logo, nestas condições , não existe tal b.

Exemplo 2.7. 16 10(mod 6) como 16 e 10 são múltiplos de 2, podemos

escrever 8 2 5 2(mod 6) que não implica 8 5(mod 6) pois 8 2(mod 6).
Isto está de acordo com a proposição pois mdc(2; 6) 6= 1:

A Proposição 2.25 pode ser visualizada nas Tabelas 2.2 e 2.3 nos casos de
m = 7 e m = 6, respectivamente.

30
 Tabela 2.2

Tabela 2.3

Em termos de congruência, podemos dizer que sendo p primo e a e b

pertencem ao conjunto f0; 1; 2; :::p 1g com mdc(a; p) = 1 a congruência
ax b(mod p) tem solução única.
Os teoremas que serão vistos a seguir con…rmam essa a…rmação.

2.3.1 Teorema de Fermat

Pequeno Teorema de Fermat

Teorema 2.26. Se p é primo e se o mdc(p; a) = 1 então:

ap 1
1(mod p):

31
Demonstração: Consideremos os (p 1) primeiros positivos do conjunto
S = fa; 2a; 3a; 4a; :::(p 1)ag. Certamente, nenhum desses (p 1) inteiros é
divisível por p e, além disso, dois quaisquer deles são incongruentes módulo p,
pois, se fosse teríamos r e s tais que: ra sa(mod p); com 1 r s (p
1): Então, o fator comum a poderia ser cancelado, visto que o mdc(a; p) = 1.
Teríamos: r s(mod p), isto é pj(s r) o que é impossível, porque 0 <
s r < p. Assim sendo, dois quaisquer dos (p 1) inteiros a; 2a; 3a; :::; (p 1)a
divididos por p deixam restos distintos e, por conseguinte, cada um desses
p 1 inteiros é congruente módulo p a um único dos inteiros 1; 2; 3; :::; p 1.
Naturalmente numa certa ordem. Multiplicando ordenadamente essas p 1
congruências, teremos:

a 2a 3a ::: (p 1)a 1 2 3 ::: (p 1)(mod p);

ou seja:

ap 1
(1 2 3 ::: (p 1) 1 2 3 ::: (p 1)(mod p);

Como o mdc(p; (p 1)!) = 1, porque p é primo e p não divide (p 1)!,

podemos cancelar o fator (p 1)!, concluindo o argumento de Fermat:

ap 1
1(mod p):

Exemplo 2.8. Um exemplo para veri…cação numérica deste teorema pode

ser dado considerando p = 7, a = 5 e (p 1) = 6: Teríamos, então:

S = f5; 10; 15; 20; 25; 30g

Todos os elementos de S são incongruentes módulo 7, pois:

5 5(mod 7); 10 3(mod 7); 15 1(mod 7);

20 6(mod 7); 25 4(mod 7)e30 2(mod 7);

Pela Proposição 2.22 (v), temos:

(5 10 15 20 25 30) (5 3 1 6 4 2)(mod 7)

ordenando os fatores do primeiro termo

(5 10 15 20 25 30) (1 2 3 4 5 6)(mod 7)

32
isolando 5 nos fatores do primeiro termo

((5 1) (5 2) (5 3) (5 4) (5 5) (5 6)) (1 2 3 4 5 6)(mod 7)

separando os fatores 5

56 ( 2 3 4 5 6) (1 2 3 4 5 6)(mod 7)

escrevendo como fatorial

56 6! 6!(mod 7):

como mdc(6!; 7) = 1; pela proposição2.24, podemos cancelar 6! e teremos

56 1(mod 7):

O Teorema de Fermat é utilizado para determinar restos de divisões de

potências como as dos exemplos que segue:
Exemplo 2.9. Determine o resto da divisão de 5234 por [Link] 11 é primo
e mdc(11; 5) = 1, temos que 510 1(mod 11) aplicando o Teorema de Fermat
na questão dada, temos:

5234 510 23+4 (510 )23 54 123 54 54 625(mod 11) 9(mod 11)

Exemplo 2.10. Determine o resto da divisão de 33458 por 7. Inicialmente,

temos:33458 (4 7 + 5)458 (0 + 5)458 5458 (mod 7). Como 7 é primo e
6
mdc(7; 5) = 1, temos que 5 1(mod 7) aplicando o Teorema de Fermat na
questão dada, temos:

33458 5458 (mod 7) 56 76+2 (mod 7) (56 )76 52 (mod 7)

(56 )76 52 176 52 (mod 7) 52 (mod 7) 25(mod 7) 4(mod 7)

2.3.2 Teorema de Euler

Função Totiente (n)

De…nição 2.27. Chama-se função aritmética toda função f de…nida no con-

junto N dos naturais e com valores no conjunto Z dos inteiros, i.e., toda
função f de N em Z (f :N ! Z) .
De…nição 2.28. Chama-se Função Totiente a função aritmética (n) que
denota a quantidade de inteiros k 2 [1; 2; 3; ::::; n] ,tais que mdc(k; n) = 1:

33
Exemplo 2.11.

(1) = 1; pois mdc(1; 1) = 1

(3) = 2; pois mdc(3; 1) = 1; mdc(3; 2) = 1
(4) = 2; pois mdc(4; 1) = 1; mdc(4; 2) = 2; mdc(4; 3) = 1
(5) = 4; pois mdc(5; 1) = 1; mdc(5; 2) = 1; mdc(5; 3) = 1; mdc(5; 4) = 1

Proposição 2.29. i) Se p é primo, então (p) = p 1:

ii) Sejam m e n inteiros positivos, ambos maiores que 1, e mdc(m; n) = 1
então (m n) = (m) (n):

Demonstração: i) De fato, seja o conjunto Q = f1; 2; 3; ::; p 1g dos

números inteiros menores que p. Como p é primo nenhum elemento de Q
é fator de p, Logo para todo k 2 Q; mdc(k; p) = 1: Como há p 1 elementos
Q o resultado segue.
ii) Se considerarmos que m e n são ambos primos para podermos fazer
uso da propriedade (i), temos que (m) = m 1 e (n) = n 1 e o produto
(m) (n) = mn m n + 1 . O conjunto P = f1; 2; 3; m; ::n; ::; mng possui
m 1 elementos k1 ; k2 ; :::; km 1 tais que mdc(ki ; mn) = n e n 1 elementos
l1 ; l2 ; l3 ; ; ln 1 tais que mdc(li ; mn) = m e o próprio mn. Para o restante dos
elementos pi 2 P , temos: mdc(pi ; mn) = 1 então a quantidade de elementos
pi de P é dada por mn (m 1) (n 1) 1 logo (mn) = mn m n + 1
o que con…rma a propriedade.

A propriedade (ii) nos garante que se n é o produto de dois números

primos p e q temos que (n) = (p 1)(q 1):

Teorema de Euler
Antes de enunciarmos o Teorema de Euler, vamos considerar o seguinte lema.

Lema 2.30. Sejam a e n > 1 inteiros tais que o mdc(a; n) = 1. Se

a1 ; a2 ; :::; an são inteiros positivos menores que n e cada um deles coprimo
com n, então cada um dos inteiros a:a1 ; a:a2 ; :::; a:an é congruente módulo
n a um dos inteiros a1 ; a2 ; :::; an (não necessariamente nesta ordem em que
aparecem).

O argumento usado para a demonstração deste lema é o mesmo utilizado

na prova do Pequeno Teorema de Fermat.

34
Teorema 2.31. (Teorema de Euler) Se n é um inteiro positivo e se
mdc(a; n) = 1, então:
(n)
a 1(mod n):
Demonstração: A proposição é verdadeira para n = 1, pois a (1) 1(mod 1).
Suponhamos, pois, n > 1, e sejam a1 ; a2 ; :::; a (n) os inteiros positivos menores
que n e relativamente primos a n. Como o mdc(a; n) = 1, então, pelo Lema
2.30, os inteiros a:a1 ; a:a2 ; :::; a:a (n) são congruentes módulo n aos inteiros
a1 ; a2 ; :::; a (n) , em uma certa ordem:
a:a1 a10 (mod n); a:a2 a20 (mod n); :::; a:a (n) a (n0 ) (mod n)

onde a10 ; a20 ; :::; a (n0 ) denotam os inteiros a1 ; a2 ; :::; a (n) em uma certa ordem.
Multiplicando ordenadamente todas essas (n) congruências, obtemos:
(a:a1 ) (a:a2 ):::::(a:a (n) ) a10 a20 ::: a (n0 ) (mod n)

ou seja,
(n)
a (a1 ; a2 ; :::; a (n) ) a1 ; a2 ; :::; a (n) (mod n).

Cada um dos inteiros a1 ; a2 ; :::; a (n) é coprimo com n, de modo que podem
ser sucessivamente cancelados, o que dá a congruência de Euler:
(n)
a 1(mod n).

Nota: se p é um primo, (p) = p 1, e se o mdc(a; p) = 1, então:

(p)
a ap 1 (mod p) 1(mod p)
que nada mais é que uma generalização do Teorema de Fermat.

Corolário 2.32. Se m > 1, k 0, n 0 e a um inteiro qualquer são tais

que, mdc(a; m) = 1 e k n(mod (m)) então, ak an (mod m).
Demonstração: Consideremos o caso em que k > n. Como k n(mod (m))
existe q 1 tal que k n = q (m) e, portanto,
ak = ak n
an = aq (n)
an = (a (n) q
) an an (mod m).

Exemplo 2.12. Sejam a = 5, m = 6, k = 8 e n = 2. Temos (6) = 2;

e 8 2(mod 2). Como 52 1(mod 6), então 58 1(mod 6) e desta forma,
58 52 (mod 6).

35
O Teorema de Euler aplicado em resoluções de congruências lin-
eares A congruência linear a x b(mod m) no caso em que o mdc(a; m) =
1, admite uma única solução módulo m, que se pode facilmente obter usando
o Teorema de Euler. Com efeito, a partir da expressão

a x b(mod m)

obtemos
(m)
a x b a (mod m).
Como mdc(a; m) = 1, podemos cancelar o fator comum a, que resulta em
(m) 1
x b a (mod m):

Nas congruências abaixo encontramos a solução com a aplicação do Teo-

rema de Euler.

Exemplo 2.13. Determinar x na congruência 5 x 7(mod 8):Como

mdc(5; 8) = 1; uma aplicação do argumento acima …ca:
(8) 1
x 7 5 7 54 1
7 53 7 125(mod 8)

x 7 (120 + 5) 7 (8 15 + 5) 7 (0 + 5)(mod 8)
x 7 5 35 3(mod 8)
Note que 3 é o valor procurado , pois 5 3 = 15 7(mod 8):

Em particular, a x 1(mod n) implica em x a (n) 1 (mod n) o que nos

leva a concluir que a (n) 1 é o inverso multiplicativo de a módulo n.

Exemplo 2.14. Determine um inverso multiplicativo de 7 módulo 11. Apli-

cando o teorema de Euler e o fato de mdc(7; 11) = 1, temos x 7 (11) 1
710 1 79 [Link] 8(mod 11) assim, x = 8 é o menor inverso
multiplicativo de 7 módulo 11:

2.4 Sistemas de Congruências Lineares

No livro “Manual Aritmético do Mestre Sol”escrito por Sun Zi Suanjing (ou
Sun Tzu Suan Ching), nos primeiros séculos de nossa era, aparece o seguinte
problema:
“Temos coisas, mas não sabemos quantas; se as contarmos de três em três,
o resto é 2; se as contarmos de cinco em cinco, o resto é 3; se as contarmos
de sete em sete, o resto é 2.

36
 Quantas coisas temos?”
Utilizando congruências para resumir o problema, sendo X a quantidade
de coisas procuradas, temos:
8
< X 2(mod 3)
X 3(mod 5)
:
X 2(mod 7)

Uma maneira de resolução para este sistema será mostrada logo após o
seguinte teorema:
Teorema 2.33. Teorema Chinês do Resto(TCR) . (Restrito a duas
congruências com módulos primos entre si). Sejam m e n inteiros positivos
primos entre si. Se a e b são inteiros quaisquer, então o sistema

x a(mod m)
x b(mod n)

sempre tem solução e qualquer uma de suas soluções pode ser escrita na
forma a + m (m0 (b a) + n t); onde t é um inteiro qualquer e m0 é o
inverso de m módulo n.
Demonstração: Considere o sistema

x a(mod m)
x b(mod n)

onde m e n são inteiros positivos distintos e digamos que o número inteiro

x0 é uma solução desta congruência. Isto signi…ca que x0 satisfaz a ambas as
congruências:
x0 a(mod m)
x0 b(mod n)
Como os módulos são diferentes, só podemos combinar as duas congruências
se convertermos uma delas em uma igualdade de [Link] isto com a
primeira equação, veri…camos que

x0 = a + m k (i)

onde k é um inteiro qualquer, de forma que podemos concluir que

a+m k b(mod n)

ou ainda
m k (b a)(mod n) (ii)

37
Supondo que m e n sejam primos entre si, temos pela Proposição 2.1.2 que
m é inversível módulo n . Digamos que m0 é o inverso de m módulo n ou
m m0 1(mod n). Multiplicando (ii) por m0, obtemos
k m0 (b a)(mod n)
em outras palavras,
k = m0 (b a) + n t
para algum inteiro t. Substituindo esta expressão para k em (i), vemos que
x0 = a + m (m0 (b a) + n t):
Resumindo, provamos que x0 é uma solução do sistema.

Exemplo 2.15. Determinar o menor número inteiro que dividido por 3 tem
resto 2 e dividido por 7 tem resto 3. Devemos determinar um valor x que
satisfaça o sistema de congruências:
x 2(mod 3)
x 3(mod 7)
Chamando m0 o inverso de 3 módulo 7, temos que m0 = 5, visto que 3 5
15 1(mod 7):Pela fórmula do TCR, temos que x0 é uma solução:
x0 = 2 + 3(5(3 2) + 7t)
x0 = 2 + 15 + 21t
x0 = 17 + 21t
Logo x=17 é a menor solução positiva para o problema dado.
Embora tenha sido usado uma parte restrita do TCR o procedimento us-
ado para encontrarmos uma fórmula para x pode ser estendido para sistemas
com mais de duas congruências.
No momento só nos interessa um caso particular de sistemas, vamos
resolvê-los por substituição e utilizando os Teoremas de Fermat e Euler.
Estudaremos apenas sistemas do tipo:
8
>
> X a1 (mod b1 )
<
X a2 (mod b2 )
>
> :::
:
X an (mod bn )
onde mdc(bi ; bj ) = 1, com i = 1; 2; :::n e j = 1; 2; :::n.

38
Exemplo 2.16. Resolveremos o problema proposto no “Manual Aritmético
do Mestre Sol” 8
< X 2(mod 3)
X 3(mod 5)
:
X 2(mod 7)
pois mdc(3; 5) = 1; mdc(3; 7) = 1 e mdc(5; 7) = 1; temos da primeira equação
que existe um inteiro y tal que: X = 3y + 2: Substituindo na segunda
congruência, temos: 3y + 2 3(mod 5); que implica em 3y 1(mod 5);
donde y 3 (5) 1 33 27 2(mod 5); que signi…ca que existe um
K; inteiro, tal que y = 5K + 2:Agora temos: X = 3(5K + 2) + 2 onde
X = 15K + 8:Substituindo na terceira congruência, temos: 15K + 8
2(mod 7); que implica em 15K 6(mod 7); sendo K 6 1(mod 7)
que signi…ca que existe um U; inteiro, tal que K = 7U + 1: Finalmente:
X = 15(7U + 1) + 8 =) X = 105U + 23: Então X = 23 é a menor solução
positiva para este sistema de congruências.

2.5 Congruência e Criptogra…a

Podemos usar congruências, de maneira direta, para codi…car e decodi…car
mensagens. Vamos usar como exemplo a Cifra de César, a Cifra de Trithemius
e a Cifra de Vigenere.
Para todas elas iniciamos com uma troca de letra por número de acordo
com a Tabela 2.4.

Tabela 2.4

2.5.1 Cifra de César

Codi…cação
Sendo i o índice que indica a posição da letra na mensagem, Li o valor da
letra que queremos cifrar e Ci o valor da letra cifrada, temos:

Ci Li + d(mod 26)

39
onde d é o deslocamento utilizado. Usamos mod 26 por ser este o número de
letras do alfabeto latino.
A tabela 2.5 mostra como codi…car a palavra CODIGO com d = 15.
Tabela 2.5

Assim:
CODIGO por está Cifra de César é RDSXVD

Decodi…cação
Para decodi…car, partimos da fórmula inicial Ci Li +d(mod 26), subtraímos
d de ambos os lados da congruência e teremos:
Li = Ci d(mod 26):
Assim a decodi…cação de RDSXVD com d = 15, …ca:
Tabela 2.6

40
 Temos, então:

RDSXVD decodi…cação CODIGO

2.5.2 Cifra de Trithemius

Codi…cação
Na Cifra de César usamos Ci Li + d(mod 26); com d …xo. Na cifra de
Trithemius, como visto no Capítulo 1, o deslocamento não é …xo e sim atre-
lado a posição da letra. Para a primeira letra o deslocamento é zero, para a
segunda é um e assim por diante. Como o deslocamento vale uma unidade a
menos que a posição, temos d = i 1:A fórmula para a cifragem se torna:

Ci Li + i 1(mod 26)

Observe na Tabela 2.7 a codi…cação da expressão: CEU AZUL

Tabela 2.7

Assim:

CEUAZUL por Trithemius CFWDDZR.

Decodi…cação
Usando as propriedades das congruências e somando i 1 a ambos os termos
da expressão temos a fórmula de decodi…cação:

Li = Ci i + 1(mod 26)

41
 Caso a mensagem cifrada fosse CFWDDZR, teríamos:

Tabela 2.8

Assim, temos:

CFWDDZR decodi…cação CEUAZUL.

2.5.3 Cifra de Vigenère

Codi…cação
Vamos codi…car, usando a Cifra de Vigenère, a palavra LEITURA, tendo
como chave a palavra PRIMO. No Capítulo 1 mostramos como fazê-lo usando
o Quadrado de Trithemius. As letras do texto codi…cado são obtidas pelo
cruzamento da linha que inicia com a letra da palavra chave, com a coluna
que inicia com a letra do texto. Este modelo pode ser entendido como uma
Cifra de César com deslocamento variado. Para a Cífra de César temos:
Ci Li + d(mod 26); com d …xo. Podemos a…rmar que o deslocamento de
cada letra da mensagem é dado pelo valor associado à letra da palavra chave.
Sendo Ki o valor da i ésima letra da chave e Li o valor da i ésima letra do
texto, temos que o valor Ci da letra codi…cada é dado por:

Ci Li + Ki (mod 26):

Este método requer uma pré-codi…cação que consiste em substituir as le-

tras, tanto da mensagem como da palavra chave, por seus respectivos valores
de acordo com a Tabela 2.4.
A Tabela 2.9 mostra a maneira como devemos dispor as letras da chave
com a mensagem

42
 Tabela 2.9

enquanto a Tabela 2.10 mostra as letras já substituídas pelos valores da

Tabela 2.4
Tabela 2.10

Neste ponto, utilizamos a Tabela 2.11para codi…car a mensagem

Tabela 2.11

obtendo
LEITURA por Vigenère AVQFIGR.

Decodi…cação
Neste método a decodi…cação também necessita de uma fase preparatória da
mesmo forma que foi feita na codi…cação. Agora usamos Ci para i ésima
letra cifrada e Ki para a i ésima letra da chave. Na Tabela 2.12, temos a
pré decodi…cação.

43
 Tabela 2.12

Para decodi…carmos, devemos determinar o valor de Li a partir de Ci

Li + Ki (mod 26) que foi a fórmula utilizada para codi…car. Se subtrairmos Ki
de ambos os membros da congruência temos, como equação de decodi…cação:
Ci Ki Li (mod 26) ou Li Ci Ki (mod 26): Para evitarmos valores
negativos para Li , incrementamos em 26 o segundo termo da congruência.
Note que esse incremento não altera em nada a expressão visto que 26
0(mod 26): Assim:

Li = 26 + Ci Ki (mod 26):

Na Tabela 2.13, temos a decodi…cação de AVQFIGR

Tabela 2.13

Dessa forma

AVQFIGR decodi…cação LEITURA.

O capítulo a seguir mostra como podemos utilizar congruências para

aplicar um método mais complexo de cifragem.

44
Capítulo 3

A Teoria dos Números e a

Criptogra…a RSA

Neste capítulo trataremos, exclusivamente, da criptogra…a RSA, seu surgi-

mento, a maneira como codi…car e decodi…car mensagens e um exemplo de
cifragem simples utilizando o método, tendo como base[1]

3.1 O método de criptogra…a RSA

A procura por uma forma de criptogra…a que consiga sobrepujar a
capacidade de cálculo do computador ocupou – e ainda ocupa – o tempo
de muitos cientistas, que, mediante isso, anelam pela criação de um sistema
criptográ…co perfeito.
Antes do surgimento dos computadores propriamente ditos, os alemães,
pouco tempo depois da Primeira Guerra Mundial, desenvolveram uma máquina
de criptogra…a que consideravam infalível: a ENIGMA. De fato, ela possuía
um sistema de encriptação di…cílimo de ser decifrado. Isso fez com que os
governos francês, inglês e polonês reunissem esforços para conseguir desven-
dar o processo semiótico do referido aparelho. Tal feito foi alcançado graças,
em parte, ao fato de os aliados terem acesso a algumas máquinas obtidas
antes ou no decorrer da guerra. A equipe de cientistas envolvida no projeto
de decodi…cação era che…ada por Alan Turing, na Inglaterra. Na ocasião,
esse cientista projetou o que hoje é chamado de “Máquina de Turing”, um
dispositivo de tal so…sticação que pode ser considerado um precursor dos
computadores atuais.
Os computadores trouxeram grande avanço à ciência, à comunicação,
ao comércio etc. Porém, embora mais modernos, estavam vulneráveis aos
mesmos perigos veri…cados no uso do telégrafo, ou seja, alguma pessoa mal-

45
intencionada, com o equipamento certo, poderia interceptar mensagens e,
agora, com uma agravante: tinha a seu dispor uma poderosa máquina de
calcular com o potencial de decifrar as mensagens criptografadas.
Essa insegurança perdurou até o …nal do século passado, quando Ronald
Rivest, Adi Shamir e Leonard Adleman criaram a RSA, um dos métodos
de criptogra…a mais seguros de todos os tempos, utilizado por governos e
empresas do mundo inteiro.
Fazendo uma retrospectiva, é interessante observar que, desde as cítalas,
usadas pelos gregos, passando pelos demais sistemas criptográ…cos surgidos
posteriormente, havia, entre todos esses mecanismos, como ponto em comum,
uma chave secreta, na qual residiria a segurança na troca de correspondências.
Entretanto, nos tempos atuais, com a Internet, processos semióticos dessa
natureza seriam inviáveis. Por exemplo, no ato de efetuar uma compra via
computador, o usuário teria que receber, da empresa que organiza a página
virtual, cartas con…denciais que o orientassem acerca de como codi…car os
seus dados. Isto tornaria o comércio eletrônico inviável ou muito restrito, pois
como con…ar na segurança de uma operação mediante a emissão de cartas?
A novidade trazida pelo método RSA é que ele con…gura um sistema de
chave pública, ou seja, opera como uma porta de duas chaves diferentes: a
chave A tranca a porta, mas uma chave diferente (B) a destranca. Então, a
chave A não precisa ser secreta, e a distribuição de cópias dela não comprom-
ete a segurança. Na hipótese de esta porta guardar a entrada da seção segura
da página virtual de uma empresa, esta poderia distribuir livremente a chave
A para qualquer visitante virtual que quisesse enviar uma mensagem segura,
como, por exemplo, o número do cartão de crédito. Embora todos possam
codi…car seus dados usando a mesma chave, ninguém pode ler as mensagens
codi…cadas dos outros.
A chave A é composta por um par de números (n; e), no qual “n” é o
produto de dois números primos muito grandes, e “e”não tem fator comum
com “n”; a chave B é um número “d”, que aprenderemos a encontrar no
decorrer do processo.
A segurança deste método tem suas bases na teoria dos números e é
garantida pela di…culdade de fatoração dos números inteiros quando estes
são muito grandes. Lembremos que, de acordo com o que se estuda no
Ensino Fundamental, fatorar um número é escrevê-lo como um produto de
números primos. Por exemplo: 10 = 2 5 e 42 = 2 3 7. É claro que fatorar
números pequenos é fácil, mas, à medida que eles aumentam, a fatoração vai-
se tornando uma tarefa demorada, visto que não há uma fórmula especí…ca
para fazê-la diretamente.
O processo manual para fatorar um número “n”, dividindo o por números
primos até encontrar um divisor, exige uma quantidade de tentativas que en-

46
 p
volvem os primos “p” de 2 até “p n”. Os números utilizados pelo RSA
são números com mais de 200 algarismos. Como o processo de fatoração com
o uso de computador segue, praticamente, o mesmo princípio do processo
manual –tentativas de divisão –, e os números usados são muito grandes, se-
riam necessários alguns anos de cálculo para o melhor computador do mundo
fatorar um desses números, o que torna o esforço de fazê-lo uma tarefa im-
praticável.
Obviamente, para trabalharmos um exemplo de como criptografar usando
o RSA, não poderemos usar um número absurdamente grande. Então, vamos
utilizar números que podemos manusear com calculadora de bolso.

3.1.1 Descrição do método RSA

Consideramos, para esta explanação, n; e; p e q números inteiros, sendo p e
q primos, n = p q e mdc(n; e) = 1.

Pré-Codi…cação
As mensagens enviadas, geralmente, são textos e o método trabalha com
números. Assim, para podermos utilizá-lo cada letra do alfabeto é colocada
em correspondência biunívoca com um número de dois algarismos. Escol-
hemos um número, também de dois algarismos, diferente dos demais para
representar o espaço entre as palavras. Feito isso, a mensagem se transforma
em um número. Para tanto, podemos substituir as letras de acordo com a
Tabela 3.1.

Tabela 3.1

Esse processo é chamado de pré-codi…cação.

Fazemos cada letra corresponder a um número de, pelo menos, dois al-
garismos para evitarmos confusões. Veja que, se …zéssemos A corresponder
ao número 1, B ao 2, e assim por diante, não teríamos como saber se 12
representa AB ou L, já que esta última é a décima segunda letra do alfabeto.

47
Codi…cação
Feita a pré-codi…cação, obtemos uma sequência de números. Separamos este
número em uma sequência em blocos menores, de forma que o número for-
mado por cada bloco seja menor que n. Denotamos esses blocos por bi , onde
i = 1; 2; :::; k.
O bloco codi…cado, que chamaremos de C(bi ); é o resto da divisão bei por
n, ou C(bi ) é a menor solução positiva da congruência:

bei C(bi )(mod n) (i)

Doravante chamaremos os blocos codi…cados de xi , ou seja xi = C(bi )

para i = 1; 2; :::; k.

Decodi…cação
Para decodi…car a mensagem precisamos encontrar uma relação, ora chamada
D(xi ), tal que D(xi ) bi (mod n). Para tanto, recordemos alguns conceitos
já estudados.
Sendo bi um inteiro , relativamente primo com n, o Teorema de Euler nos
diz que:
(n)
bi 1(mod n) (ii)

Como p e q são primos. Segue, das propriedades da função Totiente de

Euler, que:
(p) = p 1 e (q) = q 1
e, ainda
(n) = (p) (q) = (p 1)(q 1):
Para decifrar a mensagem é necessário encontrar um inteiro d tal que:
e d 1(mod (n)) (iii)
o que implica em
e d 1(mod(p 1)(q 1)) (iv)
que, pelo teorema de Euler, tem como resultado
((p 1)(q 1)) 1
d e (mod(p 1)(q 1)):
Assim, de e d 1(mod (n)) concluímos que existe um inteiro t tal que
e d t (n) + 1 de onde segue que:
(n) t t (n)+1
bi bi 1 bi (1)t bi (bi ) bi (mod n)

48
e
t (n)+1
bi bed
i (bei )d (C(bi ))d (C(bi ))d xdi (mod n).
Portanto
D(xi ) xdi (mod n)
Observe que D(xi ) é a relação inversa de C(bi ):

3.1.2 Um exemplo de mensagem criptografada de

acordo com o método RSA
Vamos codi…car e decodi…car a mensagem SAIA JÁ de acordo com o RSA.
Usaremos como chave pública o par (n; e) = (253; 3):

Pré Codi…cação
Como dito anteriormente as mensagens, geralmente, são textos devemos,
então, achar uma maneira de converter a mensagem em uma sequência de
números.
Faremos isso, desconsiderando o acento agudo, de acordo com a Tabela
3.1, segundo a qual:
SAIA JÁ
torna-se
29111911552011.
Agora quebramos o grande bloco, formado inicialmente, em blocos menores
que n: Para escolher os blocos em que vamos dividir a mensagem devemos
tomar alguns cuidados. Como já foi dito: nenhum bloco deve ser maior que
n e, também, não devemos iniciar um bloco com zero. A explicação para
essa condição será dada após a codi…cação e decodi…cação da mensagem na
qual estamos trabalhando. A mensagem atual pode ser quebrada assim:

29 111 91 155 201 1.

Encerrada a fase de pré-codi…cação podemos passar à etapa de codi…cação

propriamente dita.

49
 Codi…cação A partir dos blocos
Tabela 3.2

vamos denotar o bloco codi…cado por C(bi ).

Como e = 3 a receita que vamos utilizar para calcular C(bi ) é a seguinte:
C(bi ) = resto da divisão de b3i por 253
ou
C(bi ) b3i (mod 253):
Assim, o bloco 29 da mensagem anterior deve ser codi…cado como o resto
da divisão de 293 por 253.
Fazendo as contas, temos:
C(b1 ) 293 24389 101(mod 253) =) C(29) = 101
C(b2 ) 1113 1367631 166(mod 253) =) C(111) = 166
C(b3 ) 913 753571 137(mod 253) =) C(91) = 137
C(b4 ) 1553 3723875 221(mod 253) =) C(155) = 221
C(b5 ) 2013 8120601 60(mod 253) =) C(201) = 60
C(b6 ) 13 1 1(mod 253) =) C(1) = 1
Reunindo os blocos temos a seguinte mensagem codi…cada:
101 166 137 221 60 1
e os blocos codi…cados conforme a Tabela 3.3.
Tabela 3.3

onde xi = C(bi ):
Uma observação importante a ser feita é que não podemos agrupar nova-
mente os números formando um só bloco, pois a decodi…cação da mensagem
está vinculada a cada resto, se eles forem agrupados haveria confusão. Por
exemplo três blocos que originalmente seriam 12 32 25; agrupados, for-
mariam o número 123225 que poderia ser interpretado pelos blocos 132 225
que também são restos possíveis para n = 253:

50
 Decodi…cação Agora vamos decodi…car um bloco da mensagem cod-
i…cada. Veremos de que forma, possuindo a mensagem codi…cada e a chave
secreta, podemos reconstruir a mensagem original.
A informação necessária para decodi…car consiste de dois números: n e o
inverso d > 0 de 3 módulo (p 1)(q 1), onde q e p são os únicos fatores
primos de n. Neste caso: p = 11 e q = 23, visto que 11 23 = 253:
Isto signi…ca que devemos ter;
3 d 1(mod(p 1)(q 1))
3 d 1(mod(11 1) (23 1))
3 d 1(mod 220)
aplicando o resultado
((p 1)(q 1)) 1
d e (mod(p 1)(q 1))

temos
(220) 1
d 3 (mod 220).
Como (220) = (10) (22) = 4 10 = 40, segue que.

d 340 1
339 147(mod 220)

Temos, então, que d = 147 é o menor inteiro positivo que é solução da

congruência dada.
Chamaremos o par (n; d) de chave de decodi…cação. O segredo para
a decodi…cação da mensagem se encontra nestes dois números, portanto,
apenas quem tem a função de receber a mensagem deve possuí-los.
De posse do par (n; d), calculamos D(xi ), onde:

D(xi ) = resto da divisão de xdi por n

em cada bloco para retornarmos ao bloco original.

Aplicando esta fórmula no primeiro bloco da mensagem codi…cada, temos
que D(x1 ) = D(101) é igual ao resto da divisão de 101147 por n = 253.
Efetuamos este cálculo com a ajuda dos Teorema de Fermat e da resolução
de sistemas de congruências.
Calculamos 101147 módulo 11 e 101147 módulo 23 que são os primos em
que n se fatora. Inicialmente, temos:
101 2(mod 11) (i)
101 9(mod 23) (ii).

De (i), temos:
101147 2147 (mod 11).

51
Pelo teorema de Fermat
210 1(mod 11):
Como
147 = 10 14 + 7
segue que

101147 210 14+7 (210 )14 27 114 27 27 7(mod 11) (1)

Da equação (ii), resulta

101147 9147 (mod 23)

ou, sendo 9147 = 3294 ,

101147 3294 (mod 23).
Pelo teorema de Fermat
322 1(mod 23).
Como
294 = 22 13 + 8
segue que

101147 322 13+8 (322 )13 38 113 38 38 6(mod 23) (2)

Chamando 101147 de X; temos, por(1) e (2):

X 7(mod 11)
X 6(mod 23).

Resolvemos este sistema de equações utilizando o algoritmo Chinês dos

Restos, da primeira equação temos que, existe Y 2 Z, tal que:

X = 11Y + 7.

Substituindo X na segunda equação, temos:

11Y + 7 6(mod 23) que resulta em Y 2(mod 23).

Logo, existe K 2 Z, tal que:

Y = 23K + 2.

52
Voltamos à primeira equação e substituímos o valor de Y

X = 11(23K + 2) + 7 =) X = 253K + 29

onde 29 é a menor solução positiva para o sistema e também o bloco inicial

procurado.
Procedendo da mesma maneira podemos decifrar os blocos restantes,
reagrupá-los novamente e assim obter a mensagem inicial.

D(x2 ) = D(166)
Calculamos 166147 módulo 11 e 166147 módulo 23 que são os primos em
que n se fatora. Inicialmente, temos:
166 1(mod 11) (i)
166 5(mod 23) (ii).

De (i), temos:
166147 1147 1(mod 11) (1)
Da equação (ii):
166147 5147 (mod 23).
Pelo teorema de Fermat
522 1(mod 23)
Como
147 = 22 6 + 15
segue que

166147 522 6+15 (522 )6 515 58 57 16 17 19(mod 23) (2)

Chamando 166147 de X; temos, por(1) e (2):

X 1(mod 11)
X 19(mod 23)

Resolvemos este sistema de equações utilizando o algoritmo Chinês dos

Restos: Da primeira equação temos que, existe Y 2 Z, tal que:

X = 11Y + 1

substituindo X na segunda equação, temos:

11Y + 1 19(mod 23) que resulta em Y 10(mod 23)

53
logo, existe K 2 Z, tal que:

Y = 23K + 10

voltamos à primeira equação e substituímos o valor de Y

X = 11(23K + 10) + 1 =) X = 253K + 111

onde 111 é a menor solução positiva para o sistema e também o bloco inicial
procurado.

D(x3 ) = D(137)
Calculamos 137147 módulo 11 e 137147 módulo 23 que são os primos em
que n se fatora. Inicialmente, temos:

137 5(mod 11) (i)

137 1(mod 23) (ii).

De (i), temos:
137147 5147 (mod 11).
Pelo teorema de Fermat
510 1(mod 11).
Como
147 = 10 14 + 7
segue que

137147 510 14+7 (510 )14 57 114 57 57 3(mod 11) (1)

Da equação (ii):
137147 1147 (mod 23)
segue que
137147 1(mod 23) (2)
Disto, chamando 137147 de X; temos, por(1) e (2):

X 3(mod 11)
X 1(mod 23)

54
 Resolvemos este sistema de equações utilizando o algoritmo Chinês dos
Restos: Da primeira equação temos que, existe Y 2 Z, tal que:

X = 11Y + 3.

Substituindo X na segunda equação, temos:

11Y + 7 1(mod 23) que resulta em Y 8(mod 23)

Logo, existe K 2 Z, tal que:

Y = 23K + 8

voltamos à primeira equação e substituímos o valor de Y

X = 11(23K + 8) + 3 =) X = 253K + 91

onde 91 é a menor solução positiva para o sistema e também o bloco inicial

procurado.

D(x4 ) = D(221)
Calculamos 221147 módulo 11 e 221147 módulo 23 que são os primos em
que n se fatora. Inicialmente, temos:

221 1(mod 11) (i)

221 14(mod 23) (ii)

De (i), temos:
221147 1147 1(mod 11) (1)
Da equação (ii):
221147 14147 (mod 23)
ou, sendo 14 9(mod 23) e 9147 = 3294

221147 3294 (mod 23).

Pelo teorema de Fermat

322 1(mod 23):
Como
294 = 22 13 + 8
segue que

221147 322 13+8 (322 13 38 ) (113 38 ) 38 6(mod 23) (2)

55
 Disto, chamando 221147 de X; temos, por(1) e (2):

X 1(mod 11)
X 6(mod 23)

Resolvemos este sistema de equações utilizando o algoritmo Chinês dos

Restos: Da primeira equação temos que, existe Y 2 Z, tal que:

X = 11Y + 1.

Substituindo X na segunda equação, temos:

11Y + 1 6(mod 23) que resulta em Y 14(mod 23):

Logo, existe K 2 Z, tal que:

Y = 23K + 14

voltamos à primeira equação e substituímos o valor de Y

X = 11(23K + 14) + 1 =) X = 253K + 155

onde 155 é a menor solução positiva para o sistema e também o bloco inicial
procurado.

D(x5 ) = D(60)
Calculamos 60147 módulo 11 e 60147 módulo 23 que são os primos em que
n se fatora. Inicialmente, temos:

60 5(mod 11) (i)

60 14(mod 23) (ii).

De (i), temos:
60147 5147 (mod 11).
Pelo teorema de Fermat
510 1(mod 11).
Como
147 = 10 14 + 7
segue que

60147 510 14+7 (510 )14 57 114 57 57 3(mod 11) (1)

56
Da equação (ii), resulta:
60147 14147 (mod 23)
sendo 14 9(mod 23) e 9147 = 3294
60147 3294 (mod 23).
Pelo teorema de Fermat
322 1(mod 23).
Como
294 = 22 13 + 8
segue que
60147 322 13+8 (113 38 ) 38 6(mod 23) (2)
Disto, chamando 101147 de X; temos, por(1) e (2):
X 3(mod 11)
X 6(mod 23)

Resolvemos este sistema de equações utilizando o algoritmo Chinês dos

Restos: Da primeira equação temos que, existe Y 2 Z, tal que:
X = 11Y + 3.
Substituindo X na segunda equação, temos:
11Y + 3 6(mod 23) que resulta em Y 18(mod 23)
Logo, existe K 2 Z, tal que:
Y = 23K + 18
voltamos à primeira equação e substituímos o valor de Y
X = 11(23K + 18) + 3 =) X = 253K + 201
onde 201 é a menor solução positiva para o sistema e também o bloco inicial
procurado.

D(x6 ) = D(1)
Calculamos:
1147 = 1 1(mod 253)
onde 1 é a menor solução positiva para o sistema e também o bloco inicial
procurado.
A Tabela 3.4 resume os resultados da decodi…cação

57
 Tabela 3.4

Agrupando os blocos, formamos novamente o número 29111911552011,

que, de acordo com a convenção da Tabela 3.1, signi…ca SAIA JÁ.
A…rmamos, antes de codi…carmos a mensagem, que um bloco não poderia
iniciar com zero, vamos ver o porquê.
Supondo que "...MAU USO..."seja parte de uma mensagem, codi…cada
segundo as normas da Tabela 3.5.

Tabela 3.5

A pré-codi…cação seria:

:::22103055302[Link]

sendo n = 2173, pode ser separada nos seguintes blocos:

::: 221 030 553 028 245 :::

codi…cada com e = 3;

::: 567 924 825 222 1434 :::

ao ser decodi…cada, …caria

::: 221 30 553 28 245 :::

58
quando agrupamos novamente, temos:

:::221305532[Link]

que, convertido em texto se torna

MD? W?O...

que, é claro, não corresponde à mensagem original.

Assim encerramos nosso capítulo sobre RSA.

59
Capítulo 4

Sugestão de Atividade

Os métodos de criptogra…a apresentados neste trabalho possibilitam uma

série de aplicações em aulas de matemática.
A Cifra de César, ou qualquer outro método de substituição monoal-
fabética, pode ser usada como base para estudo de análise de frequência com
uso de grá…cos em Estatística, bem como em exercícios de probabilidade.
A criptogra…a por transposição, como o próprio nome sugere, pode ser
trabalhado como modelo no estudo de transposição de matrizes.
A criptogra…a RSA, pela …loso…a utilizada, fornece um bom exemplo de
aplicação de relação inversa.
Este capítulo apresenta uma sugestão de atividade, apresentado aqui
como Plano de Aula, a ser desenvolvida no estudo de funções, particular-
mente, no estudo de função inversa. Sugerimos, num primeiro momento, a
revisão do conceito de função inversa., e também das condições necessárias
para que uma função possa ser inversivel.
O Plano de Aula aqui apresentado segue um roteiro semelhante ao método
de criptogra…a RSA, apresentado no Capítulo 3 deste trabalho.
Num primeiro momento, criamos uma tabela, Tabela 4.1, de conversão
onde damos valores numéricos às letras do alfabeto e ao espaço entre palavras.
Utilizamos essa tabela para uma transformação da mensagem escrita em uma
mensagem numérica. A maneira de realizar essa etapa é semelhante à pré
codi…cação feita em RSA, com a diferença que devemos separar cada número
com um espaço. Na prática a pré codi…cação já é uma forma simples de
cifragem.
Realizada a primeira etapa, escolhemos uma função para codi…car a men-
sagem. No RSA utilizamos congruência para realizar o processo. Como con-
gruência não é tópico de estudo do Ensino Médio, devemos utilizar funções
conhecidas dos estudantes. Sugerimos funções de primeiro grau pela facili-
dade do manuseio. A codi…cação é feita calculando a imagem da função em

60
cada valor da mensagem. Podemos fazer isso com o auxílio de uma tabela,
Tabela 4.2.
Para decodi…car, encontramos a função inversa da função usada para
codi…car e calculamos o valor da mesma em cada valor da cifra (Tabela 4.3).
A sequência dos valores da imagem relativos aos valores do código deve ser
a sequência numérica da mensagem original. Isto feito trocamos os números
pelas letras correspondentes da Tabela 4.1.

4.1 Plano de Aula

Dados de Identi…cação:
Escola:
Professor:
Disciplina: Matemática
Série: 1 Ano do Ensino Médio
Turma:
Período:

Tema:
Criptogra…a e uso de Relação Inversa

Objetivo geral:
Aplicar o conceito de função inversa.

Objetivos especí…cos:
- Calcular o valor de uma função em um ponto dado;
- De…nir a função inversa de uma função dada;
- Utilizar uma função e sua inversa como recurso para troca de mensagens
criptografadas.

Conteúdo:
- Função inversa;
- Criptogra…a.

61
Desenvolvimento do tema:Criptogra…a e uso da função inversa
A arte de usar símbolos diferenciados para representar mensagens é quase
tão antiga quanto a própria escrita. Atualmente, esse procedimento recebe o
nome de criptogra…a, termo cuja origem vem do grego kryptós (escondido)
e gráphein (escrita). De modo geral, essa técnica pode ser entendida como
o ato de aplicar um determinado código a …m de manter secreto o conteúdo
de certas informações.
O processo de codi…car e decifrar uma mensagem pode ser entendido como
uma transformação. E é justamente a palavra transformação, de um ponto
de vista intuitivo, que caracteriza o estudo das funções.
Do ponto de vista matemático, veremos a aplicação de uma função –para
cifrar uma mensagem – e sua inversa – para decifrar a mensagem cifrada.
Para tanto é necessário que a função escolhida, seja uma função bijetora,
uma vez que somente estas possibilitam a construção de funções inversas.
Utilizando números e deslocamento podemos criar uma maneira própria
de codi…cação e decodi…cação de mensagens.
Inicialmente faremos algo chamado pré-codi…cação, que consiste em asso-
ciar a cada letra do alfabeto um número, de preferência de dois algarismos,
como mostra a Tabela 4.1.

Tabela 4.1

Por exemplo: Pré codi…camos o texto

O LAPIS

que …ca

25 55 22 11 26 19 29

A partir desta tabela criamos uma relação de substituição que associe a

cada número x, da palavra pré-codi…cada um outro número y, por exemplo

62
 y = 2x 3;
esta relação é a chave de codi…cação pois com ela codi…camos a mensagem.
Com essa chave a mensagem O LAPIS é codi…cada da seguinte forma:
Tabela 4.2

Letra valor(x) cifragem(2x-3) cifra(y)

O 25 2 25 3 47
[ ] 55 2 55 3 107
L 22 2 22 3 41
A 11 2 11 3 19
P 26 2 26 3 49
I 19 2 19 3 35
S 29 2 29 3 55
agora
O LAPIS
se escreve como
47 107 41 19 49 35 55:
Conhecendo a maneira de cifrar podemos então decifrar ou retornar as
letras para a posição original. Para isso usamos uma relação inversa à usada
inicialmente, ou seja, trocamos x e y de posição, assim teremos
x = 2y 3:
Agora o x passa a ser o valor da cifra e o y o valor da letra. Isolando o y
teremos o cálculo que decifra que é
(x + 3)
y=
2
e é chamado de chave de decodi…cação.
Tabela 4.3
cifra(x) decodi…cação( (x+3)
2
) valor(y) Letra
47 (47 + 3) 2 25 O
107 (107 + 3) 2 55 [ ]
41 (41 + 3) 2 22 L
19 (19 + 3) 2 11 A
49 (49 + 3) 2 26 P
35 (35 + 3) 2 19 I
55 (55 + 3) 2 29 S

63
Exercícios
1) Considerando que cada uma das sentenças a seguir é a lei de associação de
uma função bijetora, obtenha a lei de associação da inversa de cada função.
a) y = 3x 5
b) y = 3x4 2
c) y = 3x
x+1
2

2)Combine com um colega uma mensagem a ser codi…cada, a expressão

de codi…cação e, a partir dela, determinem a chave de decodi…cação.
3)Interceptem, de maneira pací…ca, a mensagem de outra dupla e vejam
se é fácil decodi…car.
4)Faça alguma observação sobre esse tipo de cifragem.

Recursos didáticos:
- Quadro;
- Giz;
- Projetor Multimídia.

Avaliação:
A avaliação será feita mediante relatório de aula, participação nas atividades
e apresentação da resolução dos exercícios.

64
 Conclusão

No desenvolvimento deste estudo tivemos a certeza de que os códigos secre-

tos tem prazo de validade, pois sua criação sempre dá origem a uma força
contrária que visa quebrá-los.
Geralmente essa força é formada por cientistas a serviço de países que
estão, de alguma forma, sendo "atacados"pela complexidade do código. Essa
batalha mental entre criptoanalistas, como são chamados os cientistas que
estudam as diferentes formas de criptogra…a, faz com que os métodos devam
ser melhorados a cada instante.
Infelizmente, ou felizmente, a criptologia é uma ciência que desconhece
a paz, visto que não há como garantir por quanto tempo um método crip-
tográ…co será seguro, pois são constantemente atacados, mesmo em tempos
de paz. Governos buscam vigiar pessoas, empresas e também nações por mo-
tivo de segurança e o ataque pode vir de onde menos se espera, prova disso
é o recente escândalo da espionagem dos Estados Unidos sobre as nações
amigas.
No texto, citamos que o RSA é um modelo de criptogra…a usado para
manter a segurança das pessoas que realizam transações comerciais pela in-
ternet e falamos também sobre sua segurança. Convém ressaltar, porém que,
embora o método seja seguro, só a criptogra…a dos dados não garante que
uma pessoa não possa ter seus dados expostos na rede, não por falha na
cifragem dos mesmos e sim por descuido próprio. Atualmente não há neces-
sidade de se subir em postes, com aparelhos de escuta, para interceptar uma
mensagem e interceptá-la criptografada também não é um bom negócio para
a espionagem. Hoje os ataques são mais sutis, os usuários de internet são at-
acados em suas próprias casas, mais especi…camente em seus computadores,
por programas que roubam senhas, embutidos em mensagens, enviadas por
e-mails chamativos, que fazem com que suas senhas sejam lidas antes mesmo
de serem criptografadas. Podemos analisar a criptogra…a como uma chave
para a segurança de nossos dados pessoais, mas não adianta termos a chave
se deixamos a porta aberta.

65
 Convém ressaltar que o método RSA tem uma importância signi…cativa
para a matemática, pois deu uma nova dimensão à Teoria dos Números, que
possuía, antes dele , pouca aplicação prática, mostrando que em matemática,
em alguns casos, podemos ter a solução antes mesmo do problema.
Embora apresente uma série de possibilidades, a criptogra…a é pouco
explorada em atividades escolares, geralmente aparece como desa…os. Isso
é justi…cável pela sua natureza instigadora que desperta a curiosidade do
aluno. Então por que não explorá-la mais?
Mostramos neste trabalho que isto é possível, sem que seja necessário o
uso de cálculos mirabolantes que desestimulam nosso educando. O exemplo
sugerido pode ser aplicado sem que seja necessário abrir um espaço no cur-
rículo só para tratar de criptogra…a, podemos utilizá-la no estudo de funções,
como sugerido, além de matrizes, probabilidade, estatística, propriedade das
potências entre outros.
Devido ao tempo em que foi elaborado, férias escolares, não temos resul-
tado de aplicação em sala de aula. Distribuímos e discutimos as questões
com alguns professores que se mostraram otimistas em relação aos resulta-
dos que podem ser obtidos, tais como: um interesse maior pela disciplina e
esclarecimentos sobre a aplicação da mesma
Como a criptogra…a está atrelada à tecnologia e é cada vez maior o número
de estudantes que tem acesso a ela, boa parte de nossos alunos já possuem,
celulares, smartphones ou tablets, é justi…cável que devam também ter acesso
ao modo como suas mensagens são protegidas.

66
Referências Bibliográ…cas

[1] Coutinho, S. C., Números Inteiros e Criptogra…a RSA, Série de

Computação e Matemática, IMPA, Segunda Edição, 2003.

[2] Fabossi, Tomas Edson Barros, Números In-

teiros e Criptogra…a [Link]ível em:
[Link]
Acesso em:07/12/2013

[3] Fonseca, Rubens Vilhena: Teoria dos Números - Disponível em:

[Link]
UEPA. Acesso: 05/12/2013.

[4] Hefez, Abramo, Elementos de Aritmética, [Link]. Rio de Janeiro: SBM,

2011.

[5] Sautoy, Marcus Du, A música dos números primos: a história de

um problema não resolvido da matemática; tradução, Diego Alfaro.
Rio de Janeiro: Zahar, 2007.

[6] Silva, Elen Viviani Pereira da, Intro-

dução à Criptogra…a RSA. Disponível em:
[Link]
Acesso em:07/12/2013

[7] Tkotz, Viktoria. Iintroduçao à criptogra…a [Link]ível em

[Link] aces-
sado em 20/11/2013

[8] WIKIPÉDIA. Wikipedia, the free encyclopedia. Wikimedia Foun-

dation, Inc. Disponível em: [Link] Acesso: dez. 2013.

[9] Paiva, Manoel [Link]ática: Paiva/ Manoel Rodrigues

Paiva - 2. ed.- São Paulo: Moderna, 2010.

67