# Known vs. Chosen (plaintext and ciphertext) and RSA

I want to know whether I can break RSA (textbook) with known plaintext/ciphertext attacks.

Known plain-text

Let $c$ be the ciphertext and $m$ the plaintext.

$$c = m^a \mod n$$

Since all I have is the plain and ciphertext, all I could do here is guess the decryption exponent $a$ until I find one that leads turn $c$ into my known $m$.

Known ciphertext

In this case, I would have to factor $n$ (hard) in order to find $p$ and $q$.

Is the above correct? I would appreciate if someone could point the right direction.

• $a$ (usually denoted $e$) is part of the public key, and therefore is public (and the attacker knows it). "Ciphertext only" attacks are a historical idea, but the model is too weak for today's idea of security. "Known plaintext" is an attack which is mostly used for symmetric ciphers, because in the public key encryption it does not exist (the attacker can always do a chosen plaintext attack). For PKE interesting attacks are chosen plaintext attacks and chosen ciphertext attacks, and textbook-RSA is resistant against neither of these attacks
– tylo
Feb 6, 2014 at 18:46
– tylo
Feb 6, 2014 at 18:46
• I liked your mention about the historical reason. Makes sense. Thank you. Feb 6, 2014 at 22:37
• Btw. "chosen plaintext attack" means informally, that the attacker can choose one or more plaintexts and in return gets the encryption of this plaintext. But how this results in an advantage for the attacker is very different for symmetric and public key encryption. And therefore, security definitions are also different.
– tylo
Feb 7, 2014 at 10:20

Actually, with RSA, we generally assume that the attacker knows the public key (the modulus $n$ and the public exponent $e$); with that, he can encrypt as much plaintext as he cares to (by selecting a value $M$ and computing $M^e \bmod n$). So, in that sense, the term 'known plain-text attack' doesn't apply, as we assume the attacker can do a chosen plain-text attack.
As for the variant "what if the attacker has some plaintext/ciphertext pairs, but doesn't have the public key; what can he do? Actually, it turns out that if the public exponent isn't too large, the attacker is in luck; if the attacker takes two known plaintext/ciphertext pairs $P_1, C_1$ and $P_2, C_2$, he can compute $gcd( P_1^e - C_1, P_2^e - C_2)$ for plausible public exponents; if he guesses the correct one, that value will be $k\cdot n$ for some integer $k$ which is extremely likely to be small. That gives him the public key.
As for guessing the decryption exponent, well, I suppose that the attacker could try, but he's not likely to have success. It is known that knowledge of encryption and decryption exponents is equivalent to factoring; that is, if you know $e$ and $d$, you factor $n$ (and if you know how to factor $n$, you can compute $d$ given $e$). Hence, guessing the decryption exponent is hard; if it wasn't, the problem of factorization wouldn't be easier. (And, if you're asking "why can't you step through all the possible possible private exponents", the answer is that $d$ is generally only a few bits smaller than $n$; if $n$ is 1024 bits, $d$ might be 1020 bits; that's rather too many possibilities to step through).