Universidade de São Paulo

Instituto de Matemática e Estatı́stica

Bacharelado em Matemática Aplicada e Computacional

Anderson Reis Rosa

Uma Aplicação da Teoria dos Números e

Curvas Elı́pticas à Criptografia

Supervisor: Prof. Dr. Kostiantyn Iusenko

São Paulo
Setembro de 2019
Resumo

A criptografia é uma ferramenta indispensável para proteger informações

em sistemas computacionais, ela também é uma disciplina fascinante pois
cruza diversas áreas de conhecimentos (ciência da computação, matemática,
estatı́stica, engenharia elétrica, fı́sica e teoria da comunicação). Ela tem uma
função fundamental que é encapsular mensagens, por isso, ela tem um papel
imprescindı́vel em uma comunicação minimamente segura.
Apesar de existirem outros fatores que tornam uma comunicação segura,
vamos nos concentrar na encriptação de uma mensagem, embora esta não
impeça a interceptação dos dados que trafegam em um canal de comunicação.
Ela torna o conteúdo da mensagem inelegı́vel para um humano compreender,
portanto, encriptar uma mensagem nos garante a privacidade do conteúdo.
Porém, para garantir um sistema de encriptação confiável, ela precisa ser
implementada de forma correta como a que discutiremos brevemente.
Este trabalho aborda a teoria que muitos sistemas criptográficos moder-
nos utilizam para implementar seus algoritmos. Entraremos em temas estu-
dados em teoria dos números e curvas elı́pticas.
Palavras-chaves: teoria dos números, curvas elı́pticas, criptografia, segu-
rança de dados.

i
Abstract

Encryption is an indispensable tool for protecting information in compu-

tational systems, it is also a fascinating discipline because it crosses several
areas of knowledge (science of computing, mathematics, statistics, electrical
engineering, physics and communication theory). She has one fundamental
function that is to encapsulate messages, so it has a indispensable in a min-
imally secure communication.
Although there are other factors that make communication secure, let
us concentrate on encrypting a message, although this does not prevent the
interception of the data that travels on a communication channel. It makes
the content of the message ineligible for a human to understand, therefore,
to encrypt a message we guarantee the privacy of the content. However, to
ensure a system that encryption, it must be implemented in the correct way
we will discuss briefly.
This work addresses the theory that many modern cryptographic systems
use to implement their algorithms. We will studied in number theory and
elliptic curves.
Keywords: number theory, elliptical curves, encryption, data security.

ii
Sumário

1 Introdução 1
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . 6

2 Conceitos de Criptografia 7
2.1 Breve história da criptografia . . . . . . . . . . . . . . . . . . 7
2.2 Segurança na Comunicação . . . . . . . . . . . . . . . . . . . 11
2.3 Dois métodos para trocar informações . . . . . . . . . . . . . . 12
2.3.1 Criptografia Simétrica . . . . . . . . . . . . . . . . . . 13
2.3.2 Criptografia Assimétrica . . . . . . . . . . . . . . . . . 14
2.3.3 Simétrica Vs Assimétrica . . . . . . . . . . . . . . . . . 16
2.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Fundamentos em Teoria dos Números 19

3.1 Divisibilidade e Algoritmo de Divisão . . . . . . . . . . . . . . 20
3.1.1 Princı́pio da Boa Ordem . . . . . . . . . . . . . . . . . 20
3.1.2 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.3 Algoritmo da Divisão . . . . . . . . . . . . . . . . . . . 21
3.2 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . 26

iii
SUMÁRIO iv

3.3 Aritmética Modular . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4 Teorema Fundamental da Aritmética . . . . . . . . . . . . . . 46
3.5 Teorema Chinês do Resto . . . . . . . . . . . . . . . . . . . . 51
3.6 Teorema de Fermat e Euler . . . . . . . . . . . . . . . . . . . 52
3.6.1 Teorema de Euler . . . . . . . . . . . . . . . . . . . . . 55
3.6.2 Teorema de Fermat . . . . . . . . . . . . . . . . . . . . 55
3.7 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4 Grupos, Anéis e Corpos 59

4.1 Grupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Anéis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3 Corpos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.3.1 Corpos Finitos da forma GF (p) . . . . . . . . . . . . . 62
4.3.2 Corpos Finitos da Forma GF (2n ) . . . . . . . . . . . . 65
4.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5 Curvas Elı́pticas 80
5.1 Curvas Elı́pticas sobre R . . . . . . . . . . . . . . . . . . . . . 82
5.2 Curvas Elı́pticas sobre Zp . . . . . . . . . . . . . . . . . . . . 86
5.3 Curvas Elı́pticas sobre GF (2m ) . . . . . . . . . . . . . . . . . 91
5.4 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

6 Aplicação à Criptografia 96
6.1 Criptografia de Curva Elı́ptica . . . . . . . . . . . . . . . . . . 97
6.2 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

7 Conclusão 104
Lista de Figuras

1.1 Exemplo de curva elı́ptica y 2 = x3 − x + 1 . . . . . . . . . . . 4

2.1 Criptografia Simétrica . . . . . . . . . . . . . . . . . . . . . . 14

2.2 Criptografia Assimétrica . . . . . . . . . . . . . . . . . . . . . 15

5.1 Exemplos de curvas elı́pticas . . . . . . . . . . . . . . . . . . . 83

5.2 A curva elı́ptica E23 (1, 1) . . . . . . . . . . . . . . . . . . . . . 89
5.3 A Curva Elı́ptica E24 (g 4 , 1) . . . . . . . . . . . . . . . . . . . . 93

v
Lista de Tabelas

3.1 Aritmética Módulo 8. . . . . . . . . . . . . . . . . . . . . . . 36

3.2 Aritmética com as classe de resı́duos módulo 6. . . . . . . . . 39
3.3 Propriedades da aritmética modular para inteiros em Zm . . . . 41
3.4 Exemplo do Algoritmo Eucledeano Estendido. . . . . . . . . . 46
3.5 Alguns valores da Função Totient de Euler ϕ(n). . . . . . . . 55

4.1 Aritmética em GF (7). . . . . . . . . . . . . . . . . . . . . . . 64

