20-year-old MIT LCS35 Time Capsule Crypto-Puzzle solved

[Mark Rose]

This week MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) announced that a 20-year-old cryptographic puzzle was just solved by a self-taught programmer from Belgium, 15 years earlier than MIT scientists expected.

Bernard Fabrot spent the last three and a half years computing the solution to a puzzle first announced by MIT researchers in 1999.

https://www.csail.mit.edu/news/progr...graphic-puzzle

https://people.csail.mit.edu/rivest/...escription.txt

[R. Gerbicz]

"Bernard Fabrot spent the last three and a half years computing the solution to a puzzle first announced by MIT researchers in 1999.
..
The puzzle essentially involves doing roughly 80 trillion successive squarings of a starting number
..
Fabrot used a simple Intel Core i7-6700 found in consumer PCs, and computed the solution using the GNU Multiple Precision Arithmetic Library (GMP)."

I could get this in roughly 2.14 years on identical hardware, without going very deep we can use the faster mpz_powm with some intelligence, test:
I can complete 40 million iterations in 34 seconds. Do the math.

Read n=6314466083072888893799357126131292332363298818330841375588990772701957128924885547308446055753206513618346628848948088663500368480396588171361987660521897267810162280557475393838308261759713218926668611776954526391570120690939973680089721274464666423319187806830552067951253070082020241246233982410737753705127344494169501180975241890667963858754856319805507273709904397119733614666701543905360152543373982524579313575317653646331989064651402133985265800341991903982192844710212464887459388853582070318084289023209710907032396934919962778995323320184064522476463966355937367009369212758092086293198727008292431243681 has 2046 bits.
ans=4994097331495993759590792520652782896298040702842052804596091316575363414862676472297324459047461969855851762208911221321241374084825500814598324057817295157460163428748617431743371535373584519311479667686627715728864057273036107427545351441992333703764148710086798963155916759426741193579376396522818496357335032139598670494577520161356987154136310419315797156777208723685881823376284494131513590136899083068033919977865483124290662185228944009736543594763905898717659641198560483737149541481094888019426062490884384838074953205628739379413727850315986194387378032781404281175230300985834217585463046424665894367379
done 40000000 iterations in time=44 sec.
ans=4994097331495993759590792520652782896298040702842052804596091316575363414862676472297324459047461969855851762208911221321241374084825500814598324057817295157460163428748617431743371535373584519311479667686627715728864057273036107427545351441992333703764148710086798963155916759426741193579376396522818496357335032139598670494577520161356987154136310419315797156777208723685881823376284494131513590136899083068033919977865483124290662185228944009736543594763905898717659641198560483737149541481094888019426062490884384838074953205628739379413727850315986194387378032781404281175230300985834217585463046424665894367379
done 40000000 iterations in time=34 sec.

[R. Gerbicz]

Originally Posted by Mark Rose

https://people.csail.mit.edu/rivest/...escription.txt

"An interesting question is how to protect such a computation from
errors. If you have an error in year 3 that goes undetected, you may
waste the next 32 years of computing. Adi Shamir has proposed a slick
means of checking your computation as you go, as follows. Pick a
small (50-bit) prime c, and perform the computation modulo cn rather
than just modulo n. You can check the result modulo c whenever you
like; this should be a extremely effective check on the computation
modulo n as well."

Here I'd use the extremely cheap Gerbicz error checking.

[ewmayer]

Originally Posted by R. Gerbicz

Here I'd use the extremely cheap Gerbicz error checking.

Shamir's trick is fine as far as computing w.r.to general moduli goes, but yes, when are working with special-form moduli using fast DWT-based transform arithmetic, we now have better tools thanks to our local experts. :)

