[lucb1e]

> (on one core, it's not parallelizable)

Why is that? From what I see on Wikipedia ("n is a specific 616-digit (or 2048-bit) integer that is the product of two large primes (which are not given)" sounds like a textbook RSA public key), it's an offline brute force challenge, a guessing game, so different computers (or cores) could independently take different slices of the guessing space. I will admit that prime factorization is one of my weak spots and I'll just resort to a few minutes of running pari-gp for that, since I know it uses some algorithm that is much better than brute force (it was orders of magnitude faster than alternatives for a CTF challenge involving a 512-bit RSA key).

Even if the factorization process' time spent is dominated by finding the next prime to try, rather than testing a prime for correctness for example, why couldn't you start anywhere in the 2048-bit space and find the next primes from there? Is there something you can use from the ciphertext that makes you need to start at a certain point and generate (single core) from there onwards? It sounds like the holy grail for key strengthening without memory trade-off options like scrypt and argon2 both struggle with

[adastra22]

From the actual problem description:

Note that the puzzle can be solved by performing t successive squarings modulo n, beginning with the value 2. That is, set

W(0) = 2

W(i+1) = (W(i) ^ 2) (mod n) for i=1, 2, ...

and compute W(t).

There is no known way to perform this computation more quickly than to perform the t squarings sequentially, unless the factorization of n is known.

[lucb1e]

Ah! Thanks. That immediately answers the second thing I was wondering about, since 2k RSA keys are still deemed safe (if barely / not for secrets that need to last a long time into the future)

[TacticalCoder]

In addition to what GP answered: note that I didn't crack anything. I just really did all the 79 trillion sequential computation needed to find the solution. That's the really need thing: you can encode the problem in a split second and yet decide how many sequential steps are needed to find the solution.

[adastra22]

Yeah the cost of breaking the time lock is presumably less than breaking the order of the group.