Self-taught Belgian bloke cracks crypto conundrum that was supposed to be uncrackable until 2034

'It was easy, for some definition of easy,' solver tells El Reg


A cryptographic puzzle proposed two decades ago that involves roughly 80 trillion squarings has been cracked much earlier than expected – in just three and a half years.

We say cryptographic because it involves a verifiable delay function [PDF], a moderately hard cryptographic function.

The conundrum was set by Ronald Rivest in 1999, the R in RSA and a computer science professor at MIT's Computer Science and Artificial Intelligence Laboratory (MIT CSAIL). Here's how he described the problem:

To solve the puzzle, first compute w = 2^(2^t) (mod n). Then exclusive-or the result with z. (Right-justify the two strings first.) The result is the secret message (8 bits per character), including information that will allow you to factor n. (The extra information is a seed value b, such that 5^b (mod 2^1024) is just below a prime factor of n.)

And t, n, and z are given, and are very large numbers: t is 79685186856218, and the other two have 616 digits each.

In announcing his challenge, Rivest promised to reveal the contents of a time capsule around 2033 – some 70 years after the opening of MIT’s Artificial Intelligence Laboratory, which has been revamped to MIT CSAIL, or when the puzzle has been solved, whichever is sooner.

The contents of the time capsule is mostly a secret. Bill Gates contributed some paraphernalia from Microsoft’s ancient Altair BASIC programming language, Redmond’s first product developed in 1975. Other people that stashed stuff in the capsule, including Sir Tim Berners-Lee and Robert Metcalfe, both pioneers of the internet and computer networking.

On Monday, the puzzle was solved by Bernard Fabrot, a self-taught independent Java developer from Belgium. The time capsule will, thus, be cracked open by Rivest for the world to see on May 15, and the secret message revealed.

Big problems require smart solutions

The puzzle involves computing 22t (mod n), where n is a 2048-bit product of two prime numbers. You can try to solve the equation directly, but that would take too long. The mathematical enigma is also designed in a way that prevents the use of parallel computing to brute force the solution, since it’s impossible to compute it quickly without knowing the factorization of n. And it's a given you can't factorize n.

Instead, you can use successive squarings modulo n, starting with the number two. In other words, set W(0) = 2 W(i+1) = (W(i)2) (mod n) for i>0, and compute W(t), where t is the above big number. Here’s an example of the calculation, using much smaller numbers for demonstration purposes: n is 253 (11 * 23) and t is 10. Then we can compute:

2(21) = 22 = 4 (mod 253)

2(22) = 42 = 16 (mod 253)

2(23) = 162 = 3 (mod 253)

2(24) = 32 = 9 (mod 253)

2(25) = 92 = 81 (mod 253)

2(26) = 812 = 236 (mod 253)

2(27) = 2362 = 36 (mod 253)

2(28) = 362 = 31 (mod 253)

2(29) = 312 = 202 (mod 253)

w = 2(2t) = 2(210) = 2022 = 71 (mod 253)

A middle finger to Moore's Law

So, there you have it, 71 is the magic factorisation for the problem when n is 253 and t is 10. Now repeat this exercise with the actual numbers. Rivest predicted that the problem would be solved by 2034 judging by the amount of hefty compute required and the effect of Moore’s Law.

“The value of t was chosen to take into consideration the growth in computational power due to Moore's Law,” he wrote in setting the challenge.

“Based on the SEMATECH National Technology Roadmap for Semiconductors (1997 edition), we can expect internal chip speeds to increase by a factor of approximately 13 overall up to 2012, when the clock rates reach about 10GHz. After that improvements seem more difficult, but we estimate that another factor of five might be achievable by 2034. Thus, the overall rate of computation should go through approximately six doublings by 2034.”

He believed that a single computer would have to be running for 35 years continuously, where the hardware would have to be upgraded every year to the next fastest chip available. But he underestimated the progression of hardware, as the problem has been solved earlier than expected.

