Hacker News new | past | comments | ask | show | jobs | submit login
Belgian programmer solves MIT’s 20-year-old time capsule cryptographic puzzle (mit.edu)
698 points by MrXOR on Apr 29, 2019 | hide | past | web | favorite | 118 comments

That'd be me (fellow HNer and belgian programmer)... Very happy to see this upvoted up to HN's frontpage! Any question welcome but I cannot post the solution until the time-capsule opening ceremony on the 15th of May : )

EDIT: WIRED article just in. Haven't read it yet. Link if anyone is interested: https://www.wired.com/story/a-programmer-solved-a-20-year-ol...

EDIT2: forgot to tell but the mining pool Antpool posted a message in the block header / coinbase data of Bitcoin's block 573138 saying "Congrats Bernard Fabrot for solving LCS35!". My brother tried to time this with the press release which was supposed to come out on friday but then the press release got pushed back to today/monday. So yeah, coinbase data of block 573 138 is kinda very cool (it requires cooperation of a mining pool because it's not just in a transaction but in a block). TYVM to the everybody at Antpool! Big thanks for that : )

>Although Rivest initially released the puzzle’s code in Java, Fabrot realized it could be solved faster if he used the GNU Multiple Precision Arithmetic Library, free software written in C for doing “precise arithmetic.” So Fabrot dedicated one of the CPU cores on his home desktop computer to running squaring operations in an attempt to solve the puzzle. He says his computer was running the operation 24/7, except when he would have to leave on vacation or there was a power outage.

It seems as if your 2014 comment hinted at this project. Applause for keeping this tight lipped for those years.

2014 comment: >Java is quite fast compared to most languages but for some things it is still terribly slow compared to C / C++. I had to do some big integers crunching lately and tried: Java, Go, Go with GMP, C (GMP) and Haskell (using GMP under the hood). Eventually I went for good old C with the latest GMP version for it was the fastest for my use case (with Haskell and Go with GMP coming close but still not as fast as C). Java was, for the computation I needed to do... Eight times slower than C! I know I was hitting a edge case for a very specific kind of computation but still. [0]

[0]: https://news.ycombinator.com/item?id=7979006

Just want to add that GMP is not "C". The critical parts are written in assembly. It's not really possible to do fast multiple-precision arithmetic in C. You need direct access to add with carry instructions and the like.

Yes, access to hardware intrinsics is what can really accelerate arithmetic - C makes this pretty easy though.

As an aside, .NET Core 3.0 will deliver access to intrinsics - not sure if Java or any other managed platform already has this?

Your nick sounds familiar. "richtea" I'd say I remember but no idea from where.

Yeah I'm sorry that my comment from late 2014 gave that false impression that I said GMP was written in C. What I meant was that it was, when I did the testing, slightly faster to call GMP from C than from Haskell, Clojure, Java. I remember I tried all these back then and calling GMP for C was a bit more efficient. Now I know there are now ways to call libs like this from Java without paying the old foreign function call penalty: but I didn't know about that in 2014. So I called GMP from C because it was faster. Out of memory I'd have said GMP was C with inline assembly but I may be wrong ; )

Most of it is just straight up assembly. I don't think there's much inline assembly because that's hard to maintain for multiple platforms.

Rich Tea is a British biscuit. Maybe that's why you remember it?

> Bernard Fabrot spent the last three and a half years computing the solution to a puzzle

TacticalCoder last HN comment is from Dec 5, 2015. Checks out.

Kudos to you, well done!

I actually thought this might get posted to HN, so I went through a lot of pain to find back a way to get my HN login back (basically had no access to the email with which I opened an account here: I had to dive deep down in some Google Suite tied to a domain name to find a way into the user account and eventually reset my HN password). I'm glad I did in time and didn't miss this thread!

Could have used the world's best 2fa. "I can prove my identity because I have the answer to LCS35".

Pretty sure @dang would have accepted that!

Well, you sure seems like the kind of guy who will go through a lot of pain to get quick results.

Was this a side project? did it require much attention after the initial setup?

> Was this a side project? did it require much attention after the initial setup?

Totally a side project.

It hardly required any attention: just making sure the computation was running and making sure to backup the intermediate results once in a while (I had backups everywhere of the intermediate results: remote servers, USB keys, DVD, other computers at home, email, etc.).

I only needed to do a few tiny steps once I found the secret message (which contains a number which allows to compute one of the two prime numbers).

