Read more: “Unbreakable: Eight codes we can’t crack“
Nestled in the archives at the Massachusetts Institute of Technology is a metre-tall container made of lead. Its specific contents are a mystery to be revealed only when an accompanying encrypted message is solved. Only one man has the solution: , co-inventor of the RSA algorithm, one of the most ubiquitous methods for encrypting online communications.
To celebrate his lab’s 35th anniversary in 1999, Rivest devised inspired by his algorithm. Only when the solution is revealed, his rules state, may the lead bag be opened. He estimated it would take 35 years to solve – unless somebody could find a shortcut.
Advertisement
“It should take 35 years to solve the puzzle – unless somebody can find a shortcut”
Rivest’s coded message is hidden in 616 numbers. The method of encryption differs from an alphabet-based code, in which each letter matches another. It involves converting numbers into their binary form after solving a heinously difficult mathematical problem.
The problem that Rivest devised is simple to state: divide one number over 7.2 quadrillion digits long – 2279685186856218 – by a second number over 600 digits long. Then find the remainder.
The remainder, also over 600 digits long, is the “key” to unlocking the code. The codebreaker must convert it to binary form – a series of 1s and 0s – and compare it with a binary version of the 616 numbers of the original code. This comparison procedure is used to create a third string of binary: when the 1s and 0s match, that equals a 0; when they don’t, that’s a 1. Then you’re almost there: since binary can also represent the alphabet, the codebreaker would translate this third string of binary into the letters of the secret message.
So why would that take 35 years to solve? Rivest designed the initial division problem to be so big that it would take three decades of continuous computation to calculate – and that’s assuming that computing speed doubles roughly every two years, as predicted by Moore’s law. The calculation can only be done in sequential steps, says Rivest, making it invulnerable to distributed computer networks or the parallel processors used in supercomputers.
In theory though, there could be a shortcut. The second 600-plus-digit number in the calculation is the product of two large prime numbers. If these could be found, the computation could be completed in much less time, because a different mathematical technique could be applied.
Finding those factors would be no mean feat, however. The difficulty of factoring products of two large primes is the core mathematical fact underlying RSA encryption, a widespread method to allow two parties online to communicate securely without both of them needing a secret key. Rivest developed it in 1977 along with Adi Shamir and Len Adleman.
For example, if Alice wished to send Bob a secure message, she could ask him for a number and do a relatively simple and non-reversible calculation to encrypt the message. That number, the message’s “public key” is not secret. It is essentially the product of two large prime numbers. Only Bob can decrypt the message, because only he knows what the two primes are. The largest was achieved by a team led by Thorsten Kleinjung at the Swiss Federal Institute of Technology in Lausanne. It was 232 digits long, so it wasn’t close to the size of the 600-plus-digit number in Rivest’s puzzle.
Rivest told New Scientist that he thinks his original estimates of how long the puzzle would take may be too optimistic. “Computing power isn’t increasing quite as fast as predicted, in terms of ability to do fast sequential computations,” he says. Barring a breakthrough in the art of factoring, decrypting the message will likely take longer than expected.
Still, Rivest has underestimated codebreakers in the past. In 1977, he helped to design a puzzle for ‘s recreational mathematics column in Scientific American. The solution to the puzzle required factoring a 129-digit number. Nobody managed it at the time, but in 1991 a team of 600 volunteers did it in eight months, helping to reveal the message: “The Magic Words Are Squeamish Ossifrage.” (Ossifrage is the name of a type of vulture, and means “bone-breaker”.) Rivest and colleagues had estimated, based on the computing power of the time, that the task would take 40 quadrillion years.
Read previous article: “Unbreakable: Beale’s buried treasure“
Read next article: “Unbreakable: Kryptos, a monument to CIA secrecy“