panel

Adi Shamir visa snub: US govt slammed after the S in RSA blocked from his own RSA conf

READ MORE

Fabrot wrote the equation in a few lines of C code and called upon the GNU Multiple Precision Arithmetic Library, a free mathematical software library to run the computation over 79 trillion times. He used a bog standard PC with an Intel Core i7-6700 processor, and took about three and a half years to finally complete over 79 trillion calculations.

“The computation in itself is 'easy' for some definition of easy: it is 'just' 79 trillion times the same operations,” Fabrot told El Reg. “So the code for a software based approach is very small. But I think it's not easy to have the patience to run such a computation for 3 and a half years. It requires some discipline to relaunch the computation, to follow the progress, to not just give up.”

A company called Supranational, led by CEO Simon Peffers, meanwhile, is on course to crack the puzzle in just 61 days. Peffers and the gang, who were unaware of Fabrot's efforts, took a different approach, preferring to crank out the numbers using a squaring algorithm optimized for a Xilinx VU9P chip, an FPGA.

“Basically, we optimized circuits for an FPGA toward low latency which allows us to perform each individual squaring operation much faster than a general purpose CPU could do,” Peffers told The Register. “Between the algorithmic improvements and the specialized hardware it is about 10x faster versus a software approach.” ®

Similar topics


Other stories you might like

  • A peek into Gigabyte's GPU Arm for AI, HPC shops
    High-performance platform choices are going beyond the ubiquitous x86 standard

    Arm-based servers continue to gain momentum with Gigabyte Technology introducing a system based on Ampere's Altra processors paired with Nvidia A100 GPUs, aimed at demanding workloads such as AI training and high-performance compute (HPC) applications.

    The G492-PD0 runs either an Ampere Altra or Altra Max processor, the latter delivering 128 64-bit cores that are compatible with the Armv8.2 architecture.

    It supports 16 DDR4 DIMM slots, which would be enough space for up to 4TB of memory if all slots were filled with 256GB memory modules. The chassis also has space for no fewer than eight Nvidia A100 GPUs, which would make for a costly but very powerful system for those workloads that benefit from GPU acceleration.

    Continue reading
  • GitLab version 15 goes big on visibility and observability
    GitOps fans can take a spin on the free tier for pull-based deployment

    One-stop DevOps shop GitLab has announced version 15 of its platform, hot on the heels of pull-based GitOps turning up on the platform's free tier.

    Version 15.0 marks the arrival of GitLab's next major iteration and attention this time around has turned to visibility and observability – hardly surprising considering the acquisition of OpsTrace as 2021 drew to a close, as well as workflow automation, security and compliance.

    GitLab puts out monthly releases –  hitting 15.1 on June 22 –  and we spoke to the company's senior director of Product, Kenny Johnston, at the recent Kubecon EU event, about what will be added to version 15 as time goes by. During a chat with the company's senior director of Product, Kenny Johnston, at the recent Kubecon EU event, The Register was told that this was more where dollars were being invested into the product.

    Continue reading
  • To multicloud, or not: Former PayPal head of engineering weighs in
    Not everyone needs it, but those who do need to consider 3 things, says Asim Razzaq

    The push is on to get every enterprise thinking they're missing out on the next big thing if they don't adopt a multicloud strategy.

    That shove in the multicloud direction appears to be working. More than 75 percent of businesses are now using multiple cloud providers, according to Gartner. That includes some big companies, like Boeing, which recently chose to spread its bets across AWS, Google Cloud and Azure as it continues to eliminate old legacy systems. 

    There are plenty of reasons to choose to go with multiple cloud providers, but Asim Razzaq, CEO and founder at cloud cost management company Yotascale, told The Register that choosing whether or not to invest in a multicloud architecture all comes down to three things: How many different compute needs a business has, budget, and the need for redundancy. 

    Continue reading

Biting the hand that feeds IT © 1998–2022