Did you knew for certain that your program will solve the puzzle at some time? Did you have an estimation of the date?

> Did you knew for certain that your program will solve the puzzle at some time?

The description of the problem itself explains a way to verify that intermediate results are correct.

> Did you have an estimation of the date?

Yes and that one is easy: I wrote a little piece of code (in Clojure, whatever, it's unrelated to finding the solution) which would check at which intermediate result the computation was and then compute an "ETA".

Fun story: I'd regularly send my brother something like this...

{ :time-left-in-years 1.239341704718417 :eta "1 year 2 month(s) 26 day(s)" :percentage-done 0.6284244211583109 }

(that's an actual estimate I found in my old emails)

: )

> TacticalCoder last HN comment is from Dec 5, 2015. Checks out.

I didn't realize... Your comment is actually extremely funny: I love it : )

Yeah, it's more or less when I started computing that. This is hilarious.

I just want to be a part of this thread. Congrats :)

Whoa, are you the Bernard Fabrot that wrote intro to Linux books in the late '90s early '00s (https://www.amazon.com/Bernard-Fabrot/e/B004N6XBQC/ref=ntt_d...)? If yes, I have to say thank you very much — I owe you my career!

And fun fact: that (french) book was actually typeset in LaTeX but I had to fight big times with my published/editor so that they'd accept LaTeX as they wanted me to typeset it using QuarkXPress. I knew how to use Quark XPress but I wanted that book to be typeset from Linux, with LaTeX. And eventually they accepted ^ ^

That's interesting. The fun fact is nobody uses QuarkXpress anymore (almost everyone in the design world switched to Indesign) while LaTeX ... is eternal. So wise choice.

That'd be me too!

I'd love to hear more about it: you can email me bernard @ fabrot dot com

Hi Bernard. Can you shed some light on why Rivest's prediction that this puzzle would take 35 years of computation was so wildly off? In the paper he predicts that clock speeds would reach 10Ghz by 2012, he also predicts another 5 fold speed improvement by 2034. I am not sure what the actual technological improvements have been since 1999 but it seems our processors are way below his predictions of where we would be in 2012, let alone 2034. He states:

> "We estimate that the puzzle will require 35 years of continuous computation to solve, with the computer being replaced every year by the next fastest model available. Most of the work will really be done in the last few years, however."

So how were you able to perform a calculation that should take 35 years in just 4? Where did Rivest get his assumptions wrong?

You still need the same amount of iterations (79 685 186 856 218)[1] to resolve the problem but it's now faster because

SIMD instructions[2] lowered the amount of cpu cycles needed per operation.

Novel algorithms[3] lowered the amount of operations needed per iteration.

[1] https://people.csail.mit.edu/rivest/lcs35-puzzle-description... (short description at the bottom).

[2] https://en.wikipedia.org/wiki/SIMD

[3] https://gmplib.org/manual/Algorithms.html

The problem appears to be sequential so how would SIMD help? Also what advances in squatting algorithms have there been specifically? None of the links you have provided appear relevant

The numbers involved are quite large. They don't fit into a single computer word.

The problem is designed so that iterations have to be sequential, but a single iteration can use parallelism.

I see this problem as simultaneously a cryptographic challenge and a DevOps one.

So mine isn't a cryptographic question, but I'd love to know what steps you took to ensure integrity and uptime of your consumer i7 hardware, and capture of each partial step of the solution, while you ran your algorithm.

EDIT: also, congratulations! (How did I leave that out!?)

I'm no cryptographer so it's good news you don't have any cryptographic question ; )

I basically used my everyday workstation. There were 79 trillions operations to be made and I'd save the intermediate result every 1 billion result (so approximately every 22 minutes I'd save a result).

The computation cannot be parallelized and the i7 I was using has four cores. So basically instead of turning it every night off I'd simply leave it running 24/7.

I'd simply backup the files with the intermediate results once in a while. I rebooted the computer about 50 times in 4 years and during those 4 years during about 3 and half years it was computing towards the solution.

But I coded (totally unrelated things), compiled things from source, browsed the web, did my email, etc. from the very workstation which computed the solution.

The computation is easy to relaunch from any intermediate step.

Thanks for the congrats!

Wow, this is awesome! Great job computing it.

