Novo recorde de quebra de criptografia alcançado, com menos ajuda do que o habitual da Lei de Moore

3

Pesquisadores alcançaram um novo marco nos anais da criptografia, com o fatoramento do maior tamanho de chave RSA já calculado e um cálculo correspondente do maior logaritmo discreto inteiro de sempre. Novos registros desse tipo ocorrem regularmente à medida que o desempenho do hardware do computador aumenta com o tempo. Os registros anunciados na noite de segunda-feira são mais significativos porque foram alcançados consideravelmente mais rapidamente do que as melhorias de hardware previam, graças a melhorias no software usado e nos algoritmos implementados.

Muitos algoritmos de criptografia de chave pública dependem de números extremamente grandes que são o produto de dois números primos. Outros algoritmos de criptografia baseiam sua segurança na dificuldade de resolver certos problemas discretos de logaritmo. Com tamanhos de chave suficientemente grandes, não há maneira conhecida de quebrar a criptografia que eles fornecem. A fatoração dos grandes números e a computação de um logaritmo discreto anulam as garantias criptográficas para um determinado tamanho de chave e forçam os usuários a aumentar o número de bits de entropia que ele usa.

o novos registros incluem a fatoração de RSA-240, uma chave RSA com 240 dígitos decimais e um tamanho de 795 bits. A mesma equipe de pesquisadores também calculou um logaritmo discreto do mesmo tamanho. Os registros anteriores foram a factoring em 2010 de um RSA-768 (que, apesar de seu dígito, é uma chave RSA menor que a RSA-240, com 232 dígitos decimais e 768 bits) e o computação de um logaritmo discreto principal de 768 bits em 2016.

A soma do tempo de computação para os dois novos registros é de cerca de 4.000 anos-núcleo, usando as CPUs Intel Xeon Gold 6130 (rodando a 2,1 GHz) como referência. Como os registros anteriores, esses foram realizados usando um algoritmo complexo chamado Number Field Sieve, que pode ser usado para executar tanto o fatoramento inteiro quanto os logaritmos discretos de campo finito. Um detalhamento aproximado do tempo gasto na peneiração e matriz do fatorador RSA e no cálculo do problema de logaritmo discreto são:

  • Peneiramento RSA-240: 800 anos-núcleo físicos
  • Matriz RSA-240: 100 anos-núcleo físicos
  • Peneiração DLP-240: 2400 anos-núcleo físicos
  • Matriz DLP-240: 700 anos-núcleo físicos

Lei de Moore fica em segundo plano

É a primeira vez que registros para fatoração inteira e logaritmo discreto são quebrados juntos. É também a primeira vez que dois registros foram estabelecidos usando o mesmo hardware e software. Essas não são as únicas coisas que diferenciam os marcos mais recentes dos anteriores.

Quando novos recordes são estabelecidos, os decretos da Lei de Moore inevitavelmente desempenham um papel importante. A Lei de Moore é a tendência de que os chips de computador geralmente dobram o número de transistores que eles têm a cada 18 meses. O aumento de transistores, por sua vez, aumenta o poder computacional dos computadores que os executam, dando aos computadores maior velocidade e desempenho ao longo do tempo.

Embora a Lei de Moore tenha sido originalmente uma observação feita pelo cofundador da Intel, Gordon Moore, em 1965, ela passou a ser vista como uma força quase inevitável da natureza, como as leis da física. Dada a marcha implacável da Lei de Moore, seria incomum se registros como o anunciado na segunda-feira não ocorressem regularmente.

Este, no entanto, é menos orientado pela Lei de Moore do que os marcos anteriores e mais pelas melhorias feitas no software que realiza a peneiração de campo numérico. Para demonstrar o aumento da eficiência, os pesquisadores executaram seu software em hardware idêntico ao usado para calcular o logaritmo discreto de 768 bits em 2016. Eles descobriram que usar o hardware antigo para peneirar o tamanho recorde de 795 bits levaria 25% menos tempo do que o mesmo equipamento para executar o cálculo DLP de 768 bits.

Outro sinal do desempenho aprimorado: usando hardware idêntico a partir de 2016, o cálculo no logaritmo de 795 bits foi 1,33 vezes mais rápido do que no de 768 bits. As estimativas amplamente aceitas no campo da criptografia prevêem que o logaritmo de tamanho maior seja cerca de 2,25 vezes mais difícil de calcular. Em conjunto, isso sugere um aumento de três vezes no desempenho em relação ao esperado (ou seja, 2,25 * 1,33 = 3). Como o hardware era o mesmo para os dois tamanhos de bit, o aumento de desempenho não é atribuível à disponibilidade de computadores cada vez mais rápidos.

"A aceleração pode ser atribuída a várias melhorias algorítmicas que foram implementadas para esses cálculos", escreveram os pesquisadores no anúncio de segunda-feira à noite. A chave para essas melhorias foram as atualizações feitas no software de código aberto usado para implementar a peneira de campo numérica. Conhecido como CADO-NFS, compreende 300.000 linhas de código escritas em C e C ++.

Emmanuel Thomé, pesquisador sênior do Instituto Nacional de Ciência da Computação e Matemática Aplicada da França e líder da equipe que estabeleceu o recorde, disse que não é fácil descrever as otimizações nos termos dos leigos. As melhorias, ele escreveu em um email, incluem:

  • trabalhámos em uma melhor paralelização e uso de memória (mas nossos concorrentes também o fizeram, para ser perfeitamente honesto).
  • aproveitamos mais sistematicamente os algoritmos assintoticamente rápidos em algumas partes intensivas da computação.
  • há uma grande parte desse negócio de registros criptográficos que chama a arte de "escolher parâmetros". Fizemos isso muito bem. Uma parte importante da imagem é a capacidade de testar muitos conjuntos de parâmetros diferentes e classificá-los usando ferramentas de simulação precisas que desenvolvemos.

Mas é apenas um pouco menos alusivo do que dizer "várias melhorias".

Outros pesquisadores da equipe incluíram Fabrice Boudot, do Ministério da Educação Nacional da França e da Universidade de Limoges, Pierrick Gaudry do Centro Nacional Francês de Pesquisa Científica, Aurore Guillevic, do Instituto Nacional de Ciência da Computação e Matemática Aplicada da França, Nadia Heninger, da Universidade. da Pensilvânia e da Universidade da Califórnia, San Diego, e Paul Zimmermann, do Instituto Nacional de Ciência da Computação e Matemática Aplicada da França.

Com tanta atenção dedicada ao advento dos computadores quânticos e sua capacidade de quebrar facilmente a criptografia de chave pública de hoje, os pesquisadores têm estado ocupados desenvolvendo novos esquemas que podem suportar tais ataques.

"Enquanto isso, os pesquisadores vêm progredindo no aprimoramento dos algoritmos clássicos para resolver o fatorial e o log discreto, o que, juntamente com a lei de Moore, resulta em novos tamanhos de chave quebráveis ​​pelos recursos computacionais disponíveis para os acadêmicos", escreveu Heninger em um email. "A opinião dos profissionais é basicamente que esperamos que eles tenham seguido os conselhos para mudar para pelo menos 2048 bits RSA, Diffie-Hellman ou DSA, há vários anos, o que os manteria a salvo de qualquer uma dessas melhorias".

Fonte: Ars Technica