4.2 Aritmética em GF (23 ). . . . . . . . . . . . . . . . . . . . . . 68
4.3 Aritmética Polinomial Modular x3 + x + 1. . . . . . . . . . . 71
4.4 Euclides Estendido [(x8 + x4 + x3 + x + 1), (x7 + x + 1)] . . . 73
4.5 Gerador de GF (23 ) usando x3 + x + 1 . . . . . . . . . . . . . 77
4.6 GF (23 ) Aritmética usando geradores para o polinômio (x3 +
x + 1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.1 Pontos da curva elı́ptica E23 (1, 1) . . . . . . . . . . . . . . . . 88

5.2 Pontos na Curva Elı́ptica E24 (g 4 , 1) . . . . . . . . . . . . . . . 92

6.1 CCE troca de chaves . . . . . . . . . . . . . . . . . . . . . . . 99

6.2 Tamanho de chaves comparáveis em termos de esforço com-
putacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

vi
Capı́tulo 1

Introdução

1.1 Motivação
O matemático alemão Johann Carl Friedrich Gauss (1777−1855) disse: “A
matemática é a rainha das ciências, e a teoria dos números é a rainha da ma-
temática” [14], este (teoria dos números) é um ramo da matemática pura de-
dicado ao estudo das propriedades dos números. Vamos abordar sua aplicação
na computação, por exemplo, na criptografia.
Cabe aqui uma curiosidade da origem da expressão teoria dos números.
O termo mais antigo para se referir a ele é aritmética. No inı́cio do século
XX, ele foi substituı́do por “teoria dos números” (a palavra “aritmética”,
usada pelo público em geral para significar “cálculos elementares”, também
adquiriu outros significados na lógica matemática, como na aritmética de
Peano, e na ciência da computação, como na aritmética de ponto flutuante).
Uma das primeiras obras a compilar resultados aritméticos na história
da matemática foi o livro Arithmetica, de Diofanto de Alexandria (nascido
entre 201 e 214 — falecido entre 284 e 298). Neste livro, ele trabalha com uma
série de problemas cuja resolução busca as soluções racionais para sistemas de

1
CAPÍTULO 1. INTRODUÇÃO 2

equações polinomiais, geralmente com o padrão f (x, y) = z 2 ou f (x, y, z) =

w2 . Por este motivo, equações polinomiais onde se propõe encontrar soluções
racionais ou inteiras são hoje conhecidas como Equações Diofantinas.
Pode-se dizer que Diofanto estudava pontos racionais (ou seja, pontos cu-
jas coordenadas são racionais em curvas e variedades algébricas); entretanto,
ao contrário dos gregos do perı́odo clássico, que faziam o que agora conhece-
mos como álgebra básica em termos geométricos, Diofanto fazia o que cha-
mamos de geometria algébrica básica em termos puramente algébricos. Em
uma linguagem moderna, o trabalho de Diofanto encontrava parametrizações
racionais de variedades, isto é, dada uma equação, por exemplo, seguindo o
padrão f (x1 , x2 , x3 ) = 0, seu objetivo (em essência) era encontrar três funções
racionais g1 , g2 e g3 tais que, para todos os valores de r e s, de x1 = g1 (r, s),
x2 = g2 (r, s) e x3 = g3 (r, s) sejam uma solução de f (x1 , x2 , x3 ) = 0.
Diofanto também estudou as equações de algumas curvas não-racionais
(para as quais nenhuma parametrização racional é possı́vel) e, neste caso,
ele conseguiu encontrar alguns pontos racionais sobre essas curvas (o que
parece ser a primeira ocorrência das curvas elı́pticas) por meio de uma cons-
trução (não-geométrica) equivalente a traçar uma tangente à curva E em um
ponto racional P conhecido e encontrar o outro ponto de intersecção entre a
tangente e a curva.
O problema central da geometria diofantina era determinar se uma equação
diofantina tinha soluções e quantas eram. A abordagem adotada foi pensar
nas soluções de uma equação como um objeto geométrico.
Por exemplo, uma equação em duas variáveis define uma curva no plano.
Mais geralmente, uma equação, ou sistema de equações, em duas ou mais
variáveis define uma curva, uma superfı́cie ou algum outro objeto no espaço
n-dimensional. Na geometria diofantina, pergunta-se se existem pontos ra-
CAPÍTULO 1. INTRODUÇÃO 3

cionais (pontos cujas coordenadas são racionais) ou pontos inteiros (pontos

cujas coordenadas são inteiras) na curva ou na superfı́cie. Se houver algum
desses pontos, o próximo passo é perguntar quantos existem e como são dis-
tribuı́dos. Duas questões básicas nessa direção é: há uma quantidade finita
ou infinita de pontos racionais em uma dada curva (ou superfı́cie)? E quanto
aos pontos inteiros?
Um exemplo aqui pode ser útil. Considere a equação de Pitágoras x2 +
y 2 = 1; gostarı́amos de estudar suas soluções racionais, isto é, suas soluções
(x, y) tais que x e y são ambos racionais. Isto é o mesmo que pedir por todas
as soluções inteiras para a2 +b2 = c2 , pois qualquer solução da última equação
nos dá como resultado x = a/c, y = b/c para a primeira. É também o mesmo
que pedir todos os pontos com coordenadas racionais na curva descrita por
x2 + y 2 = 1. (Esta curva é um cı́rculo de raio 1 em torno da origem.)
Este exemplo ilustra a importância do trabalho de Diofanto de Alexandria
em seu livro, Arithmetica. Para determinar se uma equação diofantina tinha
soluções e quantas eram, a estratégia adotada por ele era pensar nas soluções
de uma equação como um objeto geométrico, por exemplo, curvas elı́pticas.
Cabe aqui sinalizar que as curvas elı́pticas são especialmente relevantes na
teoria dos números e constituem uma área importante da pesquisa acadêmica
atual; por exemplo, elas também foram usadas na prova, por Andrew Wi-
les [20], do último Teorema de Fermat, elas também podem ser usadas em
criptografia, a Criptografia de Curvas Elı́pticas (CCE), que é uma apro-
ximação para criptografia de chaves públicas com base na estrutura algébrica
de curvas elı́pticas sobre corpos finitos. Neste trabalho vamos nos concentrar
nesta aplicação das curvas elı́pticas e também nos fundamentos de teoria dos
números e das curvas elı́pticas, por este motivo, apesar da abordagem con-
ceitual dos últimos parágrafos, para prosseguir no trabalho, será necessário
CAPÍTULO 1. INTRODUÇÃO 4

uma definição forma, que faremos a seguir.

Uma curva elı́ptica é uma curva algébrica plana definida por uma equação
da forma y 2 = x3 + ax + b, e não singular; isto é, que não possui singularidade
ou auto-interseções, por exemplo, seja a = −1, b = 1, então temos a seguinte
curva elı́ptica:

y E
4

2
P
x
−6 −4 −2 O 2 4 6

−2

−4

Figura 1.1: Exemplo de curva elı́ptica y 2 = x3 − x + 1

Se y 2 = f (x), onde f é qualquer polinômio de grau três em x sem raı́zes

repetidas, o conjunto solução é uma curva plana não-singular, uma curva
elı́ptica. Se f tem grau quatro e é livre de quadratura, esta equação descreve
novamente uma curva plana; no entanto, não tem escolha natural de ele-
mento identidade. Mais genericamente, qualquer curva algébrica, por exem-
plo, a curva obtida a partir da intersecção de duas superfı́cies quadráticas
embutidas no espaço projetivo tridimensional, é chamada de curva elı́ptica,
desde que tenha pelo menos um ponto racional para atuar como a identidade.
CAPÍTULO 1. INTRODUÇÃO 5

1.2 Objetivos
Buscaremos abordar conceitos relacionados à Criptografia de Curvas Elı́pticas
e estudar o algoritmo utilizado para gerar chaves públicas baseadas na es-
trutura algébrica de curvas elı́pticas sobre corpos finitos. Esta criptografia
requer chaves menores em comparação com a criptografia não-CCE (com
base em corpos de Galois simples) para fornecer uma segurança equivalente.
As possibilidades de aplicação das curvas elı́pticas a criptografia são várias,
como por exemplo, para assinaturas digitais e geradores pseudo-aleatórios.
Indiretamente, elas também podem ser usadas para encriptação, combinando
a chave pública com um algoritmo de chave simétrica.
Provavelmente, o termo criptografia é conhecido pelo leitor devido a sua
utilização nos mais variados contextos. Geralmente, o termo criptografia se
refere aos processos matemáticos de tornar uma mensagem impossı́vel de ser
lida, a não ser pela pessoa que tem a chave para “desencriptar”, fazendo com
que o texto se torne legı́vel novamente.
A criptografia se expandiu para além de simples mensagens secretas; hoje,
você pode usar a criptografia para propósitos mais elaborados, como, por
exemplo, para identificar o autor das mensagens.
A criptografia é a melhor tecnologia que nós temos para proteger in-
formações, por exemplo, bancos online usam esta técnica para “esconder” os
dados de seus usuários de terceiros, e provedores de serviços de internet fazem
o mesmo, aliás, estes serviços não conseguiriam garantir o mı́nimo de segu-
rança para os dados dos seus usuários sem a criptografia. Ela se desenvolveu
de tal maneira que é praticamente impossı́vel quebrar o código − quando
utilizada de forma correta.
CAPÍTULO 1. INTRODUÇÃO 6

1.3 Organização do texto

O restante desta monografia está organizado da seguinte forma. O capı́tulo 2
apresenta um pouco sobre a trilha histórica da criptografia e também os con-
ceitos fundamentais sobre criptografia simétrica e assimétrica. O capı́tulo 3 e
capı́tulo 4 descrevem os fundamentos de teoria dos números, que servem de
base para compreender os conceitos de criptografia moderna. O capı́tulo 5
descreve o conceito de curvas elı́pticas. Por fim, falamos no capı́tulo 6 sobre
a aplicação dos conceitos apresentados nos capı́tulos anteriores à CCE.
Capı́tulo 2

Conceitos de Criptografia

Neste capı́tulo, apresentamos conceitos fundamentais da criptografia e suas

aplicações. Tendo isto em mente, esta parte discute brevemente a história
da criptografia, abordando desde seus primórdios até algumas das avançadas
técnicas existentes atualmente. Sendo assim, deve ficar claro para o leitor
a diferença entre criptografia simétrica e assimétrica, também como a
forma pela qual a utilização destas técnicas é capaz de garantir o estabe-
lecimento de uma comunicação segura, este capı́tulo foi retirado quase que,
literalmente, da dissertação de mestrado de Marcos Simplicio [8] embora te-
nham sido feitas melhorias e ajustes necessários conforme o trabalho de David
Kahn (1996) [11].

2.1 Breve história da criptografia

A história da criptografia está intimamente ligada à da escrita. Os primeiros
traços de sua utilização datam de 2000 A.C., no Egito. Durante séculos, a
criptografia se baseou em dois grandes princı́pios de cifras:

7
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 8

• Substituição: Em um alfabeto, pode-se trocar um conjunto de letras

entre si. O mais famoso exemplo desta técnica de codificação é, pro-
vavelmente, o alfabeto de César, que consiste na substituição de cada
letra de um alfabeto, por exemplo o alfabeto latino, pela i-ésima le-
tra em um alfabeto cı́clico (a letra “x” sendo seguida pela letra “y”,
esta sendo seguida pela letra “z’, então retornando para “a”), ou seja,
substituı́mos a letra “d” por “a” do alfabeto cı́clico, “e” deste mesmo
alfabeto por “b” e assim por diante, chegando até a substituição de
“a” por “x”, “b” por “y” e “c” por “z”, havendo assim um número de
possibilidades de substituições igual ao número de letras do alfabeto
cı́clico, por esta razão ele é chamado de alfabeto de César e chamá-lo
cifra de César é um erro, porque para ser considerada uma cifra, a troca
entre as letras precisa ser feita de maneira aleatória e não dependendo
da sequência alfabética. Um aprimoramento do alfabeto de César é a
cifra de Vigenère (do século XVI, Roma), que consiste na separação
do alfabeto em n conjuntos, cada um utilizando uma chave diferente.
Desta maneira, cada conjunto respeita uma chave de substituição. Por
exemplo, definimos duas chaves K1 e K2 , as letras localizadas em uma
posição ı́mpar do alfabeto serão enviadas para K1 posições adiante,
enquanto que a chave K2 será utilizada para as demais.

Saindo do perı́odo renascentista, entrando no século XIV, temos a

criação das máquinas de rotores que utilizam a técnica de substituição,
como por exemplo, a máquina de Herbern (utilizando apenas um rotor)
e a máquina Enigma, criada pela força militar alemã.
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 9

• Permutação: modifica-se a ordem das letras do texto claro, ou seja,

que possa ser compreendido por um humano. O mais antigo exemplo de
utilização desta técnica é atribuı́do aos Espartanos, na antiga Grécia,
1
que utilizavam-se de um bastão conhecido pelo nome de scytale ou
skytale. O processo de codificação consistia em enrolar uma faixa de
pergaminho no skytale, escrevendo então a mensagem clara sobre este
pergaminho. Para decifrar o texto, basta enrolar a faixa em um ou-
tro skytale de mesmo tamanho, alinhando o texto de forma a torná-lo
legı́vel.

Hoje, no contexto dos documentos digitais, as “palavras” de uma mensa-

gem foram substituı́das pelos seus bits ou bytes. Entretanto, as técnicas de
substituição e permutação continuam válidas perfeitamente.
Além desta breve explicação sobre estes dois conceitos (substituição e
permutação), cabe aqui destacar como o trabalho Communication Theory of
Secrecy Systems de Claude Shannon (1949) [17] foi importante na área da
Teoria da Informação.
Ele enuncia neste trabalho o que hoje é chamado de Segredo Perfeito:
a probabilidade de se obter um texto claro a partir de quaisquer conjuntos
de textos cifrados deve ser a mesma, ou seja, a dificuldade de se obter textos
claros deve ser independente do número de textos cifrados de que dispõe
um atacante. Ele também mostra que a combinação da mensagem original
com uma chave completamente aleatória de mesmo tamanho satisfaz este
requisito, resultado em uma cifra de segurança máxima, denominada One-
Time Pad. No entanto, como as chaves somente podem ser utilizadas uma
única vez e são potencialmente grandes, a utilização de tal cifra na maioria
1
Em criptografia, scytale é uma ferramenta usada para executar uma cifra de trans-
posição, consistindo de um cilindro com uma tira de pergaminho enrolada em torno dele
sobre a qual está escrita uma mensagem.
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 10

das aplicações práticas é inviável.

Com trabalhos cientı́ficos como este de Shannon e também com o desen-
volvimento dos computadores e de redes de telecomunicação ao longo das
últimas décadas, a criptografia deixou de ser restrita aos meios diplomático
e militar, permitindo a criação de diversas cifras e também maneiras de ata-
ques às mesmas. É desta forma que, em 1975, foi promovido um concurso
semi-público para a escolha de um padrão criptográfico destinado a aplicações
civis. O vencedor do concurso foi um algoritmo proposto pela IBM e alterado
pela Agência de Segurança Nacional americana (Natinal Security Agency −
NSA) segundo critério não divulgados na época, dando origem ao Data En-
cryption Standard − DES (NIST, 1977) [7]. O projeto da cifra baseia-se na
chamada Estrutura de Feistel, sendo efetivamente adotado como padrão de
codificação pelo governo americano em 1977. Porém, o DES é atualmente
considerado obsoleto, principalmente, pelo seu reduzido tamanho de chave
(56 bits), pouco segura se considerada a capacidade computacional disponı́vel
atualmente, e pelo seu pequeno tamanho de bloco (64 bits), que pode facilitar
ataques futuros.
Apesar de o DES ter sido, definitivamente, aposentado pelo Instituto Na-
cional de Padrões e Tecnologia Americano (Nacional Institute of Standard
and Technology − NIST) em 2004, foi criada uma solução paliativa para apro-
veitar a ampla base existente de implementações desta cifra em hardware e
software, conhecida como 3-DES (ou DES Triplo). Ele consiste em efetuar por
3 vezes a codificação usando DES simples, com 3 chaves distintas de 56 bits,
K1 , K2 e K3 resultando em uma segurança, aproximadamente, equivalente à
de uma cifra de 112 bits. Existe ainda uma variante bastante popular que con-
siste em utilizar a chave K2 com o algoritmo de decodificação, de forma que
o 3-DES executa a sequência codificação-decodificação-codificação (CDC).
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 11

Apesar de esta construção não ser diferente em termos de segurança, ela é

interessante pela possibilidade de simular o DES simples usando o 3-DES
com 3 chaves.
O padrão de codificação atual foi definido em outubro do ano 2000, após
um novo concurso (desta vez verdadeiramente público) patrocinado pelo
NIST, que teve inı́cio oficial em junho de 1997. Dentre os 5 finalistas, o algo-
ritmo Rijindael (Daemen; Rijmen, 2002) [3], desenvolvido pelos criptógrafos
belgas Joan Daemen e Vincent Rijmen, foi escolhido como o Advanced En-
cryption Standard − AES (NIST, 2001) [19]. O Rijindael foi desenvolvido
a partir de um outro algoritmo chamado de SQUARE (Daemen; Knudsen;
Rijmen, 1997).

2.2 Segurança na Comunicação

O termo Criptografia (do grego: kryptós,“esconder”, e gráphein, “escrever”)
é, historicamente, associado à arte de “esconder informações” ou “encapsular
informação”, termo que pode ser interpretado como a capacidade de fornecer
confidencialidade à informação.
Resumidamente, pode-se então definir um algoritmo criptográfico (ou ci-
fra) como uma função reversı́vel que transforma textos claros (também
denominados mensagens claras) P em textos cifrados (ou mensagens
cifradas) C e vice-versa, utilizando, no processo, uma ou mais chaves crip-
tográficas K.
Portanto, supondo que duas pessoas estão trocando textos, se Alice quer
enviar uma mensagem a Bob (seguindo a tradição de nomes, frequentemente,
adotados no universo da Criptografia) de forma segura, mesmo que o canal
de comunicação usado seja, caracteristicamente, inseguro como é o caso da
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 12

Internet, ela irá codificar sua mensagem usando uma função de codificação
E e uma chave de codificação (Ke ).
Para ser capaz de decifrar e, portanto, de ler a mensagem de Alice, Bob irá
utilizar uma função de decodificação D e também uma chave de decodificação
(Kd ). Um terceiro indivı́duo que não tenha acesso a estas chaves deve então
ser incapaz de espreitar o diálogo.
Apesar da confidencialidade ser uma das principais áreas de aplicação da
criptografia, atualmente, esta apresenta um campo mais amplo, respondendo
às seguintes necessidades:

• Confidencialidade: garantir que as mensagens trocadas poderão ser

compreendidas somente pelos usuários desejados, de tal forma que ape-
nas eles sejam capazes de extrair a informação nela contida.

• Integridade: possibilidade de verificar a consistência da informação

contida em uma mensagem. Tal serviço não garante que as mensagens
não sejam alteradas durante a transmissão, mas sim que a ocorrência
da alteração possa ser detectada.

• Autenticação: possibilidade de comprovar a identidade de um in-

divı́duo que participa da comunicação.

• Irretratabilidade: garantia de que nem o remetente nem o desti-

natário de uma determinada mensagem possam negar sua transmissão,
recepção ou posse.

2.3 Dois métodos para trocar informações

Formalmente, os processos de codificação e decodificação podem ser definidos
da seguinte forma: Seja P um conjunto de textos claros, C um conjunto de
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 13

textos cifrados e K um conjunto de chaves. Uma função de codificação E

associa a cada par (P, Ke ) ∈ P × K um elemento C = E(P, Ke ) ∈ C, para
obtermos a mensagens claras novamente usamos a função de decodificação
D, de forma que D(E(P, Ke ), Kd ) = P .

2.3.1 Criptografia Simétrica

Até o ano de 1976, a única forma conhecida de criptografia era a criptografia

de chave secreta ou criptografia simétrica: para que dois indivı́duos
pudessem se comunicar de forma segura, ambos precisavam compartilhar
uma mesma chave secreta para codificação e decodificação, conhecida apenas
por eles. Isto gerava problemas, principalmente, com relação à distribuição
destas chaves, que precisavam ser trocadas através de um meio seguro antes
que fosse possı́vel utilizar qualquer forma de criptografia. Portanto, se Alice e
Bob decidem utilizar um esquema de codificação simétrica para se comunicar,
eles devem partilhar uma mesma chave K, conhecida apenas por eles, pelo
menos na teoria porque estamos descartando a possibilidade de um terceiro
indivı́duo ter acesso a estas chaves. Esta chave será usada tanto na operação
de codificação quanto decodificação, ou seja, Ke = Kd = K. A figura 2.1
2
ilustra o processo.
2
PAlice é a mensagem clara de Alice e PBob é a mensagem clara para Bob. Além disso,
C é mensagem cifrada, EAlice é função de codificação do texto (ou mensagem) de Alice e
DBob é a função de decodificação do texto de Alice por Bob.
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 14

PAlice EAlice C DBob PBob

Ke K Kd

Figura 2.1: Criptografia Simétrica

O AES e o DES são dois exemplos de algoritmos que adotam o esquema

de criptografia simétrica.

2.3.2 Criptografia Assimétrica

Apesar de algumas fontes (Williamson, 1976) [9] alegarem que este tipo de
criptografia já era conhecido no meio militar, foi apenas em 1976 que os
criptógrafos ingleses Diffie e Hellman (Diffie; Hellman, 1976) [4] apresentaram
ao meio civil o esquema conhecido como criptografia assimétrica (ou
criptografia de chave pública).
Sua utilização permite que indivı́duos estabeleçam uma comunicação se-
gura sem a necessidade de um compartilhamento prévio de chave criptográfica
simétrica.
Portanto, são usadas duas chaves diferentes para codificação e decodi-
ficação: uma chave pública Ku e sua correspondente chave privada Kr . Quando
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 15

Alice deseja enviar uma mensagem confidencial P a Bob, ela deve codificar
a mensagem usando a chave pública de Bob, que pode ser encontrada aber-
tamente na Internet ou junto a uma entidade com esta atribuição (Entidade
Certificadora), por exemplo. Desta forma, é gerada uma mensagem cifrada
C que apenas Bob é capaz de decifrar, posto que ele é o único que conhece
3
sua chave privada. A figura 2.2 ilustra este processo.

Eve

PAlice EAlice C DBob PBob

Ku(Bob) K Kr(Bob)

Figura 2.2: Criptografia Assimétrica

Um dos exemplos mais conhecidos deste tipo de cifra é o algoritmo RSA

(Rivest, Shamir, Adelmen; 1977) [19], cuja segurança baseia-se na dificuldade
computacional de se fatorar números grandes.
3
PAlice é a mensagem clara de Alice e PBob é a mensagem clara para Bob. Além disso,
C é mensagem cifrada, EAlice é função de codificação do texto (ou mensagem) de Alice
e DBob é a função de decodificação do texto de Alice por Bob. Quando Alice assina uma
mensagem usando sua chave privada, Bob pode ter certeza que é com ela (e não com Eve,
por exemplo), que ele está iniciando uma conversa.
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 16

2.3.3 Simétrica Vs Assimétrica

Existe um grande interesse na utilização de criptografia de chave pública, pela

sua capacidade de prover diversas funcionalidades essenciais no domı́nio da
segurança da informação. Dentre as suas aplicações, destacam-se: assinatura
digital, autenticação de usuários e distribuição de chaves.
Uma assinatura digital é uma forma de comprovar a autoria de uma
mensagem ou documento. Sucintamente, o procedimento para sua geração
consiste no cálculo de um resumo criptográfico de tamanho fixo (também
conhecido como hash) da mensagem que se deseja assinar. Isto pode ser feito
utilizando, por exemplo, uma função da famı́lia SHA (NIST, 2002) [1].
O hash é então codificado com a chave privada do autor da mensagem. O
resultado é a assinatura digital da mesma: como apenas este indivı́duo tem
acesso à sua chave privada, apenas ele seria capaz de criar tal assinatura,
que pode se verificar por meio da sua chave pública. Assim, caso Bob receba
uma mensagem supostamente assinada por Alice, ele pode decodificá-la com
a chave pública de Alice e comparar o resultado com o hash da mensagem
recebida.
Caso os mesmos sejam idênticos, pode-se concluir que aquele documento
foi realmente assinado por Alice; caso contrário, é possı́vel que a assinatura
não pertença a Alice (por exemplo, Eve pode tê-lo assinado) ou que o docu-
mento foi alterado na transmissão (acidental ou intencionalmente). O fato do
hash da mensagem ser assinado ao invés da mensagem completa está relaci-
onado a questões de desempenho: não importando o tamanho da mensagem,
a codificação se dá sobre dados de tamanho fixo e arbitrariamente pequeno.
O processo de autenticação é muito semelhante à assinatura digital, porém,
possui uma sutil (e importante) diferença: enquanto a assinatura digital prova
que um documento pertence a uma determinada pessoa, mesmo muito tempo
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 17

após a geração do mesmo, o processo de autenticação visa à identificação dos

interlocutores antes do inı́cio da comunicação. Desta forma, quando Alice
assina uma mensagem usando sua chave privada, Bob pode ter certeza que é
com ela (e não com Eve, por exemplo), que ele está iniciando uma conversa.
Por fim, o compartilhamento das chaves simétricas pode ser feito por
Alice e Bob sem a necessidade de uma canal de comunicação seguro: basta
Alice enviar para Bob uma mensagem contendo a chave simétrica desejada,
codificada com um algoritmo assimétrico e a chave pública de Bob. Desta
forma, Bob será o único capaz de recuperar a chave simétrica enviada por
Alice.
A razão pela qual o próprio algoritmo de chave pública não é utilizado
durante toda a comunicação é simples: desempenho. É uma fato conhecido
que algoritmos assimétricos apresentam um desempenho bem inferior àquele
dos algoritmos simétricos.
O RSA, por exemplo, é de 100 a 1000 vezes mais lento do que o DES
e usa chaves bem maiores, sendo 1024 bits um tamanho bastante comum.
Portanto, após as fases iniciais de comunicação usando algoritmos de chave
pública, os pares comunicantes, geralmente, passam a utilizar um algoritmo
simétrico com a chave compartilhada.
CAPÍTULO 2. CONCEITOS DE CRIPTOGRAFIA 18

2.4 Resumo
Este capı́tulo abordou alguns dos conceitos mais básicos e essenciais relativos
à área de estudo da criptografia, além de um breve histórico foram enume-
rados os serviços básicos aos quais a mesma se presta: confidencialidade,
integridade, autenticação e irretrabilidade. Foi ainda explicada a dife-
rença entre criptografia simétrica e assimétrica, e como as mesmas são
utilizadas.
Capı́tulo 3

Fundamentos em Teoria dos

Números

Neste capı́tulo e no próximo apresentamos alguns conceitos fundamentais de

teoria dos números, mais especificamente, falaremos sobre divisibilidade e al-
goritmo de divisão, algoritmo de euclides, aritmética modular, e no próximo
capı́tulo falaremos sobre grupos, anéis e corpos, temas usados para compre-
ender cifras simétricas, além disso, falaremos sobre teorema fundamental
da aritmética, Fermat, Euler e Chinês do Resto, temas fundamentais para
entender cifras assimétricas.
O leitor deve conhecer estes assuntos para se aprofundar no trabalho,
mais detalhes podem ser encontrados nos livros “Understanding Crypto-
graphy” [5], “Cryptography and Network Security” [18], “A Course in Num-
ber Theory and Cryptography” [13] e “Números: Uma Introdução à Ma-
temática” [15].

19
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 20

3.1 Divisibilidade e Algoritmo de Divisão

Vamos abordar algumas propriedades, definições e teoremas para explicar os
conceitos de divisibilidade e algoritmo de divisão.

3.1.1 Princı́pio da Boa Ordem

Todo subconjunto não vazio S ∈ Z de elementos não-negativos possui ele-

mento minimal, isto é, o elemento x ∈ S tal que para todo y ∈ S temos que
x ≤ y.

3.1.2 Divisibilidade

Uma equação do tipo a = xb pode ou não ter solução em Z = {. . . , −2, −1, 0, 1, 2, . . .};
isto dependerá dos coeficientes a e b da equação. Quando tal solução existe,
diz-se que a é divisı́vel por b. Mais precisamente:

Definição 1(Divisibilidade). Sejam a e b ∈ Z, diz-se que b, diferente

de zero, divide a, ou que b é divisor de a ou, ainda, que a é um múltiplo
de b, se existe um inteiro m tal que a = mb.

Usaremos a notação b | a para indicar que b divide a. A negação dessa

afirmação será indicada por b - a. Por outro lado, no que 0 | a se, e somente
se, a = 0. Neste caso, o quociente não é único pois 0m = 0, para todo inteiro
m.
Posteriormente, vamos precisar de algumas propriedades simples de divi-
sibilidade para números inteiros, que são as seguintes, lembrando que quais-
quer que sejam os números inteiros a, b, c, d, e também assumimos que os
divisores são diferentes de zero, valem:
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 21

• (i) Se a | 1, então a = ±1.

• (ii) Se a | b e b | a, então a = ±b.

• (iii) Todo b 6= 0 divide 0.

• (iv) Se a | b e b | c, então a | c.

• (v) Se a | b e a | c, então a | (mb + nc) ∀m, n ∈ Z.

3.1.3 Algoritmo da Divisão

Dado qualquer número inteiro positivo b e qualquer inteiro não negativo a,

se dividirmos b por a, nós obtemos um quociente inteiro q e um resto r que
obedecem o seguinte teorema:

Teorema 1(Algoritmo da Divisão). Sejam a e b inteiros, com b > 0.

Então, existem q, r ∈ Z, únicos, tais que a = bq + r e 0 ≤ r < b.

Demonstração. Considere o conjunto S = {a − bt | t ∈ Z, a − bt ≥ 0}.

Suponha a ≥ 0, neste caso, a − b0 = a ∈ S. Por outro lado, se a < 0,
a−ba = a(1−b) ≥ 0, portanto a(1−b) ∈ S, logo, S 6= ∅. Como todo conjunto
não vazio de inteiros não negativos contém um mı́nimo pelo Princı́pio da Boa
Ordem, seja r o menor elemento de S. Por definição, r é da forma r = a − bq
para um q ∈ Z qualquer, e r ≥ 0. Além disso, temos que r < b, pois, caso
contrário, r−b seria um elemento de S menor que r, contradizendo a definição
de r; de fato, se r ≥ b, então nós terı́amos 0 ≤ r − b = a − b(q + 1). Isso
prova a existência de r e q. Para provar a unicidade, suponha que a = bq + r
e a = bq 0 + r0 , onde 0 ≤ r < b e 0 ≤ r0 < b. Então subtraindo estas duas
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 22

equações e rearranjar os termos, obtemos:

r0 − r = b(q − q 0 )

Então, r0 − r é um múltiplo de b; porém, 0 ≤ r < b e 0 ≤ r0 < b implica

que |r0 − r| < b, assim sendo, a única possibilidade é r0 − r = 0. Além disso,
0 = b(q − q1 ) e b 6= 0 isto implica que q − q 0 = 0.

Agora, vamos definir a função piso, teto e também o operador mod, por
fim, definiremos o conceito de ideal e refinaremos ainda mais o Teorema 1,
estes assuntos servirão de base para nosso trabalho.
Função Piso e Teto
Seja b·c e d·e, respectivamente, a função piso e teto, que são funções de
R para Z. Para x ∈ R, a função piso de x, bxc, é o maior número inteiro
m ≤ x; é equivalentemente dizer que bxc é o único número inteiro m tal
que m ≤ x < m + 1, ou de outra forma, tal que x = m +  para algum
 ∈ [0, 1[. Além disso, a função teto de x, dxe, é o menor número inteiro
m ≥ x; é equivalentemente dizer que dxe é o único número inteiro m tal que
m − 1 < x ≤ m, ou de outra forma, tal que x = m −  para alguns  ∈ [0, 1[.
Significado do Mod
O operador mod é usado neste trabalho e na literatura de duas maneiras
diferentes: primeiro, veremos como um operador, que, a partir de dois argu-
mentos inteiros, retorna o resto entre eles, e mais tarde o veremos como uma
relação de congruência. Vou explicar as distinções e definições deles nesta
subseção e nas próximas:
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 23

Definição 2(Operador Mod). Sejam a, b inteiros, com b > 0. Pelo

Teorema 1, existem q, r ∈ Z únicos que satisfazem a = bq +r e 0 ≤ r < b.
Portanto, podemos definir:

a mod b := r;

isto é, por a mod b denotamos o resto da divisão de a por b. Como já
vimos que b | a se, somente se, a mod b = 0. Dividindo ambos os lados
da equação a = bq + r por b, obtemos a/b = q + r/b. Como q ∈ Z e
r/b ∈ [0, 1[, temos que q = ba/bc. Então,

a mod b = a − b ba/bc .

Pode-se usar esta equação para estender a definição de a mod b para todos
os inteiros a e b com b 6= 0; para b < 0, simplesmente definimos a mod b como
a − b ba/bc. Logo, podemos generalizar o Teorema 1 quando dividimos o
inteiro a por um inteiro positivo b, o resto desta divisão está em um intervalo
diferente de [0, b[. Então, seja x qualquer número real, e considere o intervalo
[x, x+b[. Este intervalo contém precisamente b inteiros, ou seja, dxe , . . . , dxe+
b − 1. Portanto, aplicando o Teorema 1 com a − dxe no lugar de a, temos o
teorema:

Teorema 2. Sejam a, b ∈ Z com b > 0, e seja x ∈ R. Então existem

q, r ∈ Z únicos, tais que a = bq + r e r ∈ [x, x + b[.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 24

Significado de Ideal
Vamos iniciar agora o conceito de ideal, gostarı́amos de alertar para o
fato de que a definição clássica de ideal é feita para um anel em geral, porém,
como a utilização neste trabalho se restringe a ideias sobre inteiros, vamos
restringir, também, as definições para nossas necessidades.

Definição 3(Ideal). Um conjunto não-vazio I ⊆ Z é chamado de ideal

se ∀a, b ∈ I e para todo z ∈ Z, temos:

a+b∈I e az ∈ I.

É fácil ver que todo ideal I contém 0: como a ∈ I para algum inteiro a,
temos que 0 = a · 0 ∈ I, aliás, note que se um ideal I contém um inteiro a,
ele também contém −a, pois −a = a · (−1) ∈ I. Assim, se um ideal contém
a e b, ele também contém a − b. É claro que {0} e Z são ideais. Além disso,
um ideal I é igual a Z se somente se 1 ∈ Z; para ver isto, note que 1 ∈ Z
implica que para cada z ∈ Z, temos z = 1 · z ∈ I, e portanto, I = Z; caso
contrário, se I = Z, então em particular, 1 ∈ Z.
Para a ∈ Z, definimos aZ := {az : z ∈ Z}; isto é, aZ é conjunto de todos
os múltiplo de a. Se a = 0, então claramente aZ = {0}; de outra forma, aZ
consiste os inteiros distintos:

. . . , −3a, −2a, −a, 0, a, 2a, 3a, . . .

É fácil de ver que aZ é um ideal: para todo az, az 0 ∈ aZ e z 00 ∈ Z, temos

que az + az 0 = a(z + z 0 ) ∈ aZ e (az)z 00 ∈ aZ. O ideal aZ é chamado de ideal
gerado por a, e um ideal da forma aZ para algum a ∈ Z é chamado de ideal
principal.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 25

Observe que para todo a, b ∈ Z, temos que b ∈ aZ se, e somente se, a | b,

aliás, note que para cada ideal I, temos que b ∈ I se, e somente se, bZ ⊆ I.
Ambas observações são consequências simples das definições, como o leitor
pode verificar. Se combinarmos estas duas observações, nós percebemos que
bZ ⊆ aZ se, e somente se, a | b. Vamos supor que I1 e I2 são ideais. Então
não é difı́cil perceber que o conjunto

I1 + I2 := {a1 + a2 : a1 ∈ I1 , a2 ∈ I2 }

é também um ideal. De fato, suponha que a1 + a2 ∈ I1 + I2 e b1 + b2 ∈ I1 + I2 .

Então nós temos que (a1 + a2 ) + (b1 + b2 ) = (a1 + b1 ) + (a2 + b2 ) ∈ I1 + I2 , e
para cada z ∈ Z, temos que (a1 + a2 )z = a1 z + a2 z ∈ I1 + I2 .

Exemplo 1. Considere o ideal principal 3Z. Este consiste em todos os

múltiplos de 3; isto é, 3Z = {. . . , −9, −6, −3, 0, 3, 6, 9, . . .}.

Exemplo 2. Considere o ideal 3Z+5Z. Este ideal contém 3·2+5·(−1) = 1;

já que contém 1, ele também contém todos os inteiros; isto é, 3Z + 5Z = Z.

Neste dois exemplos, mostramos a formação de ideais, observando com

mais detalhes, quando definimos um ideal principal não foi por acaso: o se-
guinte Teorema 3 diz que todos os ideais de Z são principais:

Teorema 3. Seja I um ideal de Z. Então existe um inteiro não-negativo

d tal que I = dZ.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 26

Demonstração. Primeiro vamos provar a existência do Teorema 3. Se I =

{0}, então d = 0.
Agora, vamos supor que I 6= {0}. Existe pelo menos um inteiro a 6= 0
tal que a ∈ I, então pela Definição 3 (ideal) temos que −a ∈ I. Como a e
−a pertencem a I, podemos afirmar que I contém inteiros positivos. Assim,
o conjunto I+ = {a ∈ I : a > 0} é não-vazio. Pelo Princı́pio de Boa Ordem
existe um d = min I+ .
De fato, como d ∈ I, a Definição 3 mostra que, para todo z ∈ Z, tem-se
que dz ∈ I, logo, dZ ⊂ I. Para provar a inclusão contrária, consideraremos
um elemento qualquer a ∈ I e provaremos que é um múltiplo de d. É suficiente
mostrar que d | a e podemos determinar q e r tais que a = dq + r, tal que
0 ≤ r < d. Se r 6= 0, como r = a − dq e tanto a quanto dq pertencem a I,
terı́amos que r ∈ I+ . Mas, r < d = min I+ , uma contradição. Assim, r = 0,
logo, a = dq é um múltiplo de d.

3.2 Algoritmo de Euclides

Uma das técnicas básicas da teoria dos números é o Algoritmo Euclidiano,
que é um procedimento simples para determinar o maior divisor comum de
dois inteiros positivos.
Maior Divisor Comum
Sejam a, b ∈ Z, denotamos d ∈ Z um divisor comum de a e b se d | a e
d | b; além disso, nós chamamos d de maior divisor comum de a e b se d
é não-negativo e todos os outros divisores comuns de a e b dividem d.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 27

Teorema 4. Para todo a, b ∈ Z, existe um maior divisor comum único

d de a e b, e além disso, aZ + bZ = dZ.

Demonstração. Aplicamos o Teorema 3 ao ideal I := aZ + bZ. Seja d ∈ Z

com I = dZ. Queremos mostrar que d é o maior divisor comum de a e b.
Note que a, b, d ∈ Z e d é positivo.
Como a ∈ I = dZ, nós temos que d | a; similarmente, d | b. Então temos
que d é um divisor comum de a e b.
Como d ∈ Z = aZ + bZ, existe s, t ∈ Z tal que as + bt = d. Suponha agora
que a = a0 d0 e b = b0 d0 para algum a0 , b0 , d0 ∈ Z. Então a equação as + bt = d
implica que d0 (a0 s + b0 t) = d, diz que d0 | d. Assim, qualquer divisor comum
d0 de a e b divide d. Isso prova que d é o maior divisor comum de a e b. Por
exclusividade, observe que se e é o maior divisor comum de a e b, então d | e
e e | d, e portanto, d = ±e; já que ambos d e e são ambos não negativos por
definição, logo nós temos que d = e.

Para a, b ∈ Z, vamos denotar mdc(a, b) como o maior divisor comum de

a e b.
Nós dizemos que a, b ∈ Z são primos entre si se mdc(a, b) = 1, que é o
mesmo dizer que os únicos divisores comuns de a e b são +1 e -1.
O que se segue é essencialmente apenas uma reafirmação do Teorema 4,
vamos enfatizar neste teorema:

Teorema 5. Sejam a, b, r ∈ Z e seja d := mdc(a, b). Então existe s, t ∈ Z

tal que as + bt = r se, e somente se, d | r. Em particular, a e b são primos
entre si se, e somente se, existem inteiros r e t tal que as + bt = 1.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 28

Demonstração.

as + bt = r para algum s, t ∈ Z

⇐⇒ r ∈ aZ + bZ

⇐⇒ r ∈ dZ (pelo Teorema 4)

⇐⇒ d | r.

Isso prova a primeira afirmação. A segunda declaração segue a primeira,

definindo r := 1.

Teorema 6. Sejam a, b, c ∈ Z tal que c | ab e mdc(a, c) = 1. Então c | b.

Proposição 1. Sejam a, b inteiros, d = mdc(a, b) e c um inteiro não

nulo. Então:

• (i) mdc(ac, bc) = d|c|

• (ii) Se c | a e c | b, então mdc(a/c, b/c) = d/|c|.

Teorema 7(Teorema de Euclides). Sejam a, b, c ∈ Z tais quer a | bc.

Se mdc(a, b) = 1, então a | c

Demonstração. Supondo que a | bc e mdc(a, b) = 1. Então pelo Teorema 5

nós temos que as + bt = 1 para algum s, t ∈ Z. Multiplicando por c ambos
os lados desta equação, nós temos que:

acs + bct = c. (3.1)

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 29

Como a divide acs por hipótese, e também a divide bct, então dividindo a
por ambos os lodos da equação 3.1, temos que a | |c|, logo a | c.

Encontrando o Maior Divisor Comum

Descrevemos agora um algoritmo creditado a Euclides para encontrar
facilmente o maior divisor comum de dois inteiros. Este algoritmo tem sig-
nificado subsequente neste capı́tulo. Suponha que temos inteiros a, b tais
que d = mdc(a, b). Porque mdc(|a|, |b|) = mdc(a, b), podemos assumir que
a ≥ b > 0. Agora dividindo a por b e aplicando o algoritmo de divisão, nós
podemos concluir:

a = q 1 b + r1 como 0 ≤ r1 < b (3.2)

Se acontecer que r1 = 0, então b | a e d = mdc(a, b) = b. Mas se r1 6=

0, podemos afirmar que d | r1 . Isto é devido às propriedades básicas da
divisibilidade: as relações d | a e d | b juntas implicam que d | (a − q1 b),
que é o mesmo que d | r1 . Antes de prosseguir com o Algoritmo Euclidiano,
precisamos responder a pergunta: O que é o mdc(b, r1 )? Nós sabemos que d | b
e d | r1 . Agora pegue qualquer inteiro c arbitrário que divida tanto b como
r1 . Portanto, c | (q1 b + r1 ) = a. Porque c divide tanto a quando b, devemos
ter c ≤ d, que é o maior divisor comum de a e b. Portanto d = mdc(b, r1 ).
Vamos agora retornar à equação (3.2) e assumir que r1 é diferente de 0.
Porque b > r1 , podemos dividir b por r1 e aplicar o algoritmo de divisão para
obtemos:

b = q2 r1 + r2 como 0 ≤ r2 < r1

Como foi dito antes, se r2 = 0, então d = r1 e se r2 6= 0, então d =

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 30

mdc(r1 , r2 ). O processo de divisão continua até que o resto seja igual a zero,
vamos ver isto no esquema (3.3), digamos, no (n + 1) passo no qual rn−1 é
dividido por rn .
O resultado é o seguinte:

a = q1 b + r1 , 0 ≤ r1 < b; 






b = q2 r1 + r2 , 0 ≤ r2 < r1 ; 






r1 = q3 r2 + r3 , 0 ≤ r3 < r2 ;





.. 
. 
(3.3)


0 ≤ rn < rn−1 ;

rn−2 = qn rn−1 + rn , 






rn−1 = qn+1 rn + 0, 






d = mdc(a, b) = rn .



Em cada iteração, temos d = mdc(ri , ri+1 ) até que finalmente d = mdc(rn , 0) =

rn . Assim, podemos encontrar o maior divisor comum de dois inteiros por re-
petitiva aplicação do algoritmo de divisão.
Argumentamos essencialmente de cima para baixo que o resultado final
é o mdc(a, b). Nós também podemos argumentar de baixo para cima. O pri-
meiro passo é mostrar que rn divide a e b. Segue-se da última divisão na
equação (3.3) que rn divide rn−1 . A penúltima divisão mostra que rn divide
rn−2 porque divide os dois termos à direita. Sucessivamente, vê-se que rn
divide todos os ri termos e finalmente a e b. Resta mostrar que rn é o maior
divisor que divide a e b. Se pegarmos qualquer inteiro arbitrário que divida
a e b, ele também deve dividir r1 , como explicado anteriormente. Podemos
seguir a sequência de equações na equação (3.3) abaixo e mostrar que c deve
dividir todos os ri . Portanto, c deve dividir rn , de modo que rn = mdc(a, b).
Vamos agora olhar como seria o pseudocódigo deste algoritmo:
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 31

Algoritmo 1 Algoritmo de Euclides

1: procedure Euclides(a, b) . O mdc de a e b
2: r ← a mod b
3: while r 6= 0 do . Nós temos a resposta se r é 0
4: a←b
5: b←r
6: r ← a mod b
7: end while
8: return b . O mdc é b
9: end procedure

3.3 Aritmética Modular

Quase todos os algoritmos de criptografia, tanto de cifras simétricas

quanto assimétricas são baseados em aritmética com um número finito de
elementos. Por isso, nós vamos introduzir o conceito de aritmética modular,
que é uma maneira simples de executar aritmética em um conjunto finito de
inteiros.
Congruência

Definição 4. Seja m 6= 0 um inteiro fixo. Dois inteiros a e b dizem-se

congruentes módulos m, se m divide a diferença a − b.

Portanto, pela definição acima dois inteiros a e b dizem-se congruentes

módulos m, se a mod m = b mod m, escrevemos a ≡ b (mod m) 1 . Para
indicar que a e b não são congruentes módulo m, escrevemos a 6≡ b (mod m).
1
Usamos o operador mod de duas maneiras diferentes: primeiro como um operador
que, a partir de dois argumentos inteiros, retornar o resto entre eles, como na expressão
a mod b (veja Definição 2); segundo como uma relação de congruência que mostra a
equivalência de dois inteiros, como a ≡ b (mod m).
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 32

O número inteiro m é chamado de módulo e Gauss escreveu no seu livro,

Disquisitiones Arithmeticae, que o sı́mbolo ≡ foi induzido pelo sı́mbolo de
igualdade, já que são conceitos semelhantes.
Com a nossa definição, a ≡ b (mod m) se, e somente se, m | (a − b), ou,
equivalentemente, se houver um inteiro q tal que a = b + mq.
Como m | (a − b) se, e somente se, |m| | (a − b), nós nos limitaremos a
considerar o caso em que m > 0.

Proposição 2. Seja m um inteiro fixo. Dois inteiros a e b são congruentes

módulo m se, e somente se, eles têm como resto o mesmo inteiro quando
dividimos por m.

Propriedades de Congruências
Sejam m > 0 um inteiro fixo, e a, b, c, d ∈ Z. Então, valem as seguintes
propriedades:

• (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), então a + c ≡ b + c (mod m).

• (vi) Se a ≡ b e c ≡ d (mod m), então ac ≡ bd (mod m).

• (vii) Se a ≡ b (mod m), então an ≡ bn (mod m), para todo inteiro

positivo n.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 33

• (viii) Se m | (a − b), então a ≡ b (mod m)

Demonstração. Para provar (i), observamos que m divide 0 = a − a, logo

a ≡ a (mod m). Para provar (ii), notamos que m divide a−b, então também
divide −(a − b) = b − a, logo b ≡ a (mod m). Para (iii), note também que
se m divide a − b e b − c, então também divide (a − b) + (b − c) = a − c, logo
a ≡ c (mod m). A demonstração de (iv) é análoga à anterior, e (v) segue de
(iv), observando por (i) que c ≡ c (mod m). Para provar (vi), mudaremos
levemente a estratégia. Se a ≡ b (mod m) e c ≡ d (mod m), existem inteiros
q1 e q2 tais que a = b+q1 m e c = d+q2 m, logo ac = bd+(bq2 +dq1 +q1 q2 m)m,
isto é, m | (ac − bd), donde ac ≡ bd (mod m). Novamente, (vii) segue de
(vi), tomando-se c = a, d = b e usando a indução em n. Finalmente, para
demonstrar (viii), observamos que, se m | (a − b), temos diretamente que,
m | ((a) − (b)), então, a ≡ b (mod m).

Teorema 8. Sejam a, m ∈ Z com m > 0. Então existe um único inteiro

a tal que z ≡ a (mod m) e 0 ≤ z < m, isto é, z := a mod m. Mais
geralmente, para cada x ∈ R, existe um único inteiro z ∈ [x, x + m[ tal
que z ≡ a (mod m).

Vejamos alguns exemplos:

1. Vamos encontrar o conjunto de soluções a para a congruência:

3a + 4 ≡ 6 (mod 7) (3.4)
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 34

Suponto que a é uma solução da Equação (3.4). Subtraindo 4 de ambos

os lados desta equação, nós obtemos:

3a ≡ 2 (mod 7) (3.5)

Em seguida, gostarı́amos de dividir ambos os lados dessa congruência

por 3, para obter a. Nós não podemos fazer isso diretamente, porém,
desde que 3 · 5 ≡ 1 (mod 7), podemos alcançar o mesmo efeito multi-
plicando ambos os lados em (3.5) por 5. Se fizermos isso obtemos:

a≡3 (mod 7)

Assim, se a é uma solução para (3.4), então devemos ter a ≡ 3 (mod 7);
Por outro lado, pode-se verificar que, se a ≡ 3 (mod 7), então (3.4) é
válido. Concluı́mos que os inteiros a que são soluções para (3.4) são
precisamente aqueles inteiros que são congruentes a 3 (mod 7), que
podem ser listados:

. . . , −18, −11, −4, 3, 10, 17, 24, . . .

2. Considere as horas de um relógio analógico. Se você anotar o horário a

cada uma hora, você obtém:

1h, 2h, 3h, . . . , 11h, 12h, 1h, 2h, 3h, . . . , 11h, 12h, 1h, 2h, 3h, . . .

Mesmo se continuássemos adicionando, hora a hora, esta nesta lista,

nós nunca saı́remos dela. Com este exemplo, podemos agora abordar
de uma formar mais geral como funciona aritmética modular (também
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 35

chamada aritmética do relógio).

3. Considere o conjunto dos doze números:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

Nós podemos fazer aritmética regular, desde que os resultados sejam

menores do que 12. Por exemplo:

2·3=6

4+4=8

Porém se somarmos dois elementos deste conjunto, por exemplo, 10 +

4 = 14 e se dividirmos esta soma por 12. E consideramos apenas o
resto desta divisão temos que:

14 ≡ 2 (mod 12).

Há algumas implicações a partir desta definição que vão além da regra
casual “dividir pelo módulo e considerar o resto”, nós abordaremos
estas implicações brevemente.

Operações com Aritmética Modular

Note que, pelo Teorema 1, o operador (mod m) mapeia todos os inteiros,
para o conjunto {0, 1, . . . , (m − 1)} ∈ Z. Isso sugere a seguinte pergunta:
Podemos realizar operações aritméticas dentro dos limites deste conjunto?
A resposta é sim, e as operações possuem as propriedades esperadas como
veremos abaixo. Esta técnica é conhecida como aritmética modular:
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 36

• 1. (a mod m + b mod m) mod m = (a + b) mod m

• 2. (a mod m − b mod m) mod m = (a − b) mod m

• 3. (a mod m · b mod m) mod m = (a · b) mod m

Demonstração. Nós vamos demonstrar a primeira, as outras duas são análogas.

Seja a mod m = ra e b mod m = rb . Então nós podemos escrever a = ra + jm
para um inteiro j e b = rb + km para um inteiro k. Como

(a + b) mod m = (ra + jm + rb + km) mod m

= (ra + rb + (k + j)m) mod m

= (ra + rb ) mod m

= (a mod m + b mod m) mod m

Vamos observar um exemplo destas operações na Tabela 3.1 logo abaixo:

+ 0 1 2 3 4 5 6 7 · 0 1 2 3 4 5 6 7 w −w w−1
0 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 0 0 −
1 1 2 3 4 5 6 7 0 1 0 1 2 3 4 5 6 7 1 7 1
2 2 3 4 5 6 7 0 1 2 0 2 4 6 0 2 4 6 2 6 −
3 3 4 5 6 7 0 1 2 3 0 3 6 1 4 7 2 5 3 5 3
4 4 5 6 7 0 1 2 3 4 0 4 0 4 0 4 0 4 4 4 −
5 5 6 7 0 1 2 3 4 5 0 5 2 7 4 1 6 3 5 3 5
6 6 7 0 1 2 3 4 5 6 0 6 4 2 0 6 4 2 6 2 −
7 7 0 1 2 3 4 5 6 7 0 7 6 5 4 3 2 1 7 1 7
(a) Adição (b) Multiplicação (c) Inversa
Tabela 3.1: Aritmética Módulo 8.

Olhando para a adição, os resultados são diretos e há um padrão regular

na matriz. Ambas as matrizes, (a) e (b), são simétricas em relação à diago-
nal principal, em conformidade com a propriedade comutativa de adição e
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 37

multiplicação. Aliás, existe um inverso aditivo, ou negativo, para cada inteiro

na aritmética modular. Para achá-lo varre-se a linha correspondente da ma-
triz (a) para encontrar o valor 0, o inteiro no topo dessa coluna é o inverso
(pois o inverso aditivo é, por definição, aquele cuja soma resulta em 0); assim
(2 + 6) mod 8 = 0. Isso significa que existe um inverso. Da mesma forma,
na matriz (b). Mas o inverso para multiplicação é dado quando procura-se
na matriz as entradas que contenham 1; o inteiro no topo dessa coluna é o
inverso multiplicativo (analogamente, o inverso multiplicativo é o elemento
cuja soma resulta em 1). Assim, 3 · 3 mod 8 = 1, ou seja, 9 dividido por 8
tem resto 1. Note que nem todos os inteiros mod 8 têm inverso, por exemplo,
2, 4 e 6.

Propriedades da Aritmética Modular

Seja a um inteiro. Chama-se [r] as classes de congruências de a módulo
m, ou seja, o conjunto formado, normalmente, de todos os inteiros que são
congruentes a a módulo m.

[r] = r + mZ := {r + mb : b ∈ Z}

= {a ∈ Z | a ≡ r (mod m)}

e, portanto,

a ∈ [r] ⇐⇒ a ≡ r (mod m) ⇐⇒ a = r + mb, b ∈ Z,

Historicamente, classes de congruências são chamadas de classe de resı́duos

ou resı́duo m, nós vamos adotar esta terminologia aqui também.
Denotaremos pelo sı́mbolo Zm o conjunto de classe de resı́duos módulo
m, o que se segue é simplesmente uma reafirmação do Teorema 7:
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 38

Definição 5. Seja m um inteiro positivo. Então Zm consiste nas m classe

resı́duos distintas [0], [1], [2], . . . , [m − 1], além disso, para todo x ∈ Z,
cada classe de resı́duos módulo m contém uma representação exclusiva
no intervalo [x, x + m[.

Podemos “equipar” Zm com operações que definem adição e multiplicação.

É natural pensarmos para a, b ∈ Z a seguintes definições:

[a] + [b] := [a + b],

[a] · [b] := [a · b].

É preciso verificar se estas definições são inequı́vocas, ou seja, mais precisa-

mente, deve-se verificar que se [a] = [a0 ] e [b] = [b0 ], então [a + b] = [a0 + b0 ] e
[a·b] = [a0 ·b0 ]. Porém, esta propriedade segue imediatamente das propriedades
de congruências (iv) e (vi).
Observe que para todo a, b, c ∈ Z, nós temos:

[a] + [b] = [c] ⇐⇒ a + b ≡ c (mod m),

[a] · [b] = [c] ⇐⇒ a · b ≡ c (mod m).

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 39

Por exemplo, a classe de resı́duos módulo 6 são:

[0] = {. . . , −12, −6, 0, 6, 12, . . .}

[1] = {. . . , −11, −5, 1, 7, 13, . . .}

[2] = {. . . , −10, −4, 2, 8, 14, . . .}

[3] = {. . . , −9, −3, 3, 9, 15, . . .}

[4] = {. . . , −8, −2, 4, 10, 16, . . .}

[5] = {. . . , −7, −1, 5, 11, 17, . . .} .

A Tabela 3.2 mostra a adição e multiplicação das classe de resı́duos módulo

6:
+ [0] [1] [2] [3] [4] [5] · [0] [1] [2] [3] [4] [5]
[0] [0] [1] [2] [3] [4] [5] [0] [0] [0] [0] [0] [0] [0]
[1] [1] [2] [3] [4] [5] [0] [1] [0] [1] [2] [3] [4] [5]
[2] [2] [3] [4] [5] [0] [1] [2] [0] [3] [4] [0] [2] [4]
[3] [3] [4] [5] [0] [1] [2] [3] [0] [3] [0] [3] [0] [3]
[4] [4] [5] [0] [1] [2] [3] [4] [0] [4] [2] [0] [4] [2]
[5] [5] [0] [1] [2] [3] [4] [5] [0] [5] [4] [3] [2] [1]
(a) Adição (b) Multiplicação

Tabela 3.2: Aritmética com as classe de resı́duos módulo 6.

Em vez de usarmos o intervalo [0, 6[, poderı́amos também usar um outro

intervalo, como, por exemplo, [3, −3[. Então, em vez de nomear as classe de
resı́duos [0], [1], [2], [3], [4], [5], poderı́amos usar [-3], [-2], [-1], [0], [1], [2].
Observe que [-3] = [3], [-2] = [4] e [-1] = [5].
De todos os inteiros em uma classe de resı́duos, o menor inteiro não nega-
tivo é aquele usado para representar a classe de resı́duos. Encontrar o menor
inteiro não negativo ao qual k é congruente módulo m é chamado de redução
k módulo m.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 40

Há uma peculiaridade da aritmética modular que a diferencia da aritmética

comum. Primeiro, observe que (na aritmética modular) nós podemos escre-
ver:

Se a + b ≡ a + c (mod m), então b ≡ c (mod m) (3.6)

5 + 23 ≡ 5 + 7 (mod 8); 23 ≡ 7 (mod 8)

A equação (3.6) é consistente com a existência de um inverso aditivo.

Adicionando inverso aditivo de a para ambos os lados equação (3.6), nós
temos:

(−a) + a + b ≡ (−a) + a + c (mod m)

b ≡ c (mod m)

Porém, a propriedade abaixo (análoga à anterior, mas para multiplicação)

somente é verdadeira quanto mdc(a, m) = 1. Ou seja, somente quando a e m
são primos entre si, nós podemos afirmar que:

Se a · b ≡ a · c (mod m), então b ≡ c (mod m). (3.7)

Para compreender melhor isso, vamos pegar os inteiros, por exemplo, a =

6, b = 3, c = 7 e m = 8. Portanto, aplicando na equação 3.7 temos que:

6·3≡6·7 (mod 8)
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 41

Portanto, 3 6≡ 7 (mod 8) pois o mdc(6, 8) = 2.

Semelhante ao caso da equação (3.6), podemos dizer que a equação (3.7)

é consistente com a existência de um inverso multiplicativo. Aplicando o
inverso multiplicativo a em ambos os lado da equação (3.7), temos:

(a−1 )ab ≡ (a−1 )ac (mod m)

b ≡ c (mod m)

Sendo assim, podemos realizar aritmética modular dentro de Zm e esta

segue as propriedades que descreveremos a seguir. Sejam x, y, z ∈ Z temos a
seguinte Tabela 3.3:

Propriedades Expressões
(x + y) mod m = (y + x) mod m
Comutatividade
(x · y) mod m = (y · x) mod m
((z + x) + y) mod m = (z + (x + y)) mod m
Associatividade
((z · x) · y) mod m = (z · (x · y)) mod m
Distributiva (z · (x · y)) mod m = ((z · x) + (z · y)) mod m
(0 + z) mod m = z mod m
Identidade
1 · z mod m = z mod m
Inverso Aditivo Para todo inteiro w ∈ Zm , existem um z tal que (w + z) ≡ 0 (mod m)

Tabela 3.3: Propriedades da aritmética modular para inteiros em Zm .

Mostraremos na próxima seção que isso implica que Zm é um anel comu-

tativo com um elemento de identidade.
Algoritmo Euclidiano Revisado
Para qualquer inteiro a não-negativo e qualquer inteiro b positivo temos,

mdc(a, b) = mdc(b, a mod b), (3.8)

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 42

por exemplo, mdc(55, 22) = mdc(22, 55 mod 22) = mdc(22, 11) = 11.
Seja d = mdc(a, b), então, pela definição de maior divisor comum, temos
que d | a e d | b. Para qualquer b inteiro positivo, podemos expressar a desta
forma

a = qb + r ≡ r (mod b)

a mod b = r

com q, r ∈ Z. Assim sendo, a mod b = a−qb para algum inteiro q. Além disso,
sabemos que se d | b, então ele divide qb. Nós também temos que d | a, logo,
d | (a mod b). Isso mostra que d é um divisor comum de b e também a mod b.
Por outro lado, se d é um divisor comum de b e também a mod b, então d | qb
e também é verdade que d | qb + a mod b, que é equivalentemente a dizer que
d | a. Então, o conjunto de divisores comuns de a e também de b é igual ao
conjunto de divisores comuns de b e a mod b. Portanto, isso comprova que o
mdc(a, b) = mdc(b, a mod b).
Note que a equação 3.8 pode ser usada repetidamente para determinar o
maior divisor comum.

mdc(18, 12) = mdc(12, 6) = mdc(6, 0) = 6

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 43

Sendo assim, o esquema 3.3 pode ser reescrito da seguinte maneira:


a = q1 b + r1 ; r1 = a mod b 






b = q2 r1 + r2 ; r2 = b mod r1 






r1 = q3 r2 + r3 ; r3 = r1 mod r2





.. 
. 
(3.9)



rn−2 = qn rn−1 + rn ; rn = rn−2 mod rn−1 






rn−1 = qn+1 rn + 0, rn+1 = rn−1 mod rn = 0 






d = mdc(a, b) = rn .



Podemos implementar o Algoritmo Euclidiano de forma recursiva:

Algoritmo 2 Algoritmo de Euclides

1: procedure Euclides(a, b)
2: if b = 0 then
3: return a
4: else
5: return Euclides(b, a mod b)
6: end if
7: end procedure

Algoritmo Euclidiano Estendido

Passamos agora a olhar para uma melhoria do Algoritmo Euclidiano que
será importante para cálculos posteriores na área de corpos finitos e também
em algoritmos de criptografia, como o RSA. Dados dois inteiros a e b, o
Algoritmo Euclidiano Estendido não apenas calcula o maior divisor comum
d, mas também dois inteiros adicionais x e y a seguinte equação:

ax + by = d = mdc(a, b) (3.10)
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 44

Antes de examinarmos o algoritmo, vamos olhar para alguns dos valores

de x e y quando a = 42 e b = 30. Note que mdc(42, 30) = 6.
Aqui está uma representação parcial em forma de matriz dos possı́veis
valores gerados d pela equação (3.10) acima:

y\x −3 −2 −1 0 1 2 3
 
−3 −216 −174 −132 −90 −48 −6 36 
 
−2 
−186 −144 −102 −60 −18 24 66 

 
−1 
−156 −114 −72 −30
 
12 54 96 

 
0 −126 −84 −42 0 42 84 126
 
 
 
1  −96 −54 −12 30 72 144 186
 
 
2  −66 −24 18 60 102 144 188
 
 
 
3 −36 6 48 90 132 174 216

Observe que todas as entradas desta matriz são divisı́veis por 6. Isto não é
uma surpresa porque ambos os valores 42 e 30 são divisı́veis por 6, então
todo número da forma 42x + 30y = 6 · (7x + 5y) é um múltiplo de 6. Observe
também que o mdc(42, 30) = 6 aparece na matriz acima. Em geral, pode-se
mostrar que, dados dois inteiros a e b, o menor valor positivo de ax+by é igual
ao mdc(a, b). Agora vamos demonstrar o Algoritmo de Euclidiano Estendido
para determinar (x, y, d) dado a, b. Passamos novamente pela equação (3.10),
e para cada passo i podemos encontrar inteiros xi e yi que satisfazem ri =
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 45

axi + byi . Nós terminamos com a seguinte sequência:


a = q1 b + r1 , r1 = ax1 + by1 ; 





b = q2 r1 + r2 , r2 = ax2 + by2 ;








r1 = q3 r2 + r3 , r3 = ax3 + by3 ; 

.. (3.11)
.







rn−2 = qn rn−1 + rn , rn = axn + byn ;







rn−1 = qn+1 rn + 0.



Observe, que agora podemos reorganizar os termos para escrever

ri = ri−2 − ri−1 qi (3.12)

Também na linha i − 1 e i − 2, nós encontramos os valores

ri−2 = axi−2 + byi−2 , e ri−1 = axi−1 + byi−1

Substituindo na equação (3.12), temos:

ri = (axi−2 + byi−2 ) − (axi−1 + byi−1 )qi = a(xi−2 − qi xi−1 ) + b(yi−2 − qi yi−1 )

Porém, nós já assumimos que ri = axi + byi . Portanto,

xi = xi−2 − qi xi−1 , e yi = yi−2 + qi yi−1

Precisamos fazer vários comentários adicionais aqui. Em cada linha, cal-

culamos um novo resto ri com base nos restos das duas linhas anteriores,
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 46

sabendo ri−1 e ri−2 . Para iniciar o algoritmo, precisamos dos valores r0 e r−1 ,
que são apenas a e b. Portanto, é simples determinar os valores necessários
para x−1 , y−1 , x0 e y0 . Sabemos do Algoritmo Euclidiano que o processo
termina com um resto igual a zero, e que o maior divisor comum de a e b
é d = mdc(a, b) = rn . Mas também determinamos que d = rn = axn + byn .
Portanto, na equação (3.10), x = xn e y = yn . Por exemplo, vamos usar
a = 1759 e b = 550, e resolver 1759x + 550y = mdc(1759, 550). Os resultados
são mostrados na Tabela 3.4. Assim, nós temos: 1759 · (–111) + 550 · 355 =
–195249 + 195250 = 1.

i ri qi xi yi
-1 1759 1 0
0 550 0 1
1 109 3 1 -3
2 5 5 -5 16
3 4 21 106 -339
4 1 1 -111 355
5 0 4
Resultado: d = 1; x = −111; y = 355.

Tabela 3.4: Exemplo do Algoritmo Eucledeano Estendido.

3.4 Teorema Fundamental da Aritmética

Uma preocupação central da Teoria dos Números é o estudo dos números

primos. Nesta seção forneceremos uma visão geral sobre este assunto e mos-
traremos que todo inteiro não igual a 0, 1, -1 pode-se expressar como produto
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 47

de números primos, de forma única, a menos da ordem dos fatores. Esse re-
sultado, conhecido como o Teorema Fundamental da Aritmética, já aparece
no livro do IX de Os Elementos de Euclides e destaca a importância dos
primos na Teoria dos Números: eles desempenham um papel análogo ao dos
átomos na estrutura da matéria. Todos os outros números podem ser obtidos
através de produtos entre os números primos.

Definição 6(Números Primos). Um inteiro p diz-se primo se tem

exatamente dois divisores positivos, 1 e |p|.

Note que a definição exclui propositadamente o 0, que tem infinitos divi-

sores positivos, e os inteiros 1 e -1 que têm um divisor positivo.
Um número diferente de 0, 1 e -1 que não é primo diz-se composto. Note
que, da definição, vem imediatamente que, se um inteiro não-nulo a é com-
posto, ele admite um divisor b tal que |b| seja diferente de 1 e de |a|, isto é,
um divisor b tal que 1 < |b| < |a|. Um divisor nessas condições diz-se um
divisor próprio de a.
Suponha que p é um primo, a ∈ Z e tomando a Definição 6 temos que

p | a =⇒ mdc(a, p) = p,

p - a =⇒ mdc(a, p) = 1.

Sendo assim combinando esta observação com o Teorema 7, temos:

Teorema 9. Seja p um número primo e sejam a, b ∈ Z. Se p | ab, então

p | a ou p | b.

Demonstração. Assumindo que p | ab. Se p | a, a tese está verificada. Caso

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 48

contrário, como observado logo acima o mdc(a, p) = 1, assim pelo Teorema 7,

temos que p | b.

Cololário 1. Se um inteiro primo p divide um produto a1 a2 . . . an , então

p | ak para algum k = 1, . . . , n, ou seja, 1 ≤ k ≤ n.

Demonstração. Vamos provar por indução sobre n. Para n = 1 temos que

p | a1 de fato.
Agora seja n > 1, e assumindo que temos n − 1 termos. Então, pelo
Teorema 9, p | a1 ou p | a2 . . . an ; se p | a1 , que é verdade pelo caso base; caso
contrário, por indução, p divide um dos a2 . . . an .

Teorema 10. Seja p um inteiro diferente de 0, 1 e −1. Então, p é primo

se, e somente se, toda vez que p divide um produto de dois números, p
divide pelo menos um dos fatores.

Demonstração. Suponha que p tenha a propriedade do enunciado mas não

seja primo. Então, |p| pode ser escrito da forma |p| = a · b, onde a e b são
divisores próprios positivos, isto é, verificam

1 < a < |p|,

1 < b < |p|

Consequentemente, p | ab, mas p - a e p - b; logo, uma contradição.

Lema 1. Todo inteiro a > 1 pode ser escrito como produto de números
primos.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 49

Teorema 11. Seja n > 1. Então, existem primos positivos p1 ≤ p2 ≤

. . . ≤ pt tais que a = p1 p2 . . . pt , e essa decomposição é única.

Teorema 12(Teorema Fundamental da Aritmética). Seja a um

inteiro diferente de 0. Então, existem primos positivos p1 < p2 < . . . < pr
e inteiros positivos n1 , n2 , . . . , nr tais que a = Epn1 1 . . . pnr r , em que E =
±1, conforme a seja positivo ou negativo, além disso, essa decomposição
é única.

Demonstração. Temos que a = E |a|, onde E = 1 ou E = −1, conforme a

seja positivo ou negativo. Como |a| é positivo, do Teorema 11, temos que
existe primos p1 ≤ p2 ≤ . . . ≤ pt tais que

a = Ep1 p2 . . . pt .

Agrupando os primos eventualmente repetidos, podemos escrever

a = Epn1 1 . . . pnr r

A unicidade segue diretamente do Teorema 11.

Cololário 2. Sejam a e d inteiros diferentes de 0. Então, existem primos

positivos p1 < p2 < · · · < pt e inteiros não-negativos n1 , . . . , nt , m1 , . . . , mt
(mas eventualmente iguais a zero, se necessário) tais que

a = E1 pn1 1 . . . pnt t ,

d = E2 pm1 mt
1 . . . pt ,

em que Ei = ±1parai = 1, 2.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 50

Usando essas decomposições, podemos dar um critério de divisibilidade

que formulamos apenas para inteiros positivos (observe que isso não é uma
perda de generalidade, já que d | a se, e somente se, |d| divide |a|).

Lema 2. Sejam a = pn1 1 . . . pnt t e d = pm mt

1 . . . pt
1
inteiros positivos, onde
p1 , . . . , pt são primos positivos e ni , mi são inteiros não-negativos para todo
1 ≤ i ≤ t. Então, d | a se, e somente se, mi ≤ ni , 1 ≤ i ≤ t.

Teorema 13. Sejam a = pn1 1 . . . pnt t e b = pm mt

1 . . . pt inteiros nas condições
1

do lema 2. Então,

d = mdc(a, b) = pα1 1 . . . pαt t , em que αi = min(ni , mi ), 1 ≤ i ≤ t,

m = mmc(a, b) = pβ1 1 . . . pβt t , em que βi = max(ni , mi ), 1 ≤ i ≤ t.

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 51

3.5 Teorema Chinês do Resto

Teorema 14(Teorema Chinês do Resto). Sejam {mi }ki=1 inteiros,

primos entre si dois a dois (isto é, i 6= j para todo 1 ≤ i, j ≤ k), e sejam
b1 , . . . , bk inteiros arbitrários. Então, existe uma solução a ∈ Z para o
sistema de congruências lineares

a ≡ b1 (mod m1 )

a ≡ b2 (mod m2 )
..
.

a ≡ bk (mod mk ).

Além disso, qualquer b ∈ Z é uma solução para este sistema de con-

Qk
gruências lineares se, e somente se, a ≡ b (mod m), onde m := i=1 mi .

Demonstração. Para provar a existência de uma solução a para o sistema

de congruências lineares, primeiro vamos mostrar como construir inteiros do
tipo e1 , . . . , ek tal que para i, j = 1, . . . , k, temos que

1 (mod mi ) se i = j



ej ≡  (3.13)
0 (mod mi ) se i 6= j.


Se fizermos isso, em seguida, definindo

k
X
a := ai e i ,
i=1
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 52

para j = 1, . . . , k, temos que

k
X
a= ai ei ≡ aj (mod mj ),
i=1

uma vez que todos os termos nesta soma são zero módulo mj , exceto para o
termo i = j, que é congruente com aj módulo mj .
Construiremos agora os inteiros do tipo e1 , . . . , ek que sejam satisfatórios
Qk
para equação 3.13. Seja m := i=1 mi com i = 1, . . ., k, e também seja
m∗i := m/mi ; isto é, m∗i é o produto de todos os números mj com i 6= j. Como
{mi }ki=1 são inteiros, primos entre si dois a dois, segue que para todo i entre
1 e k, temos que mcd(mi , m∗i ) = 1, e podemos definir também ti := (m∗i )−1
mod mi e ei := m∗i ti . Uma vez que ei ≡ 1 (mod mi ), mi | m∗j para todo
i 6= j e ej ≡ 0 (mod mi ), temos que a equação 3.13 é satisfeita. Isso prova
a existência de uma solução a para o sistema de congruências. Se a ≡ b
(mod m), então temos que mi | m para i = i, . . . , k, vemos que a ≡ bi ≡ b
(mod mi ) para i = 1, . . . , k, então b também resolve o sistema de congruências
lineares.
Finalmente, se b é uma solução para o sistema de congruências lineares,
então a ≡ bi ≡ b (mod mi ) para i = 1, . . . , k. Portanto, mi | (a − b) para
i = 1, . . ., k. Sendo assim {mi }ki=1 são inteiros primos entre si, isto implica
que m | (a − b), ou equivalentemente dizer que, a ≡ b (mod m).

3.6 Teorema de Fermat e Euler

Dois teoremas que desempenham papéis importantes na criptografia de chave
pública são o Teorema de Fermat e o Teorema de Euler.
Função Totient de Euler
Antes de apresentarmos o Teorema de Euler, precisamos definir uma
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 53

função importante em teoria dos números. Estamos nos referindo à Função

Totient, ela é definida como:

Definição 7. Seja n ∈ Z e n ≥ 1, indicaremos por ϕ(n) a função:

ϕ(n) := |Z∗n | .

Equivalentemente, ϕ(n) é a quantidade de números compreendidos entre

1 e n − 1 que são relativamente primos a n. Denotamos o conjunto destes
n o
números como A = x1 , x2 , . . . , xϕ(n) , onde cada xi é tal que 1 ≤ xi ≤ n
e mdc(xi , n) = 1. A função assim definida chama-se Função Totient ϕ de
Euler.

Por exemplo, se n = 4, os inteiros positivos menores que ou iguais a 4

que são primos em relação a ele são os inteiros 1 e 3, ou seja, os elementos de
A = {1, 3} que são primos com relação a 4, assim ϕ(4) = 2. Analogamente,
temos ϕ(5) = 4, ϕ(6) = 2.
Usando o Teorema 3.5 é fácil obter uma boa fórmula para ϕ em termos da
fatoração em primos de n, conforme estabelecemos com o teorema a seguir.

Teorema 15. Sejam {ni }ni=1 inteiros positivos e primos entre si dois a
Qk
dois, e n := i=1 ni .

k
Y
ϕ(n) = ϕ(ni ).
i=1

A Tabela 3.5 lista os primeiros 30 valores de ϕ(n). O valor de ϕ(1) é sem

significado, porém, é definido como 1. Para um número primo p deve ficar
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 54

claro que:

ϕ(p) = p − 1.

Supondo que nós temos dois números primos p e q com p 6= q. Então,

podemos mostrar que, para n = pq,

ϕ(n) = ϕ(pq) = ϕ(p) · ϕ(q) = (p − 1) · (q − 1)

Demonstração. Considerando que ϕ(n) = ϕ(p)·ϕ(q) e o conjunto de números

inteiros positivos menores do que n, isto é, {1, . . . , (pq − 1)}, e o conjunto de
inteiros positivos que não são primos com relação a n, ou seja, {p, 2p, . . . , (q − 1)p},
e {q, 2q, . . . , (p − 1)q }. Então, temos que:

ϕ(n) = (pq − 1) − [(q − 1) + (p − 1)]

= pq − (p + q) + 1

= (p − 1) · (q − 1)

= ϕ(p)ϕ(q)

Por exemplo, se ϕ(21) = ϕ(3) · ϕ(7) = (3 − 1) · (7 − 1) = 2 · 6 = 12. Os

elementos de A = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} são todos primos
com relação a 21.
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 55

n ϕ n ϕ n ϕ
1 1 11 10 21 12
2 1 12 4 22 10
3 2 13 12 23 22
4 2 14 6 24 8
5 4 15 8 25 20
6 2 16 8 26 12
7 6 17 16 27 18
8 4 18 6 28 12
9 6 19 18 29 28
10 4 20 8 30 8

Tabela 3.5: Alguns valores da Função Totient de Euler ϕ(n).

3.6.1 Teorema de Euler

Teorema 16(Teorema de Euler). Sejam a e n inteiros com n ≥ 1,

tais que mdc(a, n) = 1. Então, aϕ(n) ≡ 1 (mod n).

Não vamos fazer a demonstração deste teorema pois ela é bem extensa. Fica
a cargo do leitor. Sendo assim, vamos ver alguns exemplos:
• 1. a = 3; n = 10; ϕ(10) = 4; aϕ(n) = 34 = 81 ≡ 1 (mod 10);

• 2. a = 2; n = 11; ϕ(11) = 10aϕ(n) = 210 = 1024 ≡ 1 (mod 11).

3.6.2 Teorema de Fermat

Teorema 17(Teorema de Fermat). Sejam p um primo e a um inteiro

tal que p - a, então
ap−1 ≡ 1 (mod p)
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 56

Demonstração. Considere o conjunto de inteiros (i) = {a, 2a, 3a, . . . , (p − 1)a}.

Dados dois elementos quaisquer desse conjunto, eles não são congruentes en-
tre si módulo p, pois, se xa ≡ ya (mod p) com 1 ≤ x, y ≤ p − 1, como
mdc(a, p) = 1, cancelando terı́amos x ≡ y (mod p), o que não acontece, já
que os elementos do conjunto (ii) = {1, 2, 3, . . . , p − 1} não são congruentes
entre si módulo p. Além disso, nenhum dos elementos de (i) é congruente
a 0 módulo p, já que, se p | xa, com 1 ≤ x ≤ p − 1, então p | x ou p | a,
o que não acontece. Segue-se então que os elementos de (i) são congruentes
aos elementos de (ii). Temos, então p − 1 congruências da forma

a ≡ x1 (mod p)

2a ≡ x2 (mod p)
..
.

(p − 1)a ≡ xp−1 (mod p)

onde x1 , x2 , . . . , xp−1 são os inteiros 1, 2, . . . , p − 1, eventualmente em uma

outra ordem. Multiplicando essas congruências, temos

a · 2a · . . . (p − 1)a ≡ 1 · 2 · (p − 1) (mod p)

ou seja,

(p − 1)!ap−1 ≡ (p − 1)! (mod p)

Como mdc((p − 1)!, p) = 1, podemos cancelar e obtemos

ap−1 ≡ 1 (mod p)
CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 57

Note que, se p é primo, ϕ(p) = p − 1; então o Teorema de Fermat segue

como um caso particular do Teorema de Euler.

aϕ(n)+1 ≡ a (mod n) (3.14)

Cololário 3. Sejam p um primo e a um inteiro arbitrário. Então, ap ≡ a

(mod p).

Demonstração. Se p - a, do Teorema 17 temos que ap−1 ≡ 1 (mod p); multi-

plicando os membros dessa congruência por a segue que ap ≡ a (mod p).
Se p | a, então p | ap , e consequentemente p | (ap − a); logo ap ≡ a
(mod p).

O Teorema de Fermat pode ser usado para provar diversos resultados

sobre divisibilidade. Ilustraremos esta afirmação com alguns exemplos:

• 1. Seja a um inteiro arbitrário. Provaremos que o algarismos das uni-

dades de a e de a5 é o mesmo (quando escritos em base 10).

Se r e s indicam esses algarismos, como a ≡ r (mod 10) e a5 ≡

s (mod 10), para concluir a igualdade bastará mostrar que a5 ≡ a
(mod 10). Do Teorema de Fermat, temos que a5 ≡ a (mod 5), logo,
5 | (a5 − a). Por outro lado, 2 | (a5 − a), pois a e a5 são ambos pares
ou ambos ı́mpares. Como mdc(2, 5) = 1, temos que 10 | (a5 − a), como
querı́amos demostrar.

• 2. Dados a e b inteiros arbitrários e p um primo, tem-se que

(a + b)p ≡ ap + bp (mod p).

CAPÍTULO 3. FUNDAMENTOS EM TEORIA DOS NÚMEROS 58

De fato, tomando módulo p e usando o Teorema de Fermat, temos que

(a + b)p ≡ a + b ≡ ap + bp (mod p).

3.7 Resumo
Neste capı́tulo demos uma breve explicação das principais definições e teore-
mas que servem como base para o leitor compreender os próximos capı́tulos
e também os conceitos usados para aplicar cifras simétricas, por exemplo,
AES, e cifras assimétricas RSA e CCE. Estes exemplos são largamente
usados hoje para codificar uma mensagem como foi citado no capı́tulo 3.
Capı́tulo 4

Grupos, Anéis e Corpos

No capı́tulo 4 abordaremos estes três temas: grupos, anéis e corpos, eles são
elementos fundamentais de um ramo da Matemática conhecido como álgebra
abstrata ou álgebra moderna.
Estamos preocupados com conjuntos cujos elementos podemos operar al-
gebricamente; isto é, podemos combinar dois elementos do conjunto, talvez
de várias maneiras, para obter um terceiro elemento do conjunto.
Essas operações estão sujeitas a regras especı́ficas, que definem a natureza
do conjunto. Por convenção, a notação para as duas classes principais de
operações nos elementos do conjunto é geralmente a mesma que a notação
para adição e multiplicação em números ordinários. No entanto, é importante
notar que, na álgebra abstrata, não estamos limitados a operações aritméticas
comuns. Tudo isso deve ficar claro quando prosseguirmos neste capı́tulo.

59
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 60

4.1 Grupos
Um grupo é um conjunto,G, juntamente com uma operação • (chamada de
lei do grupo G) que combina quaisquer dois elementos a e b para formar outro
elemento, denotado de a • b. Para se qualificar como um grupo, o conjunto
e a operação, {G, •}, devem satisfazer quatro requisitos conhecidos como
axiomas do grupo:

• (A1) Operação fechada em G: Para todo a e b ∈ G, o resultado da

operação, a • b, também está em G.

• (A2) Associatividade: Para todo a, b e c ∈ G, a • (b • c) = (a • b) • c.

• (A3) Identidade: Há um elemento e ∈ G tal que a • e = e • a = a

para todo a ∈ G.

• (A4) Inverso: Para cada a ∈ G, existe um elemento a0 ∈ G, comu-

mente denotado a−1 (ou −a, se a operação for denotada +) tal que
a • a0 = a0 • a = e, no qual e é o elemento de identidade.

Se um grupo tem um número finito de elementos, é denominado de grupo

finito, e a ordem deste grupo é igual ao número de elementos no grupo.
Caso contrário, o grupo é chamado de grupo infinito.
Um grupo se diz ser abeliano se ele satisfaz o seguinte axioma, além dos
citados acima:

• (A5) Comutatividade: a • b = b • a, ∀a, b ∈ G.

CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 61

4.2 Anéis

Um anel é um conjunto, R, composto por duas operações, + e ·, chamadas

de adição e multiplicação respectivamente, tal que ∀a, b, c ∈ R, os seguintes
axiomas são obedecidos:

• (A1 a A5) R é um grupo abeliano em relação à adição; isto é, R

satisfaz os axiomas A1 a A5 em relação à operação +. Assim, o inverso
de um elemento a com respeito à operação adição no anel é −a e o
elemento neutro desta operação é o 0.

• (M1) Operação fechada em R: Se a e b ∈ R, então a·b está também

em R.

• (M2) Associatividade: a · (b · c) = (a · b) · c, ∀a, b, c ∈ R.

• (M3) Distributividade: a · (b + c) = a · b + a · c, ∀a, b, c ∈ R.

Um anel é dito comutativo se satisfaz a seguinte condição adicional:

• (M4) Comutatividade: a · b = b · a, ∀a, b ∈ R.

Definimos um domı́nio de integridade, que é um anel comutativo que

obedece aos seguintes axiomas:

• (M5) Identidade: Existe um elemento 1 ∈ R tal que a · 1 = 1 · a =

a, ∀a, b ∈ R

• (M6) Sem divisores de zero: Se a, b ∈ R e ab = 0, então temos que

a = 0 ou b = 0.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 62

4.3 Corpos

Primeiramente, vamos definir o que é um corpo. Um corpo F, é um

conjunto de elementos com duas operações, + e ·, chamadas de adição e mul-
tiplicação respectivamente, todos os elementos a, b, c ∈ F seguem os seguintes
axiomas:

• (A1 a A5 e M1 a M6) F é um domı́nio de integridade, ou seja, F

satisfaz axiomas A1 a A5 e M 1 a M 6.

• (M7) Inverso Multiplicativo Para todo a ∈ F, exceto 0, existe um

elemento a−1 ∈ F tal que a · a−1 = a−1 · a = 1.

Em essência, um corpo é um conjunto no qual podemos fazer adição e mul-

tiplicação comutativa sem sair do conjunto e que contém o inverso multipli-
cativo de cada elemento.

4.3.1 Corpos Finitos da forma GF (p)

Nós definimos um corpo como um conjunto que obedece a todos os axi-

omas da seção anterior. Estes não são de interesse particular no contexto de
criptografia. Porém, corpos finitos desempenham um papel crucial em muitos
algoritmos criptográficos.
Pode ser mostrado que a ordem de corpos finitos (número de elementos)
deve ser uma potência de um primo, pn , onde n é um inteiro positivo. Nós
discutimos números primos na seção 3.4.
O corpo finito de ordem pn é geralmente escrito da forma GF (pn ); GF
significa “Galois Field”, em homenagem ao matemático que primeiro estudou
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 63

corpos finitos. Dois casos especiais são de interesse para nossos propósitos
neste trabalho.
Quando n = 1, nós temos o corpo finito GF (p); este corpo finito tem
uma estrutura diferente dos corpos finitos quando n > 1, por esta razão nós
também falaremos sobre os corpos finitos da forma GF (2n ).
Corpos Finitos de Ordem p
Sejam p um primo e GF (p) o corpo finito de ordem p, represen-
tado como um conjunto Zp de inteiros {0, 1, . . . , p − 1} juntamente com as
operações aritméticas módulo p.
Lembrem-se de que mostramos na seção 3.3 que o conjunto Zn de inteiros
{0, 1, . . . , n − 1}, juntamente com as operações aritméticas módulo n, é um
anel comutativo (veja a Tabela 3.3). Observamos que qualquer inteiro em
Zn tem um inverso se, e somente se, esse inteiro é relativamente primo em
relação a n 1 . Se n é primo, então todos os inteiros não negativos em Zn
são relativamente primos em relação a n, e portanto, existe um inverso para
todos os inteiros diferentes de zero em Zn , portanto, para Zp , nós podemos
adicionar mais uma propriedade:

• Inverso Multiplicativo (w−1 ) Para todo w ∈ Zp , w 6= 0, existe um

z ∈ Zp tal que w · z ≡ 1 (mod p)

Porque w é relativamente primo em relação a p, se nós multiplicarmos

todos os elementos de Zp por w, os restos resultantes são todos os elementos
de Zp permutados. Assim, exatamente um dos restos tem o valor 1. Portanto,
existe um inteiro em Zp (denominado w−1 ) que, quando multiplicado por w,
resulta em 1; portanto, Zp é de fato um corpo finito, aliás, podemos conferir
1
Como afirmamos na discussão da equação (3.7), dois inteiros são relativamente pri-
mos se o máximo divisor comum de ambos é 1.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 64

a equação (3.7) através do inverso de a:

Se (a · b) ≡ (a · c) (mod m), então b ≡ c (mod p) (4.1)

Basta multiplicar ambos os lados da equação (4.1) pelo inverso de a.

((a−1 ) · a · b) ≡ ((a−1 ) · a · c) (mod p)

b ≡ c (mod p)

Encontrando o Inverso Multiplicativo em GF (p)

É relativamente fácil encontrar o inverso de um elemento em GF (p) para
pequenos valores de p. Simplesmente montamos uma Tabela 4.1, e o resultado
desejado pode ser lido diretamente. No entanto, para grandes valores de p,
esta abordagem não é prática.
+ 0 1 2 3 4 5 6 · 0 1 2 3 4 5 6 w −w w−1
0 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 0 0 −
1 1 2 3 4 5 6 0 1 0 0 0 0 0 0 0 1 6 1
2 2 3 4 5 6 0 1 2 0 2 4 6 1 3 5 2 5 4
3 3 4 5 6 0 1 2 3 0 3 6 2 5 1 4 3 4 5
4 4 5 6 0 1 2 3 4 0 4 1 5 2 6 3 4 3 2
5 5 6 0 1 2 3 4 5 0 5 3 1 6 4 2 5 2 3
6 6 0 1 2 3 4 5 6 0 6 5 4 3 2 1 6 1 6
(a) Adição (b) Multiplicação (c) Inversa
Tabela 4.1: Aritmética em GF (7).

Se a e b são relativamente primos, então existe um inverso de b módulo

a, ou seja, se mdc(a, b) = 1 existe um b−1 ≤ a tal que b · b−1 = 1 (mod a).
Se a é um número primo e b ≤ a, então a e b são relativamente primos
e o mdc(a, b) = 1. Com isso podemos encontrar b−1 usando o Algoritmo de
Euclides Estendido.
Sendo assim, retomando a equação (3.10), podemos resolvê-la pelo Algo-
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 65

ritmo de Euclides Estendido:

ax + by = d = mdc(a, b)

Agora, se mdc(a, b) = 1, então nós temos que ax + by = 1. Usando a

igualdade da aritmética modular, definida na seção 3.3, nós podemos dizer
que:

(ax mod a + by mod a) mod a = 1 mod a

=⇒ 0 + (by mod a) = 1

Porém, se by mod a = 1, então y = b−1 e aplicando o Algoritmo Euclidi-

ano Estendido para equação (3.10) encontramos o valor do inverso multiplica-
tivo b se mdc(a, b) = 1. Considere o exemplo que apresentamos na Tabela 3.4,
temos que a = 1759 e b = 550. A solução da equação 1759x + 550y = 1, y é
igual 355.
Portanto, y = b−1 = 355. Para verificar que y é de fato o inverso de b,
calculamos 550 · 355 mod 1759 = 195250 mod 1759 = 1.

4.3.2 Corpos Finitos da Forma GF (2n )

Na subseção anterior, nós mencionamos que a ordem de um corpo finito deve

ser do tipo pn , no qual p é um número primo e n é um inteiro positivo. Na
subseção 4.3.1 nós analisamos um caso especial de corpos finitos de ordem
p. Descobrimos que, usando aritmética modular em Zp , todos os axiomas de
um corpo, citados na seção 4.1 estão satisfeitos. Para um polinômio sobre pn ,
com n > 1, operações módulo pn não formam um corpo. Nesta seção, nós
apresentamos que estruturas que satisfazem os axiomas para um corpo em
um conjunto com pn elementos e também GF (2n ).
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 66

Praticamente, todos os algoritmos, sejam eles de chaves simétricas ou

de chaves públicas (assimétricas), envolvem operações com aritmética nos
inteiros. Se uma das operações usadas no algoritmo é divisão, então pre-
cisamos trabalhar com aritmética sobre um corpo. Por conveniência e por
eficiência de implementação, nós precisamos operar com inteiros que se en-
caixam exatamente em um determinado número de bits, sem padrões de bits
desperdiçados. Isto é, desejamos trabalhar com números inteiros no intervalo
de 0 a 2n − 1 que se encaixem em uma palavra com n-bits.
Suponha que nós queremos definir um algoritmo de encriptação conven-
cional que opera dados de 8 bits de cada vez, e queremos realizar a di-
visão. Com 8 bits, nós podemos representar inteiros no intervalo de 0 a
255. Porém, 256 não é um número primo, de modo que com a aritmética
módulo Z256 , o conjunto Z256 não é corpo (pois para um polinômio sobre
pn , com n > 1, operações módulo pn não formam um corpo). O número
primo mais próximo de 256 é 251. Então, o conjunto Z251 , usando o módulo
251, é um corpo. Contudo, neste caso, o padrões de 8 bits representando
os números inteiros de 251 a 255 não seriam usados, resultando num uso
ineficiente de armazenamento.

Como o exemplo anterior indica, se todas as operações aritméticas forem

usadas e desejarmos representar uma gama completa de inteiros em n-bits,
então as operações módulo 2n não funcionarão. Equivalentemente, o con-
junto de inteiros módulo 2n para n > 1, não é um corpo finito de ordem
pn . Além disso, mesmo que o algoritmo de criptografia use apenas adição e
multiplicação, mas não divisão, o uso do conjunto Z2n é questionável.
Suponha que nós queremos usar um bloco de 3-bits em nosso algoritmo
de encriptação, usando apenas operações de adição e multiplicação. Então,
as operações 8 são bem definidas, como mostra a Tabela 3.1. Porém, note que
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 67

na matriz (b) de multiplicação, os inteiros diferentes de zero não aparecem na

mesma proporção de vezes. Por exemplo, existem apenas quatro ocorrências
de 3, mas doze ocorrências de 4. Por outro lado, como foi dito existem corpos
finitos da forma GF (2n ), então existe em particular um corpo finito de ordem
23 = 8. Isso é mostrado na Tabela 4.2, neste caso o número de ocorrências
de inteiros diferentes de zero é uniforme, para resumir temos:

Inteiro 1 2 3 4 5 6 7
Ocorrências em Z8 4 8 4 12 4 8 4
3
Ocorrências em GF (2 ) 7 7 7 7 7 7 7

Por enquanto, vamos deixar de lado a questão de como as matrizes da Ta-

bela 4.2 foram construı́das e, em vez disso, vamos fazer algumas observações.

• 1. As tabelas de adição e multiplicação são simétricas em relação a

diagonal principal, em conformidade com a propriedade da comutati-
vidade de adição e multiplicação. Esta propriedade é também exibida
na Tabela 3.1, que usa mod 8.

• 2. Todos os elementos não nulos possuem um inverso multiplicativo,

como pode ser visto na matriz (b) da Tabela 4.2, ao contrário do caso
da Tabela 3.1.

• 3. O esquema definido pela Tabela 4.2 satisfaz todos requisitos para

um corpo finito. Portanto, podemos nos referir a este esquema para
GF (23 ).

• 4. Por convenção, nós vamos usar uma notação de 3 bits para cada um
dos elementos de GF (23 ).

Intuitivamente, um algoritmo que mapeie os inteiros de maneira desigual

pode ser criptograficamente mais fraco do que aquele que fornece um ma-
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 68

peamento uniforme. Então, os corpos finitos da forma GF (2n ) são atrativos

para algoritmos criptográficos.
Podemos concluir que o ideal é procura um conjunto composto de 2n
elementos, juntamente com a definição de adição e multiplicação sobre o
conjunto que define um corpo. Podemos atribuir um único inteiro no intervalo
de 0 a 2n − 1 para cada elemento do conjunto.
000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111
+ 0 1 2 3 4 5 6 7 · 0 1 2 3 4 5 6 7 w −w w−1
000 0 0 1 2 3 4 5 6 7 000 0 0 0 0 0 0 0 0 0 0 0 −
001 1 1 0 3 2 5 4 7 6 001 1 0 1 2 3 4 5 6 7 1 1 1
010 2 2 3 0 1 6 7 4 5 010 2 0 2 4 6 3 1 7 5 2 2 5
011 3 3 2 1 0 7 6 5 4 011 3 0 3 6 5 7 4 1 2 3 3 6
100 4 4 5 6 7 0 1 2 3 100 4 0 4 3 7 6 2 5 1 4 4 7
101 5 5 4 7 6 1 0 3 2 101 5 0 5 1 4 2 7 3 6 5 5 2
110 6 6 7 4 5 2 3 0 1 110 6 0 6 7 1 5 3 2 4 6 6 3
111 7 7 5 5 4 3 2 1 0 111 7 0 7 5 2 1 6 4 3 7 7 4

(a) Adição (b) Multiplicação (c) Inversa

Tabela 4.2: Aritmética em GF (23 ).

Tenha em mente que não usaremos aritmética modular porque como

vimos isso não resulta em um corpo. Em vez disso, mostraremos como a
aritmética polinomial fornece um meio para construir o corpo desejado.

Aritmética Polinomial Modular

Considere o conjunto S de todos os polinômios de grau n − 1 ou menor
sobre o corpo Zp . Então, cada polinômio tem a forma

n−1
f (x) = an−1 xn−1 + an−2 xn−2 + · · · + a1 x + a0 = ai x i
X

i=0

na qual cada ai assume um valor no conjunto {0, 1, . . . , p − 1}. Existe um

total de pn polinômios diferentes em S.

Exemplo 1. Os polinômios neste conjunto são:

Com a definição apropriada das operações aritméticas, cada conjunto S
é um corpo finito. A definição consiste nos seguintes elementos:
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 69

0 x 2x
0 x x2 x2 + x
1 x + 1 2x + 1 2 2
1 x+1 x +1 x +x+1
2 x + 2 2x + 2
para p = 2 e n = 3 e 23 = 8
para p = 3 e n = 2 e 32 = 9

• 1. A aritmética segue as regras da aritmética polinomial usando as

regras básicas da álgebra.

• 2. Aritmética sobre os coeficientes é realizada módulo p, ou seja, usamos

as regras de aritmética para o corpo finito Zp .

• 3. Se a multiplicação resultar em um polinômio de grau maior que

n − 1, então o polinômio é reduzido em módulo por algum polinômio
irredutı́vel fixado m(x) de grau n, ou seja, dividimos por m(x) e man-
temos o resto. Para um polinômio f (x), o resto é expresso como r(x) =
f (x) mod m(x).

Nós vamos chamar o conjunto {f (x) mod m(x) | f (x) ∈ Zp [x]} de po-
linômios modulares de m.
O AES para 8 bits usa aritmética no corpo finito GF (28 ), com o polinômio
irredutı́vel m(x) = x8 + x4 + x3 + x + 1. Considere os dois polinômios f (x) =
x6 + x4 + x2 + x + 1 e g(x) = x7 + x + 1. Então

f (x) + g(x) = x7 + x6 + x4 + x2

f (x) · g(x) = x13 + x11 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + 1

Logo, f (x) · g(x) mod m(x) = x7 + x6 + 1.

Tal como acontece com a aritmética modular, temos a noção de classe

resı́duos, na aritmética polinomial modular. Se o polinômio m(x) tem grau n,
então a quantidade da classe resı́duos módulo m(x) consiste de pn elementos.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 70

A classe resı́duos [x+1], ( mod m(x)), consiste em todos os polinômios a(x)

tais que a(x) ≡ x + 1 (mod m(x)). Equivalentemente, a classe resı́duos
[x + 1] consiste em todos os polinômios a(x) que satisfazem a igualdade
a(x) mod m(x) = x + 1.

Pode-se mostrar que o conjunto de todos os polinômios modulares de

um polinômio de grau n irredutı́vel m(x) satisfaz os axiomas da seção 4.1
e, portanto, forma um corpo finito. Além disso, todos os corpos finitos de
determinada ordem são isomorfos; isto é, quaisquer duas estruturas de corpo
finito de uma determinada ordem são a mesma estrutura, mas a representação
ou rótulos dos elementos podem ser diferentes.

Para construir o corpo finito de ordem GF (23 ), nós precisamos escolher

um polinômio irredutı́vel de grau 3. Existem dois possı́veis: (x3 + x2 + 1) e
(x3 + x + 1). Da Tabela 4.3 temos GF (23 ) para o polinômio m(x) = x3 +
x + 1, mas porı́amos escolher m(x) = (x3 + x2 + 1). Note que este conjunto
de tabelas tem a mesma estrutura que a Tabela 4.2. Assim, conseguimos
encontrar um maneira de definir um corpo de ordem 23 .
Agora podemos ler adições e multiplicações da tabela facilmente. Por
exemplo, considere o binário 100 + 010 = 110. Isto é equivalente a x2 + x.
Também considere 100 · 010 = 011, isto é equivalente a x2 · x = x3 e reduzir
para x + 1.

Encontrando o Inverso Multiplicativo em GF (2n )

Assim como o Algoritmo de Euclides pode ser adaptado para encontrar o
mdc de dois polinômios, o Algoritmo Euclides Estendido pode ser adaptado
para encontrar o inverso de um polinômio.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 71

Especificamente, o algoritmo encontrará o inverso de b(x) módulo a(x) se

o grau de b(x) for menor do que o grau de a(x) e mdc(a(x), b(x)) = 1. Se
a(x) é um polinômio irredutı́vel, então ele não tem nenhum fator diferente
de si ou 1, portanto, temos que mdc(a(x), b(x)) = 1.
O algoritmo pode ser caracterizado da mesma maneira como fizemos com
o Algoritmo de Euclides Estendido (AEE) para os inteiros. Dado os po-
linômios a(x) e b(x) com o grau de a(x) maior do que o de b(x), nós deseja-
mos resolver a seguinte equação para os valores de v(x), w(x), e d(x), onde
d(x) = mdc(a(x), b(x)):

a(x)v(x) + b(x)w(x) = d(x)

Se d(x) = 1, então temos que w(x) é um inverso de b(x) módulo a(x). Da

Tabela 4.3 temos:
000 001 010 011 100 101 110 111
+ 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
000 0 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
2 2 2
001 1 1 0 x+1 x x +1 x x +x+1 x2 + x
010 x x x+1 0 1 x2 + x + 1 x2 + x x2 + 1 x2
011 x+1 x+1 x 1 0 x2 + x + 1 2
x +x x2 + 1 x2
100 x2 x2 x2 + 1 x2 + x x2 + x + 1 0 1 x x+1
2 2
101 x +1 x +1 x2 x2 + x + 1 x2 + x 1 0 x+1 x
110 x2 + x x2 + x x2 + x + 1 x2 x2 + 1 x x+1 0 1
111 x2 + x + 1 x2 + x + 1 x2 + x x2 + 1 x2 x+1 x 1 0
(a) Adição
000 001 010 011 100 101 110 111
· 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
000 0 0 0 0 0 0 0 0 0
001 1 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
010 x 0 x x2 x2 + x x+1 1 x2 + x + 1 x2 + 1
011 x+1 0 x+1 x2 + x x2 + 1 x2 + x + 1 x2 1 x
100 x2 0 x2 x + 1 x2 + x + 1 x2 + x x x2 + 1 1
101 x2 + 1 0 x2 + 1 1 x2 x x2 + x + 1 x+1 x2
110 x2 + x 0 6 7 1 5 3 2 4
2
111 x +x+1 0 x2 + x + 1 x2 + 1 x 1 x2 + 1 x2 x+1
(b) Multiplicação

Tabela 4.3: Aritmética Polinomial Modular x3 + x + 1.

CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 72

A Tabela 4.4 apresenta o calculo da inversa de (x2 + x + 1) mod (x8 +

x4 + x3 + x + 1). O resultado é (x7 + x + 1)−1 = (x7 ). Logo, temos que
(x7 + x + 1)(x7 ) ≡ 1 (mod (x8 + x4 + x3 + x + 1)).

Considerações Computacionais
Se o polinômio f (x) pertence a GF (2n ),

n−1
n−1 n−2
ai x i ,
X
f (x) = an−1 x + an−2 x + · · · + a1 x + a0 =
i=0

ele pode ser representado exclusivamente pela sequência de seus n coefi-

cientes (an−1 , an−2 , . . . , a0 ). Então, todo polinômio contido em GF (2n ) pode
ser representado por um número n − bits.
As Tabelas 4.2 e 4.3 apresentam as operações de adição e multiplicação
para GF (23 ) módulo m(x) = (x3 +x+1). A Tabela 4.2 usa a representação
binária, e a Tabela 4.3 usa a representação polinomial.

Adição: A soma de polinômios é realizada pela adição dos coeficien-

tes correspondentes, e no caso de polinômios sobre Zp , além disso, é uma
operação XOR. Então, a adição de dois polinômios em GF (2n ) corresponde
a uma operação XOR bit-a-bit.
Considere os dois polinômios pertencentes a GF (28 ) em nosso exemplo
anterior: f (x) = x6 + x4 + x2 + x + 1 e g(x) = x7 + x + 1, além disso,
considere as formas de soma: (1) polinomial, (2) binária e (3) hexadecimal 2
respectivamente:

2
Aqui cada um dos dois grupos de 4 bits em um byte é denominado por um único
caractere hexadecimal, e os dois caracteres são incluı́dos em colchetes.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 73

• (1) (x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2 + 2x + 2

• (2) (01010111) ⊕ (10000011) = (11010100)

• (3) {57} ⊕ {83} = {D4}

Multiplicação: Não existe uma operação XOR simples que realize mul-
tiplicação em GF (2n ), porém, ela é razoavelmente e fácil de implementar
com um computador. Vamos discutir a técnica usando o polinômio m(x) =
x8 + x4 + x3 + x + 1 e corpo finito GF (28 ) que é usado no AES. A técnica é
baseada na observação de que

x8 mod m(x) = m(x) − x8 = (x4 + x3 + x + 1) (4.2)

a(x) = x8 + x4 + x3 + x + 1; v−1 (x) = 1; w−1 (x) = 0

Inicialização
b(x) = x7 + x + 1; v0 (x) = 0; w0 (x) = 1
q1 (x)x; r1 (x) = x + x + x2 + 1
4 3
Iteração 1
v1 (x) = 1; w1 (x) = x
3 2
q2 (x) = x + x + 1; r2 (x) = x
Iteração 2
v2 (x) = x3 + x2 + 1; w2 (x) = x4 + x3 + x + 1
q3 (x) = x3 + x2 + x; r3 = 1
Iteração 3
v3 = x6 + x2 + x + 1; w3 (x) = x7
q4 (x) = x; r4 (x) = 0
Iteração 4
v4 (x) = x7 + x + 1; w4 (x) = x8 + x4 + x3 + x + 1
d(x) = r3 (x) = mdc(a(x), b(x)) = 1
Resultado −1
w(x) = w3 (x) = (x7 + x + 1) mod (x8 + x4 + x3 + x + 1) = x7

Tabela 4.4: Euclides Estendido [(x8 + x4 + x3 + x + 1), (x7 + x + 1)]

A equação (4.2) pode ser verificada como exemplo de uma relação mais
geral que sempre é é verdadeira para GF (2n ); Se p(x) tem grau n, então
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 74

xn mod p(x) = p(x) − xn .

Agora, vamos considerar um polinômio em GF (28 ), que tem a forma
f (x) = b7 x7 +b6 x6 +b5 x5 +b4 x4 +b3 x3 +b2 x2 +b1 x+b0 . Se nós multiplicarmos
por x, nós temos

x · f (x) = (b7 x8 + b6 x7 + b5 x6 + b4 x5 + b3 x4
(4.3)
3 2
+ b2 x + b1 x + b0 x) mod m(x)

Se b7 = 0, então o resultado é um polinômio de menor grau do que 8, que já

está em forma reduzida, e computacionalmente não faz diferença. Se b7 = 1,
então redução do módulo m(x) é obtida usando a equação (4.2):

x · f (x) = (b6 x7 + b5 x6 + b4 x5 + b3 x4 + b2 x3 + b1 x2 + b0 x)

+ (x4 + x3 + x + 1)

Segue-se que a multiplicação por x (isto é, 00000010) pode ser implemen-
tada como um deslocamento um 1-bit seguido por um XOR condicional com
(00011011), o qual representa (x4 + x3 + x + 1). Resumindo,


(b 6 b5 b4 b3 b3 b1 b0 0), se t = 1


x · f (x) = (4.4)

6 b5 b4 b3 b3 b1 b0 0) ⊕ (00011011), se b7 = 1
(b


multiplicando pela maior potência de x atingida por repetidas aplicações

da equação (4.4) e adicionando os resultados intermediários por qualquer
constante em GF (28 ).
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 75

Num exemplo anterior, nós vimos que para f (x) = x6 + x4 + x2 + x + 1,

g(x) = x7 + x + 1, m(x) = x8 + x4 + x3 + x + 1, nós temos f (x) · g(x)
mod m(x) = x7 +x6 +1. Refazendo esta conta utilizando a notação decimal,
nós precisamos calcular (01010111) · (10000011). Primeiro, determinamos
o resultado da multiplicação para potências de x:

(01010111) · (00000010) = (10101110)

(01010111) · (00000100) = (01011100) ⊕ (00011011) = (01000111)

(01010111) · (00001000) = (10001110)

(01010111) · (00010000) = (00011100) ⊕ (00011011) = (00000111)

(01011011) · (00100000) = (00001110)

(01010111) · (01000000) = (00011100)

(01010111) · (10000000) = (00111000)

Então,

(01010111) · (10000011) = (01010111) ⊕ (10101110) ⊕ (00111000)

= (11000001)

que é equivalente a x7 + x6 + 1.

Usando Gerador
Apresentaremos uma técnica equivalente para construir um corpo finito
da forma GF (2n ), usando o mesmo polinômio irredutı́vel, que é mais conve-
niente. Para começar, precisamos de duas definições:
Um gerador g de um corpo finito F de ordem q (contendo q elementos)
é um elemento cujas primeiras q − 1 potências geram todos os elementos não
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 76

nulos de F . Isto é, os elementos de F consistem em {0, g 0 , g 1 , . . . , g q−2 }.

Seja um corpo F cujas operações são definidas módulo f (x), onde f (x) é
um polinômio irredutı́vel como vimos anteriormente. Um elemento b contido
em F é chamado de raiz do polinômio se f (b) = 0.
Por fim, pode ser mostrado que uma raiz g de um polinômio irredutı́vel
é um gerador de um corpo finito cujas operações são definidas módulo esse
polinômio.
Considere o corpo finito GF (23 ), cujas operações são definidas módulo
f (x) = x3 + x + 1. Então, o gerador g deve satisfazer f (g) = g 3 + g +
1 = 0. Tenha em mente, como discutido anteriormente, que não precisamos
encontrar uma solução numérica para igualdade. Em vez disso, lidamos com
aritmética polinomial em que aritmética nos coeficientes é realizada módulo
2. Assim sendo, a solução para seguinte equação é g 3 = −g − 1 = g + 1. É
possı́vel perceber que g de fato gera todos os polinômios de grau menor que
3, pois:

g 4 = g(g 3 ) = g(g + 1) = g 2 + g

g 5 = g(g 4 ) = g(g 2 + g) = g 3 + g 2 = g 2 + g + 1

g 6 = g(g 5 ) = g(g 2 + g + 1) = g 3 + g 2 + g = g 2 + 2g + 1 = g 2 + 1

g 7 = g(g 6 ) = g(g 2 + 1) = g 3 + g = 2g + 1 = 1 + g 0

Vimos que as potências de g geram todos os polinômios não negativos em

GF (23 ). Além disso, deve ser claro que g k = g k mod 7
para qualquer inteiro
k. A Tabela 4.5 apresenta os resultados do gerador de GF (23 ) usando o
polinômio f (x) = x3 + x + 1.
Esta representação por potências torna a multiplicação fácil. Para mul-
tiplicar na notação de potência, basta adicionar ao expoente módulo 7. Por
exemplo, g 4 + g 6 = g 10 mod 7 = g 3 = g + 1. O mesmo resultado é alcançado
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 77

Potência Polinomial Binaria Decimal (Hex)

0 0 000 0
0 7
g (= g ) 1 001 1
g1 g 010 2
2 2
g g 100 4
g3 g+1 011 3
4 2
g g +g 110 6
g5 g2 + g + 1 111 7
6 2
g g +1 101 5

Tabela 4.5: Gerador de GF (23 ) usando x3 + x + 1

usando aritmética polinomial:

Temos que g 4 = g 2 +g e g 6 = g 2 +1, então, (g 2 +g)·(g 2 +1) = g 4 +g 3 +g 2 +g,
em seguida precisamos determinar (g 4 + g 3 + g 2 + g) mod (g 3 + g + 1). Nós
obtemos, então, o resultado g + 1, o mesmo obtido usando a notação de
potência.
A Tabela 4.6 apresenta a adição e a multiplicação para GF (23 ) usando
a notação de potência. Note que isso produz os resultados idênticos para a
representação polinomial (Tabela 4.3) com algumas linhas e colunas inter-
cambiadas.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 78

000 001 010 100 011 110 111 101

+ 0 1 G g2 g3 g4 g5 g6
000 0 0 1 G g2 g+1 g2 + g g2 + g + 1 g2 + 1
2
001 1 1 0 g+1 g +1 g g2 + g + 1 g2 + g g2
010 g g g+1 0 g2 + g 1 g2 g2 + 1 g2 + g + 1
100 g2 g2 g2 + 1 g2 + g 0 g2 + g + 1 g g+1 1
011 g3 g+1 g 1 g2 + g + 1 0 g2 + 1 g2 g2 + g
110 g4 g2 + g g2 + g + 1 g2 g g2 + 1 0 1 g+1
111 g5 g2 + g + 1 g2 + g g2 + 1 g+1 g2 1 0 g
101 g6 g2 + 1 g2 2
g +g+1 1 2
g +g g+1 g 0
(a) Adição
000 001 010 100 011 110 111 101
· 0 1 G g2 g3 g4 g5 g6
000 0 0 0 0 0 0 0 0 0
001 1 0 1 G g2 g+1 g2 + g g2 + g + 1 g2 + 1
010 g 0 g g2 g+1 g2 + g g2 + g + 1 g2 + 1 1
100 g2 0 g2 g+1 g2 + g g2 + g + 1 g2 + 1 1 g
011 g3 0 g+1 g2 + g g2 + g + 1 g2 + 1 1 g g2
110 g4 0 g2 + g g2 + g + 1 g2 + 1 1 g2 + g + 1 g2 g+1
111 g5 0 g2 + g + 1 g2 + 1 1 g g2 g+1 g2 + g
101 g6 0 g2 + 1 1 g g2 g+1 g2 + g g2 + g + 1
(b) Multiplicação

Tabela 4.6: GF (23 ) Aritmética usando geradores para o polinômio (x3 +x+1).

4.4 Resumo
Neste capı́tulo, definimos o que são grupos, anéis e suas propriedades. Defi-
nimos o que são corpos, como construir um corpo finito de ordem p, onde p
é primo. Especificamente, definimos o conjunto GF (p) com as propriedades:

• 1. GF (p) consiste em p elementos.

• 2. As operações + e · são definidas sobre o corpo finito GF (p). As

operações de adição, multiplicação podem ser executadas sem sair deste
conjunto. Cada elemento do conjunto diferente de 0 tem um inverso.

• 3. São validas as propriedades de corpo, de domı́nio de integridade e

as propriedades de anel.
CAPÍTULO 4. GRUPOS, ANÉIS E CORPOS 79

Nós vimos que os elementos de GF (p) são as classes de resı́duos repre-

sentadas pelos inteiros {0, 1, . . . , p − 1} e que as operações aritméticas são
adição e multiplicação mod p.

Além disso, apresentamos como construir um corpo finito de ordem 2n .

Especificamente, definimos o conjunto GF (2n ) com as propriedades:

• 1. GF (2n ) consiste de 2n elementos.

• 2. As operações + e · são bem definidas sobre um corpo finito GF (2n ).

As operações de adição, multiplicação podem ser executadas sem sair
dele. Cada elemento do conjunto diferente de 0 tem um inverso.

• 3. São validas as propriedades de corpo, de domı́nio de integridade e

as propriedades de anel.

Vimos que os elementos de GF (2n ) podem ser definidos como o conjunto

das classes de resı́duos módulo m(x) dos polinômios com coeficientes em Z2
de grau n − 1 ou menor e o nulo, onde m(x) é um polinômio irredutı́vel de
grau n. E também que eles podem ser representados por um valor com n-bits.
Também vimos que uma definição equivalente de um corpo finito GF (2n )
faz o uso de um gerador e que a aritmética é definida usando potências do
gerador.
Capı́tulo 5

Curvas Elı́pticas

Neste capı́tulo, apresentamos definições fundamentais sobre curvas elı́pticas

que servirão de base para o capı́tulo 6. Mais detalhes podem ser encontrados
no livro de Anthony W. Knapp e Neal Koblitz, “Elliptic Curves” [2] e no
de William Stallings, “Cryptography and Network Security” [18] que foram
utilizados como referências.
1
Uma curva elı́ptica é uma curva algébrica plana definida por uma
equação não-singular da forma:

y 2 = x3 + ax + b. (5.1)

Formalmente, seja E uma curva elı́ptica sobre um corpo K, E é uma curva

cúbica não-singular em duas variáveis f (x, y) = 0 com um ponto racional k
(que deve ser um “ponto no infinito” O) da curva no plano projetivo. O corpo
K pode ser, por exemplo, o conjunto dos números reais.
Para compreender melhor esta definição precisamos revisar o conceito de
grupo abeliano. Em seguida, examinaremos o conceito de curvas elı́pticas
1
ANTHONY W. KNAPP. A Course in Number Theory and Cryptography. Springer,
1994

80
CAPÍTULO 5. CURVAS ELÍPTICAS 81

definidas sobre o conjunto dos números reais. Isto será seguido por um olhar
sobre curvas elı́pticas definidas em corpos finitos. Finalmente, nós seremos
capazes de examinar codificadores de curvas elı́pticas. Na seção 4.1 falamos
de grupos abelianos, vamos relembrá-los:

Grupos Abelianos
Um grupo abeliano é um conjunto, G, juntamente com uma operação 2
• (chamada lei do grupo G) que combina quaisquer dois elementos a e b
para formar outro elemento, denotado por a • b. Para se qualificar como um
grupo, o conjunto e a operação, {G, •}, devem satisfazer quatro requisitos
conhecidos como axiomas do grupo:

• (A1) Operação fechada em G: Para todo a e b ∈ G, o resultado da

operação, a • b, também está em G.

• (A2) Associatividade: Para todo a, b e c ∈ G, a • (b • c) = (a • b) • c.

• (A3) Identidade: Há um elemento e ∈ G tal que a • e = e • a = a

para todo a ∈ G.

• (A4) Inverso: Para cada a ∈ G, existe um elemento a0 ∈ G, comu-

mente denotado a−1 (ou −a, se a operação for denotada +) tal que
a • a0 = a0 • a = e, onde e é o elemento identidade.

• (A5) Comutatividade: a • b = b • a, ∀a, b ∈ G.

Uma curva elı́ptica é definida por uma equação em duas variáveis e

seus respectivos coeficientes como já observamos na equação (5.1). Para crip-
tografia, as variáveis e coeficientes são restritos a elementos em um corpo
2
O operador • é genérico e pode ser referir a adição, multiplicação, ou qualquer outro
operador matemático.
CAPÍTULO 5. CURVAS ELÍPTICAS 82

finito. Antes de discutirmos sobre isto, nós vamos olhar as curvas elı́pticas
nas quais as variáveis e coeficientes são números reais. Este caso é mais fácil
de compreender por enquanto.

5.1 Curvas Elı́pticas sobre R

Curvas Elı́pticas não são elipses. Elas são assim chamadas porque eram
descritas por equações cúbicas, similares àquelas usadas para calcular a
comprimento de uma elipse. No geral, equações cúbicas para curvas elı́pticas
assumem a seguinte forma, conhecida como Equação de Weierstrass:

y 2 + axy + by = x3 + cx2 + dx + e

onde a, b, c, d, e ∈ R e x e y também assumem valores nos números reais 3 ,

para o nosso propósito, é suficiente nos limitarmos a equação (5.1).
Tal equação é dita cúbica, ou de grau 3 porque seu maior expoente é o
3, como já vimos na definição de uma curva elı́ptica, o O é um elemento
chamado de “ponto no infinito” ou o ponto zero, nós vamos discutir isto em
breve. Para desenhar esta curva, precisamos resolver esta equação:

√
y= x3 + ax + b

3
Note que x e y são variáveis, que assumem valores. Isto está em contraste com nossa
discussão sobre anéis e corpos polinomiais no capı́tulo 3, em que x foi tratado como
indeterminado.
CAPÍTULO 5. CURVAS ELÍPTICAS 83

Para valores fixos de a e b, o gráfico consiste em valores positivos e nega-

tivos de y para cada valor de x. Então, cada curva é simétrica sobre y = 0.
Defina o conjunto dos pontos da curva elı́ptica E(a, b) consistindo em
todos os pontos (x, y) que satisfazem a equação (5.1) juntamente com o
elemento O.
Portanto, usar um valor diferente do par (a, b) resulta em um conjunto
diferente de E(a, b). Podemos gerar diferentes curvas conforme retratado na
figura 5.1. Lembremos que a definição da curva elı́ptica também requer que
a curva seja não-singular.

b = −1 b=0 b=1 b=2

a = −2
a = −1
a=0
a=1

y 2 = x3 + a · x + b

Figura 5.1: Exemplos de curvas elı́pticas

CAPÍTULO 5. CURVAS ELÍPTICAS 84

Descrição Geométrica
Podemos dizer que um grupo pode ser definido baseado no conjunto
E(a, b) para valores especı́ficos de a e b na equação (5.1), se a seguinte
condição for atendida:

4a3 + 27b2 6= 0. (5.2)

Para definir o grupo, nós devemos definir uma operação, que vamos cha-
mar de adição e denotar por +, para o conjunto E(a, b), onde a e b satisfazem
a equação (5.2). Em termos geométricos, as regras para adição podem ser de-
claradas da seguinte forma: Se três pontos em uma curva elı́ptica estão em
linha reta, então sua soma é O. A partir desta definição, nós podemos definir
as regras de adição de uma curva elı́ptica.

• 1. O serve como identidade aditiva. Portanto, O = −O e para qualquer

ponto P na curva elı́ptica, P + O = P . No que segue, nós assumimos
que P 6= O e Q 6= O.

• 2. O oposto de um ponto P é o ponto com a mesma coordenada x,

porém, o oposto da coordenada y; Isso é, se P = (x, y), então −P =
(x, −y). Note que estes dois pontos e ponto no infinito podem ser unidos
por uma linha vertical, isto é, P + (−P ) + O = P − P + O = O.

• 3. Para somar dois pontos P e Q com diferentes valores da coordenada

x, deve-se desenhar uma linha reta entre estes dois pontos e encontrar
o terceiro ponto R na intersecção com a curva (a menos que a linha
seja tangente à curva em P ou Q, neste caso nós temos que R = P
CAPÍTULO 5. CURVAS ELÍPTICAS 85

ou R = Q, respectivamente). Para formar uma estrutura de grupo, nós

definimos a adição como: P + Q = −R, ou seja, nós definimos P + Q
como a imagem espelhada (com respeito ao eixo x) do terceiro ponto
de intersecção.

• 4. A interpretação geométrica do item anterior também se aplica a dois

pontos, P e −P , com a mesma coordenada x. Os pontos são unidos por
uma linha vertical, que pode ser visto também como a interseção da
curva no ponto infinito. Por isso, temos que P + (−P ) = O, que é
consistente com o item (2).

• 5. Para multiplicar um ponto Q por 2, desenhe a linha tangente e

encontre o outro ponto de interseção S. Então Q + Q = 2Q = −S.

Com a lista de regras acima, pode-se mostrar que o conjunto E(a, b) é

um grupo abeliano.

Descrição Algébrica
Nós apresentamos alguns resultados que nos possibilitam o cálculo da
4
adição sobre curvas elı́pticas. Para dois pontos distintos, P = (xP , yP ) e
Q = (xQ , yQ ), que são diferentes de zero, a inclinação da reta r que os une
é ∆ = (yQ − yP )/(xQ − xP ). Existe exatamente um outro ponto no qual r
intercepta a curva elı́ptica, e que é o oposto da soma de P e Q. Após algumas
manipulações algébricas, podemos expressar a soma R = P + Q da seguinte
maneira:
4
Para se aprofundar nesta explicação veja mais detalhes no livro referência [2] desta
seção.
CAPÍTULO 5. CURVAS ELÍPTICAS 86

xR = ∆2 − xP − xQ
(5.3)
yR = −yP + ∆(xP − xR )

Nós também precisamos ser capazes de somar um ponto a si mesmo:

P + P = 2P = R. Quando yP 6= 0, as expressões são:
!
3x2P + a 2
xR = − 2xP
2yP
! (5.4)
3x2P + a
yR = (xP − xP ) − yP
2yP

5.2 Curvas Elı́pticas sobre Zp

A Criptografia de Curva Elı́ptica faz uso de curvas elı́pticas em que as
variáveis e coeficientes são todos restritos a elementos de um corpo finito.
Duas famı́lias de curvas elı́pticas são usadas em aplicações criptográficas:
curvas primárias sobre Zp e curvas binárias sobre GF (2m ) [6]. Para uma
curva primária definida sobre Zp , usamos uma equação cúbica na qual as
variáveis e coeficientes todos assumem valores no conjunto de inteiros de 0 a
p − 1 e realizamos cálculos em módulo p. Para uma curva binária definida
sobre GF (2m ), as variáveis e coeficientes assumem valores em GF (2m ) e os
cálculos são realizados sobre GF (2m ), além disso, salientamos que as curvas
primárias são melhores para aplicações de software pois as operações estendi-
das de processamento (“bit-fiddling”) não são necessárias, mas são necessárias
por curvas binárias; e que as curvas binárias são melhores para aplicações de
hardware, nas quais são necessárias pouquı́ssimas portas lógicas para criar
um sistema criptográfico poderoso e rápido. Examinamos essas duas famı́lias
CAPÍTULO 5. CURVAS ELÍPTICAS 87

nesta seção e na próxima.

Existe interpretação geométrica das curvas elı́pticas sobre os corpos fini-
tos. A interpretação algébrica usada para a aritmética de uma curva elı́ptica
sobre os números reais é facilmente transferida, e esta é a abordagem que
tomamos.
Para curvas elı́pticas sobre Zp , assim como nos números reais, nos limita-
mos à equação da forma (5.1), porém neste caso tanto os coeficientes quanto
as variáveis limitam-se a Zp :

y 2 mod p = (x3 + ax + b) mod p (5.5)

Por exemplo, a equação (5.5) é satisfeita para a = 1, b = 1, x = 9, y = 7

e p = 23

72 mod 23 = (93 + 9 + 1) mod 23

49 mod 23 = 739 mod 23

3=3

Agora considere o conjunto Ep (a, b), que consiste de todos os pares (x, y) ∈
Zp × Zp que satisfazem a equação (5.5), junto com um ponto no infinito O,
onde os coeficientes a, b também são elementos de Zp e, neste caso, dizemos
que Ep (a, b) é dado pela equação (5.5).
Por exemplo, seja p = 23 e considere uma curva elı́ptica y 2 = x3 + x +
1. Para o conjunto E23 (1, 1), estamos interessados apenas nos inteiros não
negativos no quadrante de (0, 0) a (p − 1, p − 1) que satisfazem a equação
mod p. A tabela 5.1 lista os pontos (exceto o O) que são parte de E23 (1, 1). A
figura 5.2 plota os pontos de E23 (1, 1); note que os pontos, com uma exceção,
são simétricos em relação a y = 11.5.
CAPÍTULO 5. CURVAS ELÍPTICAS 88

(0, 1) (6, 4) (12, 19)

(0, 22) (6, 19) (13, 7)
(1, 7) (7, 11) (13, 16)
(1, 6) (7, 12) (17, 3)
(3, 10) (9, 7) (17, 20)
(3, 13) (9, 16) (18, 3)
(4, 0) (11, 3) (18, 20)
(5, 4) (11, 20) (19, 5)
(5, 19) (12, 4) (19, 18)

Tabela 5.1: Pontos da curva elı́ptica E23 (1, 1)

CAPÍTULO 5. CURVAS ELÍPTICAS 89

y ∈ Z23
•
• ••
•• •
•
• • •

•
•
•
•

• • •
•
•• •
• ••
•
• x ∈ Z23

y 2 = x3 + x + 1 ∈ Z23

Figura 5.2: A curva elı́ptica E23 (1, 1)

Pode ser demonstrado que um grupo abeliano finito, pode ser definido
com base no conjunto E p (a, b) dado que (x3 + ax + b) mod p não tem fatores
repetidos, isto é equivalente à condição:

(4a3 + 27b2 ) mod p 6= 0 mod p. (5.6)

Observe que a equação (5.6) tem a mesma forma que a equação (5.2).
A regra para adição sobre Ep (a, b) corresponde a técnicas algébricas des-
critas para curvas elı́pticas definidas sobre os números reais. Para todos os
pontos p, Q ∈ Ep (a, b):
CAPÍTULO 5. CURVAS ELÍPTICAS 90

• 1. P + O = P

• 2. Se P = (xP , yP ), então P + (xP , −yP ) = O. O ponto (xP , −yP )

é o oposto de P , denotado por −P , por exemplo, em E23 (1, 1) para
P = (13, 7), nós temos que −P = (13, −7). Porém, −7 mod 23 = 16,
por isso, −P = (13, 16), que também está em E23 (1, 1).

• 3. Se P = (xP , yP ) e Q = (xQ , yQ ) com P 6= −Q, então R = P + Q =

(xR , yR ) é determinado pelas seguintes regras:

xR = (λ2 − xP − xQ ) mod p

yR = (λ(xP − xR ) − yP ) mod p

onde 
y −y
 
 xQ −xP mod p, se P 6= Q


Q P
λ= 
2 +a

 3x


 2y P
P
mod p, se P = Q

• 4. Multiplicação é definida por repetidas somas, por exemplo, 4P =

P + P + P + P . Seja P = (3, 10) e Q = (9, 7) em E23 (1, 1), então,

7 − 10 −3 −1
     
λ= mod 23 = mod 23 = mod 23 = 11
9−3 6 2
xR = (112 − 3 − 9) mod 23 = 109 mod 23 = 17

yR = (11(3 − 17) − 10) mod 23 = −164 mod 23 = 20

Logo, P + Q = (17, 20). Para encontrar 2P , temos que

!
3(32 ) − 1 5 1
   
λ= mod 23 = mod 23 = mod 23 = 6
2 × 10 20 4
CAPÍTULO 5. CURVAS ELÍPTICAS 91

Para encontrar o inverso multiplicativo no passo 4 na equação anterior

em Z23 , podemos usar o Algoritmo Euclides Estendido definido na seção 4.1.
Para confirmar, note que (6 · 4) mod 23 = 24 mod 23 = 1.

xR = (62 − 3 − 3) mod 23 = 30 mod 23 = 7

yR = (6(3 − 7) − 10) mod 23 = (−34) mod 23 = 12

e 2P = (7, 12). Para determinar a segurança das várias cifras de curvas

elı́pticas, é interessante saber a quantidade de pontos em um grupo abeliano
finito definido a partir de uma curva elı́ptica. No caso do grupo finito Ep (a, b),
o número de pontos N é delimitado por

√ √
p+1−2 p≤N ≤p+1+2 p

Observe que o número de pontos em Ep (a, b) é, aproximadamente, igual ao

números de elementos em Zp , isto é, p elementos.

5.3 Curvas Elı́pticas sobre GF (2m)

Lembre-se de que no capı́tulo 4 falamos que um corpo finito da forma
GF (2m ) consiste de 2m elementos, juntamente com operações de adição e
multiplicação que podem ser definidas sobre polinômios. Para curvas elı́pticas
sobre GF (2m ), nós usamos uma equação cúbica na qual as variáveis e os
coeficientes assumem valores em GF (2m ) para algum número m no qual os
cálculos são realizados usando as regras de aritmética em GF (2m ).
Acontece que a forma da equação cúbica apropriada para aplicações crip-
tográficas para curvas elı́pticas é um pouco diferente em GF (2m ) do que a
CAPÍTULO 5. CURVAS ELÍPTICAS 92

forma usada em Zp . A forma apropriada é esta:

y 2 + xy = x3 + ax2 + b, (5.7)

(0, 1) (g 5 , g 3 ) (g 9 , g 13 )
(1, g 6 ) (g 5 , g 11 ) (g 10 , g)
(1, g 13 ) (g 6 , g 8 ) (g 10 , g 8 )
(g 3 , g 8 ) (g 6 , g 14 ) (g 12 , 0)
(g 3 , g 13 ) (g 9 , g 10 ) (g 12 , g 12 )

Tabela 5.2: Pontos na Curva Elı́ptica E24 (g 4 , 1)

onde se compreende que as variáveis x e y e os coeficientes a e b são

elementos de GF (2m ) e que os cálculos são realizados em GF (2m ).
Agora vamos considerar o conjunto E2m (a, b) consistindo de todos os pares
de inteiros (x, y) que satisfazem a equação (5.7), junto com os pontos no
infinito O.
Por exemplo, vamos usar o corpo finito GF (24 ) com o polinômio irre-
dutı́vel f (x) = x4 + x + 1. Isso produz um gerador g que satisfaz f (g) = 0
com o valor de g 4 = g + 1, ou em binário, g = 0010. Podemos desenvolver as
as potências de g da seguinte maneira:

g0 = 0001 g4 = 0011 g 8 = 0101 g 12 = 1111

g1 = 0010 g5 = 0110 g 9 = 1010 g 13 = 1101
g2 = 0100 g6 = 1100 g 10 = 0111 g 14 = 1001
g3 = 1000 g7 = 1011 g 11 = 1110 g 15 = 0001

Por exemplo, g 5 = (g 4 )(g) = g 2 + g = 0101.

Agora considere a curva elı́ptica y 2 + xy = x3 + g 4 x2 + 1. Neste caso,
a = g 4 e b = g 0 = 1. Um ponto que satisfaz esta equação é (g 5 , g 3 ):
CAPÍTULO 5. CURVAS ELÍPTICAS 93

(g 3 )2 + (g 5 )(g 3 ) = (g 5 )3 + (g 4 )(g 5 )2 + 1

g 6 + g 8 = g 15 + g 14 + 1

1100 + 0101 = 0001 + 1001 + 0001

1001 = 1001

A tabela 5.2 lista os pontos (com exceção do O) que são parte de E24 (g 4 , 1),
a figura 5.3 plota os pontos de E24 (g 4 , 1).

y ∈ GF (2m )

•
•
• • •
•
•
•

• • •

•
• x ∈ GF (2m )

Figura 5.3: A Curva Elı́ptica E24 (g 4 , 1)

Pode ser mostrado que um grupo abeliano finito podem ser definido com
base no conjunto E2m (a, b), desde que b 6= 0. As regras para adição pode ser
CAPÍTULO 5. CURVAS ELÍPTICAS 94

declaradas da seguinte forma. Para todos os pontos P , Q ∈ E2m (a, b):

• 1. P + O = P .

• 2. Se P = (xP , yP ), então P +(xP , xP +yP ) = O. O ponto (xP , xP +yP )

é o oposto de P , isto é, denotamos por −P .

• 3. Se P = (xP , yP ) e Q = (xQ , yQ ) com P 6= −Q, então P 6= Q e

R = P + Q = (xR , yR ) é determinado pelas seguintes regras:

xR = λ 2 + λ + xP + xQ + a

yR = λ(xP − xR ) + xR + yP

onde
!
yQ + yP
λ=
xQ + xP

• 4. Se P = (xP , yP ), então R = 2P = (xR , yR ) é determinado pelas

seguintes regras:

xR = λ2 + λ + a

yR = xP2 (λ + 1x)R

onde

yP
 
λ = xP +
xP
CAPÍTULO 5. CURVAS ELÍPTICAS 95

5.4 Resumo
Vimos neste capı́tulo que a CCE é uma alternativa em relação ao padrão
RSA. Definimos as curvas elı́pticas e que elas pertencem aos corpos finitos,
além disso, a CCE é baseada em curvas elı́pticas, e esta segue as propriedades
de um grupo abeliano, por fim, demos uma explicação algébrica e geométrica
das curvas elı́pticas.
Capı́tulo 6

Aplicação à Criptografia

Neste capı́tulo abordaremos os conceitos tratados nos capı́tulos anteriores

aplicados à Criptografia de Curva Elı́ptica.
A maioria dos produtos e padrões que usam criptografia de chave pública,
para criptografar assinaturas digitais usam RSA [16]. O comprimento da
chave para a segurança e o uso da RSA aumentou nos últimos anos, e isso
colocou uma carga de processamento mais “pesada” em aplicativos que usam
este padrão.
Este fardo tem ramificações, especialmente, para sites de comércio eletrônico
que realizam um grande número de transações seguras. Um sistema concor-
rente desafia a RSA: Criptografia de Curva Elı́ptica (CCE).
A principal atração da CCE, em comparação com a RSA, é que parece
oferecer segurança igual para um tamanho de chave muito menor, reduzindo
assim a sobrecarga de processamento. Por outro lado, mesmo que a teoria
da CCE tenha sido escrita faz algum tempo, apenas recentemente o seu uso
começou a aparecer com mais frequência, e despertou maior interesse dos
cripto-analı́ticos, paralelo a isto surgiu também sondagens sobre a fraquezas
da CCE. Assim, o nı́vel de confiança na CCE tem sido aprimorado, frequen-

96
CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 97

temente, para se tornar padrão em muitas aplicações.

CCE é, fundamentalmente, mais difı́cil de explicar do que RSA ou Diffie-
Hellman [4], e uma descrição matemática completa está além do escopo deste
trabalho de conclusão de curso.
Uma série de cifras de chave pública baseia-se no uso de grupo abeliano.
Por exemplo, em Diffie-Hellman a troca de chaves envolve multiplicar pares
de inteiros diferentes de zero módulo um número primo q. Chaves são gera-
das por exponenciação sobre grupos. Para atacar as cifras construı́das pelo
algoritmo Diffie-Hellman [4], o invasor deve encontrar k dado a e ak ; note
que isto é um problema logarı́tmico.
Em Criptografia de Curva Elı́ptica, uma operação de multiplicação é
usada e, como vimos, a multiplicação neste conjunto é equivalente a várias
adições dos pontos da curva elı́ptica. Portanto, a criptoanálise tem como uma
das suas funções determinar o valor de k dado a e (a · k).

6.1 Criptografia de Curva Elı́ptica

A operação de adição em Criptografia de Curva Elı́ptica (CCE) é a contrapar-
tida da multiplicação modular no RSA, e adição múltipla é a contrapartida
de exponenciação modular. Para formar um sistema criptográfico usando cur-
vas elı́pticas, precisamos encontrar um “problema difı́cil” correspondente à
fatoração do produto de dois primos ou tomar o logaritmo discreto.

Considere a equação Q = kP onde Q, P ∈ Ep (a, b) e k < p. É relativamente

fácil calcular Q dado k e P , porém é relativamente difı́cil determinar k dado
Q e P . Isto é chamado de problema de logaritmo discreto para curvas
elı́pticas.

Damos um exemplo tirado do site ([Link]). Considere o

CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 98

grupo E23 (9, 17). Este é um grupo definido pela equação y 2 mod 23 =
(x3 + 9x + 17) mod 23. Qual é o logaritmo discreto k de Q = (4, 5) na
base P = (16, 5)?
Podemos usar o método de força bruta, para responder esta questão, que
consiste em calcular múltiplas vezes o valor de P até encontrar Q temos que:

P = (16, 5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10);

6P = (7, 3); 7P = (8, 7); 8P = (12, 17); 9P = (4, 5),

portanto, como 9P = (4, 5) = Q, o logaritmo discreto Q = (4, 5) na base

P = (16, 5) é k = 9. Em uma aplicação real, k seria tão grande que
tornaria o método de forçar bruta inviável.

Análogo a troca de chaves Diffie-Hellman

Troca de chaves usando curvas elı́pticas pode ser feito da seguinte ma-
neira. Primeiro escolha um inteiro grande q, que seja um número primo p ou
um inteiro de forma 2m , e parâmetros de curva elı́ptica a a b para equação 5.5
ou equação 5.7. Isto define o grupo elı́ptico dos pontos Eq (a, b). Em seguida,
escolha um ponto base G = (x1 , y1 ) em Ep (a, b) cuja ordem é um valor muito
grande n. A ordem n de um ponto G em uma curva elı́ptica (ou seja, o
menor inteiro positivo n tal que n · G = O) e G são parâmetros do sistema
criptográfico conhecido por todos os participantes.
Um troca de chaves entre os usuários Alice e Bob pode ser realizada
segundo a Tabela 6.1.
CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 99

Elementos Públicos Globais

curva elı́ptica com parâmetros a, b e q, onde q é um
Eq (a, b)
um primo ou um inteiro da forma 2m
G ponto na curva elı́ptica cujo a ordem é um valor n grande

Geração da Chave Pública de Alice

Selecionar nA privada nA < n
Calcule PA pública PA = n A · G

Geração da Chave Pública de Bob

Selecionar nB privada nB < n
Calcule PB pública PB = n B · G

Cálculo da Chave Secreta de Alice

k = n A · PB

Cálculo da Chave Secreta de Bob

k = n B · PA

Tabela 6.1: CCE troca de chaves

• 1. Alice escolhe um inteiro nA menor que n, ou seja, ela seleciona uma

das chaves privadas que foram criadas por ela. Então, ela gera uma
chave pública PA = nA · G; A chave pública de Alice é um ponto em
Eq (a, b).

• 2. Bob similarmente seleciona uma chave privada nB e calcula uma

chave pública PB .

• 3. Alice gera a chave secreta k = nA · PB ; Bob também gera uma chave

secreta k = nB · PA .

Os dois cálculos na etapa 3 produzem o mesmo resultado porque

nA · PB = nA · (nB · G) = nB · (nA · G) = nB · PA
CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 100

para quebrar este esquema, um invasor precisaria ser capaz de computar

k dado G e k · G, que é assumido como sendo difı́cil.
Por exemplo 1 , dado p = 211; Ep (0, −4), que é equivalente à curva y 2 =
x3 − 4; e G = (2, 2). Primeiro podemos calcular 240 · G = O. A chave
privada de Alice é nA = 121, então a chave pública de Alice é gerada por
PA = 121 · (2, 2) = (115, 48). A chave privada Bob é nB = 203, então a chave
pública de Bob é dada por 203 · (2, 3) = (130, 203). O compartilhamento da
chave secreta é 121 · (130, 203) = 203 · (115, 48) = (161, 69).
Perceba que a chave secreta é um par de números. Se esta chave for usada
como uma chave de sessão para criptografia convencional, então um único
número deve ser gerado. Nós poderı́amos simplesmente usar as coordenadas
de x ou alguma função simples das coordenadas de x.
Codificação e Decodificação de Curvas Elı́pticas
Várias abordagens para codificar/decodificar usando curvas elı́pticas fo-
ram analisadas na literatura. Nesta subseção, nós vamos olhar para talvez a
mais simples. A primeira tarefa neste sistema é codificar a mensagem de texto
simples m para ser enviada como um ponto Pm na curva. É o ponto Pm que
será criptografado como um texto cifrado e subsequentemente decodificado.
Note que não podemos simplesmente codificar a mensagem como a coor-
denada x ou y de um ponto porque nem todas essas coordenadas estão em
Eq (a, b); por exemplo, como podemos perceber da tabela 5.1.
Novamente, existem várias abordagens para essa codificação, as quais não
abordaremos aqui, mas basta dizer que existem técnicas relativamente diretas
que podem ser usadas.
Como no sistema de troca de chaves um sistema de codificação/decodificação
requer um ponto G e um grupo elı́ptico Eq (a, b) como parâmetros.
1
Fornecido por Ed Schaefer da Universidade Santa Clara
CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 101

Todo usuário, seleciona uma chave privada e gera uma chace pública,
vamos pegar dois usuários quaisquer que chamaremos de B e A. Se o usuário
A seleciona uma chave privada nA e gera uma chave pública PA = nA · G.
Para codificar e enviar um texto claro ou mensagem clara, Pm , para B, A
escolhe um inteiro positivo aleatório k, com isso, podemos produzir (gerar)
o texto cifrado ou mensagem cifrada, Cm , consistindo do par de pontos:

Codificação

Cm = {k · G, Pm + k · PB }

Note que A usou a chave pública, PB , do usuário B para codificar o texto

claro.
Agora para B decodificar a mensagem cifrada, ele multiplica o primeiro
ponto do par da chave secreta dele e subtrai o resultado do segundo ponto:

Decodificação

Pm + k · PB − nB · (k · G) = Pm + k · (nB · G) − nB · (k · G) = Pm

Com isso, ele decodifica a mensagem, por fim, note que para cifrar a
mensagem clara, nós adicionamos k · PB a Pm , portanto, ninguém a não
ser A ou B, sabem o valor de k, mesmo que PB seja uma chave pública e,
portanto, o invasor tenha acesso, ninguém poderá decodificar a cifra k · PB a
não ser B.
Contudo, A acaba incluindo uma “pista” neste processo de codificação
obrigatoriamente, que é suficiente para decifrar a mensagem, se alguém sou-
ber a chave privada nB de B. Para um invasor recuperar a mensagem, ele
CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 102

(invasor) teria que computar k com valor de G e k · G, o que é considerado

difı́cil.
Vamos pegar um exemplo deste processo de criptografia, que pode ser
encontrado em Koblitz [13], pegue p = 751; Ep (−1, 188), que é equivalente
à curva y 2 = x3 − x + 188; e G = (0, 376). Suponha que Alice deseja enviar
uma mensagem para Bob que esteja codificada no ponto Pm = (562, 211) e
que Alice selecione o número aleatório k = 386, a chave pública de Bob é
PB = (201, 5).
Temos que 386 · (0, 376) = (676, 558) e (562, 201) + 386 · (201, 5) =
(385, 328). Assim, Alice envia o texto cifrado Cm = {(676, 558), (385, 328)}
para Bob de forma codificada (criptografada).

Segurança da Criptografia de Curvas Elı́pticas

A segurança da CCE depende de quão difı́cil é determinar k dado k · P e
P . Isto é chamado de problema do logaritmo da curva elı́ptica. Uma técnica
eficiente para obter o logaritmo da curva elı́ptica é conhecida como método
Pollard Rho [12].
Vamos usar este método para comparar vários algoritmos mostrando ta-
manhos de chaves comparáveis em termos de esforço computacional para
criptoanálise (veja a Tabela 6.2). Como pode ser visto, um tamanho de chave
consideravelmente menor pode ser usado para a CCE em comparação com a
RSA.
Além disso, para comprimento de chaves iguais, o esforço computacional
necessário para CCE e RSA é comparável segundo Jurisc [10]. Assim, há
uma vantagem computacional no uso de CCE como um comprimento de
chave menor que uma RSA comparativamente seguro.
CAPÍTULO 6. APLICAÇÃO À CRIPTOGRAFIA 103

Esquema Simétrico Esquema Baseado CCE RSA

(tamanho da chace em bits) (tamanho do n em bits) (tamanho do módulo em bits)
56 112 512
80 160 1024
112 224 2048
128 256 3072
192 384 7680
256 512 15360

Tabela 6.2: Tamanho de chaves comparáveis em termos de esforço computa-

cional

6.2 Resumo
Neste capı́tulo falamos sobre o uso de Criptografia de Curva Elı́ptica e
também dissemos que a troca de chaves em CCE é semelhante ao Diffie-
Hellman e explicamos como codificar e decodificar uma mensagem usando
esse método. Por fim, falamos sobre a confiabilidade da segurança da CCE.
Capı́tulo 7

Conclusão

Este trabalho teve como pretensão apresentar os conceitos fundamentais para

compreendermos as bases das cifras largamente usadas em sistemas que apli-
cam criptografia em seus ambientes de produção, quando se pretende cons-
truir uma comunicação confiável entre dispositivos, segura e confidencial.
Portanto, teoria dos números e curvas elı́pticas são a base para compreen-
dermos o funcionamento dos algoritmos criptográficos modernos.

104
Referências Bibliográficas

[1] Secure Hash Standard (SHS) - NIST.

[2] Anthoy W. Knapp. Elliptic Curves. Princeton University Press, 1999.

[3] Joan Daemen and Vincent Rijmen. The design of Rijndael AES Advan-
ced Encryption Standard. Springer-Verlag, 2002.

[4] Whitfield Diffie and Martins E. Hellman. New directions in crypto-

graphy, 1976.

[5] Christof Paar e Jan Pelzl. Understanding Cryptography. Springer, 2010.

[6] A. Fernandes. Elliptic curve cryptography, 1999.

[7] IBM. Data Encryption Standard (DES). Federal Information Processing

Standard Publication 46, 1977.

[8] Marcos Antonio S. J. Algoritmos criptográficos para redes de sensores,

2008.

[9] Williamson M. J. Non-secret encryption using a finite field., 1974.

[10] Jurisic, A., and Menezes, A. Elliptic curves and cryptography, 1997.

[11] David Kahn. The codebreakers, Dec 1996.

105
REFERÊNCIAS BIBLIOGRÁFICAS 106

[12] Jonathan Katz and Yehuda Lindell. Introduction to modern crypto-

graphy, 2007.

[13] Neal Koblitz. A Course in Number Theory and Cryptography. Springer,

1994.

[14] Calvin T. Long. Elementary Introduction to Number Theory. Waveland,

1995.

[15] Francisco Cesar Polcino .M. Números, 2001.

[16] R.L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital
signatures and public, key cryptography, 1977.

[17] Claude E. Shannon. Communication theory of secrecy systems. Bell

System Technical, 28:656–715, 1949.

[18] William Stallings. Cryptography and Network Security. Pearson, 2011.

[19] Joan Daemen Vincent Rijmen. Specification for the Advanced Encryp-
tion Standard (AES). Federal Information Processing Standards Publi-
cation 197, 2001.

[20] Andrew Wiles. Modular Elliptic Curves and Fermat’s Last Theorem,
1995.