This reminds me of a time during college a professor gave us an extra credit assignment to essentially find prime factoring large numbers (classic problem). I had come up with a pretty bad solution, but thought it might just finish in time for the deal line if I left it running all week. Of course a transformer blew up the day before the deadline, and I never knew... chances are my program would have never terminated :P

That's amazing dedication. Congrats. Did your power bill increase noticably?

No it really didn't. I think I mentioned here elsewhere in a comment but I use an Intel Core-i7 6700 "non K": so the version that is not meant to be overclocked and which Intel rates as having a max TDP of 65W. And this would be with the four cores running. I don't know the TDP / power consumption when it's turbo-boosting at 3.9 or 4.0 Ghz (when one or two cores are at full speed on the 6700, it goes from 3.4 to 3.9 or 4.0 on these cores).

Basically I like my workstation to be quiet. Really very quiet: as in I can only hear it if I put my ear on the tower. So I never have ultra power hungry CPUs. I don't game so no GPU besides the integrated one. A M.2 SSD which consumes next to nothing.

Power bill probably did increase a bit but honestly it was lost in the noise: I definitely didn't notice anything : )

> The computation cannot be parallelized

Is there a proof of this somewhere? Operations that seem vaguely similar, like doubling repeatedly, can be easy to "parallelize".

The puzzle is based on a paper from 1996 by Rivest, Shamir and Wagner: https://people.csail.mit.edu/rivest/pubs/RSW96.pdf

Each step depends on the result of the previous step. I don't know of any claim that the crypto/maths behind the paper do not hold.

You can use a FPGA or build an ASIC: but as far as I know as long as the crypo in this paper hold, it's not parallelizable.

> Each step depends on the result of the previous step.

But this doesn't mean anything. If I said to take a number and add 1 eighty trillion times, each step would depend on the result of the previous step, but obviously it would be unnecessary to actually compute each step.

The reason this isn't the same is that addition is associative, so you can parallelize it like this: `((1+1)+1)+1 = (1+1)+(1+1)`.

A fast way to calculate something like `g^x` for some large `x` is to iteratively square:

and the puzzle is designed so that `i` is large (`79_685_186_856_218`)

Of course, this doesn't prove that computing `g^x` is sequential, but it does show why it is different than computing `1+1+...+1`.

Doesn't this suggest that computing 2^i is just as hard?

You can compute g^(2^i) by just multiplying g's in the same way that you can compute 2^i by adding 1s, and multiplication is as associative as addition is. Specifying that you want g^(2^i) rather than g^k for some arbitrary k looks like a way of ensuring that a partial product computed in parallel (say, g^3) will be of nearly no value, because every partial product that helps compute the total will already be produced by the single agent doing squares.

So why compute g^(2^i) rather than just 2^i? Is 2^i in fact hard to compute? (In binary representation, it certainly isn't, but maybe 3^i is?)

Using the doubling trick you can compute `2^i` in `log i` time, so you can compute `2^(2^i)` in `log 2^i = i` time. Let `i` be big enough, and you've got a "difficult" problem.'

Read the paper. It tells you why they think it's better than that. And I think that has stood so far.

> Read the paper. It tells you why they think it's better than that.

OK, I read the paper.

This is the entire discussion of the inherent difficulty of repeated squaring:

> More importantly, repeated squaring seems to be an "intrinsically sequential" process. We know of no obvious way to parallelize it to any large degree. (A small amount of parallelization may be possible within each squaring.) Having many computers is no better than having one. (But having one fast computer is better than one slow one.) The degree of variation in how long it might take to solve the puzzle depends on the variation in the speed of single computers, and not on one's total budget.

I see two problems here:

(1) This is a purely conclusory argument, suggesting that a better response would have been a simple "no, there's no proof".

(2) This does not even attempt to address the question I posed, which was whether it is necessary to compute the intermediate results in order to compute the final result.

In fact, we know that the intermediate results are not necessary to compute the final result, because that is how the message gets enciphered in the first place. It can be done by factoring the modulus, and obviously there is no proof that that is difficult to do.

But beyond that, it also isn't immediately obvious that it must necessarily be impossible to compute the final result directly by means that don't require factoring the modulus. It is possible that somewhere in the literature on Blum Blum Shub this question has been analyzed, but that goes a bit beyond your suggestion to "read the paper".

So, I'm stumped. Tell me what you saw in the paper that you thought would answer my question?

> In fact, we know that the intermediate results are not necessary to compute the final result, because that is how the message gets enciphered in the first place. It can be done by factoring the modulus, and obviously there is no proof that that is difficult to do.

Well, there's no mathematical proof. But physicists and judges would accept that there's lots of money and fame to be made breaking eg RSA, so countless people have tried and keep trying, but haven't come up with much good so far.

The answer to your question is, "No, there is no proof."

This is similar to the answer to, "Is there any proof that RSA is uncrackable?"

The security is based upon the assumed hardness of certain mathematical problems.

I hate it when people think they know better than the experts. Do you really think that if they could have made it run in parallel they wouldn't have? Get off your high horse and solve it yourself if you're so smart.

Seems to me like a good-faith effort to understand. And respect for the experts isn't the same as unquestioningly accepting all of their assumptions.

As for the uptime it's a pretty reliable machine: I'm running the i7-6700 (non K, so non overclocked) version. Intel lists it at 65W max TDP but that'd be with all the cores at 100% I guess. It's a 3.4 Ghz CPU turbo-boosting when only one core is at 100% to 4.0 Ghz on that one core.

OS is Debian stretch: it's rock solid in my experience.

It was rebooted on average once a month (I switched country, there were black outs, I upgraded the OS, etc.) but there have been stretches where it was up for several months in a row, happily cranking!

Hi @TacticalCoder, One question!?

From Rivest-Shamir-Wagner's paper[1]:

“Solving the puzzle should be like having a baby: two women can’t have a baby in 4.5 months."

[1] https://people.csail.mit.edu/rivest/pubs/RSW96.pdf


first thanks a lot for posting this to HN!

Then: is there a question somewhere in your post which I missed? : )


