Msieve & Yafu - RSA Exponents and bruteforcing

Question

I am a layman in regards to the math behind RSA (and in general, relatively), and my goal is to bruteforce a large quantity of 512-bit RSA keys. Having searched around, I see that msieve, yafu, and an Amazon FaaS (Factoring as a Service) program are the main candidates, however, cracking the keys with Amazon would be impractical cost-wise, and the keys I would like to crack (for a long-shutdown videogame I'll specify, nothing malicious), have an exponent of 17.

In short, I would like to know...

1. If specifying the exponent alongside the modulus is needed, and if so, how to actually specify the exponent (preferably with msieve, since according to this it's the only algorithm proven to crack a key of this size) as there seems to be no option for that (msieve version 1.53).

2. Whether having multiple computers/CPU cores would speed this proccess up, and how to use them if possible (this and the msieve readme seem to imply this is the case). I'm also a bit curious as to how it's done in a mere few hours via Amazon despite the above programs being single-threaded.

Answer 1

The fact that public exponent $e$ is $17$ does not help. The standard attack against RSA keys generated correctly (except for the small size of their public modulus $N$) is to factor $N$. That's the only input of the factoring task, which is where overwhelmingly most of the effort goes.

$e$ is involved only in preparing the final form of the private key, which is easy: the code to prepare the private key from $e$ and prime factors $p$, $q$ of $N$ is in anything that generates an RSA key in the desired format. For the $N(n,d)$ format, a working $d$ is $e^{-1}\bmod((p-1)(q-1))$ and that's a one-liner in Python: d=pow(17,-1,(p-1)*(q-1)).

At 512-bit, GNFS is the algorithm of choice and the two usual bottlenecks are sieving and the matrix step. Multiple CPUs definitely help for sieving. For the matrix step, it's complicated, but a machine with large memory is required.

Have a look at CADO-NFS for an implementation.

It is disputed if GPUs are useful at factoring, and I have yet to find any account of actual use at 512-bit.

If you have multiple $N$ with some generated by a defective process, there might be special attacks computing the GCD for pairs of $(N_i,N_j)$, $i<j$. When one is found that is not $1$, that trivially factors $N_i$ and $N_j$. It's worth trying if the "long-shutdown videogame" was using a poor key generator, even more so in a CTF context. There are improvements to this, both computational and to extend the class of exploitable weak generators; see this.