Criptografia números primos e algoritmos

Criptografia números primos e algoritmos

(Parte 1 de 4)

Criptografia, Números Primos e Algoritmos

Publicações Matemáticas

Criptografia, Números Primos e

Algoritmos 4a edição

Manoel Lemos Universidade Federal de Pernambuco impa

Copyright 2010 by Manoel Lemos Impresso no Brasil / Printed in Brazil Capa: Noni Geiger / Sérgio R. Vaz

Publicações Matemáticas

• Introdução à Análise Funcional – César R. de Oliveira • Introdução à Topologia Diferencial – Elon Lages Lima

• Criptografia, Números Primos e Algoritmos – Manoel Lemos

• Introdução à Economia Dinâmica e Mercados Incompletos – Aloísio Araújo

• Conjuntos de Cantor, Dinâmica e Aritmética – Carlos Gustavo Moreira

• Geometria Hiperbólica – João Lucas Marques Barbosa

• Introdução à Economia Matemática – Aloísio Araújo

• Superfícies Mínimas – Manfredo Perdigão do Carmo

• The Index Formula for Dirac Operators: an Introduction – Levi Lopes de Lima

• Introduction to Symplectic and Hamiltonian Geometry – Ana Cannas da Silva

• Primos de Mersenne (e outros primos muito grandes) – Carlos Gustavo T. A. Moreira e Nicolau Saldanha

• The Contact Process on Graphs – Márcia Salzano

• Canonical Metrics on Compact almost Complex Manifolds – Santiago R. Simanca

• Introduction to Toric Varieties – Jean-Paul Brasselet

• Birational Geometry of Foliations – Marco Brunella

• Introdução à Teoria das Probabilidades – Pedro J. Fernandez

• Teoria dos Corpos – Otto Endler

• Introdução à Dinâmica de Aplicações do Tipo Twist – Clodoaldo G. Ragazzo, Mário J. Dias Carneiro e Salvador Addas Zanata

• Elementos de Estatística Computacional usando Plataformas de Software Livre/Gratuito – Alejandro C. Frery e Francisco Cribari-Neto

• Uma Introdução a Soluções de Viscosidade para Equações de Hamilton-Jacobi – Helena J. Nussenzveig Lopes, Milton C. Lopes Filho

• Elements of Analytic Hypoellipticity – Nicholas Hanges

• Métodos Clássicos em Teoria do Potencial – Augusto Ponce

• Variedades Diferenciáveis – Elon Lages Lima

• O Método do Referencial Móvel – Manfredo do Carmo

• A Student's Guide to Symplectic Spaces, Grassmannians and Maslov Index – Paolo Piccione e Daniel Victor Tausk

• Métodos Topológicos en el Análisis no Lineal – Pablo Amster

• Tópicos em Combinatória Contemporânea – Carlos Gustavo Moreira e Yoshiharu Kohayakawa

• Uma Iniciação aos Sistemas Dinâmicos Estocásticos – Paulo Ruffino

• Compressive Sensing – Adriana Schulz, Eduardo A.B.. da Silva e Luiz Velho

• O Teorema de Poncelet – Marcos Sebastiani

• Cálculo Tensorial – Elon Lages Lima

a Adilson e Astrea

Prefacio

No ano de 1989, ha precisamente duas decadas, lecionei um curso no 17o Coloquio Brasileiro de Matematica entitulado de Criptografia, numeros primos e algoritmos. As notas de aulas escritas para este curso estao esgotadas. Diante da solicitacao feita pelo IMPA para a sua reimpressao, achei interessante as reescrever completamente. Quatro motivos principais me levaram a tormar esta decisao: alguns erros tipograficos presentes nas notas originais; os avancos que ocorreram nestas duas ultimas decadas em teoria dos numeros computacional; a abordagem realizada de forma sucinta na maioria dos topicos; e a presenca de poucos exercıcios.