This is very cool. Congratulations!

How did you beat Peffers' team? Did you simply start the computation sooner, or did you reach some insight that eluded them?

No Simon Peffers' team did something more impressive: they're using a FPGA. I simply started way earlier using consumer-grade hardware (a Core i7-6700 CPU).

But you made the correct decision on whether to start the computation immediately or to start by building a "more impressive" system. Maybe it was luck that you beat them, or maybe it wasn't, but either way several years out you made the correct engineering decision on how to solve a problem with finite resources. That's impressive.

For those who didn't read the Wired article:

"In mid-March, the group began to run an algorithm" ... "FPGA was about 10 times faster than a high-end commercial CPU running non-optimized software. Based on the chip’s computing efficiency" they "calculated that they would have the correct solution" "on the evening of May 10, just two months after they started the calculation. Yet when they reached out to MIT to let them know a solution was imminent, Rivest informed them that Fabrot had beaten them to the punch."

We read here that he started end of 2015! Rivest believed at the time he constructed the puzzle, almost 20 years ago, that he has constructed the puzzle that would keep the vault locked until 2034, based on his expectations then of the increase of the computing speed. Obviously, predicting the developments of 35 years is not so easy, and the single-CPU computer speeds did improve faster. Anyway...


It's actually the algorithmic improvements that were faster, if I read everything here and in the article right. Not the raw single-CPU computer speed per se.

> It's actually the algorithmic improvements that were faster

I’d really like to know about those! Any links?

Disagree. I'd choose to work with you first on a project, but until facing such a nice problem congrats!

No disrespect intended to that team. It's an impressive accomplishment, and they're the ones who can publish in a journal for all due academic credit.

However, it also depends on what you value. Sometimes for some problems crossing the finish line first is winning, or seems able to simply allow the worlds technical advances to compound faster than more novel approaches whose future utility is unknown.

During all those years one person stopped to think about the goal in the most optimal way and ask, what's really the simplest solution here? Is custom hardware the only practical way? Everyone was allowed to think about implementation costs.

In other words, the most impressive part is what was not done. Great work.

A real-life Tortoise and the Hare story! (In the sense that slow and steady progress won the day. I do not wish to imply that Peffers team has any of the negative qualities of the hare.)

Kinda: a friend told me exactly that the other day. But we then discussed it: technically the hare started first and then rested, which is not what Simon and his team did : )

Fellow HNer and fellow Belgian here. Congratulations! If you're ever around Leuven I'd love to buy you a beer and have a chat ;-)

Quite a few of us in here! I spend a lot of time in other countries so I'm not that often in Belgium but I'll make sure to contact you when I come around. We should exchange emails. You can email me at bernard at fabrot dot com !

