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

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.

-

## migrated from security.stackexchange.comOct 23 '13 at 6:56

This question came from our site for Information security professionals.

1) Any native brute-force is ridiculously more expensive than sieving based attack. You can't even brute-force RSA-256 2) Why do you say "no plaintext available"? Since RSA is asymmetric, an attacker can produce as many plaintext/ciphertext pair as they like. –  CodesInChaos Oct 23 '13 at 7:45
@CodesInChaos my understanding of how attack 1 was done was as an observer, or peer on the same subnet seeing packets. My goal is to understand how relatively hard each approach is... So if an advance in math is discovered I can estimate the impact to security –  LamonteCristo Oct 23 '13 at 10:15

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.

-
Regarding x/2... since I'm testing values for φ, φ has the same length as the key, and all of φ must be even, can I simply eliminate the odd values for φ and cut my brute-force space in half? or does 2^x-1 refer to something else? –  LamonteCristo Oct 23 '13 at 13:06
Oh sure. If the key space is larger than ten billions times the size of the Universe, then cutting it in half means that it only gets as large as five billions times the size of the Universe. A great gain indeed. –  Thomas Pornin Oct 23 '13 at 13:46
And this is exactly why I keep coming here for perspective. Thank you! –  LamonteCristo Oct 23 '13 at 13:53