- 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.