Mail sent! (meeusdylan at protonmail dot com).

Yeah, always nice to see who you can run into on hackernews! I'm sure there's plently of us Belgians lurking on here :)

Hi, and belated congratulations!

Are you by any chance planning to release your source after the ceremony? It'd be really interesting to read some peak-efficiency GMP code as that's a library I've always been interested in.

Additionally, do you happen to know how much longer it could take to factor modulus n and then compute the value for 2^(2^t) using the methods described in the paper? i.e. instead of repeated squaring compute

  2^(2^t mod phi(n)) mod n

There is also a thread on reddit's r/technology https://www.reddit.com/r/technology/comments/bitha2/belgian_...

Well played! If only I had made my attempt earlier!

    AMD Phenom(tm) II X4 B50 Processor
    56.674783% (0x2912f5a00000 / 0x48792741a51a) ETA: 1 year 138 days (2020-09-18)

How much work was involved in the 3.5 years ? What tips would you say worked for you ? What do you think you do in your life that might have given you a leg up in cracking the puzzle ? (besides being intellectually inclined and adept)

> How much work was involved in the 3.5 years ?

Already answered somewhere but lost in this thread...

Hardly anything. Relaunching the computation after a black out or an OS reinstall or when I moved from one country to another : )

Also once in a while going ballistic with backups as to not lose x months / years of computations.

Then at the end doing as the puzzle says to do: xor to get the secret message. Get b from the secret message and do 5^b mod (2^1024) then find the first prime above the resulting number. Divide n by that first prime to get the second prime. This took no time.

> What do you think you do in your life that might have given you a leg up in cracking the puzzle ?

I don't know. It required finding it (mostly chance there), reading it and understanding how the parameters were set up, realizing that a solution could probably be found in some "reasonable" amount of time and then it required some dedication (and maybe a tiny of crazyness too) to run if for so long.

I clearly always liked optimization and learning new languages and trying libraries and whatnots: so as the solver was simple to implement I was easy to quickly try different languages / libraries. I kinda knew upon reading the puzzle that there was a good chance that it could be solved faster than expected.

But really it's like 10 or 12 lines of code. I spent some time doing performance tests but besides that it was just being patient?

I was clearly motivated by the idea that I could be the first one to find the solution to this puzzle. That one carrot worked wonderfully on me : )

> computed the solution using the GNU Multiple Precision Arithmetic Library (GMP).

Great job. Kudos.

Hey, congrats ! I like your display shown in the Wired article.. it looks very ergonomic ! Could you tell me what brand/model it is ? Thanks :-)

EDIT: got it, it's LG 38UC99-W.. thanks

Thanks, I was looking for the display specs as well :)

It completely makes my day that the solver is on HN.

Nice work man

Congratulations! Any ideas for the next challenge?

What was the ascii sentence result and what were the factorization instructions (presumably just a large prime factor of the result)?

It was decided that the solution would be kept secret until the 15th of May, when the time-capsule shall be opened.

As the problem states: there's a number allowing to factorize n. There's also a little message.

A dedicated ASIC based on MOS current mode logic (MCM) in normal 14nm should get at least 10x higher speed than that FPGA. You'd probably be thermal limited to, say 100 Adders in parallel working on partial products (full-width) clocked to 10~20 GHz (power is basically linear in frequency and a 1GHz adder consumes ~ 40 mW). That gives you a base multiplication speed of 0.5~1GHz and 40~80W power consumption. AFAIK their FPGA runs at ~65MHz.

Congratulations! I’m curious if a quantum algorithm could help with this, as the problem deals with factoring large numbers?

What are your thoughts on projecteuler.com?

I obviously love all the kind of algorithmic puzzle / challenges / competition.

I haven't done many from Project Euler but I did participate a lot in the "TopCoder" competition back when TopCoder started (that'd be many many years ago).

I think it's a great way to learn about algorithms or to learn a new programming language.



Congratulations!! This may cost me some karma bit it is definitely worth guessing!!

Is the answer.... 42? :)

In all seriousness, I hope that on May 16th you will post your efforts/solutions/other miscellanea somewhere, and will come back to HN and make a "Show" post for us all to admire and celebrate with you.

Celebration at the MIT on the 15th of May and it is public.

I don't have a blog (yet) but I do have a few things I'd like to write about (not just this puzzle) and share with other enthusiasts so I think I'll simply start a blog. But it won't be on the 16th: I'll need some time to come back home etc.

