Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Tuesday April 30 2019, @12:38PM   Printer-friendly
from the how-many-watts-were-needed-to-compute-the-result? dept.

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.

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

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)

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 Rivest in setting the challenge.

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

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.


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 5, Insightful) by Nerdfest on Tuesday April 30 2019, @01:43PM

    by Nerdfest (80) on Tuesday April 30 2019, @01:43PM (#836673)

    Since he was smart enough to use the GNU Multiple Precision Arithmetic Library, I'd assume he's smart enough to use Linux or BSD.

    Starting Score:    1  point
    Moderation   +3  
       Insightful=2, Touché=1, Total=3
    Extra 'Insightful' Modifier   0  
    Karma-Bonus Modifier   +1  

    Total Score:   5