In RSA, what is faster attacking "d" when plaintext is known, or factoring when M is unknown?

Question

I'm aware of two methods to attack RSA:

1. Brute force factoring, where no plain text is available

2. Brute force (1/e) mod φ where the plain text is available as described here

Question

• Given an optimized solution either in a generic CPU, or custom ASIC, what operation is more likely to take longer, and/or consume more resources?

• How close to polynomial time will each of these calculations be?

Ideally I'd like to get a perspective on the number of operations on each approach, and the computational cost. So far it appears that for key length n, option two is 0.5 * n operations.

My goal is to determine if the computational effort per try is less than what was done in this paper, or any other effort to crack RSA.

Answer 1

Brute-forcing the private key is never a good idea with RSA, unless the key was generated with a $d$ of an artificially (very) low size. Indeed, for a 1024-bit modulus, factorization is said to have cost about $2^{77}$ (barely feasible, and estimated, with high memory-related costs, so it has not been actually done yet) while a normal $d$ will have length about 1024 bits, for a completely unrealistic exhaustive search cost.

Moreover:

• If you find out $d$, then you can easily compute the factors of $n$, so even your brute-force attack on $d$ is, in fact, a factorization attack.
• A brute force attack on the smallest of the factors of $n$ is a poor factorization algorithm (known as "trial division"), but still ludicrously faster than brute-force on $d$ ($2^{512}$ against $2^{1024}$).
• This is public-key cryptography. Everybody can encrypt, using the public key. So the attacker can have billions of known pairs plaintext/ciphertext if he wishes so, by simply generating then. Chosen ciphertext attacks are another matter, though.
• You missed an exponential. When a key has length $x$ bits, brute-forcing it has cost $2^{x-1}$, not $x/2$.
• Polynomial complexity has very little relevance to the subject. Complexity classes are about asymptotic behaviour, when operand sizes grow toward infinity. This tells things about performance on a specific operand size only empirically (usually, polynomial algorithms are reasonably fast with values of "practical size", but there is no theoretical basis for why it should be so).

The usual pointer for estimates on key strength is www.keylength.com which contains nice comparators and a lot of pointers.