If you have time you could write it up in advance and publish it on the 15th. I say this because I think your post is more likely to be read by more people if you are able to publish it coinciding with the event. That way you can also share the link with anyone IRL that you meet at the ceremony who asks you for more details about it, and in turn it is more likely that some of said people share your post on social media, leading to even more people reading your post.

What was the question?

Hey, I know it's kind of off-topic, but I couldn't help noticing your OS. Are you using awesomewm/what's your setup! Also, what monitor is that?

Hi, no problem for me with the off-topicness: I said I'd gladly answer questions : )

As dsincl12 wrote it's indeed a 38": the LG 38UC99-W.

And you're correct, good catch: it's the Awesome WM running on Linux (Debian Stretch). For the geeky details: it's Awesome WM but with a patch I modified doing "useless but not useless" gaps. Basically it adds gaps between the top bar and between the windows, but it doesn't add gaps on the edge of the screen (which to me makes the more sense but YMMV).

So yeah a Core-i7 6700 / 16 GB of RAM / NVMe M.2 PCI-e 3.0 x4 SSD, which is my daily workstation (as I wrote elsewhere in this thread: I solved this on my everyday workstation).

I've got 12 virtual workspaces set up and my "main" one is in a three columns layout (with Emacs in the middle ;)

+1 for what monitor is that?

Looks like the one I have, an LG 38UC99-W.

I just tried to dig into the background of this, the original description is here:


I have a question and maybe someone can answer it: This indicates that knowledge of the factorization of the modulus n allows to do this calculation faster, which is likely how the designers of this puzzle calculated the result.

However it's not explained how that happens and how the factors of n help. I assume this may be someone related to RSA, as there you also are able to do something much faster if you know the factors of a combined modulus. However in RSA you're able to invert a modular exponentiation. Here you seem to be able to speedup many successive exponentiations.

Is there some clever way to translate these two problems into each other and thus use an RSA-like method?

(Update: I found this paper https://people.csail.mit.edu/rivest/pubs/RSW96.pdf which explains how to do the calculation on page 4, but is still lacking an explanation why. But I guess for people fluent in number theory it's probably somehow obvious.)

> I guess for people fluent in number theory it's probably somehow obvious

It's "obvious" to the people who are aware of how RSA works, and know that Rivest based his derivation of the puzzle on the properties on which RSA encryption also depends.

Note, Rivest is one of Rivest–Shamir–Adleman: "The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978."

See also:


In shortest and simplest, the "hardest" part is just that the numbers which have to be processed are huge and that nobody knows an algorithm which would avoid doing a lot of the calculations to factor such huge numbers. Then for Rivest as he created the "puzzle" the goal was just how to construct one special huge number which encrypts the message. Constructing all that is then by a clever design faster than solving. Those who try to solve the puzzle don't have the exact construction numbers Rives used, just the result which has to be attacked by "brute force" calculations. The intermediate results during that process aren't predictable faster than simply calculating them, but every next depends on the previous one.

But not everything related to RSA is mathematically rigorously proved, as you can see in the Wikipedia article.

It seems like no one has answered your question so I'll give it my best shot.

We want to find the value of 2^(2^t) mod n where n = pq. It's a well known number-theoretic fact that 2^phi(n) mod n = 1, where phi is the Euler totient function (https://en.wikipedia.org/wiki/Euler%27s_totient_function).

This theorem is called Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_theorem). For n = pq, phi(n) = (p-1)(q-1)

So if 2^phi(n) = 1, then 2^(2 * phi(n)) = 1 and 2^(3 * phi(n)) = 1 and so on, so we really only need to know the value of 2^t mod phi(n). We can compute this value in O(log(t)) operations via repeated squaring, and once we know this value (let's call it k), then we just need to compute 2^k mod n to finish, which again, can be done quickly using repeated squaring.

Here's a quick demo in python:

  $ python
  >>> p = 8721676787107355947610787701585837629266743108012786178142468507932506290346645194233003705268505408163930982434418938387386290453411395078603729114734341
  >>> q = 8903989072246145056499086678843460912573461209473391355874543630090691433843393509873230695095738299681258115825746186699033768361727241007153178256782969
  >>> n = p * q
  >>> phi = (p - 1)*(q - 1)
  >>> t = 1000
  >>> x = 2
  >>> for _ in range(t):
  ...     x = (x*x) % n
  >>> x
  >>> k = pow(2, t, phi)
  >>> y = pow(2, k, n)
  >>> y
  >>> x == y
The key here (as in the RSA cryptosystem) is that we have no way of computing phi(n) without knowing the factorization of n.

Wow, congrats! My computer has for the last 16 YEARS been trying to break RC5-72: http://stats.distributed.net/participant/phistory.php?projec...

Ah "Ron's Code 5". It's Ron Rivest too ofc!

Good you post this because I had no idea what I could keep my computer busy with now that LCS35 is solved ; )

