Uma equipe internacional de cientistas da computação estabeleceu um novo recorde para dois dos problemas computacionais mais importantes que são a base de quase toda a criptografia de chave pública que é usada atualmente no mundo real.

A criptografia de chave pública é usada em vários aplicativos, incluindo criptografar dados sensíveis e confidenciais e assinaturas digitais. Na criptografia de chave pública, as chaves vêm em pares, um público, e um privado, e a segurança do esquema de criptografia ou assinatura digital depende do fato de que se acredita ser intratável computacionalmente para calcular a chave privada a partir da chave pública. A fatoração e o logaritmo discreto são dois desses problemas fundamentais que se acredita serem difíceis de resolver.

A equipe fatorou a maior chave ainda, um número inteiro de 795 bits, e também calculou um logaritmo discreto de um número inteiro de 795 bits. No total, isso levou cerca de 35 milhões de horas de computação.

Os tamanhos de chave quebrados por esse cálculo de registro não são normalmente usados ​​na prática por aplicativos criptográficos modernos. Contudo, É necessário obter registros computacionais regulares para atualizar os parâmetros de segurança criptográfica e as recomendações de tamanho de chave.

Graças aos avanços algorítmicos, esses cálculos foram realizados usando muito menos poder computacional do que foi estimado com base em registros anteriores ou na lei de Moore.

Os registros anteriores eram de 768 bits em ambos os casos. O registro de fatoração anterior datado de 2010, e o registro de logaritmo discreto anterior datado de 2016.

Uma vez que os registros computacionais para fatoração e log discreto foram obtidos simultaneamente para inteiros do mesmo tamanho e no mesmo hardware computacional, este trabalho influencia o entendimento da comunidade científica sobre a dificuldade relativa desses dois problemas. Era comum acreditar que o problema do logaritmo discreto era pelo menos 10 vezes mais difícil do que a fatoração. Este trabalho mostra que a diferença é muito menor, na ordem de um fator de três.