I n t r o d u ç ã o à C r i p t o g r a f i a
2 2 V o l u m e
L u i z M a n o e l F i g u e i r e d o
.
Luiz Manoel Figueiredo
Introdução à Criptografi a
Volume 2 – Módulo 2
UFF – Instituto de Matemática
Celso José da Costa
EB – Centro de Estudos de Pessoal
Antônio Carlos Guelfi
O material constante desta disciplina foi produzido sob o auspício de
Convênio de cooperação técnico-acadêmica entre o Exército Brasileiro e a
Universidade Federal Fluminense.
Apoio:
Material Didático
2010/1
Publicado por: Centro de Estudos de Pessoal (CEP)
Copyright © 2006 Centro de Estudos de Pessoal
Todos os direitos reservados ao Centro de Estudos de Pessoal (CEP)
Praça Almte. Júlio de Noronha S/N – Leme – Tel.: (21) 2275-0100
22010-020 Rio de Janeiro – Brasil
ELABORAÇÃO DE CONTEÚDO
Luiz Manoel Figueiredo
CAPA
Eduardo Bordoni
PRODUÇÃO GRÁFICA
Oséias Ferraz Patricia Seabra
972m
Figueiredo, Luiz Manoel.
Introdução à Criptografi a. v. 2 / Luiz Manoel Figueiredo.
– Rio de Janeiro: UFF / CEP – EB, 2010.
172p.; 21 x 29,7 cm.
ISBN: 85-7648-331-9
1. Algoritmo de Euclides. 2. Teorema de Fermat.
3. Teorema de Euler. 4. Teorema chinês. I. Título.
CDD: 510
Fundação Cecierj / Consórcio Cederj
Rua Visconde de Niterói, 1364 – Mangueira – Rio de Janeiro, RJ – CEP 20943-001
Tel.: (21) 2334-1569 Fax: (21) 2568-0725
Presidente
Masako Oya Masuda
Vice-presidente
Mirian Crapez
Coordenação do Curso de Matemática
UFF – Regina Moreth
UNIRIO – Luiz Pedro San Gil Jutuca
Universidades Consorciadas
Governo do Estado do Rio de Janeiro
Secretário de Estado de Ciência e Tecnologia
Governador
Alexandre Cardoso
Sérgio Cabral Filho
UENF – UNIVERSIDADE ESTADUAL DO
NORTE FLUMINENSE DARCY RIBEIRO
Reitor: Almy Junior Cordeiro de Carvalho
UERJ – UNIVERSIDADE DO ESTADO DO
RIO DE JANEIRO
Reitor: Ricardo Vieiralves
UNIRIO – UNIVERSIDADE FEDERAL DO ESTADO
DO RIO DE JANEIRO
Reitora: Malvina Tania Tuttman
UFRRJ – UNIVERSIDADE FEDERAL RURAL
DO RIO DE JANEIRO
Reitor: Ricardo Motta Miranda
UFRJ – UNIVERSIDADE FEDERAL DO
RIO DE JANEIRO
Reitor: Aloísio Teixeira
UFF – UNIVERSIDADE FEDERAL FLUMINENSE
Reitor: Roberto de Souza Salles
.
SUMÁRIO
PROGRAMA DA DISCIPLINA ………………………………………………………………………………………………………………………….1
PLANO DE AULAS DA UNIDADE 1 …………………………………………………………………………………………………………………2
PLANO DE AULAS DA UNIDADE 2 …………………………………………………………………………………………………………………3
UNIDADE 1 ……………………………………………………………………………………………………………………………………………………5
AULA 1 NÚMEROS PRIMOS ………………………………………………………………………………………………………………………….6
Texto 1 Teoria dos números ……………………………………………………………………………………………………………………………6
Texto 2 Divisores …………………………………………………………………………………………………………………………………………..8
Texto 3 Números perfeitos ……………………………………………………………………………………………………………………………..11
Texto 4 Números primos ………………………………………………………………………………………………………………………………..13
Texto 5 A infinitude dos números primos ………………………………………………………………………………………………………..15
Atividades ……………………………………………………………………………………………………………………………………………………17
AULA 2 ALGORITMO DA DIVISÃO ………………………………………………………………………………………………………………18
Texto 6 Axioma de Eudoxius …………………………………………………………………………………………………………………………18
Texto 7 O algoritmo da divisão ………………………………………………………………………………………………………………………18
Texto 8 O máximo divisor comum (mdc) …………………………………………………………………………………………………………20
Texto 9 O mínimo múltiplo comum (mmc) ………………………………………………………………………………………………………..25
Texto 10 O mdc e mmc de vários inteiros ……………………………………………………………………………………………………….25
Texto 11 Como calcular o máximo divisor comum ……………………………………………………………………………………………26
Atividades ……………………………………………………………………………………………………………………………………………………27
AULA 3 ALGORITMO DE EUCLIDES ……………………………………………………………………………………………………………28
Texto 12 Dois resultados preliminares ……………………………………………………………………………………………………………28
Texto 13 O algoritmo de Euclides …………………………………………………………………………………………………………………..29
Texto 14 Cálculo do mdc e do mmc através da fatoração …………………………………………………………………………………31
Texto 15 Relação entre mdc(a,b) e mmc(a,b) ………………………………………………………………………………………………….33
Texto 16 Convergência do algoritmo de Euclides ……………………………………………………………………………………………..34
Atividade ………………………………………………………………………………………………………………………………………………………37
AULA 4 TESTES DE PRIMALIDADE …………………………………………………………………………………………………………….38
Texto 17 Primeiro teste de primalidade …………………………………………………………………………………………………………..38
Texto 18 Teorema dos números primos ………………………………………………………………………………………………………….42
Atividades ……………………………………………………………………………………………………………………………………………………44
AULA 5 ARITMÉTICA MODULAR …………………………………………………………………………………………………………………45
Texto 19 Relações ……………………………………………………………………………………………………………………………………….46
Texto 20 Congruência módulo n …………………………………………………………………………………………………………………….48
Texto 21 Classes de equivalência …………………………………………………………………………………………………………………..50
Texto 22 Classes de congruência ………………………………………………………………………………………………………………….51
Atividades ……………………………………………………………………………………………………………………………………………………54
AULA 6 OPERAÇÕES COM CLASSES DE CONGRUÊNCIA …………………………………………………………………………..55
Texto 23 Definição de soma e de produto de classes ……………………………………………………………………………………….55
Texto 24 Tabelas de soma e de multiplicação …………………………………………………………………………………………………58
Texto 25 Divisibilidade ………………………………………………………………………………………………………………………………….59
Texto 26 Potências ………………………………………………………………………………………………………………………………………62
Atividades ……………………………………………………………………………………………………………………………………………………65
AULA 7 DIVISÃO MODULAR ……………………………………………………………………………………………………………………….66
Texto 27 A inversa de uma classe de congruência módulo n …………………………………………………………………………….66
Texto 28 Quando uma classe em n
n
tem inversa? ……………………………………………………………………………………….67
Texto 29 A congruência linear ax≡bmodn ………………………………………………………………………………………….69
Texto 30 Como escrever o mdc de dois inteiros em combinação linear ………………………………………………………………71
Atividades …………………………………………………………………………………………………………………………………………………….75
AULA 8 TEOREMA DE FERMAT ………………………………………………………………………………………………………………….76
Texto 31 Fermat …………………………………………………………………………………………………………………………………………..76
Texto 32 O teorema de Fermat ………………………………………………………………………………………………………………………77
Texto 33 Aplicação do teorema de Fermat à solução de potências …………………………………………………………………….81
Texto 34 Equações diofantinas ………………………………………………………………………………………………………………………82
Texto 35 Uso das congruências para resolver equações diofantinas …………………………………………………………………..83
Atividades ……………………………………………………………………………………………………………………………………………………85
UNIDADE 2 ………………………………………………………………………………………………………………………………………………….87
AULA 9 TESTE DE PRIMALIDADE DE FERMAT ……………………………………………………………………………………………88
Texto 36 Testes de primalidade ………………………………………………………………………………………………………………………88
Texto 37 Teste de Fermat ……………………………………………………………………………………………………………………………..89
Texto 38 Números de Carmichael ………………………………………………………………………………………………………………….91
Texto 39 Teste de Miller-Rabin ………………………………………………………………………………………………………………………93
Atividades …………………………………………………………………………………………………………………………………………………….96
AULA 10 TEOREMA DE EULER ……………………………………………………………………………………………………………………97
Texto 40 Euler ……………………………………………………………………………………………………………………………………………..97
Texto 41 A função de Euler ……………………………………………………………………………………………………………………..97
Texto 42 Teorema de Euler …………………………………………………………………………………………………………………………102
Atividades ………………………………………………………………………………………………………………………………………………….106
AULA 11 TEOREMA CHINÊS DOS RESTOS ……………………………………………………………………………………………….107
Texto 43 Exemplo com duas equações ………………………………………………………………………………………………………….107
Texto 44 Exemplo com três equações ……………………………………………………………………………………………………………108
Texto 45 Teorema chinês dos restos ……………………………………………………………………………………………………………110
Texto 46 Aplicações à criptografia: partilha de um segredo ………………………………………………………………………………114
Texto 47 Partilha de um segredo com o teorema chinês dos restos …………………………………………………………………115
Atividades …………………………………………………………………………………………………………………………………………………..118
AULA 12 RSA ……………………………………………………………………………………………………………………………………………119
Texto 48 A criptografia de chave pública ………………………………………………………………………………………………………..119
Texto 49 RSA ……………………………………………………………………………………………………………………………………………..121
Texto 50 O GP/Pari ……………………………………………………………………………………………………………………………………..123
Texto 51 Considerações práticas: escolha dos primos e preenchimento de bits …………………………………………………125
Texto 52 Assinatura digital ……………………………………………………………………………………………………………………………127
Texto 53 A segurança do RSA ……………………………………………………………………………………………………………………..128
Texto 54 Os desafios RSA …………………………………………………………………………………………………………………………..129
Atividade …………………………………………………………………………………………………………………………………………………….130
AULA 13 LOGARITMO DISCRETO ………………………………………………………………………………………………………………131
Texto 55 Raízes primitivas módulo n …………………………………………………………………………………………………………….131
Texto 56 Grupos e subgrupos ……………………………………………………………………………………………………………………..133
Texto 57 Logaritmos discretos ………………………………………………………………………………………………………………………135
Atividades ………………………………………………………………………………………………………………………………………………….139
AULA 14 APLICAÇÕES À CRIPTOGRAFIA ………………………………………………………………………………………………….140
Texto 58 Teste de Lucas ……………………………………………………………………………………………………………………………..140
Texto 59 Esquema de troca de chaves de Diffie-Hellman ………………………………………………………………………………..143
Texto 60 ElGamal ……………………………………………………………………………………………………………………………………….145
Texto 61 Algoritmo de assinatura digital …………………………………………………………………………………………………………147
Atividades ………………………………………………………………………………………………………………………………………………….150
AULA 15 CRIPTOGRAFIA COM O USO DE CURVAS ELÍPTICAS …………………………………………………………………151
Texto 62 Curvas elípticas …………………………………………………………………………………………………………………………….151
Texto 63 Corpos finitos ……………………………………………………………………………………………………………………………….152
Texto 64 Grupo de uma curva elíptica ……………………………………………………………………………………………………………154
Texto 65 Criptografia de curvas elípticas ……………………………………………………………………………………………………….157
Atividades …………………………………………………………………………………………………………………………………………………..161
COMPLEMENTE SEU ESTUDO …………………………………………………………………………………………………………………..162
SOLUÇÕES DAS ATIVIDADES …………………………………………………………………………………………………………………….163
REFERÊNCIAS …………………………………………………………………………………………………………………………………………..170
AUTOR ………………………………………………………………………………………………………………………………………………………171
Programa da disciplina
Ementa
Aritmética dos inteiros: números primos, algoritmo da divisão, mdc e mmc,
algoritmo de Euclides. Aritmética modular: congruência módulo, soma e produto de
classes, inversa de uma classe módulo n. Teoremas de Fermat, Euler e o teorema
chinês dos restos. Testes de primalidade: teste das divisões sucessivas, teste de
Fermat, teste de Rabin-Miller, números de Charmichael.
Criptografia de chave pública: princípios, o algoritmo RSA, assinatura digital.
O problema do logaritmo discreto, teste de Lucas, esquema de troca de chaves de
Diffie-Hellman, ElGamal e o algoritmo de assinatura digital. Criptografia com o uso
de curvas Elípticas: curvas elípticas, grupo de uma curva elíptica e aplicações.
Carga horária
60 horas
Objetivo
Apresentar a área da Matemática chamada Teoria dos Números, abordando
os resultados utilizados em criptografia.
Metodologia
O conteúdo programático será apresentado na forma de textos e exemplos,
com atividades a serem realizadas. Para complementar seu estudo, serão sugeridos
livros e websites.
Avaliação
Prova escrita ao final da disciplina e avaliação a distância (atividades online). 1
Plano de Aulas
Unidade 1 – Teoria dos Números
Conteúdo Onde encontrar
Aula 1 – Números Primos
Teoria dos Números
Divisores
Números perfeitos
Textos 1 a 5
Aula 2 – Algoritmo da Divisão
Axioma de Eudoxius
Algoritmo da divisão
Máximo divisor comum e mínimo múltiplo comum
Textos 6 a 11
Aula 3 – Algoritmo de Euclides
Cálculo do mdc e do mmc através da fatoração
Convergência do Algoritmo de Euclides
Textos 12 a 16
Aula 4 – Testes de Primalidade
Primeiro teste de primalidade
Teorema dos números primos
Textos 17 e 18
Aula 5 – Aritmética Modular
Relações
Congruência módulo n
Classes de equivalência
Classes de congruência
Textos 19 a 22
Aula 6 – Operações com classes de congruência
Definição de soma e de produto de classes
Tabelas de soma e de multiplicação
Divisibilidade e potências
Textos 23 a 26
Aula 7 – Divisão modular
Inversa de uma classe de congruência módulo n
MDC de dois inteiros como combinação linear
Textos 27 a 302
Conteúdo Onde encontrar
Aula 8 – Teorema de Fermat
Aplicação do teorema de Fermat
Equações diofantinas
Textos 31 a 35
Carga horária: 25 h
Unidade 2 – Criptografia de Chave Pública
Conteúdo Onde encontrar
Aula 9 – Teste de Primalidade de Fermat
Testes de primalidade
Teste de Fermat
Números de Carmichael
Teste de Miller-Rabin
Textos 36 a 39
Aula 10 – Teorema de Euler
Função
de Euler
Textos 40 a 42
Aula 11 – Teorema Chinês dos Restos
Exemplo com duas e três equações
Aplicações à criptografia
Partilha de um segredo com o teorema
Textos 43 a 47
Aula 12 – RSA
Criptografia de chave pública
GP/Pari
Assinatura digital
Segurança do RSA
Textos 48 a 54
Aula 13 – Logaritmo Discreto
Raízes primitivas módulo n
Grupos e subgrupos
Logaritmos discretos
Textos 55 a 57
Aula 14 – Aplicações à Criptografia
Teste de Lucas
Esquema de troca de chaves de Diffie-Hellman
ElGamal
Algoritmo de assinatura digital
Textos 58 a 613
Conteúdo Onde encontrar
Aula 15 – Criptografia com o uso de Curvas
Elípticas
Corpos finitos
Grupo de uma curva elíptica
Criptografia de curvas elípticas
Textos 62 a 65
Carga horária: 35 h4
Unidade
Teoria dos Números
Caro aluno, seja bem-vindo à disciplina Números
primos e criptografia de chave pública.
Nesta primeira unidade, você vai estudar os
conceitos e resultados matemáticos que são
a base das aplicações em criptografia de
chave pública.
Bom estudo!
15
Aula 1 – Números Primos
Nesta primeira aula, você vai conhecer os números primos, que são a base para o
estudo dos inteiros.
A grande importância dos números primos está em que todo inteiro pode ser escrito
de maneira essencialmente única como produto de primos, como veremos a seguir.
Texto 1 – Teoria dos Números
A Teoria dos Números é a área da Matemática que estuda as propriedades dos números inteiros
e os problemas que aparecem naturalmente neste estudo….