Em 2 de dezembro de 2019, a lista de discussão da teoria dos números
nmbrthry@listserv.nodak.edu relatou a
fatoração do número RSA-240 (240 casas decimais, 795 bits). Esta é uma nova conquista em criptografia e teoria dos números e a próxima tarefa concluída na lista
RSA Factoring Challenge .
Aqui está o número e seus fatores:
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
Com base na tendência atual, você pode imaginar aproximadamente quando o RSA-1024 (309 dígitos decimais) e o RSA-2048 (617 dígitos) serão invadidos.
As realizações anteriores foram a
fatoração de um número de 768 bits (232 casas decimais) em 2009 e o
logaritmo discreto de um número de 768 bits em 2016 .
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 confiam na dificuldade de resolver alguns problemas logarítmicos discretos. Com tamanhos de chave suficientemente grandes, não há maneira conhecida de quebrar essa criptografia. A fatoração de grandes números e o cálculo do logaritmo discreto destroem 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 ao gerar um segredo.
Cifras cada vez mais sofisticadas estão gradualmente quebrando à medida que o desempenho da CPU aumenta e os algoritmos melhoram.
Após a invenção do algoritmo de campo numérico geral (GNFS) no início dos anos 90, nada de revolucionário apareceu no campo da fatoração de números inteiros, embora algumas otimizações significativas tenham sido feitas. Por exemplo, nos últimos anos, os pesquisadores conseguiram acelerar bastante a fase de encontrar um polinômio adequado.
A fatoração do RSA-240 também se destaca da série geral, porque foi realizada não apenas pelo aumento da capacidade computacional, mas também pela otimização de software e algoritmos. Para provar a eficácia das alterações feitas, os pesquisadores lançaram o programa no mesmo equipamento usado para calcular o logaritmo discreto de 768 bits em 2016. Eles descobriram que peneirar uma matriz de números de 795 bits é 25% mais rápido que peneirar uma matriz de números de 768 bits sem otimização.
O mesmo grupo de pesquisadores calculou um logaritmo discreto do mesmo tamanho. Pela primeira vez na história, os registros para logarming discreto e fatoração de números do mesmo tamanho são definidos simultaneamente e até no mesmo hardware e software.
Graças à otimização de algoritmos e software, o logaritmo discreto de um número de 795 bits foi acelerado em 33% em comparação com o logaritmo de um número de 768 bits sem otimização no mesmo hardware.
Segundo a teoria, o logaritmo de um número de 795 bits é 2,25 vezes mais complicado que um número de 768 bits. Isso significa que o efeito de otimização é na verdade três vezes (2,25 × 1,33 = 3).
Ambos os tipos de cálculos foram realizados usando o algoritmo de campo do número da peneira no programa
CADO-NFS de código aberto. Entre as otimizações - paralelização aprimorada e uso de memória, bem como muito trabalho para encontrar parâmetros de cálculo mais ideais (um software especial foi desenvolvido para testar e classificar diferentes parâmetros de cálculo).
A quantidade de tempo computacional para os dois novos registros é de aproximadamente 4000 anos de operação dos núcleos físicos dos processadores Intel Xeon Gold 6130 (a uma frequência de 2,1 GHz), se esse processador for usado como referência.
Uma divisão aproximada do tempo em fatoração e logaritmo:
- Rastreio RSA-240: 800 anos-núcleo
- Matriz RSA-240: 100 anos-núcleo
- Rastreio DLP-240: 2400 anos-núcleo
- Matrix DLP-240: 700 anos-núcleo
A conquista foi marcada por uma equipe de pesquisa liderada por Emmanuel Thomé, pesquisador líder do
Instituto Nacional Francês de Informática e Matemática Aplicada .
Os inventores da cifra RSA publicaram
números RSA
de todos os tamanhos até RSA-2048. Todos podem tentar hackear eles.
Com base na tendência atual, você pode calcular quando o RSA-1024 (309 caracteres) e o RSA-2048 (617 caracteres) serão invadidos. Se você extrapolar a programação, receberá cerca de 2031 e 2073, respectivamente. Mas vemos que a otimização de software e algoritmos pode aproximar significativamente esse termo. Talvez o RSA-2048 seja hackeado durante a nossa vida.
Na prática, o RSA recomenda o uso do tamanho mínimo de chave RSA de 2048 ou 4096 bits.
A julgar pelo desenvolvimento de computadores quânticos, eles não chegarão tão perto de quebrar chaves desse tamanho, embora seja difícil prever algo aqui. Em 2012,
o algoritmo Shore lidou com a
fatoração de 21 (3 × 7), cinco bits de entropia. Esse número permaneceu por muito tempo um registro de fatoração quântica, mas em 2018, a fatoração do produto dos números primos
4088459 foi demonstrada nos processadores IBM de 5 e 16 qubit, que já são 22 bits.