Nos quatro primeiros meses de 1989, as notas de aulas para o curso que lecionei no coloquio em julho do mesmo ano foram escritas. Redigi estas notas em um caderno. Como, naquela epoca, nao utilizava o TEX, nao digitei as notas. Quem o fez foi Oscar. Aos erros tipogaficos que cometi ao redigir, Oscar talvez tenha acrescentado mais alguns. Na revisao, nao fui capaz de encontrar todos. Para os mais jovens, pode parecer estranho nao ter digitado em TEX. Mas a decada de 80 foi de transicao. Quando fazia o Ensino Fundamental fiz um curso de datilografia. Ganhei dos meus pais uma maquina de escrever Olivetti. Para que a margem esquerda fosse alinhada, necessitava, ao chegar na ultima palavra, fazer a conta de quantas letras podiam ser digitadas antes do fim da linha para fazer o ajuste. Era um processo muito trabalhoso. A pior parte era jogar fora toda uma pagina quando um erro era cometido. Sımbolos matematicos nem pensar! So os disponıveis no teclado. Esta maquina me acompanhou tambem no Ensino Medio.

Ao ingressar na universidade, nao necessitava digitar textos, pois nao e comum que trabalhos sejam solicitados nas disciplinas de ciencias matematicas. Nao lembro de nenhum. Apenas no mestrado tive de escrever minha dissertacao. Digitei a versao preliminar em uma maquina eletrica que podia corrigir os erros. Quando necessario, tive de deixar espaco para escrever a mao as letras gregas e os sımbolos matematicos. A versao final, digitada por Delsa ou Neide, nao lembro bem, foi feita em maquina similar. Nestas maquinas, as letras vinham em relevo em uma esfera. Existiam esferas com sımbolos matematicos e letras gregas. Quando era necessario digitar um caracter deste tipo, bastava trocar a esfera. Era muito trabalhoso, mas era um enorme progresso. Na versao final de minha dissertacao nada foi escrito a mao. Fui para o doutorado. Ao chegar em Oxford deparei com maquinas de escrever, na sala de cafe dos estudantes, que possuıam dois teclados: um normal e outro com letras gregas e sımbolos matematicos. Para mudar de teclado, bastava transferir o tambor. Achei que teria dificuldade em redigir meus resultados em uma maquina tao estranha. Logo descobri que o Instituto de Matematica tinha disponibilizado 1 computador pessoal para todos os estudantes de pos-graduacao digitarem seus resultados e que estas maquinas tinham sido descartadas. Estavamos no final de 1984. Destaquei o numero 1 porque computadores pessoais eram raros nesta epoca.

Um novo mundo se abriu para mim. Descobri que podia digitar todos os sımbolos matematicos. Bastava escolher em algumas tabelas. A margem esquerda era feita automaticamente. As formulas podiam ser centralizadas sem dificuldade. Utilizava o processador de textos conhecido como T3. Ou era T3? Nao lembro bem. Ao chegar de volta no Brasil, passei a utilizar o CHIWRITE. Ambos, quando comparados com o TEX, sao bastante rudimentares. Em 1989, ainda nao utilizava o TEX. Hoje utilizo uma de suas variantes que e conhecida como LATEX. Estas notas foram digitadas por mim. Qualquer erro tipografico sera de minha inteira responsabilidade. Nao terei como terceirizar parte deles.

A maior parte destas notas foi redigida quando lecionava a disciplina Criptografia e Algoritmos aqui na UFPE. Os textos utilizados para ilustrar as aplicacoes dos diversos sistemas de criptografia abordados tratam de futebol. Quando escritos, o Santa Cruz ainda jogava

vii na segunda divisao. Neste ano, terminou como lanterna de um dos grupos da quarta. Deixo, como exercıcio para o leitor, adivinhar em que ano lecionei a disciplina.

Nestas duas ultimas decadas, a pesquisa nesta area foi intensa.

