Navegar

Números Inteiros e Criptografia RSA

Números Inteiros e Criptografia RSA
Autor(es) : Severino Collier Coutinho
Páginas : 213
Publicação : IMPA, 2014
ISBN: 978-85-244-0124-4
2ª edição

A palavra criptografia ainda evoca imagens de agentes secretos sorrateiramente transferindo informações sigilosas a nações rivais. Entretanto, a principal missão da moderna criptografia é proteger as informações referentes a transações bancárias e comerciais que transitam entre computadores numa rede.

Este livro é uma introdução elementar a um dos métodos criptográficos mais populares atualmente, o RSA, e à área da Matemática que lhe serve de fundamento, a Teoria dos Números.

O tratamento matemático do material é rigoroso, mas a apresentação é pouco convencional, recheada de exemplos concretos e notas históricas. Isto torna o livro mais agradável de ler do que o compêndio matemático tradicional.

O enfoque adotado é francamente algorítmico, e as demonstrações são, sempre que possível, construtivas. Além disso os pré-requisitos necessários à leitura do livro são mínimos, o que o põe ao alcance de um estudante do segundo grau.

Descrição

Este livro tem uma meta muito precisa: descrever em detalhes um dos métodos de criptografia mais usados em aplicações comerciais, o RSA. Para compreendê-lo é preciso ter bastante familiaridade com as noções de máximo divisor comum, números primos, fatoração, aritmética modular e função totiente, entre outras. O objetivo deste livro é portanto, o de fornecer a base matemática necessária ao entendimento e aplicação do método RSA. A maior parte dos conceitos e métodos de que vamos precisar faz parte da área da matemática conhecida comom teoria de números.

A descrição acima é fiel ao espírito deste livro, mas revela apenas uma de suas facetas; o que poderíamos chamar de ponto de vista do estudante de informática. É fácil dar uma outra descrição, igualmente fiel, e melhor adaptada ao estudante de matemática. Deste outro ponto de vista, este livro é uma introdução elementar à teoria de números e às estruturas algébricas, com ênfase em resultados construtivos e métodos algorítmicos. Assim procuramos estudar conceitos abstratos através de suas manifestações concretas, e as demonstrações que conduzem a algoritmos efetivos foram preferidas às puramente existenciais.

Sem dúvida que, para muitos, este livro vai servir principalmente como um guia à criptografia matemática. Mas é importante não esquecer que quase toda a matemática utilizada no RSA foi desenvolvida sem nenhuma finalidade prática. Para Fermat, Euler, Gauss ou Riemann, o estudo das propriedades dos números inteiros era apenas uma área fascinante da matemática. Nela combinam-se resultados muito simples com demonstrações de enorme engenhosidade. Isto nos deve ajudar a lembrar que a matemática tem vida própria, e que suas aplicações, por muitas que sejam, são apenas uma faceta de seu enorme impacto na história cultural da humanidade.

Neste espírito, o livro não se restringe à descrição mais econômica possível do RSA, mas procura inserir as técnicas matemáticas requeridas em um esquema mais amplo. Por exemplo, tratamos os testes de primalidade como uma aplicação da teoria de grupos. Com um pouco de esforço poderíamos fazer desaparecer os grupos, reduzindo assim as demonstrações a cálculos com fórmulas mais ou menos elementares. Entretanto, um dos efeitos desta ‘simplificação’ seria uma apresentação mais difícil de motivar; que é uma desvantagem. Além disso, o uso dos grupos trás à tona as semelhanças entre os testes de primalidade e alguns métodos de fatoração (de números de Mersenne e Fermat), o que é uma grande vantagem. Isto sem mencionar as inúmeras aplicações dos grupos a outras áreas.

Este livro foi desenvolvido a partir de noras de aulas escritas para o curso de álgebra para a informática da Universidade Federal do Rio de Janeiro. Seu público original foram os estudantes de primeiro período de informática e matemática. Isto determinou muitas das características do livro, e é responsável por algumas de suas idiossincrasias. Em primeiro lugar, os requisitos assumidos são mínimos; e são discutidos em detalhe na seção 8 da introdução. O texto também não pressupõe nenhum conhecimento prévio de computação. Entretanto, uma certa experiência com noções básicas de programação dará melhor perspectiva a muitas das questões tratadas aqui. Por isso alguns exercícios simples de programação são incluídos ao final de cada capítulo. A maior parte destes programas gera dados a serem comparados com alguma conjectura ou resultado da teoria de números, de modo que são o que poderíamos chamar de ‘experimentos matemáticos’.

