Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
$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 at 18:46
    
(comment too long, wanted to add a link) (see IND-CPA) –  tylo Feb 6 at 18:46
    
I liked your mention about the historical reason. Makes sense. Thank you. –  coder Feb 6 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 at 10:20
add comment

1 Answer 1

up vote 3 down vote accepted

I'm not exactly certain what answer you're looking for; I tried to cover all the obvious bases.

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).

As for a literal "ciphertext-only attack", where an attacker is given some ciphertext without either the corresponding plaintext or the public key, well, on the face of it, that looks to be difficult; however we generally don't assume that attackers are hobbled in such extreme ways.

share|improve this answer
    
Thanks a lot for the well written explanation. It is a pity I cannot find all the attacks (effective and ineffective) on RSA in one place, you made clear in your answer for these two. –  coder Feb 6 at 22:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.