Livro 77 PDF
Livro 77 PDF
Livro 77 PDF
Editores
2014
A Sociedade Brasileira de Matematica Aplicada e Computacional -
SBMAC publica, desde as primeiras edicoes do evento, monografias dos
cursos que sao ministrados nos CNMAC.
Para a comemoracao dos 25 anos da SBMAC, que ocorreu durante
o XXVI CNMAC em 2003, foi criada a serie Notas em Matematica
Aplicada para publicar as monografias dos minicursos ministrados nos
CNMAC, o que permaneceu ate o XXXIII CNMAC em 2010.
A partir de 2011, a serie passa a publicar, tambem, livros nas areas
de interesse da SBMAC. Os autores que submeterem textos a serie
Notas em Matematica Aplicada devem estar cientes de que poderao
ser convidados a ministrarem minicursos nos eventos patrocinados pela
SBMAC, em especial nos CNMAC, sobre assunto a que se refere o
texto.
O livro deve ser preparado em Latex (compatvel com o Miktex
versao 2.9), as figuras em eps e deve ter entre 80 e 150 paginas. O
texto deve ser redigido de forma clara, acompanhado de uma excelente
revisao bibliografica e de exerccios de verificacao de aprendiza-
gem ao final de cada captulo.
2014
UMA INTRODUCAO A CRIPTOGRAFIA DE
CHAVE PUBLICA ATRAVES DO METODO EL
GAMAL
Editora: SBMAC
Patrocnio: SBMAC
c
Copyright 2014 by Luis Menasche Schechter. Direitos reservados, 2014 pela SB-
MAC. A publicacao nesta serie nao impede o autor de publicar parte ou a totalidade
da obra por outra editora, em qualquer meio, desde que faca citacao a edicao origi-
nal.
Schechter, L. M.
Uma Introducao a Criptografia de Chave Publica
Atraves do Metodo El Gamal - Sao Carlos, SP :
SBMAC, 2014, 124 p., 21.5 cm - (Notas em Matematica
Aplicada; v. 77)
e-ISBN
e-ISBN 978-85-8215-063-4
???????
CDD - 51
Para Rosa e Luziane,
meus pilares,
meus oasis.
Agradecimentos
Prefacio xi
1 Introducao 1
1.1 Objetivos da Criptografia . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Breve Panorama Historico . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Mudanca de Paradigma: Chave Publica . . . . . . . . . . . . . . . . 6
1.4 Roteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Aritmetica Modular 13
2.1 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Relacoes de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Inteiros Modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Operacoes Modulares . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Sistemas de Congruencias . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Numeros Primos 41
3.1 Conceitos e Resultados Fundamentais . . . . . . . . . . . . . . . . . 41
3.2 Crivo de Eratostenes . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Teste de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4 Grupos 61
4.1 Definicoes Basicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Os Grupos Finitos U (n) . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 Subgrupos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4 Grupos e Subgrupos Cclicos . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5 O Metodo El Gamal 77
5.1 Esquema Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Criptografia El Gamal . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Assinatura Digital El Gamal . . . . . . . . . . . . . . . . . . . . . . 88
5.4 Assinatura Digital DSA . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
ix
x
xi
xii
Introducao
teriam acesso a mensagem que contem diversas instrucoes taticas, ganhando entao
vantagem na batalha.
Em termos mais gerais, podemos dizer que, no exemplo acima, o mensageiro fun-
ciona como o canal de transmissao da mensagem entre o remetente (comandante
do primeiro agrupamento) e o destinatario (comandante do segundo agrupamento).
Temos entao que este e um canal inseguro para a transmissao de mensagens, ja
que ha a possibilidade de interceptacoes das mensagens que trafegam neste canal.
Sempre que temos um cenario como este, em que um remetente deseja enviar
uma mensagem para um destinatario onde
2. a mensagem contem algum tipo de conteudo privado que so deve ser visto
pelo remetente e pelo destinatario,
movimentacao nos rotores, se a mesma tecla for pressionada duas vezes seguidas,
a letra correspondente a esta tecla sera encriptada pela maquina de duas formas
diferentes. Assim, o mapeamento entre letras na mensagem original e letras na
mensagem encriptada nao e mais fixo como na Cifra de Cesar, de modo que o metodo
de contagem de frequencias nao pode mais ser diretamente aplicado para burlar a
seguranca da criptografia da Maquina Enigma. Considerando que existem 263 ou
264 possveis posicionamentos dos rotores, nota-se que qualquer analise estatstica
com o objetivo de obter o conteudo da mensagem original a partir da interceptacao
de uma mensagem encriptada e sem o conhecimento da chave de encriptacao devera
ser consideravelmente mais refinada do que a analise estatstica utilizada no caso
da Cifra de Cesar.
Pode-se notar que, apesar de ser mais sofisticada do que a Cifra de Cesar, a
criptografia da Maquina Enigma tambem e um metodo de criptografia de chave
privada. Caso um intruso saiba a posicao inicial dos rotores da maquina (e possua
uma Maquina Enigma a disposicao), ele podera realizar a decriptacao das mensa-
gens.
Quando a Maquina Enigma comecou a ser utilizada pelos alemaes na Segunda
Guerra Mundial, acreditava-se que a criptografia implementada por ela era im-
possvel de ser quebrada. De fato, durante um bom tempo, os esforcos para acessar
o conteudo das mensagens encriptadas com a Enigma se mostraram inuteis. Isto,
por sua vez, se refletiu em uma grande vantagem da Alemanha sobre a Inglaterra e a
Franca. Em particular, os submarinos alemaes conseguiram impor grandes derrotas
a marinha britanica.
Com o passar do tempo, entretanto, a Maquina Enigma mostrou possuir vul-
nerabilidades. Um time de cientistas, matematicos e militares ingleses conseguiu
desenvolver um metodo para obter o conteudo original de mensagens encriptadas
com a Enigma. Como esperado, este metodo era baseado em analises estatsticas
extremamente sofisticadas. De fato, estas analises eram tao sofisticadas que foi
necessaria a construcao de computadores dedicados somente a realizar todos os
calculos necessarios para a obtencao do conteudo das mensagens. Devido a isso, a
quebra da criptografia da Maquina Enigma acabou por se tornar uma das primeiras
aplicacoes de grande porte da computacao.
Com a quebra da criptografia da Maquina Enigma, pouco a pouco a vantagem
militar alema foi sendo revertida. O momento da quebra desta criptografia coincide
aproximadamente com o momento da mudanca dos rumos da guerra, que passou a
tender para o lado dos aliados. Desta forma, o trabalho de quebra da criptografia
da Maquina Enigma teve relevancia fundamental para o momento que estava sendo
vivido na Europa.
O matematico ingles Alan Turing fazia parte do time que conseguiu a quebra da
criptografia da Maquina Enigma e teve um papel fundamental tanto na elaboracao
dos calculos necessarios para a obtencao do conteudo das mensagens como no projeto
e construcao dos computadores que passaram a realizar tais calculos. Alan Turing
e um dos pioneiros da Ciencia da Computacao, tendo desenvolvido, alem deste
trabalho fundamental na area de criptografia, trabalhos nas areas de Teoria da
Computacao, Inteligencia Artificial e Computacao Cientfica. Para maiores detalhes
sobre sua vida e suas diversas contribuicoes ao desenvolvimento da computacao, o
livro [9] pode ser consultado.
Para os leitores que se interessam pelo desenvolvimento historico dos metodos de
criptografia, recomendamos a consulta ao livro [11]. Este livro realiza uma analise
historica bastante detalhada e completa a respeito da evolucao dos metodos de
criptografia ao longo do tempo, desde a antiguidade ate os dias de hoje.
6 Introducao
metodo El Gamal, que sera o metodo estudado ao longo deste livro, devemos estudar
os algoritmos existentes para a resolucao do Problema do Logaritmo Discreto em
grupos finitos. Este estudo do lado destrutivo nao interessa apenas a pessoas mal
intencionadas. Ele e muito importante tambem para quem implementa o sistema e
para os usuarios legtimos dele. O conhecimento dos algoritmos disponveis para a
resolucao do problema matematico associado a um metodo de criptografia de chave
publica ou assinatura digital e importante do ponto de vista pratico, pois, mesmo
que este problema seja difcil de ser computacionalmente resolvido no caso geral, os
algoritmos existentes sao eficientes em alguns casos particulares. Tais casos devem
entao ser evitados durante a construcao dos sistemas, para que sua seguranca nao
seja comprometida.
Desta forma, tentando obter uma visao global dos varios aspectos envolvidos
na implementacao segura e eficiente de metodos de criptografia de chave publica e
de assinatura digital, estudaremos o problema matematico subjacente ao metodo
El Gamal, que e o Problema do Logaritmo Discreto em grupos finitos, como ele e
utilizado na construcao do metodo e tambem diversos algoritmos apresentados na
literatura para a resolucao de alguns casos deste problema matematico.
Encerramos esta secao apresentando alguns outros livros que tratam de metodos
de criptografia de chave publica e de assinatura digital, assim como dos problemas
matematicos subjacentes a eles. Para um estudo detalhado do metodo RSA, descrito
brevemente acima, o livro [3] e uma otima referencia em Lngua Portuguesa. Outros
livros que abordam estes topicos com um bom nvel de detalhe sao [16], [13] e [10].
1.4 Roteiro
Neste livro, temos o objetivo de estudar o metodo El Gamal de criptografia de chave
publica e de assinatura digital. De modo a delinear nosso caminho ate este objetivo,
apresentamos a seguir um roteiro dos assuntos que serao abordados no decorrer dos
proximos captulos.
Apos o panorama introdutorio apresentado ao longo deste captulo, iniciamos,
no Captulo 2, a apresentacao dos conceitos matematicos subjacentes a construcao
do metodo El Gamal.
No Captulo 2, apresentamos a chamada aritmetica modular, que sera utili-
zada em todos os calculos realizados pelo metodo El Gamal. A nocao central da
aritmetica modular e a nocao de relacao de congruencia modulo n, onde n e um
inteiro maior do que 1.
Iniciamos o captulo discutindo os conceitos basicos de divisibilidade entre nume-
ros inteiros. Um conceito muito importante que sera apresentado e o maximo divisor
comum entre dois inteiros positivos a e b. Iremos apresentar tambem um algoritmo
que, alem de calcular o maximo divisor comum, calcula simultaneamente outros
dois inteiros que serao uteis para nossas aplicacoes. Este e o Algoritmo Euclidiano
Estendido.
Em seguida, apresentamos o conceito de relacao de equivalencia para, logo apos,
discutirmos o caso particular de relacao de equivalencia que ira nos interessar pelo
restante do livro: a relacao de congruencia modulo n. Para podermos definir
esta relacao, utilizamos os conceitos de divisibilidade entre inteiros. Descrevere-
mos entao os conjuntos Zn , onde n > 1, dos inteiros modulo n, construdos a
partir das relacoes de congruencia modulo n. Explicaremos tambem como realizar
as operacoes aritmeticas de soma, diferenca, produto e potenciacao com elemen-
tos destes conjuntos e como calcular inversos multiplicativos destes elementos. Em
Roteiro 9
1.5 Exerccios
1. Qual e o objetivo principal da criptografia? O que torna a sua aplicacao
necessaria?
2. Explique as diferencas entre um metodo de criptografia de chave privada e
um metodo de criptografia de chave publica. De dois exemplos de metodos
pertencentes a cada categoria.
Exerccios 11
Aritmetica Modular
2.1 Divisibilidade
Nesta secao, apresentamos os conceitos basicos de divisibilidade entre numeros in-
teiros. Para isto, iniciamos pelas definicoes de quociente e resto de uma divisao
inteira.
14 Aritmetica Modular
a = bq + r e 0 r < b.
a = bq + r e a = bq 0 + r0 ,
0 = b(q q 0 ) + (r r0 ),
3. Enquanto r b, faca:
3.1. q q + 1
3.2. r r b
Todas as instrucoes que fazem parte do bloco que deve ser repetido estao recua-
das em relacao a instrucao de repeticao inicial e comecam com o mesmo numero
da instrucao inicial (3). Desta forma, com esta notacao, e facil determinar quais
instrucoes devem ser repetidas ou quais instrucoes sao condicionalmente executadas.
Finalmente, encerrando por hora a discussao sobre a notacao que utilizamos para
descrever os algoritmos, vamos explicar o que significa o smbolo #. Quando este
smbolo aparece em alguma linha da sequencia de instrucoes, tudo o que vem depois
dele e um comentario, isto e, alguma explicacao ou auxlio sobre aquela instrucao.
Um comentario serve apenas para as pessoas que estao lendo o algoritmo, mas nao
afeta de forma alguma a execucao da instrucao onde ele aparece.
Vamos agora discutir especificamente o Algoritmo da Divisao que apresentamos
acima. Como ele possui uma instrucao de repeticao, e importante verificar que o
algoritmo nao fica repetindo eternamente o bloco de instrucoes dentro desta ins-
trucao de repeticao. Tambem e importante verificar, como em qualquer algoritmo,
que o resultado que ele produz ao final da execucao de todas as instrucoes e correto,
isto e, satisfaz a descricao dada pela sada do algoritmo. No caso particular do
Algoritmo da Divisao, precisamos nos certificar que o resultado final e realmente o
quociente e o resto da divisao inteira dos numeros fornecidos como entrada.
Para verificar estes dois pontos, vamos olhar a sequencia de valores armazenados
nas variaveis q e r ao longo da execucao do algoritmo. O valor armazenado nestas
variaveis e alterado a cada repeticao da instrucao de repeticao que destacamos
acima. A tabela abaixo exibe as sequencias de valores.
Repeticoes 0 1 2 3 ... u1 u
q 0 1 2 3 ... u1 u
r a a b a 2b a 3b . . . a (u 1)b a ub
a + b = d.
que zero, eventualmente tera que aparecer na sequencia de divisoes um resto igual
a zero, fazendo o algoritmo terminar.
Vamos agora mostrar que o ultimo resto diferente de zero na sequencia de di-
visoes do Algoritmo Euclidiano e realmente o maximo divisor comum entre a e b.
Para isso, precisamos de um lema auxiliar.
Vamos agora olhar para a sequencia de divisoes na Figura 2.1 na ordem reversa,
comecando pela ultima. Como rn = 0, a ultima divisao pode ser escrita como
rn2 = rn1 qn . Isto significa que rn1 divide rn2 . Como rn1 tambem divide a si
proprio, temos que rn1 e um divisor comum entre rn2 e rn1 . Entretanto, rn1
nao pode possuir nenhum divisor maior do que si mesmo. Assim, nao pode haver
nenhum divisor comum entre rn2 e rn1 maior do que rn1 , o que significa que
mdc(rn2 , rn1 ) = rn1 .
Vamos observar agora a penultima divisao: rn3 = rn2 qn1 + rn1 . Aplicando
o lema acima a esta igualdade, temos que mdc(rn3 , rn2 ) = mdc(rn2 , rn1 ). Mas
acabamos de mostrar que mdc(rn2 , rn1 ) = rn1 , logo mdc(rn3 , rn2 ) = rn1 .
Se continuarmos aplicando o lema acima a todas as divisoes (de baixo para cima),
iremos concluir que, em todas elas, como nas duas que ja analisamos, o maximo
divisor comum entre o dividendo e o divisor e sempre igual a rn1 . Em particular,
da primeira divisao a = bq1 + r1 , conclumos que mdc(a, b) = rn1 . Logo, o ultimo
resto diferente de zero na sequencia de divisoes (rn1 ) e realmente o maximo divisor
comum entre a e b. Podemos concluir entao que o Algoritmo Euclidiano, conforme
esquematizado nas duas primeiras colunas da Figura 2.1, retorna o resultado correto.
Para obtermos o Algoritmo Euclidiano Estendido, estendemos os calculos re-
alizados pelo Algoritmo Euclidiano com os calculos descritos na terceira coluna da
Figura 2.1. A ideia do Algoritmo Euclidiano Estendido para calcular os inteiros
e tais que
a + b = mdc(a, b)
e bastante simples e efetiva. Uma vez que mdc(a,b) e um resto produzido na
sequencia de divisoes do Algoritmo Euclidiano, ao inves de tentar calcular direta-
mente os valores de e , o algoritmo calcula valores i e i tais que
i a + i b = ri ,
20 Aritmetica Modular
para cada resto ri , onde 1 i n 1. A motivacao por tras desta ideia e que
o valor de i possa ser calculado a partir dos valores j , com j < i, ja calculados
anteriormente, com um procedimento analogo para o valor de i . Assim, os valores
de i e i seriam calculados simultaneamente com os valores de qi e ri durante a
sequencia de divisoes. Como mdc(a, b) = rn1 , os valores de e que desejamos
como resposta do algoritmo serao n1 e n1 .
Vamos agora mostrar como calcular os valores de j+2 e j+2 assumindo que ja
foram calculados anteriormente os valores de j , j , j+1 e j+1 , tais que
j a + j b = rj e j+1 a + j+1 b = rj+1 ,
conforme as igualdades presentes na terceira coluna da Figura 2.1.
Da primeira coluna da Figura 2.1, temos a divisao
rj = rj+1 qj+2 + rj+2 ,
que pode ser escrita como
rj+2 = rj qj+2 rj+1 . (2.1.1)
Queremos calcular j+2 e j+2 satisfazendo a igualdade j+2 a + j+2 b = rj+2
(novamente, conforme ilustrado na terceira coluna da Figura 2.1).
Substituindo, na igualdade (2.1.1), rj , rj+1 e rj+2 pelos valores dados pelas
igualdades da terceira coluna da Figura 2.1, obtemos
j+2 a + j+2 b = (j a + j b) qj+2 (j+1 a + j+1 b),
que e equivalente a
j+2 a + j+2 b = (j qj+2 j+1 )a + (j qj+2 j+1 )b.
Esta ultima igualdade nos diz que, se tomarmos
j+2 = j qj+2 j+1 e
(2.1.2)
j+2 = j qj+2 j+1 ,
estes valores irao satisfazer a igualdade j+2 a + j+2 b = rj+2 . Assim, a medida
que formos produzindo os quocientes e restos das divisoes sucessivas, podemos si-
multaneamente calcular os valores de j+2 e j+2 , bastando para isso armazenar
os dois valores anteriores j e j+1 e os dois valores anteriores j e j+1 de forma
a utiliza-los nas formulas acima.
Nos resta ainda um problema final para podermos utilizar de fato o Algoritmo
Euclidiano Estendido. Sabemos calcular os valores parciais de e se conhecermos
os dois valores parciais anteriores de cada um. Mas como fazemos para calcular 1
e 1 ? Olhando novamente para o raciocnio acima, vemos que o que nos permitiu
obter j+2 e j+2 a partir dos valores anteriores foi a divisao
rj = rj+1 qj+2 + rj+2 ,
isto e, a divisao que produz o resto rj+2 . Portanto, para descobrirmos como calcular
1 e 1 , devemos observar a divisao que produz o resto r1 :
a = bq1 + r1 .
Se utilizarmos esta divisao no raciocnio que desenvolvemos acima, conseguiremos
calcular 1 e 1 a partir de valores
e, ,
e
b e b tais que:
(
ea + be = a e
ba + bb = b.
Divisibilidade 21
Colocamos entao os valores 1768 e 62 nas duas primeiras linhas da tabela, na coluna
R. Preenchemos a primeira linha da coluna com o valor 1, a segunda linha desta
coluna com o valor 0, a primeira linha da coluna com o valor 0 e a segunda linha
desta coluna com o valor 1.
R Q
1768 1 0
62 0 1
Agora realizamos a divisao de 1768 por 62, os dois elementos da coluna R, obtendo
1768 = 62.28 + 32. Logo, o quociente e 28 e o resto e 32. Acrescentamos estes
valores nas colunas Q e R, respectivamente.
R Q
1768 1 0
62 0 1
32 28
22 Aritmetica Modular
o produto do quociente desta linha pelo valor parcial de na linha acima. Assim,
o valor parcial de nesta linha sera 1 0.0 = 1. O calculo do valor parcial de
nesta linha e inteiramente analogo, sendo 0 0.1 = 0.
R Q
76 1 0
2404 0 1
76 0 1 0
Em ambas as tabelas, o proximo passo seria realizar a divisao de 2404 por 76. Da
em diante, os calculos nas duas tabelas seriam os mesmos. Vemos entao que as
unicas diferencas entre as tabelas e que a primeira tabela tera uma linha a mais (a
primeira linha) e as colunas e sao permutadas entre as duas. Assim, podemos
concluir que o algoritmo produz o resultado correto independentemente da ordem
com que colocamos os dois numeros na coluna R da tabela. Precisamos apenas
ficar atentos com os resultados produzidos nas colunas e . O resultado final na
coluna sempre sera o multiplicador do primeiro numero colocado na coluna R
e o resultado final produzido na coluna sempre sera o multiplicador do segundo
numero colocado nesta coluna. Se trocarmos a ordem dos numeros iniciais na coluna
R, os resultados das colunas e tambem serao permutados.
Vamos agora calcular o restante da nossa tabela original, com o valor 76 no
topo.
R Q
76 1 0
2404 0 1
76 0 1 0
48 31 31 1
28 1 32 1
20 1 63 2
8 1 95 3
4 2 253 8
0 2
Temos entao que mdc(76, 2404) = 4, = 253 e = 8. De fato, calculando
253.76 + 8.2404 = 4 = mdc(76, 2404).
Precisamos fazer apenas mais uma ultima observacao a respeito dos valores de
e . Se mdc(a, b) = d, os valores de e calculados pelo Algoritmo Euclidiano
Estendido nao sao os unicos que satisfazem a igualdade a + b = d. De fato, se
e satisfazem esta igualdade, entao temos tambem
o que significa que podemos calcular uma infinidade de pares de valores satisfazendo
a igualdade.
Encerramos esta secao com um lema muito importante que sera utilizado diver-
sas vezes ao longo deste livro para auxiliar a prova de varios resultados.
24 Aritmetica Modular
Lema 2.2. Sejam m e n dois numeros inteiros positivos tais que mdc(m, n) = 1 e
seja a um numero inteiro. Entao, as seguintes afirmacoes sao verdadeiras.
Definicao 2.5 (Relacao Binaria). Dado um conjunto S, uma relacao binaria entre
elementos de S e um conjunto R S S. Para a, b S, dizemos que a esta
relacionado com b pela relacao binaria R se (a, b) R. Neste caso, tambem usamos
a notacao aRb.
0 0 00
Transitividade: Se ab = ab0 e ab0 = ab00 , entao ab0 = a0 b e a0 b00 = a00 b0 . Multiplicando
os dois lados da primeira igualdade por b00 , obtemos ab0 b00 = a0 bb00 , que pode
ser escrita como ab0 b00 = a0 b00 b. Pela segunda igualdade, podemos substituir
a0 b00 por a00 b0 , obtendo ab0 b00 = a00 b0 b. O denominador de uma fracao sempre
e diferente de zero, logo b0 6= 0. Podemos entao cancela-lo dos dois lados da
00
igualdade, obtendo ab00 = a00 b, o que nos permite concluir que ab = ab00 .
a = {b X : a b}.
E simples ver que X pode ser obtido como a uniao de todas as suas classes de
equivalencia. Entretanto, podemos obter um resultado mais forte do que este: as
classes de equivalencia formam uma particao do conjunto X, isto e, a uniao das
classes de equivalencia e disjunta.
Uma vez que as classes de equivalencia nos fornecem uma particao do conjunto
X e que todos os elementos dentro de uma mesma classe sao considerados, com
o perdao da redundancia, equivalentes, podemos construir um novo conjunto
tomando um representante de cada uma das classes de equivalencia.
X/ = {a : a X}.
Exemplo 2.8. Retornando ao exemplo das fracoes tendo estudado estes resultados
basicos sobre relacoes de equivalencia, vemos que uma fracao nao e simplesmente
um par de inteiros (a, b) onde b 6= 0, como as vezes ouvimos na escola. Como
diversos pares diferentes representam a mesma fracao, uma fracao na realidade e
um elemento do conjunto quociente X/ , onde X e o conjunto de pares de inteiros
(a, b) onde b 6= 0 e e a relacao de igualdade de fracoes que estudamos no exemplo
acima. Em outras palavras, uma fracao e uma classe de equivalencia. Qual dos
elementos dessa classe nos escolhemos para representar a fracao nao importa. O
resultado das contas com fracoes nao depende desta escolha. Entretanto, a escolha
mais comum e pela chamada fracao reduzida, isto e, a fracao em que o maximo
divisor comum entre o numerador a e o denominador b e igual a 1.
e o da reta infinita dos numeros inteiros, mas sim o de um relogio circular fechado
com 12 ou 24 casas. A relacao de congruencia modulo n e a aritmetica modular
derivada dela sao uma generalizacao desta ideia: ao inves dos calculos serem feitos
sobre a reta infinita dos inteiros, eles sao feitos sobre um relogio circular fechado
com n casas.
Apos esta motivacao inicial, estamos prontos para definir a relacao de con-
gruencia modulo n.
Repare que nao temos uma unica relacao de congruencia. Cada inteiro n 2
da origem a uma relacao de congruencia distinta.
Exemplo 2.11. No caso das horas do dia, estamos trabalhando com a relacao de
congruencia modulo 24 ou com a relacao de congruencia modulo 12. Utilizando a
notacao de congruencias, temos:
Simetria: Sejam a e b inteiros tais que a b (mod n). Entao, pela definicao de
congruencia modulo n, temos que a b e multiplo de n. Podemos escrever
entao a b = nk, para algum k Z. Multiplicando esta ultima igualdade
por 1 em ambos os lados, obtemos b a = n(k), o que significa que b a
tambem e multiplo de n. Logo, pela definicao de congruencia modulo n, b a
(mod n).
28 Aritmetica Modular
a = {b Z : a b (mod n)}.
A partir da Propriedade 2.4, vemos que todo inteiro sera congruente modulo n
a um dos inteiros no conjunto {0, 1, 2, . . . , n 1}, ja que estes sao os possveis restos
de uma divisao em que n e o divisor. Desta maneira, nao existem outras classes
de equivalencia alem das classes 0, 1, 2, . . . , n 1. Por outro lado, dados quaisquer
dois valores distintos do conjunto acima, a Propriedade 2.3 nos diz que eles nao
serao congruentes entre si modulo n. Desta maneira, as classes de equivalencia que
listamos sao todas distintas. Conhecemos entao todas as classes de equivalencia
de Z pela relacao de congruencia modulo n e sabemos que elas totalizam n classes
distintas. Podemos entao reun-las no conjunto quociente de Z pela relacao de
congruencia modulo n.
Definicao 2.11. Dado o conjunto Z dos numeros inteiros e a relacao de con-
gruencia modulo n, que nesta definicao abreviaremos como n , o conjunto quociente
de Z por n , denotado por Z/n , e definido da seguinte forma:
faca sentido, precisamos nos certificar de que o resultado da soma sera sempre o
mesmo, independentemente de quais representantes sejam escolhidos para as duas
classes que estao sendo somadas. Formalizamos isto no teorema abaixo.
Vemos entao que a operacao modular de soma e definida de maneira bem simples,
utilizando para o seu calculo a soma tradicional de inteiros.
Exemplo 2.15. Vamos calcular 4.5 em Z3 . Pela formula acima, 4.5 = 4.5 = 20.
A forma reduzida de 20 modulo 3 e 2, logo 4.5 = 2 em Z3 .
Instrucoes:
1. R 1, A a, E t
2. Enquanto E 6= 0, faca:
2.1. Se E for mpar, entao:
2.1.1. R (R A) mod n
2.1.2. E (E 1)/2
2.2. Senao, E E/2
Operacoes Modulares 33
2.3. A (A A) mod n
3. Retorne R.
19457
Exemplo 2.16. Vamos calcular a forma reduzida de 6 em Z33 . Em outras pa-
lavras, vamos calcular o resto da divisao de 619457 por 33. Comecamos construindo
uma tabela com uma coluna para cada variavel do algoritmo e uma quarta coluna
para avaliar quais comandos condicionais serao executados em cada etapa.
R A E E mpar?
1 6 19457 Sim
Como em qualquer etapa do algoritmo, devemos substituir 19457 pelo quociente
da sua divisao por 2 na variavel E e substituir o valor da variavel A pela forma
reduzida modulo 33 do quadrado deste valor. Entretanto, como 19457 e mpar,
devemos tambem multiplicar o valor atual de R pelo valor atual de A e calcular a
forma reduzida deste produto. O quociente de 19457 por 2 e 9728. 62 = 36 e 36 3
(mod 33). Finalmente, 1 multiplicado por 6 e 6, que ja esta reduzido modulo 33. A
tabela fica entao
R A E E mpar?
1 6 19457 Sim
6 3 9728 Nao
Agora, 9728 nao e mpar. Entao nao vamos alterar o valor de R, apenas o de A e
E. Construmos o restante da tabela de acordo com esta metodologia:
R A E E mpar?
1 6 19457 Sim
6 3 9728 Nao
6 9 4864 Nao
6 15 2432 Nao
6 27 1216 Nao
6 3 608 Nao
6 9 304 Nao
6 15 152 Nao
6 27 76 Nao
6 3 38 Nao
6 9 19 Sim
Neste momento, como 19 e mpar, alem de atualizar os valores de A e E, tambem
precisamos atualizar o valor de R. O valor de R sera a forma reduzida do produto
de 6 (valor atual de R) por 9 (valor atual de A). 54 21 (mod 33), logo o novo
valor de R sera 21. O restante da tabela sera entao:
R A E E mpar?
21 15 9 Sim
18 27 4 Nao
18 3 2 Nao
18 9 1 Sim
30 15 0 Nao
Assim, temos que 619457 30 (mod 33).
Vamos agora encerrar esta secao discutindo como determinar se um dado ele-
mento de Zn possui ou nao inverso multiplicativo e tambem como calcular este
inverso nos casos em que ele existe. Em primeiro lugar, vamos definir formalmente
o que e o inverso multiplicativo de um elemento de Zn .
34 Aritmetica Modular
a + n = d.
Esta formula nao garante o calculo de um valor no intervalo 0 i < mn. Entre-
tanto, se quisermos um valor neste intervalo, basta calcular a forma reduzida de
an + bm modulo mn. Este algoritmo derivado da prova do Teorema Chines do
Resto e conhecido como Algoritmo Chines do Resto. Deixamos como exerccio a
sua descricao formal no formato dos outros algoritmos apresentados neste captulo
(Exerccio 10).
Nao e difcil perceber que o Algoritmo Chines do Resto pode ser generalizado
para situacoes em que temos uma sequencia de congruencias
x ai (mod ni ) 1 i k,
Temos que mdc(3, 11) = 1, mdc(3, 32) = 1 e mdc(11, 32) = 1, logo podemos aplicar
o Algoritmo Chines do Resto para encontrar a classe de equivalencia de x modulo
3.11.32 = 1056. Comecamos resolvendo o sistema formado pelas duas primeiras
congruencias, aplicando o Algoritmo Euclidiano Estendido aos modulos 3 e 11.
R Q
3 1 0
11 0 1
3 0 1 0
2 3 3 1
1 1 4 1
0 2
x an + bm (mod mn),
R Q
32 1 0
33 0 1
32 0 1 0
1 1 1 1
0 32
2.6 Exerccios
1. Generalize algoritmo da divisao apresentado neste captulo para que o divi-
dendo possa ser qualquer inteiro.
2. Aplique o Algoritmo Euclidiano Estendido aos seguintes pares de inteiros po-
sitivos:
2.1. 2568 e 122
2.2. 78 e 1046
2.3. 1127 e 175
2.4. 112 e 2046
3. Uma equacao diofantina linear em duas variaveis e uma equacao
ax + by = c,
9.1. 9 em Z20
9.2. 12 em Z75
9.3. 2 em Z101
9.4. 42 em Z147
10. Escreva uma descricao formal do Algoritmo Chines do Resto no formato dos
outros algoritmos apresentados neste captulo.
11. Escreva uma descricao formal da versao mais elaborada do Algoritmo Chines
do Resto apresentada no final deste captulo. Esta versao deve poder operar
com mais de duas congruencias.
13. Determine o menor inteiro positivo que deixa resto 2 na divisao por 7, resto
4 na divisao por 15 e resto 10 na divisao por 19.
40 Aritmetica Modular
Captulo 3
Numeros Primos
Uma vez que estudamos algumas propriedades dos numeros compostos, passe-
mos agora ao estudo de algumas propriedades dos numeros primos.
Iniciamos este estudo com uma prova de que existem infinitos numeros primos
entre os inteiros positivos. Ao longo do tempo, dezenas de provas da infinitude
dos primos foram desenvolvidas por diversos matematicos diferentes. O livro [24]
realiza uma catalogacao de varias destas provas.
A prova que optamos por exibir abaixo e uma das provas mais simples, bastante
similar a prova original deste resultado elaborada por Euclides no livro IX da sua
coletanea Elementos [6].
Como primeiro passo antes de podermos descrever esta prova, precisamos da
definicao do primorial de um inteiro positivo.
Definicao 3.3 (Primorial). Definimos o primorial de um numero inteiro positivo
n 2, denotado por n# , como o produto de todos os numeros primos menores ou
iguais a n.
Exemplo 3.2. Temos 6# = 5# = 5.3.2 = 30. Por outro lado, 10# = 7.5.3.2 = 210.
Utilizando a nocao acima de primorial, podemos agora provar que existem infi-
nitos numeros primos.
Teorema 3.1 (Infinidade dos Primos). Existem infinitos numeros primos.
Demonstracao: Suponha, por contradicao, que exista uma quantidade finita de
numeros primos. Logo, existe um numero primo p que e o maior de todos os pri-
mos. O primorial de p, denotado por p# , sera entao o produto de todos os numeros
primos. Vamos considerar o numero n = p# + 1. Como n > p e p e o maior numero
primo, entao n e um numero composto. Desta forma, pela Propriedade 3.1, existe
um numero primo 1 < q < n que e divisor de n, isto e, n = qn0 , para algum n0 Z.
Por outro lado, como q e primo, q tambem e divisor de p# , isto e, p# = qk, para
algum k Z. Podemos entao escrever a igualdade n = p# + 1 como qn0 = qk + 1, o
que e equivalente a 1 = q(n0 k). Mas temos entao, por esta ultima igualdade, que
q e divisor de 1. Isto implica que q = 1, o que e uma contradicao com a hipotese
anterior de que q > 1.
onde 1 < p1 < p2 < . . . < pk sao primos e ei 1, para todo 1 i k, chamados
de multiplicidades.
onde 1 < p1 < p2 < . . . < pk e 1 < q1 < q2 < . . . < ql sao primos, ei 1 , para todo
1 i k, e fj 1, para todo 1 j l.
Como temos n = p1 (pe11 1 p2e2 . . . pekk ), p1 divide n. Por outro lado, como n =
q1 q2 . . . qlfl , p1 divide este produto. Como p1 e primo, se p1 divide um produto,
f1 f2
entao ele divide ao menos um dos fatores, pela Propriedade Fundamental dos Primos
(Propriedade 3.3). Assim, existe qi , 1 i l, tal que p1 divide qi . Mas p1 e qi sao
ambos primos. A unica forma de um primo dividir outro e se ambos forem iguais.
Logo, qi = p1 . Substituindo qi por p1 na segunda fatoracao, obtemos
f f
i1 fi
n = pe11 pe22 . . . pekk = q1f1 q2f2 . . . qi1 i+1
p1 qi+1 . . . qlfl .
Temos entao que n = p1 n0 e podemos obter duas fatoracoes distintas para n0 elimi-
nando um dos fatores p1 de cada uma das fatoracoes acima. Temos entao
fi1 fi 1 f
n0 = pe11 1 pe22 . . . pekk = q1f1 q2f2 . . . qi1 p1 qi+1i+1
. . . qlfl .
Mas, como p1 > 1, temos que n0 < n. Entao, as duas fatoracoes distintas para n0
sao uma contradicao com a nossa escolha de n como o menor inteiro positivo que
possui pelo menos duas fatoracoes em primos distintas. Desta forma, a fatoracao
em primos de qualquer inteiro n 2 e unica.
Instrucoes:
1. f 2
2. Enquanto f b nc, faca: #b nc = parte inteira de n
2.1. r Resto da divisao de n por f .
2.2. Se r = 0, entao retorne f .
2.3. Senao, f f + 1
3. Retorne n.
3. Repetimos este processo em uma nova etapa, ate que nao restem mais numeros
que possam ser selecionados no primeiro passo acima.
Podemos reparar pela descricao acima que o maior merito do Crivo de Eratoste-
nes e conseguir encontrar quais sao os numeros que possuem um determinado fa-
tor sem realizar nenhuma conta de divisao. As contas de divisao sao os calculos
aritmeticos mais custosos do ponto de vista computacional.
Exemplo 3.4. Vamos realizar os passos descritos acima na lista com os inteiros
mpares entre 3 e 40.
Indice 0 1 2 3 4 5 6 7 8 9
Numero 3 5 7 9 11 13 15 17 19 21
Indice 10 11 12 13 14 15 16 17 18
Numero 23 25 27 29 31 33 35 37 39
Indice 0 1 2 3 4 5 6 7 8 9
Numero 3 5 7 0 11 13 0 17 19 0
Indice 10 11 12 13 14 15 16 17 18
Numero 23 25 0 29 31 0 35 37 0
Indice 0 1 2 3 4 5 6 7 8 9
Numero 3 5 7 0 11 13 0 17 19 0
Indice 10 11 12 13 14 15 16 17 18
Numero 23 0 0 29 31 0 0 37 0
Exemplo
3.5. No exemplo anterior, o nosso limite superior era n = 40. Temos que
b 40c = 6. Logo, apos as eliminacoes realizadas com os numeros 3 e 5, nao eram
necessarias mais eliminacoes. Apos estas duas eliminacoes, os numeros restantes ja
eram os primos que buscavamos. Isso esta de acordo com o que vimos no exemplo,
quando todas as eliminacoes que tentamos fazer com numeros maiores do que 6 se
mostraram redundantes.
eliminando com j no crivo, podemos iniciar nossa eliminacao pelo numero j 2 . Todos
os numeros anteriores que forem multiplos de j ja terao sido eliminados em alguma
etapa anterior do crivo.
Vamos denotar por k a posicao inicial do processo de eliminacao levando em
consideracao esta segunda melhoria. Temos que k deve ser o ndice de j 2 na lista.
Como temos a relacao de que o ndice i de um inteiro j na lista satisfaz a igualdade
i = (j 3)/2, o ndice k de j 2 sera k = (j 2 3)/2. Assim, ao inves de eliminarmos
os numeros de j em j na lista fazendo a primeira eliminacao na posicao i + j, onde
i e o ndice de j, continuamos eliminando os numeros de j em j, mas realizamos a
primeira eliminacao na posicao k = (j 2 3)/2.
Exemplo 3.6. No exemplo acima, se utilizarmos esta segunda melhoria, nao ha-
vera mudancas nas eliminacoes que realizamos com o 3, mas teremos diferencas nas
eliminacoes com o 5. Sem a melhoria, eliminamos os numeros nas posicoes 6, 11 e
16. Com a melhoria, a primeira eliminacao ocorreria na posicao k = (52 3)/2 =
11, prosseguindo de 5 em 5. Assim, nao seria feita a eliminacao na posicao 6, mas
seriam mantidas as eliminacoes nas posicoes 11 e 16. Pelo que vemos no exemplo
acima, a eliminacao na posicao 6 era justamente a eliminacao redundante que ocor-
ria com j = 5. Assim, esta segunda melhoria foi capaz de evitar esta eliminacao
redundante.
Exemplo 3.7. Vamos agora apresentar a aplicacao do crivo com as duas melhorias
acima para encontrar a lista de todos os primos menores ou iguais a 100.
De acordo com a primeira melhoria, so precisamos realizar eliminacoes com
numeros menores ou iguais a b 100c = 10.
Indice 0 1 2 3 4 5 6 7 8 9
Numero 3 5 7 9 11 13 15 17 19 21
Indice 10 11 12 13 14 15 16 17 18 19
Numero 23 25 27 29 31 33 35 37 39 41
Indice 20 21 22 23 24 25 26 27 28 29
Numero 43 45 47 49 51 53 55 57 59 61
Indice 30 31 32 33 34 35 36 37 38 39
Numero 63 65 67 69 71 73 75 77 79 81
Indice 40 41 42 43 44 45 46 47 48
Numero 83 85 87 89 91 93 95 97 99
Nossa primeira selecao sera o numero j = 3, com ndice i = 0. Pela segunda
melhoria, iremos eliminar os numeros de 3 em 3 comecando a eliminacao na posicao
k = (32 3)/2 = 3.
Indice 0 1 2 3 4 5 6 7 8 9
Numero 3 5 7 0 11 13 0 17 19 0
Indice 10 11 12 13 14 15 16 17 18 19
Numero 23 25 0 29 31 0 35 37 0 41
Indice 20 21 22 23 24 25 26 27 28 29
Numero 43 0 47 49 0 53 55 0 59 61
Indice 30 31 32 33 34 35 36 37 38 39
Numero 0 65 67 0 71 73 0 77 79 0
Indice 40 41 42 43 44 45 46 47 48
Numero 83 85 0 89 91 0 95 97 0
50 Numeros Primos
Instrucoes:
1. N [ ] # lista vazia
2. j 3
3. Enquanto j n, faca:
3.1. Adicione j a lista N .
3.2. j j + 2
4. t b(n 1)/2c # tamanho da lista
5. i 0
6. Enquanto (2 i + 3) b nc, faca: # primeira melhoria
6.1. j (2 i + 3)
6.2. k (j j 3)/2 # segunda melhoria
6.3. Enquanto k < t, faca:
6.3.1. N [k] 0
6.3.2. k k + j
6.4. i i + 1
6.5. Enquanto N [i] = 0, faca i i + 1.
7. L [2] # lista contendo apenas o 2
8. Adicione a L todos os elementos de N que sao diferentes de 0.
9. Retorne L.
Existem p 1 numeros inteiros nesta sequencia e todos estao no intervalo [1, p 1],
devido a reducao modulo p. Vamos mostrar que todos os numeros desta sequencia
sao diferentes entre si, o que significa que todos os numeros inteiros do intervalo
[1, p 1] aparecem nesta sequencia.
Suponha que tenhamos 1 i j p 1 e ia ja (mod p). Temos entao que
(j i)a 0 (mod p), o que significa que p divide (j i)a. Como, por hipotese, p
nao divide a, temos que p divide (j i). Entretanto, 0 j i < p 1, e o unico
inteiro neste intervalo que e divisvel pelo primo p e 0. Logo, temos j i = 0, o que
implica i = j. Desta forma, se i 6= j, ia 6 ja (mod p).
Como a sequencia de numeros acima contem exatamente os inteiros no intervalo
[1, p 1], o produto de todos os numeros na sequencia acima sera igual ao produto
de todos os inteiros neste intervalo. Desta forma,
o que implica
ap1 (p 1)! (p 1)! (mod p).
Como (p1)! 6 0 (mod p), podemos multiplicar a igualdade acima pelo seu inverso
em ambos os lados, obtendo ap1 1 (mod p).
Exemplo 3.8. O teorema nos diz que, sem precisarmos fazer nenhuma conta,
1218 1 (mod 19), 322 1 (mod 23) e 840 1 (mod 41), uma vez que 12 6 0
(mod 19), 3 6 0 (mod 23) e 8 6 0 (mod 41) e 19, 23 e 41 sao primos.
E muito importante manter sempre em mente as duas hipoteses do Pequeno
Teorema de Fermat. Podemos ter an1 6 1 (mod n) se n for composto. Alem
disso, se a 0 (mod p), entao qualquer potencia ak , k 0, tambem ira satisfazer
ak 0 (mod p), o que significa que ak 6 1 (mod p), ja que 0 6 1 (mod p).
Analisando com cuidado o Pequeno Teorema de Fermat, podemos ver que ele
nos fornece uma maneira de testar se um dado inteiro n > 2 e composto.
Suponha que n seja primo e seja b um inteiro tal que 2 b n 1. Como b e
menor do que n e diferente de zero, certamente b nao e multiplo de n. Assim, temos
que b 6 0 (mod n). Logo, como estamos supondo que n e primo, entao o Pequeno
Teorema de Fermat nos diz que bn1 1 (mod n).
Vamos entao observar este raciocnio no sentido inverso. Suponha que tenhamos
um valor de b no intervalo 2 b n 1 tal que bn1 6 1 (mod n). Se n fosse
primo, este ultimo resultado estaria contradizendo o resultado esperado a partir do
Pequeno Teorema de Fermat. Logo, neste caso, n e necessariamente composto.
Obtivemos entao o seguinte teste de composicionalidade, baseado no Pequeno
Teorema de Fermat.
Corolario 3.1. Seja n > 2 um inteiro. Se existe um inteiro b no intervalo 2
b n 1 tal que bn1 6 1 (mod n), entao n e um numero composto. Neste caso,
dizemos que b e uma testemunha de que n e composto.
Este teste e conhecido como Teste de Fermat. Repare que se o teste nos in-
forma que um numero e composto, podemos concluir com absoluta certeza que isto
e verdade, mesmo que nao saibamos nenhum de seus fatores proprios. Isto nos
Pequeno Teorema de Fermat 53
mostra um dos resultados mais contra-intuitivos deste estudo dos numeros inteiros:
e possvel determinar que um numero e composto mesmo sem saber fatora-lo.
Como vimos anteriormente neste captulo, o problema da fatoracao e um pro-
blema muito difcil do ponto de vista computacional. Logo, e uma boa notcia que
o problema de determinar se um numero e composto e o problema de calcular a
fatoracao de um numero nao sejam equivalentes, apesar de parecerem ser a primeira
vista.
Se conseguimos encontrar um inteiro b no intervalo 2 b n1 tal que bn1 6 1
(mod n), entao sabemos que n e composto. Entretanto, para um valor fixado de b
neste intervalo, se bn1 1 (mod n), entao nao podemos concluir que n e primo.
Existem numeros n que sao compostos mas satisfazem a congruencia bn1 1
(mod n). Estes numeros sao conhecidos como pseudoprimos de Fermat, ou sim-
plesmente pseudoprimos, para a base b, ja que, apesar de serem compostos, eles
tem o mesmo comportamento que um primo teria com relacao a esta congruencia
com base b.
Exemplo 3.9. O numero 341 e composto, ja que 341 = 11.31. Entretanto, 2340 1
(mod 341). Logo, 341 e um pseudoprimo para a base 2.
A existencia de pseudoprimos nos mostra que, quando selecionamos uma base
b e executamos o Teste de Fermat com esta base, calculando a forma reduzida de
bn1 modulo n, o teste podera nos dar dois resultados: o numero n e composto, se
bn1 6 1 (mod n), ou o resultado do teste e inconclusivo, se bn1 1 (mod n). O
teste e inconclusivo neste ultimo caso porque tanto os numeros primos quanto os
pseudoprimos para a base b (que sao numeros compostos) satisfazem esta ultima
congruencia. Assim, o Teste de Fermat com uma base b e capaz de distinguir alguns
numeros compostos dos numeros primos, mas nao todos. Como consequencia, ao
aplicar o Teste de Fermat com uma base, poderemos em alguns casos concluir com
absoluta certeza que um numero e composto, mas nunca poderemos concluir com
esta mesma certeza que um numero e primo.
Se o Teste de Fermat com uma base fixada nao e suficiente para determinar se
um numero e primo, uma outra ideia poderia ser aplicar a recproca do Teste de
Fermat. Se n > 2 e um inteiro e, para todo inteiro b no intervalo 2 b n 1,
temos que bn1 1 (mod n), entao n e um numero primo?
A resposta e sim. Se n > 2 for um numero composto, a congruencia bn1 1
nao pode ser verdadeira para todos os inteiros no intervalo 2 b n 1. Se n
e composto, n possui um fator proprio 2 f n 1. Em particular, como f e
fator de n, temos que mdc(n, f ) 6= 1. Entao, pelo Teorema da Inversao Modular
(Teorema 2.5), podemos concluir que nao existe nenhum inteiro positivo k tal que
f k 1 (mod n). Assim, em particular, f n1 6 1 (mod n).
Vimos entao que, caso n seja composto, existirao sempre algumas bases no
intervalo 2 b n 1 tais que bn1 6 1. Desta forma, caso pudessemos testar
todas as bases no intervalo, poderamos concluir com absoluta certeza se n e primo
ou composto. Porem, quando n e um numero muito grande, como efetivamente
acontece na pratica, este teste atraves da varredura exaustiva de todas as bases no
intervalo e totalmente inviavel.
Outra ma notcia para a eficacia do Teste de Fermat em diferenciar totalmente
numeros primos e compostos e a existencia de uma famlia infinita de inteiros com-
postos, conhecidos como Numeros de Carmichael , para os quais as unicas bases
b em que temos bn1 6 1 sao justamente as bases que utilizamos no argumento
acima, isto e, as bases em que mdc(n, b) 6= 1. Para todos os inteiros b no intervalo
2 b n 1 em que mdc(n, b) = 1, teremos bn1 1 (mod n).
54 Numeros Primos
Desta forma, conclumos que, quando o modulo p e primo, ak ar (mod p), onde r
e o resto da divisao de k por p 1. Podemos entao realizar o calculo de potenciacao
com o expoente menor r, ao inves de com o expoente maior k.
Exemplo 3.10. Vamos calcular a forma reduzida de 8293487559837 modulo 41. Como
41 e primo e 8 6 0 (mod 41), podemos utilizar o Pequeno Teorema de Fermat para
nos auxiliar, conforme explicado acima.
Comecamos dividindo 293487559837 por 40, obtendo
Logo, a forma reduzida de 8293487559837 modulo 41 e 39, sendo que nao precisamos
realizar os calculos com o expoente 293487559837 para obtermos o resultado.
3.5 Exerccios
1. Escreva uma descricao formal do algoritmo para a fatoracao completa de um
inteiro n 2 no formato dos outros algoritmos apresentados neste captulo.
O algoritmo devera obter a fatoracao conforme a descricao na Definicao 3.4.
Para isso, o algoritmo devera retornar duas listas: uma lista de fatores primos
distintos de n e uma lista das respectivas multiplicidades destes fatores na
fatoracao de n.
60 Numeros Primos
8.1. 10027
8.2. 13823
8.3. 15841
8.4. 1373653
Captulo 4
Grupos
Arithmeticae [7], escrito em Latim em 1798, quando ele tinha 21 anos, e publicado
em 1801, Gauss cataloga de maneira bastante completa resultados a respeito dos
numeros inteiros, de aritmetica modular e tambem resultados que acabaram incor-
porados a teoria de grupos, como o Teorema da Raiz Primitiva. Neste trabalho de
catalogacao, Gauss apresenta resultados de matematicos anteriores (como Euclides,
Fermat, Euler e Lagrange, entre outros), alem de acrescentar resultados e provas de
sua propria autoria. Em particular, a notacao de aritmetica modular que e utilizada
ate hoje, e que nos tambem utilizamos neste livro, e herdada das Disquisitiones
Arithmeticae.
Iniciamos o nosso estudo da teoria de grupos pela definicao mais basica, isto e,
a definicao de um grupo.
Definicao 4.1. Um grupo e um par G = (G, ), onde G e um conjunto e e uma
operacao : G G G (uma operacao que toma dois operandos em G e retorna
como resultado um elemento de G) que satisfaz as seguintes propriedades:
1. Associatividade: para todo a, b, c G, (a b) c = a (b c);
2. Existencia de elemento neutro: existe um elemento e G tal que, para todo
a G, a e = e a = a;
3. Existencia de inversos: para todo a G, existe um elemento a1 G tal que
a a1 = a1 a = e, onde e e o elemento neutro.
Quando estivermos falando de um grupo em um contexto generico, sempre uti-
lizaremos a notacao e para o elemento neutro do grupo.
Podemos reparar tambem que nao exigimos em um grupo que a operacao seja
comutativa no caso geral.
Definicao 4.2. Um grupo G = (G, ) e chamado de grupo comutativo ou grupo
abeliano se, alem das propriedades acima, ele satisfaz a seguinte propriedade:
4. Comutatividade: para todo a, b G, a b = b a.
A nomenclatura grupo abeliano e uma homenagem ao matematico noruegues
Niels Henrik Abel (1802-1829), outro pioneiro da teoria de grupos ao lado de Galois.
Tragicamente, tanto Abel quanto Galois morreram com menos de 30 anos de idade.
Vamos analisar agora alguns exemplos de pares de conjuntos e operacoes que
nao sao grupos e outros que sao grupos.
Exemplo 4.1. O par G = (N, +) nao e um grupo. A soma de naturais e associativa
e 0 e o elemento neutro da operacao, porem nem todos os naturais possuem um
inverso aditivo que tambem seja natural. Por exemplo, o inverso aditivo de 2 e 2,
mas 2 / N.
Exemplo 4.2. O par G = (Z, +) e um grupo. Neste caso, o inverso aditivo de
qualquer inteiro tambem e um numero inteiro.
Exemplo 4.3. O par G = (Zmpares , +), onde Zmpares representa o conjunto dos
inteiros mpares, nao e um grupo, pois neste caso a soma nem sequer atende a
nossa definicao de operacao. A operacao de um grupo deve ser necessariamente
uma funcao que toma dois elementos do conjunto e retorna um valor que tambem
pertenca ao conjunto. Mas no nosso exemplo atual, em que estamos trabalhando
com o conjunto dos inteiros mpares, isto nao acontece, ja que a soma de dois
inteiros mpares e um inteiro par.
Os Grupos Finitos U (n) 63
Podemos reparar que o valor de (p) que calculamos anteriormente e um caso par-
ticular da formula acima quando k = 1.
Vamos agora utilizar o resultado acima para determinar o valor de (n) para
qualquer valor de n 2. Para isso, precisaremos ainda de alguns resultados auxili-
ares.
Lema 4.1. Sejam m, n 2 tais que mdc(m, n) = 1 e seja x Zmn . Vamos denotar
por a a forma reduzida de x modulo m e por b a forma reduzida de x modulo n.
Entao, x U (mn) se e somente se a U (m) e b U (n).
Demonstracao: () Se x U (mn), entao existe x1 U (mn) tal que xx1 1
(mod mn). Logo, mn divide xx1 1. Como m divide mn, entao m divide xx1 1,
o que significa que xx1 1 (mod m). Como x a (mod m), entao ax1 1
(mod m), o que significa que a possui inverso multiplicativo modulo m, isto e,
a U (m). Um raciocnio inteiramente analogo nos mostra que b U (n).
() Se a U (m), entao existe a1 U (m) tal que aa1 1 (mod m). Ana-
logamente, se b U (n), entao existe b1 U (n) tal que bb1 1 (mod n). Como
mdc(m, n) = 1, podemos utilizar o Algoritmo Chines do Resto para calcular a
solucao unica modulo mn do sistema
y a1
(mod m)
y b1 (mod n).
Vamos mostrar agora que a solucao unica y deste sistema e o inverso multiplicativo
de x modulo mn. Como x a (mod m) e y a1 (mod m), entao xy aa1 1
(mod m). Assim, xy 1 e divisvel por m. Um raciocnio inteiramente analogo nos
mostra que xy 1 e divisvel por n. Como mdc(m, n) = 1, se m e n dividem xy 1,
entao mn divide xy 1, de acordo com o Lema 2.2. Assim, xy 1 (mod mn), o
que significa que x possui inverso multiplicativo modulo mn. Logo, x U (mn).
Na igualdade acima, aplicamos o Teorema 4.1, uma vez que o maximo divisor comum
entre potencias de primos distintos e sempre 1. Podemos agora aplicar a formula
que deduzimos anteriormente para (pk ), obtendo
4.3 Subgrupos
Nesta secao, apresentamos a nocao de subgrupo, que se relaciona com a nocao de
grupo de forma analoga a relacao entre subconjunto e conjunto. Entretanto, como
um grupo possui uma estrutura interna dada por propriedades de sua operacao,
esta estrutura tambem precisa ser considerada na definicao de subgrupo.
Definicao 4.5. Se G = (G, ) e um grupo, dizemos que H = (H, ) e um subgrupo
de G se as seguintes propriedades sao satisfeitas:
1. H G (H e um subconjunto de G);
2. Para todo h, j H, temos que h j H;
3. e H, onde e e o elemento neutro da operacao ;
4. Para todo h H, existe um elemento h1 H tal que h h1 = h1 h = e.
A partir desta definicao, podemos notar que um subgrupo nao e obtido a partir
de qualquer subconjunto do grupo original. Para que H = (H, ) seja um subgrupo
de G = (G, ), ele deve satisfazer todas as propriedades de um grupo quando olhado
isoladamente. Desta forma, para que H = (H, ) seja um subgrupo de G = (G, ),
ele deve conter o elemento neutro da operacao, todos os elementos de H devem
possuir inversos que tambem pertencam a H e a operacao deve estar bem definida
quando restrita a H, isto e, quando operamos dois elementos de H, o resultado da
operacao tambem precisa pertencer a H.
Subgrupos 67
Exemplo 4.8. Dado o grupo U (18) = {1, 5, 7, 11, 13, 17}. O conjunto H = {1, 7,
13} com a operacao de produto modulo 18 forma um subgrupo de U (18), uma vez
que H e subconjunto de U (18), 1 H, o produto de quaisquer dois elementos de H
tambem resulta em um elemento de H e o inverso de todo elemento de H tambem
pertence a H (o inverso de 1 e ele proprio e 7 e 13 sao inversos um do outro).
g1 H = {g1 h1 , g1 h2 , . . . , g1 ht }.
G = g0 H g1 H g2 H . . . gs H,
|G| = (s + 1)|H|,
H = {e, a, a2 , a3 , . . .}.
H = {e, a, a2 , . . . , ak1 }.
Vamos mostrar que todos estes elementos de H sao distintos. Suponha que
al = am , com 0 m l k 1. Entao, operando com (a1 )m dos dois lados da
igualdade, obtemos alm = e. Como m e l sao menores ou iguais a k 1, temos
que 0 l m k 1. Entretanto, k e o menor inteiro positivo tal que ak = e.
Logo, se l m < k e alm = e, a unica possibilidade e l m = 0, o que significa que
l = m. Assim, todos os elementos na descricao de H acima sao distintos. Podemos
concluir entao que, se a ordem de a e k, o conjunto H das potencias de a tera k
elementos.
Vemos que e H. Alem disso, para uma potencia al , com 1 l k 1, temos
que al akl = ak = e, logo akl e o inverso de al . Desta maneira, todo elemento
de H possui inverso tambem em H. Podemos concluir entao que (H, ) e um grupo
finito com ordem k. Alem disso, como H e um subconjunto de G, (H, ) e um
subgrupo de G.
70 Grupos
Dizemos que (H, ) e o grupo cclico gerado por a ou, alternativamente, o sub-
grupo cclico de G gerado por a. Dizemos que a e um gerador ou uma raiz primitiva
do grupo (H, ).
Vemos agora a relacao entre a nocao de ordem de um elemento a de um grupo
(menor inteiro positivo k tal que ak = e) e a nocao de ordem de um grupo (numero
de elementos do grupo). Um elemento a de ordem k gera um grupo cclico de ordem
k (um grupo com k elementos).
A partir dos conceitos de grupo cclico e de gerador ou raiz primitiva, pode-
mos definir um problema central para as aplicacoes de grupos em criptografia: o
Problema do Logaritmo Discreto.
Assim, sabemos que se G possui ordem n e l nao divide n, l certamente nao sera
o menor inteiro positivo tal que al = e.
Conforme vimos anteriormente, um grupo de ordem prima nao possui subgrupos
proprios. Assim, os unicos subgrupos de um grupo de ordem prima sao o proprio
grupo e o grupo que contem apenas o elemento neutro. Seja entao G = (G, ) um
grupo de ordem prima e seja a G tal que a 6= e. Vamos considerar o subgrupo de
G gerado por a. Como a1 = a 6= e, o subgrupo cclico gerado por a nao tem ordem
1. Por outro lado, se o subgrupo cclico gerado por a nao e o grupo que contem
apenas o elemento neutro, entao a unica opcao restante entre os subgrupos de G e
que ele seja o proprio grupo G. Desta forma, G e um grupo cclico gerado por a.
Podemos concluir entao que, se G = (G, ) e um grupo de ordem prima, entao ele e
um grupo cclico e todo elemento a G tal que a 6= e e um gerador de G.
Grupos e Subgrupos Cclicos 71
Como nenhum elemento de U (20) possui a mesma ordem de U (20), que e (20) = 8,
entao U (20) nao e um grupo cclico.
2 2 2
7 = 9 = 15 = 1. Como a ordem de H e 4 e nenhum de seus elementos tem
ordem 4, nenhum deles e um gerador de H.
Repare que a ordem de H e um numero composto. Isto nao e uma coincidencia,
uma vez que vimos anteriormente que todo grupo de ordem prima deve necessaria-
mente ser cclico.
Apresentamos agora um lema central a respeito de grupos finitos. Este lema
sera muito importante como um componente na prova de diversos resultados sobre
grupos.
Lema 4.2 (Lema Chave). Seja G = (G, ) um grupo finito e a G. Temos que
at = e se e somente se t e divisvel pela ordem de a em G.
Demonstracao: () Seja k a ordem de a em G e suponha que t seja divisvel por
k. Logo, t = kt0 , para algum t0 Z. Temos entao
0 0 0
at = akt = (ak )t = et = e.
() Suponha que at = e. Vamos dividir t por k, obtendo t = kq + r, com
0 r < k. Temos entao
e = at = akq+r = (ak )q ar = eq ar = ar .
Como k e a ordem de a, ele e o menor inteiro positivo tal que ak = e. Por outro
lado, pela igualdade acima, temos que ar = e, com r < k. Desta forma, o unico
valor possvel para r e r = 0, o que significa que t e divisvel por k.
0 0 0 0 0 0
(g m )n = (g dm )n = (g m )dn = (g m )n = e,
pelo Corolario 4.2, o que significa que a ordem de g m divide n0 , pelo Lema Chave
(Lema 4.2). Mas como d > 1, entao n0 < n. Logo, a ordem de g m e menor do que
n, o que significa que g m nao e uma raiz primitiva de G.
Grupos e Subgrupos Cclicos 73
Corolario 4.3. Seja G um grupo finito de ordem n. Se G possui ao menos uma raiz
primitiva, entao G possui exatamente (n) razes primitivas. Em outras palavras, se
G e um grupo finito cclico de ordem n, G possui exatamente (n) razes primitivas.
Demonstracao: Suponha que g e uma raiz primitiva de G. Entao, o conjunto de to-
das as razes primitivas de G pode ser calculado como {g i : 1 i < n e mdc(i, n) =
1}, de acordo com o Teorema 4.3. O numero de elementos deste conjunto e igual a
quantidade de numeros no intervalo 1 i < n que satisfazem mdc(i, n) = 1. Mas
esta quantidade e dada justamente por (n).
Seja
g(x) = f (x) ak (x s1 )(x s2 ) . . . (x sk ).
Note que o grau de g(x) e menor do que k ja que o termo ak xk de f (x) e cancelado
pelo termo ak xk que aparece em ak (x s1 )(x s2 ) . . . (x sk ). Pela hipotese
de inducao, se g(x) satisfizer as hipoteses do enunciado, a congruencia g(x) 0
(mod p) tera menos de k solucoes distintas modulo p. Entretanto, temos que g(si )
0 (mod p) para todos os valores si , 1 i k. Logo, a hipotese do enunciado de
que o termo lder do polinomio nao e congruente a zero modulo p nao pode estar
sendo satisfeita por g(x). Isso significa que g(x) e o polinomio identicamente nulo
modulo p. Assim, a partir da equacao acima, obtemos
Com estes dois lemas acima, podemos agora provar o Teorema da Raiz Pri-
mitiva. Este teorema foi apresentado e provado por Gauss no artigo 55 de suas
Disquisitiones Arithmeticae [7]. A prova que apresentamos abaixo e a mesma
apresentada no texto de Gauss.
Teorema 4.4 (Teorema da Raiz Primitiva). Se p e primo, entao U (p) e um grupo
cclico.
Demonstracao: Como p e primo, U (p) = Zp {0}, de forma que a ordem de U (p) e
p1. Vamos fatorar p1, obtendo p1 = q1e1 q2e2 . . . qkek , onde 1 < q1 < q2 < . . . < qk
sao primos distintos e ei 1 para todo 1 i k.
Para cada potencia qiei , 1 i k, nesta fatoracao, e possvel encontrar um
elemento de U (p) que tenha ordem qiei . Para isso, comecamos buscando um elemento
(p1)/qi
ai U (p) tal que ai 6 1 (mod p). Este elemento precisa existir, ja que os
elementos u U (p) tais que u(p1)/qi 1 (mod p) sao solucoes da congruencia
x(p1)/qi 1 0 (mod p), que possui no maximo (p 1)/qi < p 1 solucoes
distintas modulo p, de acordo com o Lema 4.4.
e
(p1)/qi i
Uma vez encontrado o valor ai , calculamos hi ai (mod p). Temos que
ei
q
hi i ap1
i 1 (mod p),
de acordo com o Corolario 4.2, logo a ordem de hi divide qiei pelo Lema Chave
(Lema 4.2). Suponha entao que a ordem de hi seja qit , onde t < ei . Temos entao
e e t
qt (p1)/qi i q t (p1)/qi i
1 hi i (ai i) ai (mod p),
o que significa que a ordem de ai divide (p 1)/qiei t pelo Lema Chave (Lema 4.2).
Mas como ei t > 1, (p 1)/qiei t divide (p 1)/qi . Logo, a ordem de ai divide
(p1)/qi
(p 1)/qi , o que implica que ai 1 (mod p), tambem pelo Lema Chave.
Mas isto e uma contradicao com a escolha de ai . Desta forma, a ordem de hi e
igual a qiei .
Grupos e Subgrupos Cclicos 75
Realizado este calculo para cada potencia qiei da fatoracao, obtemos elementos
h1 , h2 , . . . , hk U (p) tais que suas respectivas ordens sao q1e1 , q2e2 , . . . , qkek . Repare
que, como estas ordens sao potencias de primos distintos, se m e a ordem de hi e
n e a ordem Q de hj , com i 6= j, entao mdc(m,Q
n) = 1. Temos entao que o elemento
g, onde g 1ik hi (mod p) tem ordem 1ik qiei = p 1, de acordo com o
Lema 4.3. Logo, g e uma raiz primitiva de U (p), o que significa que U (p) e um
grupo cclico.
O Algoritmo de Gauss retorna uma das razes primitivas de U (p), mas nao ha
garantias de que ele ira retornar a menor raiz primitiva. De qualquer forma, uma
vez que uma das razes primitivas e conhecida, todas as outras podem ser calculadas
utilizando-se o Teorema 4.3.
76 Grupos
Exemplo 4.14. Vamos utilizar o Algoritmo de Gauss para calcular uma raiz pri-
mitiva de U (41). Temos entao p = 41. Fatorando p 1 = 40, obtemos 40 = 23 .5,
logo q1 = 2, q2 = 5, e1 = 3 e e2 = 1.
Comecamos com q1 = 2. 2(p1)/q1 220 1 (mod 41), mas 320 40 6 1
e1
(mod 41). Calculamos entao h1 3(p1)/q1 35 38 (mod 41).
Prosseguimos agora com q2 = 5. Fazendo 2(p1)/q2 28 10 6 1 (mod 41).
e2
Calculamos entao h2 2(p1)/q2 28 10 (mod 41).
Uma raiz primitiva de U (41) sera entao a forma reduzida de h1 h2 modulo 41.
Temos h1 h2 38.10 380 11 (mod 41). Logo, 11 e uma raiz primitiva de
U (41).
Repare que existe ainda outra maneira diferente de escrever este algoritmo. Da
maneira que implementamos o algoritmo, para cada fator primo qi , buscamos um
elemento ai que fosse adequado. A outra maneira seria realizar a busca da forma
inversa: para cada valor a no intervalo 2 a p 1, buscar quais fatores primos
qi sao atendidos por a, isto e, quais fatores primos qi satisfazem a(p1)/qi 6 1
(mod p), e calcular todos os respectivos valores de hi utilizando este elemento a. Em
seguida, enquanto restarem primos qi que nao foram atendidos, incrementamos
o valor de a e repetimos o processo. Deixamos a descricao formal desta segunda
versao do Algoritmo de Gauss como exerccio (Exerccio 5).
4.5 Exerccios
1. Seja G um grupo. Mostre que, se o quadrado de qualquer elemento de G e
igual ao elemento neutro, entao o grupo e abeliano.
2. Dados os seguintes valores de n, calcule (n):
2.1. 16807
2.2. 9282
2.3. 30375
2.4. 694575
3. Determine todos os subgrupos cclicos dos grupos abaixo, com seus respectivos
geradores:
3.1. U (8)
3.2. U (18)
3.3. U (21)
3.4. U (25)
4. Utilizando o Algoritmo de Gauss, determine uma raiz primitiva para cada um
dos grupos abaixo. Em seguida, encontre todas as razes primitivas de cada
grupo utilizando o Teorema 4.3:
4.1. U (7)
4.2. U (13)
4.3. U (19)
4.4. U (53)
5. Escreva a descricao formal da segunda versao do Algoritmo de Gauss que foi
apresentada no final da Secao 4.4.
Captulo 5
O Metodo El Gamal
Neste ponto, apos todos os conceitos matematicos necessarios a respeito dos numeros
inteiros, da aritmetica modular e da teoria de grupos terem sido apresentados,
estamos prontos para entender o funcionamento do metodo El Gamal.
Neste captulo, apresentamos o metodo El Gamal para criptografia e para assina-
tura digital, assim como o metodo DSA para assinatura digital, que e uma pequena
variacao do El Gamal. Mostraremos como construir as chaves de encriptacao e
decriptacao (ou chaves de assinatura e verificacao, no caso da assinatura digital) e
quais sao os calculos necessarios para encriptar e decriptar uma mensagem (ou para
assinar uma mensagem e verificar uma assinatura).
Discutiremos o funcionamento do metodo, mostrando que a mensagem original
sempre pode ser recuperada por quem possui a chave correta de decriptacao. Ana-
logamente, no caso da assinatura digital, mostramos tambem que uma assinatura
sempre pode ser produzida para qualquer mensagem por quem possui a chave cor-
reta de assinatura. Por outro lado, mostraremos que o metodo e bastante seguro,
mostrando que a unica maneira conhecida para um usuario nao autorizado calcu-
lar o valor da chave de decriptacao a partir apenas do conhecimento da chave de
encriptacao (ou o valor da chave de assinatura a partir da chave de verificacao)
envolve a resolucao do Problema do Logaritmo Discreto em um grupo finito, que
e um problema computacionalmente difcil. Desta forma, podemos concluir que o
metodo El Gamal e um metodo efetivo e seguro de criptografia de chave publica e
assinatura digital.
3. Decriptacao:
Desta forma, um metodo de criptografia de chave publica deve nos oferecer tres
algoritmos: um algoritmo de geracao de chaves, um algoritmo de encriptacao e um
algoritmo de decriptacao.
Por outro lado, quando Alice envia uma mensagem para Bernardo, Bernardo
gostaria de ter alguma garantia de que a mensagem realmente foi criada por Alice,
e nao por outra pessoa.
Um exemplo classico da necessidade deste tipo de garantia de autenticidade
ocorre se Bernardo for o gerente responsavel pela conta bancaria de Alice. Se
ele receber uma mensagem de alguem dizendo ser Alice e pedindo para esvaziar a
sua conta bancaria, ele precisa ter alguma forma de se certificar se a mensagem
realmente foi criada por Alice ou se foi criada por outra pessoa tentando prejudicar
Alice em uma fraude bancaria.
Esta seguranca com relacao ao remetente da mensagem pode ser fornecida pelas
assinaturas digitais. Os metodos de assinatura digital buscam justamente lidar com
esta situacao em que todas as mensagens chegam atraves de um canal inseguro e
ha a necessidade de se verificar qual foi a origem de cada mensagem. O objetivo
da assinatura digital e impedir que uma pessoa ou entidade se aproveite do canal
inseguro para enviar mensagens fingindo que e outra pessoa.
Em um metodo de assinatura digital, a chave de assinatura de Alice sera pri-
vada, de maneira que apenas ela seja capaz de gerar assinaturas para as mensagens
que ela criar. Por outro lado, a chave de verificacao da assinatura sera publica, per-
mitindo a qualquer um, incluindo Bernardo, verificar a assinatura das mensagens
recebidas de forma a determinar se a pessoa que criou originalmente a mensagem
realmente e quem diz ser. Da mesma forma que na criptografia de chave publica,
para que um sistema nestes moldes seja seguro, Alice tem que garantir que a sua
chave de assinatura permaneca efetivamente privada. Alem disso, uma vez que a
chave de verificacao e publica e, portanto, esta acessvel a todos, o calculo da chave
privada a partir da chave publica deve ser extremamente complexo do ponto de
vista computacional.
Podemos resumir entao os principais passos de um metodo de assinatura digital:
1. Geracao de chaves:
1.1. Um metodo de assinatura digital exige que Alice realize inicialmente uma
escolha de valores para alguns parametros (estes valores sao publicos apos
sua escolha).
1.2. Alice cria um par de chaves de acordo com os valores dos parametros se-
lecionados anteriormente: uma chave privada de assinatura e uma chave
publica de verificacao.
1.3. Alice divulga sua chave publica para todos.
80 O Metodo El Gamal
1.4. A partir deste momento, apenas Alice pode assinar digitalmente, utili-
zando sua chave privada, uma mensagem que foi criada por ela.
1.5. Por outro lado, qualquer um (incluindo Bernardo) pode utilizar a chave
publica de Alice para verificar assinaturas em mensagens que, ao menos
supostamente, foram criadas por ela.
2. Assinatura:
2.1. Para que Alice possa enviar uma mensagem assinada a Bernardo, ela
executa o algoritmo de assinatura oferecido pelo metodo que esta sendo
utilizado fornecendo como entradas a mensagem que ela quer enviar e a
sua chave privada. O algoritmo produzira uma assinatura para a men-
sagem.
2.2. Em seguida, Alice envia para Bernardo o par formado pela mensagem e
pela assinatura produzida pelo algoritmo.
3. Verificacao:
A B C D E F G H I J K L M
10 11 12 13 14 15 16 17 18 19 20 21 22
N O P Q R S T U V W X Y Z
23 24 25 26 27 28 29 30 31 32 33 34 35
82 O Metodo El Gamal
Teste de Miller-Rabin com varias bases no Captulo 3 e mostramos que ela pode ser arbitrariamente
pequena conforme aumentamos o numero de bases.
Criptografia El Gamal 83
Instrucoes:
quando ele for reunido aos outros blocos para recompor a mensagem original, uma
mensagem diferente sera obtida.
Exemplo 5.1. Suponha que p = 127 e a mensagem que queremos encriptar e
m = 110125. Como m p, temos que quebrar esta mensagem em blocos. Podemos
quebra-la como 1 101 25, como 1 10 125, como 110 125 e como 110 12 5,
dentre outras formas. Mas nao podemos quebra-la como 110125 ou 110125,
dentre outras formas, porque nestes casos um dos blocos esta comecando com um
zero a esquerda.
Para o algoritmo de encriptacao, vamos entao assumir que temos os parametros
p e g e a chave publica de encriptacao c e que a mensagem m ja e uma mensagem
que esta no intervalo 0 < m < p.
Para encriptar esta mensagem, comecamos selecionando aleatoriamente um va-
lor k no intervalo 1 < k < p 1. Este valor e conhecido como chave efemera,
uma vez que ele e descartado logo apos a finalizacao da encriptacao, sendo seleci-
onado um novo valor de k para cada novo processo de encriptacao. O uso de uma
chave efemera coloca o metodo de criptografia El Gamal na famlia dos chamados
metodos de encriptacao probabilstica. Em metodos de encriptacao probabilstica,
uma mesma mensagem pode ser encriptada de diversas formas diferentes, devido a
possibilidade de uso de chaves efemeras diferentes em cada processo de encriptacao.
E absolutamente essencial selecionar um novo valor aleatorio de k a cada nova
mensagem que quisermos encriptar. A repeticao do mesmo valor de k na encriptacao
de duas mensagens distintas pode abrir uma seria brecha de seguranca, conforme
notado pelo proprio El Gamal em seu artigo original [5].
Estudaremos com mais detalhes os problemas decorrentes da re-utilizacao de
valores de k em mensagens distintas ao estudarmos o metodo de assinatura digital El
Gamal, onde eles sao ainda mais serios e, portanto, mais simples de serem percebidos
e estudados.
Apos a escolha do valor de k, calculamos dois valores s e t, onde
s = g k mod p
e
t = mck mod p.
A mensagem encriptada sera entao o par (s, t), onde 0 < s, t < p.
Descrevemos abaixo o algoritmo de encriptacao, de acordo com os procedimentos
que apresentamos.
Entrada: Um numero primo p, uma raiz primitiva g de U (p), uma chave publica
c e uma mensagem 0 < m < p.
Sada: Uma mensagem encriptada m
b = (s, t), onde 0 < s, t < p.
Instrucoes:
1. Selecione aleatoriamente um valor k no intervalo 1 < k < p 1.
2. s g k mod p #s e a forma reduzida de g k modulo p
3. t (m ck ) mod p
b (s, t)
4. m
86 O Metodo El Gamal
5. Retorne m.
b
m0 = s0 t mod p.
Instrucoes:
Instrucoes:
Definicao 5.1. Uma funcao hash criptograficamente segura e uma funcao hash h
que satisfaz as seguintes propriedades:
r = g k mod p
e
s = (k 1 (h(m) ar)) mod p 1,
onde k 1 e o inverso de k modulo p1, isto e, kk 1 1 (mod p1). E fundamental
observar que o calculo de r e feito modulo p, mas o calculo de s e feito modulo p 1.
A assinatura da mensagem sera entao o par (r, s).
Descrevemos a seguir o algoritmo de assinatura, de acordo com os procedimentos
que apresentamos.
90 O Metodo El Gamal
Entrada: Um numero primo p, uma raiz primitiva g de U (p), uma chave privada
a, uma mensagem m {0, 1} e uma funcao hash criptograficamente segura
h : {0, 1} Zp .
Instrucoes:
Desta forma, esta primeira verificacao do algoritmo impede este tipo de falsificacao.
Para mais detalhes sobre a necessidade desta verificacao para evitar uma potencial
brecha de seguranca, [16] pode ser consultado.
Em seguida, calculamos dois valores u1 e u2 , onde
u1 = (v r rs ) mod p
e
u2 = g h(m) mod p.
Temos entao que a assinatura e valida se e somente se u1 = u2 .
Descrevemos abaixo o algoritmo de verificacao de assinaturas, de acordo com os
procedimentos que apresentamos.
Entrada: Um numero primo p, uma raiz primitiva g de U (p), uma chave publica
v, uma mensagem m {0, 1} , uma assinatura Am = (r, s) para m e uma
funcao hash criptograficamente segura h : {0, 1} Zp .
Instrucoes:
v r (g a )r g ar (mod p).
rs (g k )s g ks (mod p).
92 O Metodo El Gamal
e
u2 g h(m) 576 8 (mod 191).
Como u1 = u2 , a assinatura e valida.
Encerramos esta secao mostrando a brecha de seguranca que se abre quando o
mesmo valor de k e utilizado na assinatura de duas mensagens distintas m1 e m2 ,
onde m1 6= m2 .
Seja Am1 = (r1 , s1 ) a assinatura produzida para m1 e Am2 = (r2 , s2 ) a assinatura
produzida para m2 . Pelo modo como uma assinatura e calculada no algoritmo de
assinatura, temos que
r1 = g k mod p
r2 = g k mod p,
ja que o mesmo valor de k foi usado nos dois processos de assinatura. Desta forma,
r1 = r2 . Uma vez que temos esta igualdade, denotaremos entao os dois por r daqui
em diante. Vemos entao que se duas assinaturas possuem o primeiro componente
igual, isto e um indicador de que o mesmo valor de k foi utilizado para produzir
ambas.
Por outro lado, temos
Uma vez que os dois modulos sao iguais, podemos subtrair as duas igualdades,
obtendo
k(s1 s2 ) (h(m1 ) h(m2 )) (mod p 1).
Assinatura Digital El Gamal 93
Como a chave privada e um valor no intervalo 1 < a < p1, esta ultima congruencia
nos permite calcular a chave privada como a = (r1 (h(m1 ) ks1 )) mod p 1. Com
o conhecimento da chave privada, qualquer pessoa pode se fazer passar pelo reme-
tente original, assinando mensagens que serao validadas pelo algoritmo de veri-
ficacao.
Entretanto, mesmo que mdc(r, p1) 6= 1 e nao possamos calcular a chave privada
diretamente, ainda temos informacao suficiente para forjar assinaturas que serao
aceitas pelo algoritmo de verificacao. Como obtivemos o valor de k e conhecemos r,
temos agora os dois valores que satisfazem r = g k mod p. Podemos tambem calcular
k 1 , o inverso de k modulo p 1. Finalmente, tambem ja calculamos acima o valor
de ar modulo p 1.
Se queremos forjar uma assinatura valida para uma mensagem m, e precisamos
obter um valor se de forma que o par (r, se) seja uma assinatura valida para m e de
acordo com a chave privada de assinatura a (mesmo sem saber precisamente o valor
desta chave). Pela formula do algoritmo de geracao de assinatura, temos que
se = k 1 (h(m)
e ar) mod p 1.
mensagem m3 com h(m3 ) = 13. Iremos utilizar o mesmo valor de r presente nas
assinaturas de m1 e m2 , isto e, r = 105. Vamos agora calcular o valor de s pela
formula da assinatura:
Instrucoes:
r = (g k mod p) mod q
e
s = (k 1 (h(m) + ar)) mod q,
onde k 1 e o inverso de k modulo q. Como q e primo e 1 < k < q, para qualquer
valor selecionado de k teremos mdc(k, q) = 1, isto e, qualquer valor de k tera inverso
modulo q. A assinatura da mensagem sera entao o par (r, s).
96 O Metodo El Gamal
Instrucoes:
Exemplo 5.7. Vamos realizar um exemplo de assinatura com o metodo DSA. Su-
ponha que os primos escolhidos sao q = 131 e p = 2q + 1 = 263. O Algoritmo
de Gauss nos da g 0 = 259 como uma raiz primitiva de U (263). Calculamos entao
g = (g 0 )(p1)/q mod p = 2592 mod 263 = 16. Vamos assinar novamente a mensa-
gem m = 1110111, com a mesma funcao h que utilizamos nos exemplos anteriores.
Logo, temos que h(m) = 6. Vamos considerar que a chave privada que esta sendo
utilizada e a = 7 e que o valor de k selecionado e k = 10. Calculamos entao
r = (g k mod p) mod q = (1610 mod 263) mod 131 = 25 mod 131 = 25. Em seguida,
utilizando o Algoritmo Euclidiano Estendido, calculamos o inverso de k modulo q,
obtendo k 1 = 118. Finalmente, calculamos s k 1 (h(m)+ar) 118(6+7.25) 5
(mod 131). Logo, a assinatura da mensagem m = 1110111 e o par (25, 5).
u2 = (rs1 ) mod q
e
u3 = ((g u1 v u2 ) mod p) mod q.
Temos entao que a assinatura e valida se e somente se u3 = r.
Descrevemos abaixo o algoritmo de verificacao de assinaturas, de acordo com os
procedimentos que apresentamos.
Instrucoes:
5.5 Exerccios
1. Dadas as mensagens, os parametros, as chaves publicas e as chaves efemeras
abaixo, encripte as mensagens com o metodo El Gamal.
1.1. p = 107, g = 103, c = 16, m = 38, k = 2
1.2. p = 163, g = 159, c = 99, m = 89, k = 3
1.3. p = 211, g = 155, c = 57, m = 102, k = 4
1.4. p = 241, g = 14, c = 100, m = 191, k = 5
2. Dadas as mensagens encriptadas, o parametro p e as chaves privadas a seguir,
decripte as mensagens levando em conta que elas foram encriptadas com o El
Gamal.
Exerccios 99
2.1. p = 107, d = 5, m
b = (43, 39)
2.2. p = 163, d = 9, m
b = (117, 67)
2.3. p = 211, d = 12, m
b = (192, 129)
2.4. p = 241, d = 19, m
b = (32, 134)
Resolucao do Problema do
Logaritmo Discreto
x = im + j,
Instrucoes:
1. m d p 1 e #b p 1c + 1
2. j 0
3. B [ ] # lista vazia
4. Enquanto j < m, faca:
4.1. s g j mod p
4.2. Adicione s na posicao j da lista B.
4.3. j j + 1
5. Calcule, utilizando o Algoritmo Euclidiano Estendido, o inverso de g
modulo p. Vamos denota-lo por g 1 .
6. t (g 1 )m mod p
7. i 0
8. Enquanto i < m, faca:
8.1. s (h ti ) mod p
8.2. Se s B, entao:
8.2.1. Seja j a posicao de s em B.
8.2.2. x (i m + j)
8.2.3. Retorne x.
8.3. i i + 1
Este algoritmo pode precisar, no pior caso, construir duas listas de tamanho
aproximadamente p cada uma. Desta forma, no pior caso, o algoritmo ira executar
aproximadamente 2 p passos. Embora esta quantidade de passos ainda seja muito
elevada, caso p seja muito grande, ela e uma melhora substancial em relacao aos p
passos que o algoritmo ingenuo pode precisar executar.
Na pratica, se p for muito grande, nem o algoritmo ingenuo nem o BSGS serao
capazes de encontrar a solucao desejada. Entretanto, como a quantidade de passos
executada pelo BSGS e substancialmente menor do que a executada pelo algoritmo
ingenuo, a selecao de um primo p muito grande torna-se ainda mais crucial para a
seguranca dos metodos de criptografia e assinatura digital que estudamos.
Comecamos calculando m = d p 1 e = d 240e = 16. Calculamos entao a
lista B dos baby-steps g j mod p = 14j mod 241, para 0 j < 16.
j 0 1 2 3 4 5 6 7
14j mod 241 1 14 196 93 97 153 214 104
j 8 9 10 11 12 13 14 15
14j mod 241 10 140 32 207 6 84 212 76
i 0 1 2 3
65.94i 65 85 37 104
Esta em B? Nao Nao Nao Sim
Calculamos novos elementos das duas listas ate chegarmos a um valor de j tal
que yj = zj . Como temos que zj = y2j , temos yj = y2j , isto e, uma indicacao de
que um elemento da primeira lista ira se repetir. Como o proximo elemento de uma
lista e completamente determinado pela aplicacao da funcao f , se o elemento yj se
repete em y2j , entao a primeira lista passara a ter repeticoes dos elementos entre
yj e y2j1 para sempre. Temos entao o ciclo no percurso da primeira lista aludido
pela letra grega rho (), sendo que este ciclo possui comprimento j.
A partir da igualdade yj = zj , podemos concluir que g 1 h1 g 2 h2 (mod p),
para os valores de 1 , 1 , 2 e 2 calculados no decorrer das aplicacoes de f . Como
h g x (mod p), onde x e o valor que estamos tentando determinar, a congruencia
g 1 h1 g 2 h2 (mod p) pode ser escrita como
Esta congruencia pode ainda ser escrita como g (1 2 )+x(1 2 ) 1 (mod p).
Entao, o Lema Chave (Lema 4.2) nos permite concluir que a ordem de g, que e
Algoritmo Rho de Pollard 107
(1 2 ) (2 1 )x (mod p 1).
L = [t + m i : 0 i < d].
O que efetivamente obtemos entao e uma lista de valores que sao candidatos a
solucao x. Para encontrar efetivamente o valor de x, devemos testar cada valor da
lista para determinar qual deles satisfaz a congruencia g x h (mod p). O valor
de d usualmente e pequeno, de forma que ha poucos elementos na lista para serem
testados.
Apresentamos abaixo o Algoritmo Rho para a resolucao do PLD em grupos
U (p). A generalizacao do algoritmo para grupos finitos cclicos quaisquer nao e
complexa, levando em conta que ja discutimos acima o detalhe menos imediato
desta generalizacao, que e a adaptacao da funcao f . Desta forma, deixamos a
descricao do algoritmo generalizado como exerccio (Exerccio 1).
Instrucoes:
1. y 1, z 1
2. 1 0, 1 0, 2 0, 2 0
3. 1 (y, 1 ), 1 (y, 1 )
4. y f (y)
5. 2 (f (z), (z, 2 )), 2 (f (z), (z, 2 ))
6. z f (f (z))
7. Enquanto y 6= z, faca:
7.1. 1 (y, 1 ), 1 (y, 1 )
7.2. y f (y)
7.3. 2 (f (z), (z, 2 )), 2 (f (z), (z, 2 ))
7.4. z f (f (z))
8. u (1 2 ) mod p 1
9. v (2 1 ) mod p 1
10. Se v = 0, entao retorne Insucesso.
11. Aplique o Algoritmo Euclidiano Estendido a v e p 1, obtendo v +
(p 1) = d, onde d = mdc(v, p 1).
12. m (p 1)/d
13. t (( u)/d) mod m
14. i 0
15. Enquanto i < d, faca:
15.1. s t + m i
15.2. Se g s h (mod p), entao retorne s.
15.3. i i + 1
das duas listas, assim como os valores dos expoentes 1 , 1 , 2 e 2 , ate encontrarmos
uma coincidencia entre os valores:
i yi zi 1 1 2 2
0 1 1 0 0 0 0
1 3 9 1 0 2 0
2 9 81 2 0 4 0
3 27 5 3 0 5 1
4 81 45 4 0 7 1
5 243 235 5 0 16 2
6 5 46 5 1 32 6
7 15 26 6 1 66 12
8 45 234 7 1 68 12
9 135 234 8 1 136 26
10 235 234 16 2 16 54
11 118 234 16 3 32 110
12 46 234 32 6 64 222
13 138 234 33 6 128 190
14 26 234 66 12 0 126
15 78 234 67 12 0 254
16 234 234 68 12 0 254
Calculamos entao u = 1 2 = 68 0 = 68 e v = 2 = 1 = 254 12 = 242.
Aplicando o Algoritmo Euclidiano Estendido a v = 242 e p 1 = 256, obtemos
= 55 e d = mdc(v, p 1) = 2. Em seguida, calculamos m = (p 1)/d =
256/2 = 128 e t = ((u)/d) mod m = (55.68)/2 mod 128 = 50. Temos entao
que x t (mod m), isto e, x 50 (mod 128). Como 0 x < p 1 = 256,
existem dois possveis valores candidatos a serem a solucao x: x0 = t = 50 e
x1 = t + m = 50 + 128 = 178. Precisamos verificar qual deles satisfaz a congruencia
g x h (mod p).
Comecamos testando x0 = 50. Temos g x0 = 350 18 h (mod 257). Logo, a
solucao para o PLD e x = 50.
Assim, pelo Lema Chave (Lema 4.2), a ordem de gi divide qiei . Entretanto, se
0
t < qiei , entao t0 = ((p 1)/qiei )t < p 1. Desta forma, g t 6 1 (mod p), o que
significa que git 6 1 (mod p). Portanto, a ordem de gi e igual a qiei .
Como temos g x h (mod p), podemos elevar os dois lados a (p1)/qiei , obtendo
ei
gi hi (mod p), onde hi = (h(p1)/qi ) mod p. Esta nova congruencia nos da
x
(mod q1e1 )
x x1
x x2 (mod q2e2 )
.. .. ..
. . .
(mod qkek ).
x xk
Vamos agora elevar os dois lados da congruencia gixi hi (mod p) a qiei 1 , obtendo
ei 1 ei 1
q q
(gi i )xi hi i (mod p). Substitumos entao xi pela decomposicao acima, ob-
tendo
ei 1 ei 1 ei 1
q q
(gi i )xi0 +xi1 qi +...+xi(ei 1) qi hi i (mod p).
Esta congruencia pode ser escrita como
ei 1 ei ei 2 ei 1
q q q
(gi i )xi0 (gi i )xi1 +...+xi(ei 1) qi hi i (mod p).
ei
q
Entretanto, temos que gi i 1 (mod p), de forma que a congruencia acima pode
ser simplificada para
ei 1 ei 1
q q
(gi i )xi0 hi i (mod p).
ei 1 ei 1
q q
Se gi0 = (gi i ) mod p e hi0 = (hi i ) mod p, obtemos um novo PLD: (gi0 )xi0 hi0
e
qi i
(mod p). Temos que (gi0 )qi gi 1 (mod p). Logo, pelo Lema Chave (Lema 4.2),
a ordem de gi0 divide qi . Como qi e primo, a ordem de gi0 e 1 ou qi . Entretanto,
ei 1
q
gi0 6 1 (mod p), ja que gi i 6 1 (mod p). Assim, a ordem de gi0 e qi e temos o
0 xi0
PLD (gi ) hi0 (mod p) em um subgrupo de ordem qi . Resolvemos entao este
Algoritmo de Pohlig-Hellman 111
PLD com o Algoritmo BSGS, levando em conta que a ordem de gi0 e qi . Com isso,
obtemos o valor de xi0 .
Vamos utilizar um processo analogo para calcular o valor de xi1 . Elevamos os
dois lados do PLD gixi hi (mod p) a qiei 2 agora. Obtemos
ei 2 ei 1 ei ei 3 ei 2
q q q q
(gi i )xi0 (gi i )xi1 (gi i )xi2 +...+xi(ei 1) qi hi i (mod p).
ei
q
Novamente, como gi i 1 (mod p), a congruencia acima pode ser simplificada para
ei 2 ei 1 ei 2
q q q
(gi i )xi0 (gi i )xi1 hi i (mod p).
Apos termos calculado os valores de xij para todo 0 j < ei , calculamos direta-
mente o valor de xi pela formula
Instrucoes:
112 Resolucao do Problema do Logaritmo Discreto
(mod q1e1 )
x x1
(mod q2e2 )
x x2
.. .. ..
. . .
(mod qkek ).
x xk
5. Retorne x.
e2
Vamos agora trabalhar com a potencia 33 . Calculamos g2e= g (p1)/q2 mod p =
3 2
126432/3 mod 433 = 12616 mod 433 = 17 e h2 = h(p1)/q2 mod p = 7616 mod
433 = 3. Utilizando o Algoritmo Euclidiano Estendido, calculamos tambem g21 , o
e2 1
q
inverso de g2 modulo p, obtendo g21 = 51. Finalmente, calculamos g20 = g22 mod
2
p = 173 mod 433 = 198.
Vamos calcular o valor de x2 tal que g2x2 h2 (mod p). Sabemos que 0 x2 <
e2
p2 = 33 = 27. Escrevemos entao x2 = x20 + x21 3 + x22 32 . Comecamos fazendo
x2 = 0 e vamos incrementalmente atualizando o seu valor ao calcularmos os valores
de x20 , x21 e x22 .
O valor de x20 sera a solucao do PLD (g20 )x20 h20 (mod p), isto e, 198x20
198 (mod 433). Fica claro entao que x20 = 1. Atualizamos o valor de x2 para
x2 = x20 = 1.
O valor de x21 sera a solucao do PLD (g20 )x21 h21 (mod p), isto e, 198x21
234 (mod 433).
Utilizamos entao o Algoritmo BSGS para determinar o valor de x21, sabendo
que a ordem de g20 = 198 e p2 = 3. Comecamos calculando m = d 3e = 2 e
construmos a lista B de baby-steps.
l 0 1
198l mod 433 1 198
O valor de x22 sera a solucao do PLD (g20 )x22 h22 (mod p), isto e, 198x22
234 (mod 433). Como resolvemos este PLD no item anterior, sabemos que
x22 = 2. Calculamos o valor de x2 como x2 = x20 + x21 3 + x22 32 = 25.
Algoritmo do Calculo de Indices 115
(mod 24 )
x x1 15
x x2 25 (mod 33 ).
Como temos duas potencias da mesma base congruentes entre si, entao os seus
expoentes devem ser congruentes modulo a ordem desta base, isto e, modulo p 1.
Desta forma,
e1 x1 + e2 x2 + . . . + ek xk t (mod p 1).
Para calcular os valores de x1 , . . . , xk , podemos construir um sistema de k con-
gruencias modulo p 1 como a congruencia acima. Para isso, precisamos obter
pelo menos k valores t1 , t2 , . . . , tk tais que g ti mod p seja um numero P -suave, para
todo 1 i k. A partir destes valores, construmos o seguinte sistema linear com
congruencias no mesmo formato da congruencia acima:
e11 e12 . . . e1k x1 t1
e21 e22 . . . e2k x2 t2
.. .. = .. (mod p 1).
.. .. ..
. . . . . .
ek1 ek2 . . . ekk xk tk
116 Resolucao do Problema do Logaritmo Discreto
1 0 . . . 0 t01
0 1 . . . 0 t02
. . (mod p 1),
.. .. . .
. . . .. ..
0 0 ... 1 t0k
onde t01 , t02 , . . . , t0k e a solucao do sistema. Isto e, x1 = t01 , x2 = t02 , . . . , xk = t0k . As
demais linhas da matriz ampliada obtida ao final do processo, se existirem, serao
nulas.
Na ultima etapa do algoritmo, calculamos g 1 , o inverso de g modulo p. Em
seguida, buscamos um novo valor de t, agora sob uma nova condicao. Desejamos que
h(g 1 )t mod p seja P -suave. Ao contrario da primeira etapa, em que precisamos de
varios valores de t, nesta ultima precisamos de apenas um valor. Temos entao
x t + f1 x1 + f2 x2 + . . . + fk xk (mod p 1).
Algoritmo do Calculo de Indices 117
I b0
,
0 0
4.3. Seja h(g 1 )t mod p = q1f1 q2f2 . . . qkfk , onde fj 0, para todo 1 j
k.
4.4. x (t + f1 b01 + f2 b02 + . . . + fk b0k ) mod p 1
4.5. Retorne x.
As solucoes deste sistema sao tais que 6x1 2 (mod 271), 6x2 3 (mod 271) e
6x3 5 (mod 271).
Aplicamos entao a Eliminacao Gaussiana modulo 270 na matriz ampliada
1 3 0 235
1 2 1 18 .
6 1 0 231
Para zerar os outros elementos desta coluna, fazemos a primeira linha menos tres
vezes a segunda e a terceira linha menos 253 vezes a segunda. Obtemos a matriz
1 0 3 124
0 1 269 217 .
0 0 253 80
Para zerar os outros elementos desta coluna, fazemos a primeira linha menos tres
vezes a terceira e a segunda linha menos 269 vezes a terceira, obtendo
1 0 0 154
0 1 0 117 .
0 0 1 170
120 Resolucao do Problema do Logaritmo Discreto
6.6 Exerccios
1. Descreva formalmente as versoes generalizadas dos algoritmos ingenuo, Baby-
Step/Giant-Step, Rho e Pohlig-Hellman para o calculo do PLD em um
grupo finito cclico G = (G, ) de ordem n qualquer.
2. Resolva o Problema do Logaritmo Discreto g x h (mod p) utilizando o Al-
goritmo Baby-Step/Giant-Step nos casos abaixo:
2.1. g = 155, h = 181, p = 211
2.2. g = 33, h = 123, p = 269
3. Dados os parametros publicos g = 107 e p = 223 e a chave publica c = 86 de
uma implementacao do metodo de criptografia El Gamal, utilize o Algoritmo
Baby-Step/Giant-Step para obter a chave privada e decriptar a mensagem
m
b = (104, 202).
4. Resolva o Problema do Logaritmo Discreto g x h (mod p) utilizando o Al-
goritmo Rho nos casos abaixo:
4.1. g = 6, h = 2, p = 157
4.2. g = 78, h = 122, p = 193
5. Dados os parametros publicos g = 66 e p = 113 e a chave publica c = 29 de
uma implementacao do metodo de criptografia El Gamal, utilize o Algoritmo
Rho para obter a chave privada e decriptar a mensagem m b = (62, 45).
[6] EUCLIDES. The Thirteen Books of the Elements, Volume 2: Books IIIIX :
Traduzido por T. L. Heath. Second edition. New York: Dover Publications, 1956.
[8] GOLUB, G. H.; VAN LOAN, C. F. Matrix Computations. Fourth edition. Bal-
timore: Johns Hopkins University Press, 2012.
[9] HODGES, A. Alan Turing: The Enigma. Centennial edition. Princeton: Prince-
ton University Press, 2012.
[11] KAHN, D. The Codebrakers. Revised and updated edition. New York: Scribner,
1996.
121
122 Resolucao do Problema do Logaritmo Discreto
[17] MILLER, G. L. Riemanns hypothesis and tests for primality. Journal of Com-
puter and System Sciences, v. 13, n. 3, p. 300317, 1976.
[18] NATIONAL INSTITUTE OF STANDARDS AND TECHNO-
LOGY. Digital Signature Standard. 1993. FIPS 186. Disponvel em:
<http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf>.
[19] NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY. Recom-
mendation for Key Management. 2012. Special Publication 800-57 Part 1 Revi-
sion 3. Disponvel em: <http://csrc.nist.gov/publications/nistpubs/800-57/sp800-
57 part1 rev3 general.pdf>.
[22] POLLARD, J. M. Monte Carlo methods for index computation (mod p). Mathe-
matics of Computation, v. 32, n. 143, p. 918924, 1978.
[23] RABIN, M. O. Probabilistic algorithm for testing primality. Journal of Number
Theory, v. 12, n. 1, p. 128138, 1980.
[26] SHANKS, D. Class number, a theory of factorization, and genera. In: LEWIS,
D. J. (Ed.). Anais do Symposia in Pure Mathematics. Providence: American
Mathematical Society, 1971. v. 20, p. 415440.
[27] UNICODE CONSORTIUM. Unicode 6.3 Character Code Charts. 2013. Dis-
ponvel em: <http://www.unicode.org/charts/>.
[28] YONG, L. L.; SE, A. T. Fleeting Footsteps: Tracing the Conception of Arithme-
tic and Algebra in Ancient China: Traducao de Sunzi Suanjing. Revised edition.
Singapore: World Scientific Publishing, 2004.
Indice
Abel, 62 Publica, 6
Adleman, 7, 45, 115 Privada, 2
Algoritmo Cifra de Cesar, 3
Baby-Step/Giant-Step, 104 Classe de Equivalencia, 25
Chines do Resto, 37 Congruencia Modulo n, 27
de Assinatura Conjunto Quociente, 26
DSA, 96 Criptografia
El Gamal, 89 com Curvas Elpticas, 82, 118
de Decriptacao El Gamal, 86 de Chave Publica, 6, 78
de Divisao Inteira, 14 de Chave Privada, 2
de Encriptacao El Gamal, 85 El Gamal, 82
de Fatoracao, 45 Decriptacao, 86
de Gauss, 75 Encriptacao, 85
de Geracao de Chaves Geracao de Chaves, 83
da Assinatura DSA, 95 Crivo de Eratostenes, 50
da Assinatura El Gamal, 88
da Criptografia El Gamal, 83 Decriptacao, 2
de Pohlig-Hellman, 111 El Gamal, 86
de Potenciacao Modular, 32 Diffie, 6
de Verificacao da Assinatura Dividendo, 13
DSA, 97 Divisao Inteira, 13
El Gamal, 91 Divisor, 13, 17
do Calculo de Indices, 117 Proprio, 17
do Crivo de Eratostenes, 50 Primo, 42
do Teste de Miller-Rabin, 59 DSA, 94
Euclidiano Estendido, 21 Assinatura, 96
Ingenuo para o PLD, 102 Geracao de Chaves, 95
Rho, 107 Verificacao, 97
Assinatura Digital, 6, 79
DSA, 94 El Gamal, 7, 82
Assinatura, 96 Metodo de Assinatura Digital, 88
Geracao de Chaves, 95 Assinatura, 89
Verificacao, 97 Geracao de Chaves, 88
El Gamal, 88 Verificacao, 91
Assinatura, 89 Metodo de Criptografia, 82
Geracao de Chaves, 88 Decriptacao, 86
Verificacao, 91 Encriptacao, 85
Geracao de Chaves, 83
Cesar, 3 Encriptacao, 2
Carmichael, 53 El Gamal, 85
Chave, 2 Probabilstica, 85
Efemera, 85 Enigma, 4
123
124 Resolucao do Problema do Logaritmo Discreto
Eratostenes, 46 de um Grupo, 63
Euclides, 18, 43, 62
Euler, 51, 61 Pohlig, 109
Pollard, 105
Fator, 17 Potenciacao Modular, 31
Proprio, 17 Primorial, 43
Primo, 42 Problema do Logaritmo Discreto, 70, 101
Fatoracao em Primos, 44 Produto Modular, 30
Fermat, 51, 62 Propriedade
(n), 64 Fundamental dos Primos, 43
Forma Reduzida Modulo n, 29 Pseudoprimo, 53
Funcao de Fermat, 53
de Euler, 64 Forte, 57
Hash, 89
Criptograficamente Segura, 89 Quociente, 13
Galois, 61 Rabin, 56
Gauss, 61, 74 Raiz Primitiva, 70
Geracao de Chaves Relacao de Equivalencia, 24
da Assinatura DSA, 95 Resto, 13
da Assinatura El Gamal, 88 Rivest, 7, 45
da Criptografia El Gamal, 83 RSA, 45
Gerador, 70
Shamir, 7, 45
Grupo, 62
Shanks, 103
Abeliano, 62
Soma Modular, 29
Cclico, 70
Subgrupo, 66
Comutativo, 62
Cclico, 70
Finito, 63
Proprio, 67
U (n), 64
Subtracao Modular, 30
Hellman, 6, 109 Sunzi (Sun Tzu), 35
Teorema
Inteiros Modulo n, 29
da Inversao Modular, 34
Inverso Multiplicativo Modular, 33
Chines do Resto, 35
Lagrange, 61, 67 da Infinidade dos Primos, 43
Leibniz, 51 da Raiz Primitiva, 74
Lema Chave, 72 da Unicidade da Fatoracao, 44
de Fermat, 51
Maximo Divisor Comum, 17 de Lagrange, 67
Multiplo, 17 Fundamental da Aritmetica, 44
Miller, 56 Teste
de Fermat, 52
Numero de Miller-Rabin, 59
Composto, 41 Turing, 5
de Carmichael, 53
P -Suave, 115 U (n), 64
Primo, 41 Unicidade
Nicomaco, 46 da Fatoracao, 44
do Quociente e Resto, 14
Ordem
de um Elemento, 69