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: 4, Interesting) by FatPhil on Tuesday April 30 2019, @03:19PM (1 child)

    by FatPhil (863) <pc-soylentNO@SPAMasdf.fi> on Tuesday April 30 2019, @03:19PM (#836720) Homepage
    It matters that crypto experts, who are called on to give forward security estimates (statements of the form "an X-bit EC signing key will remain unforgeable by serious attacks from adversaries that can fab custom ASICs for Y years, so should only be used in lower security contexts, and not for more than Z years"), can be out by such a large factor.

    And I mean a *huge* factor.

    His model was almost certainly exponential, and almost certainly extrapolatory from what was seen during the 90s - therefore a doubling of power in the average person's hands at least every 2 years. In which case he presumed it would take 7 more "Moore" doublings - 100 times the grunt it actually took.

    And a single CPU is a terrible solution to this problem. A custom dumb-as-fuck-but-highly-parallelised bignum library running on a GPU would almost certainly have been way faster. (Maybe GMP used GPUs now, I'm not sure, I'm out of that scene nowadays.) This job is a job that *literally* only requires multipliers, and that's what GPUs are. Then again, not sure if that CPU has AVX, that gives pretty massive parallelisation.

    Anyway, Rivest kinda fucked up on this one.

    Start taking all those other security estimates with larger pinches of salt. (Others are holding strong though, there's good science behind a lot of them. Maybe Ron must have just dropped a few zeroes somewhere - but he has deviated from what others have predicted a few other times.)
    --
    Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
    Starting Score:    1  point
    Moderation   +2  
       Interesting=2, Total=2
    Extra 'Interesting' Modifier   0  
    Karma-Bonus Modifier   +1  

    Total Score:   4  
  • (Score: 2, Funny) by Anonymous Coward on Tuesday April 30 2019, @09:42PM

    by Anonymous Coward on Tuesday April 30 2019, @09:42PM (#836894)

    You don't understand statistics. Rivest said it would take an average of 35 years to solve, which means some people will solve it in 3 years and some in 67 years. The average is 35 years. I know math is fun, but leave the crypto to experts.