Destaco dois grandes avancos. O primeiro foi um algoritmo polinomial para fatorar inteiros em um computador quantico. O segundo, a descoberta de um algoritmo polinomial para decidir quando um inteiro e primo. Este algoritmo ficou conhecido como AKS. Portanto, toda a discussao sobre o algoritmo de Lenstra, que foi escrita para o curso do Coloquio, se tornou obsoleta. Abordamos os algoritmos para decidir primalidade no quarto capıtulo destas notas. Continuamos apresentando o algoritmo randomizado de Rabin que, apesar de ter mais de 30 anos, ainda e utilizado para encontrar numeros primos grandes. Discutimos o AKS, mas devido ao espırito destas notas, nao o demonstramos. No primeiro e no segundo capıtulos abordamos respecitivamente as propriedades dos inteiros e congruencias. No quinto e ultimo capıtulo fazemos uma pequena discussao sobre livros relacionados.

Por fim faco um pequeno comentario sobre a ultima reforma em nossa ortografia. A desconsideramos completamente, ja que a antiga ainda vale ate 2011, isto e, bem depois da proxima Copa. Portanto, palavras como consequentemente e sequencia ainda tem o trema nestas notas. Ficaria estranho adotar a nova ortografia sem o novo alfabeto ser utilizado para escrever mensagens. Todos os exemplos foram feitos em um alfabeto sem as letras K, Y e W.

Gostaria de agradecer ao meu colega de departamento, Professor Antonio Carlos Rodrigues Monteiro, por ter lido atentamente estas notas e feito inumeras sugestoes. Por insitencia dele, o zero virou um numero natural. Na minha abordagem inicial tinha adotado uma possicao ambıgua, o que pode parecer estranho em matematica. Como alguns autores consideram o zero como natural e outros nao, tinha decidido considerar o zero como um natural dependendo da situacao. O que, de fato, e estranho. Portanto, descartei esta abordagem informal para esta questao. Gostaria de deixar claro que o Professor Antonio nao tem nenhuma resposabilidade sobre qualquer erro que por ventura exista nestas notas. Todos, que imagino formem o conjunto vazio, sao de minha inteira responsabilidade. Sobre esta questao, vale a pena aguardar o prefacio da terceira edicao destas

viii notas, caso sejam escritas algum dia.

Em 1989, dediquei as notas de aulas escritas especialmente para o

Coloquio ao Professor Adilson Goncalves e a Professora Astrea Barreto. Ambos foram meus professores na UFPE e, quando estava no doutorado, solicitaram transferencia para a UFRJ. A contribuicao que deram para a consolidacao da matematica brasileira, atraves de sua atuacao profissional consistente ao longos das ultimas 4 decadas, foi significativa. Passados 20 anos do Coloquio, entendo que a dedicatoria continua muito atual. E pena que nao existam tantos professores nas universidades brasileiras com uma atuacao tao destacada e positiva quanto a dos dois.

Manoel Lemos Recife, 20 de setembro de 2009

Conteudo

1.1 Introducao1
1.2 Propriedades2
1.2.1 Propriedades aritmeticas2
1.2.2 Propriedades de ordem4
1.2.3 Princıpio da inducao finita6
1.2.4 Exercıcios1
1.3 Numeros primos13
1.3.1 Exercıcios15
1.4 Algoritmo da divisao de Euclides16
1.4.1 Exercıcios21
1.5 Representacao de numeros inteiros21
1.5.1 Exercıcios23
1.6 Custo de realizar operacoes aritmeticas23
1.6.1 Exercıcios26
1.7 Fatoracao unica27
1.7.1 Exercıcios28
1.8 Algumas aplicacoes da fatoracao unica29
1.8.1 Exercıcios32

1 Inteiros 1

2.1 Introducao3
2.2 Definicao34
2.2.1 Exercıcios36
2.3 Inversos multiplicativos em Zn37
2.3.1 Exercıcios40

2 Congruencias 3 ix

