How difficult is it to brute force d in RSA: d = (1/e) mod φ in a CPT attack?

Question

Given that RSA key generation works by computing:

• n = pq
• φ = (p-1)(q-1)
• d = (1/e) mod φ

If I was an attacker who wanted to brute force d, could I brute force d given just the public key, the plaintext message, and the generally known facts of RSA such as

• φ is always less than n = pq
• n is known by the attacker by the public key
• e is known by the attacker
• The implementation of d = (1/e) mod φ is reasonably efficient

The attack would be brute force φ by iterating from a max value of n, and decrease the value for φ and compare that to the known plaintext of m. An optimization of this would be to skip all values of φ that fall into the conditions of

• Prime numbers ( φ is a product of pq and therefore not prime)
• Where GCD(φ, e) != 1
• Omit values that would result in a small d (FIPS 186-3 requires $d > 2^{nlen/2}$)
• Odd values and be omitted (see comments below)
• etc... (what else can be added?)

Question

• How can I calculate or estimate the difficulty of attacking d when only the public key [edit and plain text message] is known? (no optimizations)

• With the optimizations listed above, and those you may be aware of, what is the difficulty of attacking d?

• What is a more efficient manner of attacking RSA with a known plain text attack?

Answer 1

How can I calculate or estimate the difficulty of attacking d when only the public key is known? (no optimizations)

Generate a few hundred pairs $(n,\varphi(n))$ for whatever key size you are interested in, then compute the average distance between the pairs. That would give you a guess as to how many values on average you will need to get $\varphi(n)$.

Symbolically we get something like $pq-(p-1)(q-1)=pq-pq+p+q-1=p+q-1$ That number has approximately the same number of bits as the larger of $p,q$. So for RSA-2048, we use 1024 bit primes, so the difference will have around 1024 bits. So your work factor would be around $2^{1024}$.

With the optimizations listed above, and those you may be aware of, what is the difficulty of attacking d?

For all intents and purposes it will be the same. The factors by which these optimizations reduce things are small comparatively (e.g., not trying odd values, you eliminate half of the choices which when talking security bits that is only 1 bit)

What is a more efficient manner of attacking RSA?

Factoring is the most efficient method known to date. A 768 bit RSA modulus was factored in 2009 using the number field sieve. That is the largest to date.