# Msieve & Yafu - RSA Exponents and bruteforcing

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.

• Your cheapest option would be bulk GPUs. Dec 12 '19 at 0:21
• @Legorooj GPUs are another subject which I've seen little in regards to actual application for RSA, but I will definitely look into this with whatever software I use. Msieve does appear to have a CUDA build folder. Dec 12 '19 at 0:49
• Maybe look into Google cloud? US\$1000 a month for a high end VPS with a High end NVIDIA GPU. Or the NVIDIA Jetson series? Dec 12 '19 at 4:57
• I could program it, but a) it would take me months, b) msieve is probably faster. I understand RSA very thoroughly. Dec 12 '19 at 4:58

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. 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.

• I've compiled and ran it as well as looked through its options, and this certainly seems to be the best program I've seen. Looking at examples, it outputs two factors when it finishes. Just to confirm as I haven't tested myself, this pair and the exponent 17 will be sufficient to calculate the private key? Dec 12 '19 at 23:59
• @MercuryValentine: yes, see revised second paragraph. I suggest that you try what I outline in the last paragraph before spending too much CPU cycles on GNFS. Also: if the key generator's code is available (e.g.it was in the client-side of the "long-shutdown videogame", reverse-engineering that may uncover an exploitable weakness.
– fgrieu
Dec 13 '19 at 7:18