Compare two approaches for cracking RSA key

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.

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.

• Yeah the questions are really hard to understand haha, but I appreciate the help! – DavidR Oct 17 '14 at 1:44
• @Samuel Judson: for the first part, you have the right order of magnitude, but a) the number of 1536-bit primes is about half of what you estimate; b) what's the lowest possible value for the highest of the two primes? That allows another significant reduction. $\;$ For the second part, you have given an order of magnitude of the effort involved in generating the key. The question asks to turn this into a factorization method for the key at hand, without assuming prior knowledge of the password. $\;$ Side hint: the part of the answer reading "We'll have to do this twice" is wrong. – fgrieu Oct 17 '14 at 6:34
• @fgrieu: Wow, yep, you're right on that last bit. For some reason I was thinking about generating the modulus, not testing for a divisor. And as for not having prior knowledge of the password, that's what I wasn't clear on for the question. I'd have to work through the numbers, but at that point the approach would be to reasonably assume a password of say, 24 ascii characters max, and enumerate the space, and maybe make some statement about the average speed of password cracking. I don't quite have the time today, but my guess is very much that it'll still end up faster. – sju Oct 17 '14 at 14:36
• @fgrieu: I guess I should expand on "my guess". If the reasonable assumption about the password is that it is chosen like most people choose passwords, then it should be faster on average, as the vast majority of passwords fall within a relatively small range. If we are assuming randomly generated passwords, then it should not be, as $128^{24}$ is substantially greater than $2^{128}$. – sju Oct 17 '14 at 15:02