# Attack RSA knowing the public key and brute forcing all possible message

Alice want to send a message $m$ to Bob, and encrypt it with Bob public key $K_B$.

$A \rightarrow B : \{m\}K_B$

Lets assume I have intercepted $\{m\}K_B$, I know $K_B$ and I know that $m \in D$ (Alice message belong to a relative small dictionary called $D$ )

By brute force attack, can I got through all $x \in D$ so that I find $\{x\}K_B = \{m\}K_B$ ?

• What padding is used for RSA? – SEJPM Apr 6 '18 at 18:04
• Encryption of the message using a key related a unique ciphertext. In other words, you will never find two messages with the same ciphertext. See crypto.stackexchange.com/a/2374 – Jacob H Apr 6 '18 at 20:29

If textbook RSA is used then many attacks are possible, including dictionary attacks. This is because the value that is used in modular exponentiation (called RSAEP in the standard) is just the input decoded to a number. However, plaintext RSA is susceptible to many attacks and is not considered secure; a rather obvious one is when a message with value 0 or 1 is encrypted, as the output would be 0 or 1 as well; no attacks necessary.

Normally however a secure padding method is used. The original scheme from RSA labs was PKCS#1 v1.5 padding. This padding "wraps" the message and includes many random bits that are encrypted together with the message. These bits are not know to an attacker. They can be used to check that the decryption was successful or not. The later padding method OAEP, which is provable secure, should however be used as PKCS#1 v1.5 is vulnerable to attacks on the unpadding of the message. OAEP, just like v1.5 padding, uses random bits.

PKCS#1 reads for OAEP "Generate a random octet string seed of length hLen" where hLen is the hash function used within MGF-1, often SHA-1. That means that hLen is at least 160 bits. That means that 160 bits of randomness are encrypted together with the message. It's at least 63.95 bits for PKCS#1 v1.5 padding but usually it is more (the amount of padding depends on the difference between key and message size).

So no, you cannot use dictionary attacks because the output of the RSA encryption will always be different from the given message - if a secure padding is used. However, if for some reason the random number generator fails and leaks the not-so-random bits then you could match the padding, and perform a dictionary attack.

• Thanks for the help! I was unaware of the last paragraph you wrote (though I'm quite sure I read it in my college crypto class somewhere). @Maarten thanks again for your amazing help! And honored to have your help. It's always a pleasure learning from simply reading your comments and answers :) You've helped me twice so far =) – Haris Nadeem Apr 9 '18 at 2:16

The answer depends one two points. Firstly, when you say RSA do you mean textbook RSA (also referred to as Plain Vanilla RSA) or the standard RSA (OAEP) which uses padding. Once this question is answered, the second most important is how small is your "relative small dictionary" is.

Assuming that your talking about plain vanilla RSA then given a small dictionary, then yes you could brute force the cipher to reveal the message.

As for RSA (OAEP), it is chosen ciphertext attack (CCA) secure, so I assume that using a "relatively small" dictionary may not suffice to brute force the cipher text. I'm not sure how small till it becomes vulnerable to brute force. That would probably have to be another question.

• Even before OAEP, the encryption padding in PKCS1v1, retronymed RSAES-PKCS1v1_5 in PKCS1v2 and still fairly widely used, is randomized making it secure against bruteforce, but not against Bleichenbacher's adaptive attack. – dave_thompson_085 Apr 7 '18 at 0:52