Criptografia assimétrica com o RSA

Toda a segurança do RSA está focada em um problema matemático ainda sem solução, que é o cálculo de divisores de um número. Ainda hoje a única forma conhecida para se calcular quais números dividem exatamente, sem resto, um outro número é através da tentativa e erro, ou seja, a força bruta. Muitos avanços se tem feito e muitas técnicas usadas para acelerar em muito esta tarefa, mas ela ainda é um problema que demanda muito tempo.

Contudo, basta que algum matemático descubra como calcular os divisores de um número de forma eficiente e pronto, fim do RSA. Se é que algum pesquisador secreto já não o tenha descoberto.

Faz alguns anos o RSA foi posto em cheque devido a uma descoberta envolvendo números primos. O desafio de determinar se um número é ou não primo também demanda tempo. Como tu poderias dizer que o número 65537 é ou não primo? A princípio tentando dividir ele por todos os números primos anteriores a ele. Tenta-se dividir por 2, por 3, por 5 (não teria sentido tentar por 4, pois se fosse divisível por 4, já o teria sido por 2), por 7, 11, 13... Se não se encontrar um divisor até o valor da raiz quadrada de 65537, pode-se com segurança eleger este número como sendo primo.

Esta parte foi um desafio para o RSA. Como o algoritmo, que precisa escolher P e Q primos, pode ter certeza de que são primos? O número P=339837669899793087932310819184919452667 gerado pela biblioteca openssl é primo? Como o RSA tem certeza? O fato é que não tem! Quando da escolha de P e Q não se tem certeza de que eles realmente são primos. O impacto caso não sejam é que o algoritmo ficará mais fraco, mas funcionará tranquilamente.

Chegar a conclusão de que P é realmente primo demandaria o mesmo esforço que um atacante teria para quebrar o N. Por isto o RSA limita-se a aplicar os 3 testes da primaridade. Se ele reprovar em um dos testes, não é primo e será descartado. Se passar em todos os testes, tem uma chance de X% de ser primo. Ao executar os testes várias vezes refina-se a precisão tendo-se, hoje, quase certeza de que são primos.

Pois bem, a descoberta recente (e nem tão recente assim) foi de um algoritmo que dá 100% de certeza de que um número é primo. Isto, por si só, não compromete o RSA pois o que se precisa é de um algoritmo que descubra o P e o Q a partir do N. Contudo aquela "luzinha vermelha" acabou se acendendo e uma névoa de suspeita paira sobre o RSA.

Pretendia tornar este artigo ainda mais extenso, com muitos anexos descrevendo o teorema de Euclides e os atalhos matemáticos para cálculo de módulo. Porém, estes conceitos são necessários para alunos meus resolverem alguns desafios e não pretendo publicar algo que lhes tire o prazer da descoberta!