San Diego-based MemComputing is researching the use of in-memory processing ASICs (Application Specific Integrated Circuits) to potentially crack 2048 bit RSA in real time.
MemComputing is a company and computing philosophy born out of theory. The theory is that if processing and data can be combined in memory, the so-called ‘von Neumann bottleneck’ can be broken. This bottleneck is latency introduced by having storage and processing separate, and the consequent necessity of communicating between the two.
As the computational complexity increases, the processing time required by classical computers also increases – but exponentially. The result of the bottleneck is that a category of complex mathematical problems cannot be solved by classical (basic von Neumann architecture) in any meaningful time frame.
“Among intractable combinatorial problems, large-scale prime factorization is a well-known challenge,” MemComputing researchers wrote in a paper titled Scaling up prime factorization with self-organizing gates: A memcomputing approach (PDF). It is the intractability of this problem that has kept RSA-based encryption theoretically secure for so long. It’s not that it is mathematically impossible, merely that it would take too long to be realistic using classical computers.
Where theory cannot be demonstrated by fact, the problem and solution are emulated in software. For cracking RSA, “Presently, sieve methods represent the state-of-the-art algorithms showing promise, with the general number field sieve method being the most effective. Nevertheless, even these methods struggle to factor a 2048-bit RSA key within a sensible timeframe, and past instances have taken almost 2700-CPU-years to factor an 829-bit number using computer clusters.”
The von Neumann bottleneck means that time-to-solution increases exponentially. “It is estimated that with current technology using the best-known algorithm (general number field sieve, GNFS), factoring a 2048-bit RSA key would take longer than the age of the universe,” the researchers added.
Quantum computers will be able to solve this problem within a meaningful timeframe. Hence the NIST-driven drive for more complex post-quantum algorithms able to continue protecting encryption. Estimates of the arrival of quantum computers vary greatly, but ‘decades’ is usually quoted.
Enter MemComputing’s combined memory/processing. Simulation shows that the complexity/time ratio for solving difficult problems increases only polynomially rather than exponentially. In other words, difficult problems can be solved very much faster — and the time taken to do so can be massively reduced.
MemComputing effectively wanted to know how long it would take its patented in-memory processing to crack RSA, and whether it could be done in a shorter timeframe than waiting for the arrival of quantum computers. The basic study resulted from a Small Business Innovation Research (SBIR) contract with the US Air Force.
The approach taken was to use software emulation focusing on test problems from 30 to 150 bits. “Results showed that the circuit generated the appropriate congruences for benchmark problems up to 300 bits, and the time needed to factorize followed a 2nd-degree polynomial in the number of bits,” MemComputing announced. In other words, the increasing complexity of factoring large numbers with in-memory computing increases the necessary time far more slowly than the exponential increase afforded by classical computers.
“The next step is to extend the effective range beyond 300 bits, which requires customizing the SOG design to even larger factorization problems, with the end goal of realizing the capability in an Application Specific Integrated Circuit (ASIC),” continued the company.
An ASIC is a custom chip. They are already widely used for different applications. They take longer and are more costly to produce than general purpose classical computer chips, but neither are in the same league as developing and waiting for a quantum computer.
Specifically, the researchers said, “The timing for the ASIC realization of the MEMCPU Platform is also reported. The ASIC timing can be easily estimated since the MEMCPU Platform, being a circuit emulator, returns the full dynamics of the circuit, including the simulated runtime. It is worth noting that, at this point in our R&D, the forecast for the ASIC shows the possibility of solving a 2048-bit factorization problem in tens of minutes.”
This conclusion is, of course, theory rather than demonstrable fact. The theory, however, is based on a body of fact, and theoretical research underlies much of today’s demonstrable science. If it all proves practical, the feared ‘cryptopocalypse’ (the death of current encryption) might be sooner than expected – caused by in-memory computing ASICs rather than quantum computers.
Related: How Quantum Computing Will Impact Cybersecurity
Related: Cyber Insights 2023 | Quantum Computing and the Coming Cryptopocalypse
Related: Quantum Decryption Brought Closer by Topological Qubits
Related:US Government Publishes Guidance on Migrating to Post-Quantum Cryptography