Mais um blog inútil.

Ora estava aqui eu a navegar pelas Internetes quando me deparo com um documento recente relativo à geração de primos aleatórios para quer RSA quer DSS. Ei-lo aqui.

Rapidamente se reparam nos ataques óbvios relativos especialmente ao RSA: factorização por P-1 ou P+1 (Pollard e Williams, respectivamente), o expoente público tem de estar compreendido entre 2^16 e 2^256 (evitam-se assim os imensos ataques relativos a expoentes baixos, e.g. E=3 ou E=7, etc e também os ataques que permitem obter D quando E é demasiado grande (Weger)).

Uma coisa que achei interessante e que nunca tinha visto aplicada é a distinção clara feita entre os parâmetros dos primos prováveis e os provados. Talvez alguém se pergunte porque não simplesmente aumentar a probabilidade dos testes M-R (Miller-Rabin) e pronto?

A resposta reside no facto de o teste de M-R ser baseado no teorema de Fermat (sim, o mesmo utilizado na base do RSA). Existe uma classe de inteiros, chamados números de Carmichael, que passam sempre nos testes baseados no teorema de Fermat. Assim, no pior cenário temos de contar com p1,p2,q1,q2 terem factores trivialmente factorizáveis indetectáveis por M-R. Daí os parâmetros serem maiores.

É também interessante notar que os módulos de 1024 bits já não podem ser gerados aleatoriamente (tabela B.2). Isto talvez indique qualquer coisa em relação à segurança (ou os medos de quem define os standards) do problema da factorização de inteiros.