Abril de 2019 foi um bom mês para os belgas corajosos!

O ciclista belga Victor Campanaerts quebrou o recorde mundial de hora, cobrindo uma incrível, desassistida, undrafted 55 km em um velódromo (55.089 metros, de fato) em 60 minutos.

O recorde anterior, estabelecido por Sir Bradley Wiggins em 2015, durou quase quatro anos.

Mas o profissional belga Bernard Fabrot conquistou um desafio ainda mais duradouro.

Ele quebrou um quebra-cabeça computacional retrocedido em 1999, por ninguém menos que o professor Ron Rivest, do MIT, que é o R no bem conhecido algoritmo de criptografia de chave pública RSA.

O feito de Fabrot é particularmente interessante porque Rivest projetou especialmente o quebra-cabeça na esperança de que levaria 35 anos para ser resolvido, supondo que começaram a tentar resolver assim que foi publicado.

No final, Fabrot precisou de 3,5 anos de tempo de execução de computador, superando assim a estimativa de Rivest por um fator de 10.

O quebra-cabeça é o que é conhecido como um “problema de bloqueio de tempo” – um cálculo demorado que só pode ser acelerado pelo ajuste do seu algoritmo ou pela construção de um hardware de computador mais rápido.

Os quebra-cabeças de tempo são interessantes e importantes, porque eles não podem entrar em curto-circuito simplesmente dividindo o problema em pedaços e jogando mais computadores nele.

Os quebra-cabeças de tempo bloqueado são inerentemente sequenciais, tipicamente exigindo um número de loops através de um algoritmo onde a entrada para cada iteração do loop só pode ser adquirida pela leitura na saída da iteração anterior.

A ideia é colocar todos no mesmo barco: você pode ser a maior, mais rica e mais energética empresa de computação em nuvem do mundo, mas todos esses servidores, CPUs e núcleos de CPU não permitirão que você compre seu caminho para a vitória.

Paralelização

A maioria dos problemas pode ser dividida em partes, e pelo menos algumas dessas partes podem se sobrepor.

Se você fosse convidado a contar todos os elefantes na África, por exemplo, você poderia voar para a Cidade do Cabo e ziguezaguear para o norte até chegar a Alexandria, no Egito, observando todos os elefantes enquanto seguia em frente.

Mas esta é uma tarefa inerentemente ‘paralelizável’, porque – se você ignorar complexidades como elefantes que você já contou vagando através das fronteiras nacionais, por exemplo – o número de elefantes na Zâmbia, digamos, pode ser contado ao mesmo tempo que o número na vizinha Angola.

Simplificando, você pode definir uma pessoa diferente para contar em cada país, sem se preocupar com a ordem em que eles começam – e nos maiores países, você pode subdividir a tarefa novamente, usando uma pessoa em cada província, e assim por diante.

O caminho crítico longo e sinuoso

O enigma de Ron Rivest de 1999 não pode ser dividido como nosso exercício de contagem de elefantes – no fundo, é apenas um loop único com a contagem de iterações planejada para durar cerca de 35 anos, com base em estimativas de como o poder de computação aumentaria no período.

A Rivest chegou a trabalhar em uma atualização anual, presumindo que os solucionadores de quebra-cabeças suspendessem os cálculos por um momento uma vez por ano para atualizar seus computadores para o mais recente e mais rápido do mercado.

Por que 35 anos?

O quebra-cabeça foi anunciado para comemorar o 35º aniversário do Laboratório de Ciência da Computação do MIT, que foi inaugurado no início dos anos 1960, e deveria levar mais de 35 anos para funcionar, a tempo do 70º aniversário.

No final, levou apenas 20 anos até que o quebra-cabeça fosse completado, pelo já citado Bernard Fabrot.

Como dissemos acima, ele precisou de 3,5 anos do tempo decorrido do início ao fim, terminando assim quase 15 anos mais cedo, apesar de ter começado com mais de 15 anos de atraso.

O algoritmo

O algoritmo em si é fácil de implementar.

Mas a parte difícil de completar a solução é nunca perder a noção de onde você está.

Não há “truques”, além de backups precisos e regulares do estado computacional, para permitir a recuperação se o computador travar ou se um erro ocorrer.

Sem backup bem gerenciado, qualquer falha ou interrupção significa voltar à estaca zero.

Há também o desafio, é claro, de não perder a fé ao longo do caminho e fazer as malas.

Aqui está o enigma, como Rivest definiu:

O problema é calcular 2 ^ (2 ^ t) (mod n) para valores especificados de t e n. Aqui n é o produto de dois primos grandes, e t é escolhido para definir o nível desejado de dificuldade do quebra-cabeça.

Para explicar, 2 ^ t é a notação de texto de Ron Rivest para 2 elevada ao poder de t, ou 2t, e a notação mod n significa obter o restante, ou módulo, que sobra após dividir o número original por n.

Por exemplo, 3 vai para 6 exatamente duas vezes, então 6/3 = 2 restante 0; mas se você dividir 7 por 3, você ganha 2 com 1 sobra, de modo que 7/3 = 2 restante 1.

Rivest set t para um valor de pouco menos de 80 milhões e construiu um valor de n com 2048 dígitos binários (512 dígitos hexadecimais ou 256 bytes), assim:

t = 79,685,186,856,218

n = 0x32052C40E056ED2C9141FC76C060FA685F60C45095EB69930CBE4B2C81B19C33
55FA9149150D7082284CC3903C12B98DACC7E2FC7C16907F8E946AEFB5FD1240
77E05D944B6738334E71A9BD37E1C08F2DF3D119EB95182B0F3E87B341A217BB
433F2114FEAE1555CFB974DA3D56D4AD7C1D83FD789F34143CDD3D502C104639
EE68DDC8D56D5BC6EAAC7ED16C1F5FF02159B5D52AF94979A18A60EFCABE109E
E2E90C14B6FC1225B754644D989FC1B9F87552B255997CEE22429CF49E3599DA
4B3F6D5535B83072A1D4357AE1ABFF8455B80C438EC33A5C7C6CB1ACE22C62FE
67B3040029B3C37E5EC682363A77D42FB223E194878E146D06739EC4E598A9A1

A ideia é que não há nenhum atalho pelo qual você possa calcular a resposta final, a menos que você conheça os dois números primos que foram multiplicados juntos para calcular o valor de n.

Ron Rivest, e agora Bernard Fabrot, conhece os fatores primos de n, vamos chamá-los peq, mas ninguém mais sabe.

(Rivest precisava de um atalho para seu próprio uso, para que ele pudesse calcular a resposta com antecedência, a fim de decidir quando um concorrente realmente tinha resolvido isso.)

Então, para resolver esse quebra-cabeça sem peq, você só precisa continuar multiplicando várias vezes até chegar ao fim do cálculo.

Cada multiplicação no loop usa a saída anterior como entrada, de forma que você não pode dividir a computação entre vários computadores, CPUs ou até mesmo núcleos de CPU.

Como codificá-lo

Vamos dar uma olhada no problema, usando o Python.

Em Python, o operador ** significa ‘aumentar o poder de’ ou ‘exponencial’, e % significa ‘encontrar o resto após a divisão por’ ou ‘módulo’, e vamos assumir que a função seq (n) percorre os números 1,2,3, até o n.

   exp = 2 ** 79685186856218
val = 2 ** exp
val = val% 0x32052 … 98A9A1

Fácil!

Exceto que exp na linha 1 é um número com quase 20 milhões de dígitos decimais.

Então, você precisa de 10 terabytes apenas para armazenar esse valor – e ainda assim, na próxima linha de código, pretendemos elevar 2 à potência daquele número já alarmantemente grande.

Se implementarmos a operação ** como multiplicação repetida, com 2 ** n calculado como um loop de n-etapas multiplicando 2 por 2 por 2… n vezes, você verá o quão intratável esse cálculo se parece:

   exp = 1
para i em seq (796851868562180): exp = exp * 2
val = 1
para i em seq (exp): val = val * 2
val = val% 0x32052 … 98A9A1

Isso é 80 milhões de milhões de loops no primeiro loop, apenas para descobrir quantos zilhões de bilhões de loops nós temos que fazer no cálculo real no segundo loop!

Exponenciação por quadratura

Felizmente, há uma maneira mais discreta de fazer o cálculo.

Na expressão em loop val = val * 2, aumentamos nosso expoente em 1 sempre, calculando 21, 22, 23, 24, 25 e assim por diante, à medida que o loop continua.

Mas se continuarmos fazendo o squaring val em vez de dobrar, assim…

   val = val * val

…então nós dobramos o expoente a cada vez ao invés de incrementá-lo, então passamos por 21, 22, 24, 28, 216 e assim por diante.

Então nós podemos calcular 2 (2t) com apenas t loops ao invés de 2t loops, assim (na verdade, nós fazemos um loop menos que acima porque nós começamos em 2 desta vez):

   val = 2