Um comentário sobre estilo. Freqüentemente os livros de matemática são escritos como uma monótona sucessão de definições, teoremas e demonstrações. Esta é uma penosa herança d’Os Elementos de Euclides, que foi por muitos séculos o livro de matemática mais publicado no Ocidente. É bom não esquecer que nem mesmo entre os matemáticos da Grécia Antiga este estilo marmóreo prevaleceu. Arquimedes, por exemplo, menciona em seus tratados as dificuldades que teve, as derrotas que sofreu, e até enuncia proposições que pensou verdadeiras, e mais tarde descobriu serem falsas, como um alerta a outros matemáticos. Neste livro, preferi o exemplo de Arquimedes ao de Euclides. Por isso o estilo é bastante informal, com muitas notas históricas entremeadas ao texto. A discussão dos tópicos mais difíceis começa com um exemplo característico, e não com um mergulho em uma seqüência abstrata de axiomas. Também não hesitei em descrever os algoritmos com instruções em português, e um mínimo de símbolos; nem fiz esforço para otimizá-los. Achei mais importante ser compreendido. A experiência mostra que programar estes algoritmos não oferece maiores dificuldades, mesmo ao iniciante.

Uma outra característica do livro é a maneira como é feita referência aos teoremas, proposições e algoritmos. É costumeiro numerá-los e referir-se a eles pelo número. Entretanto, boa parte dos resultados deste livro têm nomes tradicionais, e é por esses nomes que são mencionados no correr do texto. Os poucos resultados sem nome são citados pela seção e capítulo onde podem ser encontrados. Isto dificulta um pouco a leitura de quem deseja consultar o livro apenas sobre um tópico específico. Por isso achei melhor incluir índices dos principais resultados e algoritmos, relacionados em ordem alfabética, e indicando a página onde podem ser encontrados.

 

Conteúdo

Introdução

1. Criptografia
2. Criptografia RSA
3. Computação Algébrica
4. Teoria dos Números
5. Fermat, Euler e Gauss
6. O livro
7. Teoremas e demonstrações
8. Pré-requisitos

Capítulo 1. Algoritmos fundamentais

1. Algoritmos
2. Algoritmo de divisão
3. Teorema de divisão
4. Algoritmo euclideano
5. Demonstração do algoritmo euclideano
6. Algoritmo euclideano estendido
7. Exercícios

Capítulo 2. Fatoração única

1. Teorema da fatoração única
2. Existência da fatoração
3. Eficiência do algoritmo usual de fatoração
4. Fatoração por Fermat
5. Demonstração do algoritmo de Fermat
6. Propriedade fundamental dos primos
7. Números irracionais
8. Unicidade
9. Exercícios

Capítulo 3. Números primos

1. Fórmulas polinomiais
2. Fórmulas exponenciais: números de Mersenne
3. Fórmulas exponenciais: números de Fermat
4. Fórmulas fatoriais
5. Infinidade dos primos
6. Crivo de Eratóstenes
7. Exercícios

Capítulo 4. Aritmética modular

1. Relações de equivalência
2. Inteiros módulo n
3. Aritmética modular
4. Critérios de divisibilidade
5. Potências
6. Equações diofantinas
7. Divisão modular
8. Exercícios

Capítulo 5. Indução e Fermat

1. Hanói! Hanói!
2. Indução finita
3. Pequeno teorema de Fermat
4. Contando raízes
5. Exercícios

Capítulo 6. Pseudoprimos

1. Pseudoprimos
2. Números de Carmichael
3. Teste de Miller
4. Primalidade e computação algébrica
5. Exercícios

Capítulo 7. Sistemas de congruências

1. Equações lineares
2. Um exemplo astronômico
3. Algoritmo chinês do resto
4. Módulos não co-primos
5. Potências, novamente
6. Partilha de senhas
7. Exercícios

Capítulo 8. Grupos

1. Definição e exemplos
2. Simetrias
3. Interlúdio
4. Subgrupos
5. Subgrupos cíclicos
6. Determinando subgrupos
7. Teorema de Lagrange
8. Exercícios

Capítulo 9. Mersenne e Fermat

1. Números de Mersenne
2. Números de Fermat
3. Fermat, novamente
4. Exercícios

Capítulo 10. Raízes primitivas

1. Teste de Lucas
2. Outro teste determinístico de primalidade
3. Números de Carmichael
4. Preliminares
5. Teorema da raiz primitiva
6. Exercícios

Capítulo 11. Criptografia RSA

1. Pré-codificação
2. Codificando e decodificando
3. Por que funciona?
4. Por que RSA é seguro?
5. Assinaturas
6. Exercícios

Epílogo

1. Criptografia e teoria dos números
2. Teoria dos grupos
3. Computação algébrica

Apêndice. Algoritmos Complementares

1. Raízes quadradas
2. Potenciação módulo n

Bibliografia

Índice dos principais algoritmos

Índice dos principais resultados

Índice

Autor

Severino Collier Coutinho

Severino Collier Coutinho graduou-se pela Universidade Federal de Pernambuco e obteve seu doutorado na Universidade de Leeds na Inglaterra. Atualmente é professor no Instituto de Matemática da Universidade Federal do Rio de Janeiro. Seus interesses de pesquisa são na área de Álgebra e Geometria Algébrica.