2.4 O Pequeno Teorema de Fermat41
2.4.1 Exercıcios45
2.5 A exponenciacao e rapida46
2.5.1 Exercıcios47
2.6 O Teorema de Wilson48
2.7 Teorema Chines dos Restos50
2.7.1 Exercıcios53
2.8 Existencia de geradores54
2.8.1 Exercıcios56

x CONTEUDO

3.1 Introducao57
3.1.1 Exercıcios62
3.2 Trabalhando com blocos63
3.2.1 Considerando o bloco como um elemento63
3.2.2 Considerando o bloco como um vetor64
3.2.3 Exercıcios68
3.3 Criptografia com chave publica70
3.4 RSA72
3.4.1 Exercıcios7
3.5 Seguranca do RSA78
3.5.1 E possıvel descobir φ(n) a partir de n79

3 Criptografia 57 3.5.2 Pode-se descobir d sem o conhecimento de φ(n) 80

3.5.3 Extraindo raizes e-esimas em Z∗n86
3.5.4 Exercıcios86
3.6 Assinatura no RSA87
3.6.1 Exercıcios8
3.7 Chaves publicas × Metodos classicos8
4.1 Introducao90
4.1.1 Exercıcios93
4.2 Primalidade de grandes numeros94
4.2.1 Exercıcios97
4.3 Modificando um pouco o algoritmo97
4.3.1 Exercıcios103
4.4 AKS105
4.4.2 Verificando (i)106
4.4.3 Multiplicando polinomios106
4.4.4 Verificando (i)109
4.4.5 Encontrando r110
4.4.6 Exercıcios110

CONTEUDO xi

5.1 Introducao112
5.2 Sobre criptografia com chave publica112
5.3 Sobre curvas elıpticas113
5.4 Sobre numeros primos113

5 Referencias bibliograficas comentadas 112 5.5 Sobre algoritmos em teoria dos numeros . . . . . . . . 114

Capıtulo 1 Inteiros

Neste capıtulo, estamos interessados em estudar os seguintes conjuntos de numeros:

N = {0,1,2,3,} e
Z = {...,−3,−2,−1,0,1,2,3,}.

Um numero pertencente ao primeiro conjunto e chamado natural e ao segundo inteiro.

Durante estas notas iremos assumir, como axiomas, algumas propriedades desses conjuntos. Nao faremos a construcao dos inteiros a partir dos naturais, como e comumente feito em um curso de estruturas algebricas ou logica. Nem iremos supor apenas um pequeno numero de axiomas para os naturais, como os de Peano — a partir destes e possıvel definir as operacoes de adicao e multiplicacao e derivar todas as suas propriedades. Deixamos tal abordagem para um curso de logica, que se inicia com os axiomas para a teoria dos conjuntos e, a partir destes, definem-se os naturais. Neste caso, o 0 (zero) e um numero natural, o que sera adotado nestas notas. Como este enfoque para os numeros naturais e inteiros e bastante demorado, nao o consideramos neste curso.

Do paragrafo anterior, destacamos uma passagem: Existem axiomas para a teoria dos conjuntos. Iremos ignorar totalmente este fato. Usaremos livremente as propriedades de conjuntos que nos parecerem naturais. A seguir apresentaremos um paradoxo, proposto por Russell, para ilustrar este ponto. Antes comecaremos com um ditado popular: toda regra possui uma excecao. Como esta sentenca e uma regra, tem de possuir uma excecao, isto e, existe regra sem excecao. Chegamos a uma contradicao! Este mesmo fato se manifesta em teoria dos conjuntos. Agora apresentaremos o paradoxo de Russell. Seja S a colecao de todos os conjuntos A tais que A 6∈ A. Portanto, caso S seja um conjunto, S ∈ S se e somente se S 6∈ S, o que e absurdo! Logo S nao pode ser um conjunto. Daı a necessidade de axiomatizar esta teoria.

1.2 Propriedades

Feita estas observacoes (e advertencias) iniciais, passaremos a descrever as propriedades dos numeros naturais e interios, que serao de dois tipos: aritmeticas e de ordem.

