A 20-year old cryptographic puzzle — originally pegged to take 35 years to be completed — has finally been solved by a self-taught Belgian programmer. After 20 years, the puzzle designed by Ron Rivest has finally been completed by Bernard Fabrot, according to Wired.
Back in April 1999 a time capsule had been delivered to the acclaimed architect Frank Gehry — with instructions to incorporate it into a design for a building that would come to host MIT’s computer science and artificial intelligence lab.
The time capsule contains items contributed by legends such as Bill Gates and Tim Berners-Lee (the inventor of the world wide web). It was set to opened 35 years later, unless the cryptographic puzzle embedded into its design had been cracked.
Ron Rivest designed the puzzle for the time capsule, whose names also happens to lend the ‘R’ to ‘RSA’ which is arguably one of the most important cryptographic protocols created. RSA is one of the first public key cryptosystems that is widely utilised for secure data transmissions. Rivest didn’t design the puzzle to be complicated but rather just to take 35 years to be completed.
Bernard Fabrot solved it himself in just three and a half years – resulting in its completion 20 years after its inception.
The puzzle involved finding a number that is determined after running a squaring operation nearly 80 trillion times i.e. if you start with two, you’d get four and then square four to get 16. This process is then repeated nearly 80 trillion times.
Once this number has been deciphered, the puzzle solver must take the number and run a mathematical algorithm that uses a number given in the puzzle instructions. In doing so a congratulatory phrase is translated – which is the end of the puzzle.
The puzzle relies on sequential operations which, in short, means you cannot obtain the answer faster by running parallel computing. Due to the nature of the squaring process, each number must be done one step at a time. Using more computers or a supercomputer would not aid in speeding the process up.
A faster alternative
The puzzle had been coded in Java, though Fabrot realised it could be solved faster if he used the ‘GNU multiple precision arithmetic library’ – which is free software written in ‘C’ for completing precise arithmetic. He used a CPU (central processing unit) core on his computer to run the squaring operations on what was nearly a 24/7 basis, except for when he went away on holiday.
Fabrot’s timing couldn’t have been better because a group of computer scientists working on a project called ‘Cryptohage’ were using specialised hardware designed specifically to solve the puzzle.
Wired also reported that Rivest has openly admitted he had overestimated the difficulty of his puzzle because making predictions about technological advancements on a timescale so long is difficult.
Interested in reading more about crypto puzzles? Discover more about the yellow vest street art in Paris which contained a hidden Bitcoin puzzle.