Something in Common

This challenge follows the pattern of an earlier puzzle by the same author, except without the specific explanation and instructions. It relies on the RSA common-factor attack to allow the solver to decrypt eight (out of 100) RSA ciphertexts which would otherwise be expected to be much too difficult to decrypt.

The reason that this works is that these RSA keys were generated in an improper way, not using properly random numbers, so that the eight weak keys' moduli share four prime factors. When prime factors are shared between RSA moduli, the shared factors can be factored quickly and easily using an algorithm for greatest-common-divisor (GCD), which is drastically faster than a straightforward factorization with no other information would be.

The details of how to do this are found in the explanation of the older puzzle. Basically, you can parse all hundred RSA moduli out of the PEM files, and then perform all of the pairwise GCD calculations of these moduli. (There are 99×100/2=4950 possible pairs to consider, but each GCD calculation takes a trivial amount of time with a library like gmp or using your own GCD implementation. If you write your own implementation, you'll want to use modulo instead of subtraction for an important speed-up!) Four of these pairs will give something other than 1 as the GCD; this "something in common" is always one of the primes used to generate both moduli in that pair. From this, you can reconstruct the private key that corresponds to those moduli.

The eight plaintexts that you can recover this way are all excerpts from old issues of EFF's EFFector newsletter. In fact, if you look at which old issues of EFFector they come from, they are

Volume 1, issue 12
Volume 2, issue 10
Volume 3, issue 7
Volume 4, issue 5
Volume 5, issue 15
Volume 6, issue 4
Volume 7, issue 12
Volume 8, issue 14

Volume 1, issue C
Volume 2, issue A
Volume 3, issue 7
Volume 4, issue 5
Volume 5, issue F
Volume 6, issue 4
Volume 7, issue C
Volume 8, issue E