1.2.1 Propriedades aritmeticas

Seja A um conjunto munido de duas operacoes binarias: + (adicao) e · (multiplicacao). Diremos que A e um anel (comutativo) quando estas operacoes possuem as propriedades que descreveremos abaixo.

Sao comutativas: a + b = b + a e ab = ba, para todos a,b ∈ A (ab e usada, em vez de a · b, para denotar o produto de a por b);

Possuem elemento neutro: Exixtem elementos 0 (zero) e 1 (um) de A tais que 0 + a = a e 1a = a, para todo a ∈ A.

Existe inverso aditivo: para todo a ∈ A, existe −a ∈ A tal que a + (−a) = 0;

O produto distribui com relacao a adicao: a(b + c) = ab + ac, para todos a,b,c ∈ A.

Por exemplo, podemos mostrar que, em um anel A, o produto de zero por qualquer elemento a de A e igual a zero. De fato, como o zero e o elemento neutro da adicao, temos que

Multiplicando esta identidade em ambos os lados por a, obtemos que a(0 + 0) = a0.

Como o produto distribui com relacao a adicao, concluımos que: a0 + a0 = a0.

Se adicionarmos o inverso aditivo de a0 a ambos os lados da identidade, temos que:

e chegamos a conclusao desejada, isto e, a0 = 0, pois 0 e o inverso aditivo.

Sera que em um anel o zero pode ser igual ao um? Caso isto ocorra, para todo elemento a do anel, temos que

(A primeira igualdade segue porque 1 e o elemento neutro da multiplicacao e a ultima do paragrafo anterior.) Isto e, o anel contem um unico elemento que e o zero. Vamos assumir que este nao e o caso. Portanto, em qualquer anel, suporemos tambem que 0 e 1 sao distintos. Como exercıcio, verifique que o inverso aditivo de um elemento e unico.

Vamos assumir, ao longo destas notas, que o conjunto dos inteiros, munido das operacois habituais de adicao e multiplicacao, e um anel.

Outros conjuntos possuem operacoes de adicao e multiplicacao com estas mesmas propriedades, ou a maioria delas. Por exemplo, as matrizes quadradas de ordem m, com as suas operacoes de adicao e multiplicacao usuais, possuem todas estas propriedades exceto comutatividade para o produto, isto quando m > 1. Sabemos que existem matrizes X e Y , ambas nao nulas, tais que XY = 0. Logo iremos assumir que o conjunto dos inteiros possui uma outra propriedade, que e muito importante:

Nao existe divisor de zero: se a,b ∈ Z e ab = 0, entao a = 0 ou b = 0.

Esta propriedade nos permite fazer cancelamento nos inteiros. Suponha que a,b,c ∈ Z sao tais que a 6= 0 e:

Observe que a passagem da segunda para a terceira equacao se deve a nao existencia de divisores de zero, pois o produto de a por b − c e igual a 0 e daı b − c = 0, pois a 6= 0. (Para o leitor, deixamos como exercıcio listar todas as propriedades que foram utilizadas para obter cada uma destas equacoes a partir da anterior.)

1.2.2 Propriedades de ordem

Diremos que um anel A e ordenado quando existe um subconjunto P de A fechado com realacao a soma e ao produto satisfazendo a propriedade da

Tricotomia: para todo a ∈ A, temos que a = 0 ou a ∈ P ou −a ∈ P, sendo estas opcoes multuamente excludentes.

Diremos que um elemento pertencente ao conjunto P e positivo no anel A. Um elemento a de A e dito negativo em A quando −a for positivo em em A.

Para a demonstracao do proximo lema, necessitamos estabelecer o seguinte: (−1)(−1) = 1. (1.1)

Como −1 e o inverso aditivo de 1, por definicao, temos que:

Destibuindo o produto com relacao a soma e usando o fato de que o produto de zero por qualquer elemento e zero, concluımos que:

(Parte 1 de 4)

Comentários