Pesquisadores Decifram RSA-240, Maior Chave de Criptografia Conhecida, Usando 35 Milhões de Horas-Núcleo

Criptografia é usada para proteger dados que você recebe, armazena e envia, usando um dispositivo digital. O governo usa para proteger informações classificadas, corporações usam para proteger segredos de negócios, e indivíduos usam para salvaguardar informações privadas.

Quase todas as técnicas de criptografia usam strings longas para manter dados online seguros. Uma das formas mais populares de criptografia é a criptografia RSA. Baseia-se no fato de que inteiros grandes são difíceis de fatorar.

RSA é um algoritmo de criptografia assimétrica que envolve uma chave pública e uma chave privada. A chave pública contém um número que é multiplicação de dois grandes números primos. A chave privada é derivada dos mesmos dois números primos. A força da criptografia aumenta exponencialmente conforme o tamanho da chave dobra ou triplica.

Para mostrar quão segura a criptografia é contra hardware moderno, Laboratórios RSA publicaram uma lista de semiprimos (números com apenas dois fatores primos) e desafiaram pessoas a encontrar seus fatores primos originais. Até agora, 20 dos 54 números RSA listados foram decifrados.

Recentemente, uma equipe de pesquisa do Instituto Francês de Pesquisa em Ciência da Computação e Automação fatorou RSA-240, uma chave com 240 dígitos decimais que tem 795 bits de tamanho. Esta é a maior chave de criptografia decifrada até agora.

O recorde anterior foi estabelecido em 2009, com RSA-768 que tem 768 bits de tamanho e 232 dígitos decimais. Mesmo que RSA-240 seja maior que RSA-768, pesquisadores conseguiram obter seus fatores primos mais rápido que o recorde anterior.

Tempo de Computação

Além de encontrar fatores primos, pesquisadores também calcularam o logaritmo discreto de RSA-240. Esta é a primeira vez que dois recordes (fatoração inteira e logaritmo discreto) são quebrados juntos com o mesmo software e hardware.

Ambos os cálculos foram realizados com o algoritmo Number Field Sieve, usando software open-source chamado CADO-NFS.

A fatoração inteira levou quase 8 milhões de horas-núcleo, enquanto o cálculo do logaritmo discreto levou 27 milhões de horas-núcleo. O tempo total de computação é equivalente a rodar um único núcleo de computador (2,1 GHz Intel Xeon Gold 6130) por 35 milhões de horas, ou 4000 anos.

Em termos de computação, decifrar RSA-240 é 2,25 vezes mais difícil que decifrar RSA-768. Considerando que pesquisadores usaram hardware idêntico e obtiveram resultados 3 vezes mais rápido que o esperado, a aceleração pode ser atribuída às melhorias feitas em vários algoritmos na última década. A implementação do CADO-NFS, por exemplo, foi grandemente melhorada.

Estes cálculos não representam ameaça à segurança de computadores, pois chaves RSA usadas pelos computadores atuais são maiores, de 1024 a 4096 bits. No entanto, o advento de computadores quânticos pode mudar as coisas radicalmente.