When you want to recover N given some (plaintext, ciphertext) pairings
Consider the case that that you know a set of (plaintext, ciphertext) pairings - this may be that you are provided them, or that you have access to some functionality that returns ciphertexts for provided plaintexts. If you do not know the modulus, but know the exponent used (note: this may be prone to a brute-force regardless), then given these pairings you can recover the modulus used.
Let the following be known:
plaintext && ciphertext pairings:
public exponent e (e.g. e = 65537 = 0x10001)
The idea behind this attack is effectively finding common factors between pairings. Recall that, under general RSA encryption, we have:
and recall what modular arithmetic tells us about the relation between these terms, namely that:
This, rearranged, tells us that
However, this is only true for the case that
Thus:
In reality, you're likely to only need two or three (plaintext, ciphertext) pairings (in the context of ctf challenges and exercises), and as such computations can be manual if needed, but shouldn't be too complex
As it's likely you'll be dealing with large numbers, overflows and precision errors may arise in code - using libraries like gmpy provide support for integers of (theoretically) infinite size, and some nice accompanying features too (like in-built gcd and efficient modular exponentiation)
These two statements are mathematically equivalent, but one is easier to implement in code: