The risk of RSA encryption. Would individually encrypted characters be risky?

Question

Is it possible to decrypt a RSA message if the characters of the message are individually encrypted? The info you have is the message, the public key and the n which is too big to be factorizable.

Answer 1

I'm assuming you mean that each character is individually encrypted, and you get the ciphertexts and public key(s) used to encrypt the characters.

The main consideration would be whether the encryptions were performed with padding, such as OAEP. The importance of padding is well established for most cases. In particular, for this scenario, the critical weakness is the determinism of the output - unpadded RSA produces a deterministic output for a given input and key - which can be used to trivially brute-force small messages. The algorithm is simple:

1. Attacker takes the supplied public key and uses it to encrypt every possible (or even just every likely) character, individually.
2. Attacker compares each resulting ciphertext with the supplied ciphertext. If they match, the attacker knows what character produced that ciphertext and thus has "decrypted" the message.
3. Repeat for each (ciphertext, public key) pair that you have until you've "decrypted" everything.

If the messages are padded correctly, this attack is not possible. In that case, there is not (AFAIK) any reason this scheme wouldn't work.

Of course, RSA with secure key sizes is painfully slow, and using it for a large number of tiny messages is absurdly wasteful. In any realistic scenario, you would either encrypt the full message with the key (if it's short enough to do so in one "block"), or use a hybrid cryptosystem where the message is encrypted using a symmetric cipher, and the symmetric cipher's key is encrypted using an asymmetric cipher such as RSA.