A MemComputing, com sede em San Diego, está pesquisando o uso de ASICs (Circuitos Integrados de Aplicação Específica) de processamento na memória para potencialmente quebrar RSA de 2048 bits em tempo real.
MemComputing é uma empresa e uma filosofia de computação nascida da teoria. A teoria é que se o processamento e os dados puderem ser combinados na memória, o chamado “gargalo de von Neumann” poderá ser quebrado. Esse gargalo é a latência introduzida pela separação do armazenamento e do processamento e a consequente necessidade de comunicação entre os dois.
À medida que a complexidade computacional aumenta, o tempo de processamento exigido pelos computadores clássicos também aumenta – mas exponencialmente. O resultado do gargalo é que uma categoria de problemas matemáticos complexos não pode ser resolvida pela arquitetura clássica (arquitetura von Neumann básica) em qualquer período de tempo significativo.
“Entre os problemas combinatórios intratáveis, a fatoração primária em grande escala é um desafio bem conhecido”, escreveram pesquisadores da MemComputing em um artigo intitulado Ampliando a fatoração primária com portas auto-organizadas: uma abordagem de memcomputação (PDF). É a intratabilidade desse problema que manteve a criptografia baseada em RSA teoricamente segura por tanto tempo. Não é que seja matematicamente impossível, apenas que levaria muito tempo para ser realista usando computadores clássicos.
Onde a teoria não pode ser demonstrada por fatos, o problema e a solução são emulados em software. Para quebrar o RSA, “atualmente, os métodos de peneira representam os algoritmos de última geração que se mostram promissores, sendo o método de peneira de campo numérico geral o mais eficaz. No entanto, mesmo esses métodos lutam para fatorar uma chave RSA de 2.048 bits dentro de um período de tempo razoável, e instâncias anteriores levaram quase 2.700 anos de CPU para fatorar um número de 829 bits usando clusters de computador.
O gargalo de von Neumann significa que o tempo até a solução aumenta exponencialmente. “Estima-se que com a tecnologia atual usando o algoritmo mais conhecido (peneira de campo numérico geral, GNFS), fatorar uma chave RSA de 2.048 bits levaria mais tempo do que a idade do universo”, acrescentaram os pesquisadores.
Os computadores quânticos serão capazes de resolver este problema dentro de um prazo significativo. Daí o impulso orientado pelo NIST para algoritmos pós-quânticos mais complexos, capazes de continuar protegendo a criptografia. As estimativas da chegada de computadores quânticos variam muito, mas geralmente se cita “décadas”.
Insira a memória/processamento combinado da MemComputing. A simulação mostra que a relação complexidade/tempo para resolver problemas difíceis aumenta apenas polinomialmente e não exponencialmente. Por outras palavras, problemas difíceis podem ser resolvidos muito mais rapidamente – e o tempo necessário para o fazer pode ser enormemente reduzido.
A MemComputing efetivamente queria saber quanto tempo levaria para seu processamento patenteado na memória quebrar o RSA e se isso poderia ser feito em um período de tempo mais curto do que esperar pela chegada dos computadores quânticos. O estudo básico resultou de um contrato de Small Business Innovation Research (SBIR) com a Força Aérea dos EUA.
A abordagem adotada foi utilizar emulação de software com foco em problemas de teste de 30 a 150 bits. “Os resultados mostraram que o circuito gerou as congruências apropriadas para problemas de benchmark de até 300 bits, e o tempo necessário para fatorar seguiu um polinômio de 2º grau no número de bits”, anunciou a MemComputing. Em outras palavras, a crescente complexidade da fatoração de grandes números com a computação na memória aumenta o tempo necessário muito mais lentamente do que o aumento exponencial proporcionado pelos computadores clássicos.
“O próximo passo é estender o alcance efetivo além de 300 bits, o que requer a personalização do design SOG para problemas de fatoração ainda maiores, com o objetivo final de concretizar a capacidade em um Circuito Integrado de Aplicação Específica (ASIC)”, continuou a empresa.
Um ASIC é um chip personalizado. Eles já são amplamente utilizados para diversas aplicações. Eles demoram mais e são mais caros de produzir do que os chips de computador clássicos de uso geral, mas nenhum deles está no mesmo nível do desenvolvimento e da espera por um computador quântico.
Especificamente, os pesquisadores disseram: “O momento para a realização do ASIC da plataforma MEMCPU também é relatado. O tempo ASIC pode ser facilmente estimado, pois a Plataforma MEMCPU, sendo um emulador de circuito, retorna toda a dinâmica do circuito, incluindo o tempo de execução simulado. Vale ressaltar que, neste ponto de nossa pesquisa e desenvolvimento, a previsão do ASIC mostra a possibilidade de resolver um problema de fatoração de 2.048 bits em dezenas de minutos.”
Esta conclusão é, evidentemente, mais uma teoria do que um facto demonstrável. A teoria, no entanto, baseia-se num conjunto de factos, e a investigação teórica está subjacente a grande parte da ciência demonstrável de hoje. Se tudo se provar prático, o temido “criptopocalipse” (a morte da criptografia atual) poderá ocorrer mais cedo do que o esperado – causado por ASICs de computação na memória, em vez de computadores quânticos.