- Scientists have set a record by extending the longest cracked encryption from 232 digits to 240.
- These numbers are still far smaller than the values used in real cryptography, making this a computing rather than hacking victory.
- Multiplying gigantic prime numbers together is the secure backbone of RSA encryption.
Scientists in France have cracked the most complex cryptography algorithm attempted to date. The algorithm they solved is still much, much weaker than the practical cryptography used in real security, but to solve even this smaller algorithm is a big accomplishment in computing. The scientists used a bunch of computers working simultaneously around the world to turn 35 million computing hours into a doable timeframe.
Cryptography is, at its heart, a math and computing race. The encryption method the scientists used to generate a problem to solve is called the RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman. In this algorithm, two parties encrypt information by using an almost unfathomably big number made by multiplying two prime numbers together.
There are tricks to quickly know if, say, some huge number is divisible by 9 or 11. But as soon as you get to 17 and 19, there’s no longer a simple trick. What are the prime numbers that multiply together to make 667? By the nature of prime numbers, you just have to guess and check. (The answer is 23 and 29.)
The other special thing about prime number encryption is that the product of two primes is unique. These products form a special class called semiprimes. They’re not prime numbers, since we literally multiplied two factors together to obtain them. But they’re not divisible by any composite numbers either. Each has a footprint made of just two primes. Its factors are 1, the two primes, and itself. That’s it.
Composite numbers have hooks and clues that let someone begin to break them apart, and large, odd semiprime numbers have no such hook. (Since 2 is technically a prime number and the only even one, any semiprime of 2 times a large prime would be even, making it super simple to solve.)
Think about trying to break 667 into two primes. Before you get to trying 23 and 29, you have to try all the single digits and then 11, 13, 17, and 19. The numbers these researchers used global multithread computing to crack were 240 digits long, and there are infinite prime numbers for cryptographers to choose from for the entire future.
The mathematical side of RSA application holds up, sure, but sheer computer power is where it could be broken. Running programmed algorithms, computers can keep trying new combinations by brute force until one is the correct answer. Running only prime number candidates narrows the field down a lot, but 4 of the 9 billion potential 10-digit numbers are prime, which means 360,000,000 primes to try. There are trillions, quadrillions, and so forth of longer number candidates. Every extra digit you add multiplies the pool by 10.
So the same fact that makes RSA encryption mathematically daunting makes it mechanically daunting for hackers as well. And its sheer complexity is why the semiprime products of RSA encryption can be shared openly, because only someone with one of the two multiplicands in hand could work out what the second one is. Then to divide the gigantic numbers is its own daunting next challenge.
The French scientists beat the previous record in both complexity and time, solving their 240-digit problem in less time than the 232-digit team took. Even this giant number, with a cryptographic key 795 bits long, is just over a third of the 2048-bit encryption most computers use. But it’s easy to see why cryptography is a race to stay ahead of the very computers that can both run these algorithms and break them given enough time.