para i em seq (796851868562180-1): val = val * val
# Agora encontre o restante
val = val% 0x32052 … 98A9A1

É muito grande!

Este código ainda não é bom, embora agora tenhamos 80 milhões de loops no total, com um ridículo 280.000.000.

O valor numérico só fica muito grande para ser manuseado à medida que avançamos.

Mesmo fazendo apenas alguns loops na linha 2, você pode ver que o tempo gasto para cada iteração extra é praticamente o dobro em todas as etapas, porque estamos multiplicando números com o dobro de dígitos de cada vez:

   milissegundos | valor computado
0 | 2 ^ (2 ^ 1)
0 | 2 ^ (2 ^ 2)
0 | 2 ^ (2 ^ 3)
. . . . . . .
0 | 2 ^ (2 ^ 16)
1 | 2 ^ (2 ^ 17)
2 | 2 ^ (2 ^ 18)
5 | 2 ^ (2 ^ 19)
11 | 2 ^ (2 ^ 20)
25 | 2 ^ (2 ^ 21)
49 | 2 ^ (2 ^ 22)
97 | 2 ^ (2 ^ 23)
195 | 2 ^ (2 ^ 24)
406 | 2 ^ (2 ^ 25)
833 | 2 ^ (2 ^ 26)
1690 | 2 ^ (2 ^ 27)
3513 | 2 ^ (2 ^ 28)
7182 | 2 ^ (2 ^ 29)
14832 | 2 ^ (2 ^ 30)

Felizmente, na aritmética modular, você pode levar o restante ao final, como acima, ou repetidamente, a cada passo do caminho.

Somente o restante precisa ser realimentado da parte inferior do loop para a próxima multiplicação.

Então, você pode mudar a operação % dentro do loop para (em Python, o recuo mostra em qual nível de loop o código está):

   val = 2
para i em seq (796851868562180-1):
val = val * val
# Calcular o restante a cada vez
# dentro do loop, não uma vez no final
val = val% 0x32052 … 98A9A1

Os restos são todos de tamanho fixo – neste caso, eles não podem ser maiores que n-1, e dado que n tem 2048 bits, isso significa que cada estágio envolve multiplicar 2048 bits por 2048 bits e então dividir o produto de volta até um resto de 2048 bits.

A resposta acumulada val é um número de 2048 bits no final de cada iteração e, portanto, 2048 bits no início do próximo, então cada volta extra ao redor do loop adiciona a mesma quantidade de tempo, então agora estamos voando:

   milissegundos | valor computado
0 | 2 ^ (2 ^ 1)
0 | 2 ^ (2 ^ 2)
0 | 2 ^ (2 ^ 3)
0 | 2 ^ (2 ^ 4)
0 | 2 ^ (2 ^ 5)
0 | 2 ^ (2 ^ 6)
. . . . . . .
0 | 2 ^ (2 ^ 27)
0 | 2 ^ (2 ^ 28)
0 | 2 ^ (2 ^ 29)
0 | 2 ^ (2 ^ 30)

Em um Mac, fazer 1.000.000 de iterações leva pouco mais de 16 segundos, então eu posso fazer cerca de 62.500 iterações por segundo.

Nesse ritmo, levaria 80.000.000 / 62.500 segundos para completar o quebra-cabeça, que é pouco menos de 15.000 dias, ou cerca de 40 anos.

Um Mac topo de linha e um programa otimizado de divisão e divisão podem muito bem dobrar tanto a velocidade da minha CPU quanto a eficiência computacional para uma aceleração geral de 4 ×, mas eu ainda estaria pensando em 10 anos para resolver isso.

Muito bem, Bernard

Fabrot fez isso em 3,5 anos, e ele não tinha o hardware de hoje quando começou.

Então foi um bom resultado – e uma vitória empolgante, considerando que ele usou hardware de commodity.

Após o anúncio de Fabrot, uma startup de criptomoeda entrou na onda ao anunciar publicamente que resolveu esse quebra-cabeça em dois meses usando hardware especializado conhecido como Field Programmable Gate Array (FPGA).

Mas, embora o link em seu site use explicitamente o tempo passado, dizendo que o grupo “resolveu em 2 meses”, o link é um simulado que não vai a lugar nenhum, e a conta do Github que supostamente hospeda o código-fonte ainda diz ” Código em breve ‘.

A glória vai para Fabrot, que mostrou que a competência silenciosa é sua própria recompensa …

… E também é um lembrete importante de que, quando os criptógrafos nos avisam que os ataques só ficam mais rápidos, eles não estão errados!

Com informações dos parceiros do blog Naked Security.