Orientador: Claudio Leonardo Lucchesi

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

Resumo: O objetivo deste trabalho é apresentar uma descrição da implementação de um protótipo para o RSA: o PRSA. O RSA é um sistema criptográfico de chave pública e tem sido reconhecido como uma das idéias mais brilhantes que apareceram nos últimos anos na área da criptografia. Sua implementação...

Resumo: O objetivo deste trabalho é apresentar uma descrição da implementação de um protótipo para o RSA: o PRSA. O RSA é um sistema criptográfico de chave pública e tem sido reconhecido como uma das idéias mais brilhantes que apareceram nos últimos anos na área da criptografia. Sua implementação traz uma série de desafios, dentro de um espectro que vai da Teoria dos Números à. Análise de Complexidade de Algoritmos. A implementação de um protótipo para o RSA serve para estudar os gargalos que tornam a utilização prática do sistema inviável hoje em dia, mas além disso, permitiu o estudo de vários problemas correlatos à implementação do RSA, que se apresenta como um fértil campo para pesquisas. Este trabalho está organizado em três capítulos, onde são expostos vários aspectos da implementação do protótipo e cinco apêndices. No capítulo 1 são feitas algumas considerações a respeito de conceitos básicos de criptografia, com intenção de situar o contexto principal em que o trabalho foi feito. São feitas algumas definições gerais de sistemas criptográficos e é apresentado o RSA. O capítulo 2 se constitui dos principais algoritmos utilizados na implementação do programa. Além. dos algoritmos mais de alto nível em geral encontrados em artigos e livros da área, tentou-se apresentar alguns pontos a respeito da geração de números aleatórios e da aritmética de números de precisão múltipla. Já o capítulo 3 contém informações mais específicas do protótipo. É apresentada a organização modular do programa e a forma. de representação interna dos números de precisão múltipla. Além disso são mostrados dois testes de desempenho do protótipo: 1) Velocidade de ciframento e deciframento e 2) Eficiência da geração de números primos. Estas duas operações são as mais importantes na implementação do RSA. É falado também de algumas experiências feitas para permitir uma maior visualização práqca do desempenho do algoritmo de Rabin para teste de primalidade. Finalmente nos apêndices podem ser encontrados demonstrações de uso do PRSA, tabelas de números primos e uma descrição mais pormenorizada dos módulos componentes do programa.

Abstract: The main goal of this work is to present a description of the implementation of a prototype of the RSA criptosystem. The RSA is a public key cipher and has been considered one of the best inventions. in the last years in the criptography area. Its implementation brings a lot of problems,...

Abstract: The main goal of this work is to present a description of the implementation of a prototype of the RSA criptosystem. The RSA is a public key cipher and has been considered one of the best inventions. in the last years in the criptography area. Its implementation brings a lot of problems, ranging from Number Theory to Analysis of Complexity of AIgorithms. The implemented proiotype was used to investigate some computing bottlenecks that make the practical use of the RSA criptosystem not interesting today, and to study others problems that arise in the implementation. This work is divided in three chapters and tive appendixes. In Chapter 1, in order to show the context where the work was made, are presented some" basic concepts of criptography. The RSA is described in this chapter too. The chapter 2 is formed with the main algorithms that the program use. There are some algorithins more easily found in criptography literature and some commonly found in seminumerical-algorithm literature. Chapter 3 describes other aspects of the program. There are informations about the way multiple precision numbers are represented internally by the program, one overview of the organization of the program modules and some tests made with the prototype in three machines: PC, VAX - 785 and D - 8000. . The appendixes contain some results obtained by the prototype and some demonstrations of its use.