Code breakingLeveraging emerging brain-like computers for cracking codes

Published 23 March 2018

Scientists have discovered a way to leverage emerging brain-like computer architectures for an age-old number-theoretic problem known as integer factorization. By mimicking the brain functions of mammals in computing, Army scientists are opening up a new solution space that moves away from traditional computing architectures and towards devices that are able to operate within extreme size-, weight-, and power-constrained environments.

U.S. Army Research Laboratory scientists have discovered a way to leverage emerging brain-like computer architectures for an age-old number-theoretic problem known as integer factorization.

By mimicking the brain functions of mammals in computing, Army scientists are opening up a new solution space that moves away from traditional computing architectures and towards devices that are able to operate within extreme size-, weight-, and power-constrained environments.

With more computing power in the battlefield, we can process information and solve computationally-hard problems quicker,” said Dr. John V. “Vinnie” Monaco, an ARL computer scientist. “Programming the type of devices that fit this criteria, for example, brain-inspired computers, is challenging, and cracking cryptocodes is just one application that shows we know how to do this.”

The U.S. Army Research Lab (ARL) says that the problem itself can be stated in simple terms. Take a composite integer N and express it as the product of its prime components. Most people have completed this task at some point in grade school, often an exercise in elementary arithmetic. For example, 55 can be expressed as 5*11 and 63 as 3*3*7. What many didn’t realize is they were performing a task that — if completed quickly enough for large numbers — could break much of the modern day internet.

Public key encryption is a method of secure communication used widely today, based on the RSA algorithm developed by Rivest, Shamir and Adleman in 1978. The security of the RSA algorithm relies on the difficulty of factoring a large composite integer N, the public key, which is distributed by the receiver to anyone who wants to send an encrypted message. If N can be factored into its prime components, then the private key needed to decrypt the message can be recovered. However, the difficulty in factoring large integers quickly becomes apparent.

As the size of N increases by a single digit, the time it would take to factor N by trying all possible combinations of prime factors is approximately doubled. This means that if a number with ten digits takes 1 minute to factor, a number with twenty digits will take about 17 hours and a number with 30 digits about two years, an exponential growth in effort. This difficulty underlies the security of the RSA algorithm.