How to find plain text from RSA cipher text

I have a RSA cipher text c, the public key (e,n). (where c = m^e mod n)

Now I also have开发者_JAVA技巧 known the plain text m should be either "1234XXX" or "12345XXX", where "XXX" is a 3 digit number.

Can I find which one is right without testing all 3 digits number? (I just want to know if the first part is "1234" or "12345", and I don't care what the XXX is.)

You can't do that (it's a sort of know-plain-text attack). You can't derive any information on the key nor on the plain text, given an encrypted RSA message.

(Similar plain text messages don't produce similar encrypted messages)

So in your case, where you have the public key, you are still forced to encrypt all possible plain input messages (brute force), to discover the related encrypted messages.

Actually, if you use RSA properly, then you cannot even guess your 'XXX' by trying the 1000 possibilities. The core operation in RSA is a modular exponentiation, but there is a first step called padding which transforms the data to encrypt into a big integer (modulo n).

The PKCS#1 RSA standard specifies two types of padding; both include a bunch of random bytes. A consequence is the following: if you encrypt twice the same message with the same key, you will get two distinct encrypted messages. The point is, precisely, to avoid the situation which you allude to: being able to "guess" the encrypted message and verify whether the guess is right or not, with only the public key (which is public, hence assumed to be known by every attacker).

Therefore, to answer your question: if you can find your 'XXX', either by trying only 1000 RSA encryption, or through any kind of clever shortcut, then your RSA is very wrong.