RESUMO

O método de criptografia RSA é fundamentado em conceitos da teoria de números e baseia-se na codificação feita por meio de uma chave pública, dada por n=pq, onde p e q são primos distintos. Assim sendo, a segurança da mensagem codificada, depende do quão complicado será decompor n usando os recursos teóricos e tecnológicos disponíveis atualmente. Se n for o produto de números primos "pequenos", por exemplo, a fatoração será imediata usando algoritmos usuais de fatoração e um computador sem muita sofisticação, tornando o processo vulnerável. Também não basta que n seja o produto de números primos somente "grandes", pois se estes forem relativamente próximos um ao outro, não importa quão grande sejam, usando o método de fatoração de Fermat, não seria difícil a sua fatoração. Também não estamos interessados em números que sejam "populares", como os números de Mersene e de Fermat, por razões óbvias. Com o objetivo de encontrar números primos que sejam adequados para gerar a chave pública segura para a criptografia RSA, deparamos com o problema da verificação da primalidade de um dado número. Encontrar um número primo adequado não é uma tarefa simples, embora existam infinitos primos, pois, para a finalidade da criptografia RSA, devemos tomar um número que possua algumas centenas de algarismos e afirmar, com certeza, que este número é primo, tomando os cuidados anteriormente mencionados. Como (ainda) não é conhecida uma fórmula para gerar primos, na busca de um primo se faz necessário, também, aplicar testes de primalidade, que, dependendo da forma do número a ser testado, podem ser extremamente eficientes e rápidos. Antes mesmo de aplicar testes de primalidade, pode-se verificar se o número é um pseudoprimo, assim, caso seja, as chances de se obter um primo são consideravelmente maiores, caso contrário, provamos que o número é composto com bem poucos cálculos. A aplicação dos conceitos e resultados providos da Teoria dos Números à Criptografia RSA serviu de estímulo para um aprofundamento nesta área do conhecimento presente na grade curricular do curso.

Palavras-chave: Primalidade, Criptografia RSA, Fatoração