(I've just begun implementing your check for Mlucas v19.)

[axn]

Originally Posted by ewmayer

Shamir's trick is fine as far as computing w.r.to general moduli goes, but yes, when are working with special-form moduli using fast DWT-based transform arithmetic, we now have better tools thanks to our local experts. :)

Actually, the GEC's applicability is based on the form of the exponent. In this case the exponent is 2^x, so the computation is just a series of squarings, which means GEC is applicable regardless of the modulus. Would that be faster than Shamir's trick? I would think so -- what's the overhead for GEC if we choose L=10^5 (so a GEC every 10^10 iterations), about 0.001% ?

[R. Gerbicz]

Originally Posted by axn

GEC is applicable regardless of the modulus. Would that be faster than Shamir's trick? I would think so -- what's the overhead for GEC if we choose L=10^5 (so a GEC every 10^10 iterations), about 0.001% ?

Actually the Shamir's trick could be even cheaper (and still weaker), but only in that case if you are still
not using more limbs at modular squarings for (c*n). And this is unlikely with the large proposed c~50 bits prime,
and with the 2046 bits n (yeah it hasn't got 2048 bits).

That overhead is 2/L, so 0.002%. (assuming that mulmod and squaremod takes the same time).

ps. you can call it Shamir's trick but I'm almost sure that it was very well known in 1999.

[Mysticial]

How did Rivest generate the puzzle parameters? Even if you knew the two factors of n, a CRT construction of each factor would only save you a factor of maybe 2.

Clearly I'm missing something very important.

[axn]

Originally Posted by Mysticial

How did Rivest generate the puzzle parameters? Even if you knew the two factors of n, a CRT construction of each factor would only save you a factor of maybe 2.

Clearly I'm missing something very important.

a^b mod c = a^(b mod eulerphi(c)) mod c

if we know the factors of c, we can compute eulerphi(c) and thus reduce the large exponent b to a much smaller size. This takes milliseconds.

[Mysticial]

Originally Posted by axn

a^b mod c = a^(b mod eulerphi(c)) mod c

if we know the factors of c, we can compute eulerphi(c) and thus reduce the large exponent b to a much smaller size. This takes milliseconds.

Ahh.... That's neat.

[TacticalCoder]

Originally Posted by R. Gerbicz

I could get this in roughly 2.14 years on identical hardware, without going very deep we can use the faster mpz_powm with some intelligence, test:
I can complete 40 million iterations in 34 seconds

Hi there, I'm the one who found the solution. I tried your code on my Core i7-6700 and I do not get 34 seconds for the 40 million iterations: I get 44 seconds, not 34 seconds.


I tried with two GMP versions (one coming stock with Debian and one compiled from source) and I get 44 seconds for these 40 million iterations in both cases.


My CPU is a Core i7-6700: it is not the K version. It turbo-boosts to 3.9 Ghz when only one core is used.


I did this on my everyday workstation so at times more cores were used and hence my 6700 wouldn't turbo boost at 3.9 Ghz.


Did you try this on a 6700 or 6700 K?


It's a nice speedup you got there that said.


EDIT: typo. I replaced one of the "7600" by "6700".

EDIT 2: on my Core i7-6700 using R. Gerbicz' code I get about 910k sq/s. Simon Peffer's team's FPGA (a Xilinx vu9p) is getting about 15M sq/s (they'll have the solution by the 11th of May). There's a third team which is actually building an ASIC and they're using a FPGA to validate their ASIC design. Ballpark estimation from what I understood reading the emails: 10x improvement compared to the FPGA. So the ASIC team should have hardware solving this in a matter of days (as of opposed to 2 years' ish using good code and a fast machine).


EDIT 3: I'm neither a cryptographer nor a number cruncher. I just happened to realize upon reading the problem and doing a few tests that it was possible to solve this before 2034 ; )

[bsquared]

Originally Posted by TacticalCoder

EDIT 3: I'm neither a cryptographer nor a number cruncher. I just happened to realize upon reading the problem and doing a few tests that it was possible to solve this before 2034 ; )

Bravo for that realization and your tenacity, and welcome to the forum!