No início de abril de 1999, uma cápsula do tempo foi entregue ao famoso arquiteto Frank Gehry com instruções para incorporá-lo em seus projetos para o edifício que eventualmente abrigaria o Laboratório de Ciência da Computação e Inteligência Artificial do MIT, ou CSAIL. A cápsula do tempo era essencialmente um museu da história inicial do computador, contendo 50 itens contribuídos por pessoas como Bill Gates e Tim Berners-Lee.
A cápsula do tempo não deveria ser aberta por mais 35 anos – a menos que alguém pudesse resolver o quebra-cabeça criptográfico que estava incluído em seu design. O quebra-cabeça foi projetado por Ron Rivest, cujo nome empresta o “R” à RSA — um dos mais importantes protocolos criptográficos já criados.
Ele diz que não foi projetado para ser complicado. Em vez disso, Rivest criou o quebra-cabeça para que a resposta levasse quase exatamente 35 anos para ser calculada.
Em 15 de abril, quase 20 anos depois do dia em que Rivest anunciou o quebra-cabeça, Bernard Fabrot, um programador autodidata da Bélgica, resolveu o problema. As instruções originais do quebra-cabeça determinavam que a solução fosse enviada ao diretor do Laboratório de Ciência da Computação. Mas acontece que o laboratório não existe mais, foi fundido com o laboratório de IA do MIT em 2003 para criar o CSAIL.
Segundo Fabrot, a diretora do CSAIL, Daniela Rus, nem sequer estava ciente da existência do quebra-cabeça quando ele disse a ela que tinha a solução.
O enigma de Rivest basicamente envolveu encontrar o número que resulta da execução de uma potência ao quadrado de quase 80 trilhões de vezes. Por exemplo, se você começar com o quadrado de 2, você obterá 4, em seguida, o quadrado de 4 resultará em 16, repita esse processo 80 trilhões mais vezes. Você pega o número resultante e executa uma operação matemática dada nas instruções para o quebra-cabeça. Fazer isso cria um novo número que pode ser traduzido em uma curta frase de congratulação — Rivest e Fabrot se recusaram a revelar a frase exata, que foi anunciada na abertura da cápsula do tempo em 15 de maio[1].
A questão para esse quebra-cabeça é que ele requer operações sequenciais, o que significa que você não pode obter a resposta mais rapidamente usando computação em paralelo. Você precisa passar pelas operações uma de cada vez, baseando-se na resposta anterior para realizar a próxima operação. Portanto, usar mais computadores não ajudaria na solução.
Baseado na lei de Moore e em quanto tempo levava em 1999 para realizar uma operação de potência, Rivest estimou que calcular a resposta do quebra-cabeça levaria aproximadamente 35 anos.
Fabrot, que trabalha como desenvolvedor independente, diz que tropeçou no quebra-cabeça por acidente em 2015. Embora Rivest tenha inicialmente lançado o código do quebra-cabeça em Java, Fabrot percebeu que poderia ser resolvido mais rapidamente se ele usasse a biblioteca aritmética de precisão múltipla GNU, software livre escrito em C para realizar “aritmética precisa”. Então, Fabrot dedicou um dos núcleos de CPU em seu computador de mesa para executar operações de potência na tentativa de resolver o quebra-cabeça. Seu computador executou a operação 24 horas por dia, 7 dias por semana, exceto quando ele tinha que sair de férias ou havia uma queda de energia.
“Durante todos esses anos, não contei a ninguém que estava tentando resolver o quebra-cabeça, a não ser a amigos muito próximos”, diz Fabrot. “Eu sabia que tinha uma chance, mas se eu contasse a alguém, eles poderiam ter usado uma CPU mais poderosa para me ultrapassar.”
Três anos e meio depois, Fabrot finalmente completou aproximadamente 80 trilhões de operações de potência e obteve a solução para o quebra-cabeça. O timing não poderia ter sido melhor. Embora Fabrot não soubesse, um grupo de cientistas de computação e especialistas em criptografia estava trabalhando em um projeto chamado Cryptophage, que estava usando hardware especializado destinado especificamente para resolver o quebra-cabeça do MIT.
Liderado pelo ex-engenheiro da Intel, Simon Peffers, o grupo Cryptophage estava pesquisando funções de atraso verificáveis como um possível mecanismo de segurança para blockchains como Ethereum. Funções de atraso verificáveis são uma visão moderna do trabalho inicial de Rivest sobre criptografia com atraso de tempo, e sua solução pode ser obtida apenas por meio de operações sequenciais. No decorrer de sua pesquisa, o grupo Cryptophage encontrou o quebra-cabeça de Rivest, o que pareceu ser uma boa maneira de colocar sua pesquisa à prova.
Em meados de março, o grupo começou a executar um algoritmo projetado por Erdinc Ozturk, um pesquisador da Universidade Sabanci, que foi otimizado para reduzir o atraso entre as operações. Esse algoritmo foi implementado em uma Matriz de Portas Programáveis em Campo (Field Programmable Gate Array – FPGA), um chip multiuso que é programado para executar apenas um algoritmo específico, o que o torna mais eficiente do que um processador de uso geral. Usando o algoritmo de Ozturk, foi cerca de 10 vezes mais rápido do que um processador comercial de alto desempenho executando um software não otimizado.
Com base na eficiência de computação do chip, o grupo Cryptophage calculou que teriam a solução correta para o quebra-cabeça na noite de 10 de maio, apenas dois meses após o início do cálculo. No entanto, quando entraram em contato com o MIT para avisá-los que uma solução era iminente, Rivest informou-os de que Fabrot já os havia derrotado.
Rivest admite que superestimou a dificuldade de seu quebra-cabeça. Fazer previsões sobre as melhorias na tecnologia é difícil. Rivest não antecipou avanços como chips FPGA, que não eram tão sofisticados ou amplamente disponíveis como são hoje.
Embora o grupo Cryptophage não tenha sido o primeiro a resolver o enigma, Peffers disse que ainda estará na cerimônia para abrir a cápsula do tempo em 15 de maio. Somente os designers da cápsula sabem seu conteúdo completo, embora inclua contribuições de Tim Berners. Lee, inventor da World Wide Web; Bob Metcalfe, que inventou a ethernet; e Bill Gates, que contribuiu com a versão original do Altair BASIC, o primeiro produto da Microsoft. Fabrot disse que está mais animado em ver uma cópia original de um dos primeiros jogos para PC, Zork, incluído na cápsula.
Fonte
[1] nota da editora: apesar de ter encontrado uma reportagem do dia 16/05, a frase não foi divulgada nele. Aparentemente continuamos sem saber que foi a frase…
