The way mathematics continues to break out new advances into the way we understand our world and work with technology is astounding. There’s always something new being done each day and I’d argue that maths is an important foundation for anyone to build on, more so than language because you can always learn that later – having a good grasp of maths is crucial to succeed in any industry today. Today a new world record was broken with the discovery of the worlds largest prime number, standing at 17 million digits long. Not only is it amazing that we can go that far, it means a whole lot of trouble for encryption standards.
To get to the world’s largest prime number the University of Central Missouri’s Dr. Curtis Cooper ran a new search through the GIMPS system (Great Internet Mersenne Prime Search), which is dedicated to identify new Mersenne primes. Mersenne primes are prime numbers that can be expressed using a formula developed by Marin Mersenne, a French mathematician, in 1636. Mersenne primes usually are also associated with perfect numbers, which is why prime numbers are the basis of the maths behind cryptography.
When you’re breaking encryption schemes, usually you’re looking for a prime number or the base prime that the scheme uses for hashing, determining the period and any other algorithms it might use to protect data. Having all the known prime numbers on hand makes this much easier to crack, since you can brute-force an encrypted file or software that uses prime or Mersenne numbers until you land on the right number to decrypt its contents. Files and software that use very, very strong encryption schemes usually also use higher prime numbers in order to increase the difficulty when attempting to crack it, which is why some schemes also use Mersenne primes and the more recently-developed Mersenne Twist to randomise things up a little. The Mersenne Twist is what’s credited to help keep the Playstation 3 virtually unhackable with today’s technology.
With that out of the way though, reaching this new prime took Cooper 39 days to reach and verify that it was indeed a Mersenne prime. GIMPS, however, is a distributed system much like Folding@Home, so its not that powerful. Running the same checks on an optimised system using a Nvidia card took 3.6 days, a Intel Core i7 (model number not mentioned) took 4.5 days and a comparitively long six days on a 32-core Xeon/Opteron server. From the results, two things are of interest.
First, the fact that a single Nvidia GPU using CUDA verified the number in just over three days means that in the future, we’ll see more of CUDA and OpenCL being used to perfect and break advanced encryption schemes. Running brute force attacks in parallel is perfectly suited to the GPU and given that we already know over 1.5 million prime numbers and 48 Mersenne ones, we’re nearing the stage where advanced encryption schemes will become as weak as WEP. As long as Nvidia and AMD make GPUs capable of such number crunching, no encryption scheme is completely safe, unless you’re Hugh Jackman masquerading as a hacker and have a protection scheme that could take over fifty years to break.
Secondly, we’ll have to base our encryption schemes on something completely different once it becomes weak. We might have to figure biometrics into the picture as DNA can have billions and billions of combinations to choose from. Aside from the fact that we can make encryption schemes that draw in prime numbers from a pool of billions, DNA does all the hard work by creating a completely random data set to use in the encryption. Your unique DNA footprint might well become the replacement for the digital signature in the future.
That’s a very far away for now though, but its worth thinking about. Just as IPv4 addresses ran out over time, so will our ability to mask data behind randomised encryption performed on computers.
Mind boggling, ain’t it?
Discuss this in the forums: Linky