# RSA keys finding when messages are known

I have this situation, where, in a game, people send messages to each other (game moves etc...) These messages need to be encrypted, and should only be readable by the destination person. I am using RSA for this, but, recently I got a doubt. Is it possible that, if the message is one of n possible messages, can somebody with access to the encrypted one, guess the keys used? (Both public and private).

We use keys to ensure the source and destination. So, we encrypt twice, every message. Once with sender's private key, and with receiver's public key on top of it. So, it is doubly secure, and repudiation is avoided. We use RSA only, for both. Is this bad, if the attacker knows the message to be 1 out of n.

NOTE: If this is a problem, using a random number as a field in the message, and xoring the message first with it, and sending, would that solve the problem. This makes, encrypted message essentially random, for the attacker. But for person with keys, it still allows nicely to be decrypted.

Another question about encryption, does ElGamal encryption have similar issues? I plan to use both in the game app.

I confirm that "encrypt with the private key" in an asymmetric encryption scheme generally does not make sense. It seems that the only reasonable interpretation of "encrypting with the sender's private key" in your setting is that the sender actually signs the message.

Now the attack scenario you describe is not "chosen plaintext attack" but rather known plaintext attack: the attacker knows that the message is one out of n possible, known, messages. For a deterministic encryption, this would allow the attacker to find out what the message actually was, provided the list of n messages is not too big (since the encryption function is public, one can encrypt each of the n messages exhaustively and see which ciphertext matches). However, this is not possible with a standardised version of RSA such as RSAES-OAEP in PKCS #1 where the encryption is made probabilist by the use of an appropriate padding.

Using a standard implementation of RSA would not allow an attacker to recover the keys. The ElGamal scheme is also probabilistic so the same applies.

• Yes, it is actually more like "signing" only. I got the answer for my question, but, why should not sign with private key encryption? (I understand now that it is not an encryption, but something like signing only, this was the purpose of it before as well, to sign it with sender id). Is there any theoretical reason for it? For secrecy or problem of attacks? If we use, for example, 128 bit keys, is attacks for private key a problem? NOTE: I will mark it as answered, as soon as this is cleared. Problem is already there are many crypto systems in the app, signing will be another one. Oct 11, 2012 at 15:26
• I answered the question there.
– bob
Oct 13, 2012 at 9:24

Your question is a little confusing.

Encrypting with the sender's private key does not add "security", you probably meant to do a digital signature, which is a hash of the message, encrypted with the private signing key. Signing keypair and the encryption keypair should be different.

RSA is not broken if you use 2048+ bit keys, and even 1024+ keys are strong. You seem to be asking whether it can be broken under a chosen plaintext attack, if I understood correctly.

• We do two encryptions, one with senders private key, but on top it, for the same message, we encrypt again with receivers public key. So, for any attacker has to first decrypt using receivers private key, which is not possible. However, the senders private key is used (in the first layer) only to ensure that the "sender cant deny 'it is him who sent the message' " later. Oct 11, 2012 at 7:13
• "You seem to be asking whether it can be broken under a chosen plaintext attack," did not get you. I am saying, if number of possible messages is n (<= 10, lets say), then can the attacker (gained with this knowledge, and the 10 possible messages), guess the keys? Oct 11, 2012 at 7:14
• I also got your digital signature idea, that also makes sense. If this RSA encryption becomes heavy (for first layer), I will use it, yes. Oct 11, 2012 at 7:16
• @Salahuddin559 Encrypting with a private key is not encrypting. It is similar to a RSA signature, but not quite the same thing. Don't do it. Oct 11, 2012 at 8:35