RSA Criptografia

O Contexto

Projeto final da disciplina de Matemática Discreta na UFAL. O requisito era implementar o algoritmo RSA sem o uso de bibliotecas criptográficas, lidando diretamente com a teoria dos números que sustenta a segurança da web moderna.

Toda conexão HTTPS depende desse algoritmo. Implementá-lo do zero obrigou a entender o que de fato acontece por baixo, não apenas chamar uma função.

Os Desafios Matemáticos

O maior desafio não foi a lógica do RSA em si, mas implementar com eficiência as operações aritméticas que ele exige para chaves seguras.

• Exponenciação Modular Rápida: A função modular(base, exp, mod) evita estouro de memória ao calcular potências gigantescas usando a propriedade (a * b) % m de forma iterativa. Sem isso, os números envolvidos no RSA são computacionalmente inviáveis.
• Inverso Modular via Euclides Estendido: Implementação manual da função inverso_modular para encontrar a chave privada d, garantindo que (d * e) % phi == 1. Essa é a operação que torna a descriptografia possível.

Como Funciona

O usuário fornece dois números primos p e q. O sistema calcula o totiente de Euler e gera o par de chaves pública e privada. A mensagem é convertida para inteiros e cifrada com a chave pública. As chaves e a mensagem cifrada são salvas em arquivos .txt, simulando uma troca de mensagens real entre duas partes.

Ver Código Fonte