Uma análise da complexidade do algoritmo RSA implementado com o teste probabilístico de Miller-Rabin

Resumo

Este artigo descreve o funcionamento da criptografia de chaves públicas, com ênfase no algoritmo RSA. Apresenta-se o funcionamento do algoritmo, sua aplicabilidade, implementação com o uso do algoritmo probabilístico de Miller-Rabin e a complexidade de funções construídas. Através de uma implementação na linguagem Java, foi possível gerar chaves e testar a sua segurança, utilizando algoritmo de força bruta para a quebra. Com os resultados, foi observado que as chaves são geradas em tempo polinomial, enquanto a quebra necessita de tempo exponencial ao tamanho da chave, dada em bits. Portanto, a quebra de uma chave de grande tamanho através de força bruta torna-se impraticável.