Suppose I capture encrypted data that I want to decrypt. Could I use a server farm to decrypt? For argument's sake, let's say that I'm a bad actor who produces malware. I've infected around 10,000 computers and smartphones with my malware, which runs in the background and can be used to make someone else's machine run calculations for me.

I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have an array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the workload of hacking this encrypted data to get through it in about 37 days? Why or why not?
I've gotten access to some encrypted data that I'm not supposed to have. It's heavily encrypted with an asymmetric cipher, and it will theoretically take 1,000 years to crack! However, I have my array of 10,000 computers. Assuming I can use the machines to their full extent (the users are too stupid to think that anything is wrong), could I feasibly distribute the work load of hacking this encrypted data to get through it in about 37 days? Why or why not?


The answer depends entirely on what cryptanalytic problem you're hoping to solve.

Worst case: No.  For example, if you have to compute $2^{2^t} \bmod pq$ without knowing $p$ or $q$ (large random primes of sizes beyond the reach of ECM or NFS) where $t$ is very large, throwing more computers at it doesn't help (without a novel cryptanalytic breakthrough); only making the computer itself run faster—e.g., by designing an ASIC that computes it and running it at a high clock rate cooled with liquid nitrogen—will give you an answer faster.

This is because we don't know of any algorithm to compute $2^{2^t} \bmod pq$ other than starting with $x_0 = 2$ and then computing $x_i = {x_{i-1}}^2 \bmod pq$ sequentially $t$ times: except for vectorization attainable in the squaring operation, parallelism doesn't help.

Best case: Yes.  For example, if you have a password hash and you want to find a password among a large space that a single computer can search in 1000 years to search, and if you have 10 000 you can afford to run, then sure, you can divide the space into about 10 000 subspaces—for instance, all those passwords starting with aaa, aab, aac, etc.—and get a factor of 10 000 speedup by searching the subspaces independently.

Actually, if you have a collection of password hashes and you're content to find one of the passwords, you can get an even better speedup than a factor of 10 000 by a multi-target attack.

In general, you are limited by Amdahl's law: if the fraction of time spent a sequential program that can be parallelized is $P$, then the best possible speedup attainable by parallelism is a factor of $S = 1/(1 - P)$; that is, if it previously took time $T$, then with parallelism it can take at best time $T/S$.

For computing $2^{2^t} \bmod pq$, $P$ is essentially 0—the problem is, as far as we know, inherently sequential (short of factoring $pq$), so $1/(1 - P) = 1$ meaning that parallelism doesn't change the time at all.

For searching among keys $k$ to find one matching a given hash $H(k)$, $P$ is essentially 1—the problem is embarrassingly parallelizable, so $1/(1 - P) = \infty$, meaning that the time can be made arbitrarily small with parallelism.

Will this matter for serious cryptography?  No.
Serious cryptosystems are generally chosen so that the cost of an attack is higher than you can ever afford.  For example, you will never find one of any plausible number of AES-256 keys by brute force, because the cost will far exceed $2^{128}$ evaluations of AES, which you don't have the pocket change to pay for the energy to do, no matter how much you parallelize it.  The same goes for finding any Curve25519 private key by the best known discrete logarithm algorithms given all the Curve25519 public keys in the world.

Note that even with Amdahl's law, trading parallelism for time doesn't necessarily reduce cost: the energy to power 365 computers for a day is about the same as the energy to power one computer for a year.  In some cases—like parallel rainbow tables or distinguished points in a multi-target attack—it does reduce cost!  But you're not guaranteed a cost reduction just by parallelizing a computation.  In other cases—like Grover's algorithm on a (hypothetical) quantum computer—parallelizing the computation may raise the cost!