Compare two approaches for cracking RSA key

Question

I came across these questions while studying for a crypto course, does anyone have any ideas on how to answer these?

(a) Random prime numbers of size 1536 bits are chosen to generate an RSA modulus of size 3072 bits. Knowing that the number field sieve factorization algorithm would succeed in factorizing an RSA modulus of this size in $2^{128}$ elementary operations on average, compare the two following approaches for cracking this RSA key:

i. factorizing the modulus using the aforementioned number field sieve factorization algorithm; or

ii. factorizing the modulus by enumerating candidate prime factors and looking for one that divides the modulus.

(b) Same question as above, but this time the primes p and q that make up the modulus n = pq are no longer randomly chosen, but derived deterministically from a user-supplied password. (E.g., we can use a pseudo-random generator to map the password to a pseudo-random number r of the right length, then use primality testing to find the first prime that is greater than r.) Feel free to make any reasonable assumption you need regarding the password.

Answer 1

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time.

To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by

$\pi(x) \sim \frac{N}{\ln N}$.

As such, there are approximately

$\frac{2^{1536}}{\ln 2^{1536}} = 2.24 \times 10^{459}$

candidate primes to test. In reality, division of numbers this large is not an elementary operation, but even assuming it were to be one, on average we'd need half that number's worth. I think it's safe to say that (a.i) is the better choice.

As for part(b), I'm may be getting confused, but what I believe this is stating is that our key is generated by taking an input password $p$ and using it to seed a PRNG. We then generate an output stream of 1536 bits, and then select the next prime greater than our output as the first prime? And I presume this implies that we have access to said password?

If so then on average we'll have to look at

$\frac{1}{2} \cdot \ln 2^{1536} \approx 533$

different numbers before we find a prime. We'll have to do this twice though, so that's a little over a thousand primality tests on average. So the speed is then dependent on the number of elementary operations in our testing algorithm and PRNG, but assuming modern constructs (say, ISAAC and Miller-Rabin) the candidate approach should work better.

Sorry if I understand the question incorrectly. It's not the best written.