Wait a minute, did the solution method amount to "do the straightforward thing using libgmp and then run it for 3 years straight?"

Precisely. And I did this on my everyday workstation, which I also used simultaneously for coding, browsing, emailing, etc.

Is that not epic? : )

Now I think it's fair to say that part of the solution also consisted in realizing that using a fast big integer library it was doable in three years something.

Since you were backing up the partial results, I assume this means you could load such a backup and continue from it if something happened to the running machine.

Does that mean that you could, if you wished, have switched to a different machine and just continued where you left off? E.g., could the Peffers team, if they knew about it, theoretically have taken your partial results and run them on their FPGA to obtain the final result a little bit faster than if would have been otherwise?

(Not suggesting this is in any way what you should have done. Just curious)

> Does that mean that you could, if you wished, have switched to a different machine and just continued where you left off?

Totally. It's even explained in the original problem description: the idea was that every year you'd switch to more efficient hardware, picking up the computation where you let it off, until Moore's law stopped applying.

I considered upgrading from my i7 6700 to a 8700-K overclocked for slightly faster clock speed (and maybe some instructions taking fewer cycles). It'd have saved some time.

I was going to ask how they would check if the answer is correct, because they too would need "35 years" to find it...

... but then I realized that N is a product of two primes, which Rivest knows, so he can take a shortcut and compute the answer faster. That is, the answer is known.

But this makes you wonder if factoring that N would've been a faster route to solving this puzzle. What do you guys think?

[1] https://people.csail.mit.edu/rivest/lcs35-puzzle-description...

That's why I love HackerNews, you can meet those type of interesting personalities and ask them questions right here!

Can you tell us a bit more about your self-taught background? What do you do for a living? How did you hear about the challenge?

I found the challenge by chance. It was so long ago I don't exactly remember when. Thought it was 2015 but an old comment of mine on HN seems to indicate I may have started looking into this back in 2014, when I was still using a core-i5 CPU : )

> Can you tell us a bit more about your self-taught background?

Sure... I started programming in BASIC at 11 years old on the most inconceivable setup ever: an Atari 2600, which was a gaming console (the infamous one which lead to the video industry crash of 1983 with a landfill filled with E.T. cartdridges). So how do you write BASIC on that at 11 years old? Well your mom offers you a "BASIC cartridge" which comes with a keyboard in two parts you plug in the joystick ports! (horrible experience but I do remember writing tiny programs drawing colored lines using that).

Then the Commodore C-64: more BASIC, some assembly using a "power cartrigde", mainly to modify (hack?) games. Then the Commodore Amiga: learning to write intros and demos. Then the PC (386, 486, and so on): writing a video game (finished but never published but it landed me my first job: long way too long story), writing more intros and demos (won a PC demo compo in Sweden). I'll blog one day (when I'll have a blog) about that PC / DOS video game which was running at 60 Hz on a 386 because it used a cool collision detection method I came up with (which as far as I know is unique and was pixel perfect even back then and was and still is particularly efficient). I still do have both the source and the binary for that game.

For the languages I mainly did BASIC then assembly (680x0 and 80x86), C with inline assembly, C++, Java... Then I stuck with Java for a very long time. Got a Sun Certified Java Programmer certification around 2000 (which makes me an oldtimer): only cert I ever got.

I cannot say I didn't do boring Java consultancy for even more boring companies/organizations. And thankfully once in a while a fun professional project ; )

Nowadays I'm still programming in Java as for my own projects I like to write proof of concepts using Clojure (and ClojureScript). And as I'm an Emacs (IntelliJ for Java though) user if of course waste a lot of time with elisp, hacking my Emacs config!

I hope you still love HN ; )

Given that processor technology has underperformed Moore's law since 1999, I'm surprised that Rivest underestimated the time needed to complete the challenge. I wonder how that happened.

From my completely noob understanding, the implementation of this particular operation of squaring has managed to outrun the law.

Ballpark latency numbers per 2048-bit modular multiplication:



ASIC—1ns (expected)

If you're a hardware engineer (or mathematician) interested is building an ultra-low latency ASIC, please email justin@ethereum.org

Source: https://twitter.com/drakefjustin/status/1123143447551053824

Context: https://www.youtube.com/watch?v=zqL_cMlPjOI

"Based on Moore’s law and how long it took to run the squaring operation in 1999, Rivest estimated that computing the answer to the puzzle should take approximately 35 years."

So how did Rivest create the puzzle back then in the first place, without taking 35 years to generate it?

The asymmetry of three things is essentially what secures of a lot of cryptography:

  1. multiplying two large prime numbers together (easy)
  2. Factoring the result without knowledge of those primes (extremely difficult)
  3. Factoring the result with knowledge of one of the primes (easy)
Those properties are essentially what make up the foundation of a lot of public key crypto.

For this puzzle, knowing the factorisation of n allowed a shortcut to quickly generate the puzzle, but without that factorisation it required squaring numbers 79,685,186,856,218 times sequentially so parallelism isn't a help.

The actual code to generate the puzzle was in the original puzzle description at https://people.csail.mit.edu/rivest/lcs35-puzzle-description... .

From a fellow Belgian : congratulations!

It's very inspiring to see a self-taught programmer achieve such an impressive result.

Any chance of the capsule ceremony being live streamed? Would be cool to follow.

Congrats! +32 represent! Which beer(s) did you drink to celebrate?

Wow quite a few belgian in here! Weirdly enough I'm not that big of a beer drinker but... Although I didn't celebrate finding the solution in any other way than doing a silly dance in front of my family I did celebrate the HN thread reaching 2nd place on the frontpage by drinking a Mort Subite / Lambic Kriek : )

OT: Can anyone be kind enough to link to the specific model of TacticalCoder's monitor setup as captured in this Wired photo [0]?


0: https://www.wired.com/story/a-programmer-solved-a-20-year-ol...

Looks like Massdrop addicted (keyb, mat, sad, maybe the whatch and monitor too?)

Ah no, I don't use Massdrop.

Keyboard is a Happy Hacking Keyboard Pro JP. Mat was a gift from my brother and I have no idea where it comes from. Monitor is a LG. Watch is a slightly fancy swiss mechanical diver's watch ; )

Aaah, living the Topre Life I see? Great to see these babies outside of the mech keyboard subreddit.

AhAhAh. However cool desktop! :)

What would be the off the self hardware (CPU) to use for this problem today? Still Intel, or AMD, or does ARM architecture do squaring fast? Or something else entirely, like GPU?

Can someone ELI5?


Hey All! Cryptophage team here (https://www.cryptophage.com). Feel free to ask any questions about our alternative approach to solving the puzzle that Bernard just cracked!


One questions: Solving this puzzle has any impact on Verifiable Delay Functions security (specially Chia's VDF[1])?

[1] https://github.com/Chia-Network/vdf-competition


Hey MrXOR! First off, thanks for posting this link to HN! Second, the VDF used here leverages RSA groups, while the Chia implementation uses Class groups. These two VDFs are compared here: https://crypto.stanford.edu/~dabo/pubs/papers/VDFsurvey.pdf. Both the VDFs are subject to hardware and algorithmic speedups which will not impact the security of their use as long as these are taken into account. If you are interested in learning more about VDFs I would recommend looking at this collaborative project by Ethereum and Filecoin: https://vdfresearch.org/.

Excuse me, Another question:

From [1]:

>> Cryptophage project solved it in 2 months.

What about ASICs (NSA's power and love!)? How long would it take? any estimation? 2 days? :-)

[1] https://www.cryptophage.com

We are currently investigating ASICs, but a rough estimation would be that they could be at least 10x faster, if not more (e.g. 6 days or less)

Hi there. Can you share some pointers to the alternate algorithm that was mentioned?

Thanks and congrats to you as well for reducing the calculation time!

The goal was to extract as much parallelism from a single squaring operation as possible using the available hardware resources. We used a Xilinx FPGA. There will be a paper detailing the exact algorithm in the coming weeks. In the interim, if you are interested in digging into code, you can find some of the primitives for the design here: https://github.com/supranational/primitives

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact