You have to think a little outside the box to answer this one. Please
assume I understand the basics of public key encryption reasonably
well and use it all the time.

I'm looking for confirmation of the following: 

Given another party's public key and your own public/private key pair,
and a known plain text message: Is it possible or impossible (or
computationally infeasible), to generate the cipher text
message/string that, if you were to "receive" and decrypt it, would
decrypt into the known plain text message?

That's confusing, I know. So here's a simplistic, concrete example: 

Given Party A and Party B, each with a key pair and each other's public keys. 

Suppose a plain text message of: 1234567890 

And suppose that if Party A encrypted this plain text using his key
pair and Party B's public key, he ended up with cipher text of
"4tqgh9wetffeqwiu" (yes, that's simplistic cipher text, but humor me).

Could Party B, starting with the known plain text of 1234567890, and
using his own key pair and party A's public key, predict (or generate)
the ciphered message that Party A would send (4tqgh9wetffeqwiu),
which, when decrypted by Party B, would result in that unciphered
message of 1234567890?

My thought is that there is no easy way to "back into" the cipher text
someone would send you if you already knew the plain text. That it
would either be computationally infeasible, or at least
extraordinarily difficult (understanding that the shorter the plain
text message, the less brute force it would take).

But I'd like to confirm this, with a brief explanation of why, if possible.

---

Request for Question Clarification by keystroke-ga on 06 Nov 2006 06:24 PST

Hello fingahs,

What cipher are you assuming?

--keystroke-ga

---

Clarification of Question by fingahs-ga on 30 Nov 2006 02:32 PST

I'm sorry for the delay in my answer -- I never got any notification
of activity on this question, so didn't know you had asked for
clarification or provided answers.

I am not wedded to the encryption method. One of my goals is to get
the delivered, signed and encrypted message as short as possible while
remaining computationally infeasible to spoof. So, while I would
expect to use an AES or CAST cipher, as PGP can do, and SHA-2 256
hashing, I'd be open to suggestions.

If I can get an 8 character alphanumeric payload encrypted and signed
delivered in less than 30-36 total hex characters, that would be
ideal.

From the answsers below, what I gather is that without signing, this
is trivial to crack/predict; but if signed, then spoofing the message
and sender of the message becomes computationally infeasible.

You say A encrypts with his key pair (public key or private?) then
with B's public key.

If it's A's public key (because that's "encryption"), any third party
with both public keys can do the A encryption followed by the B
encryption, getting "4tqgh9wetffeqwiu", so then the problem posed is
trivial.

If it's A's private key, and A signs then encrypts, then you are asking to predict:
   E_B(D_A(1234567890)) = x
given B's private key. But if you can predict that, then you can predict
   D_B(E_B(D_A(1234567890))) = D_B(x)
which means
   D_B(x) = D_A(1234567890)
and you have an oracle for signing for A.

If A encrypts then signs, then you have to predict:
   D_A(E_B(1234567890)) = x
Let's say that this magic function is called
   f(1234567890) = x
So to predict
   D_A(y)
then you compute D_B(y) and use that inside your f function to get
   f(D_B(y)) = D_A(E_B(D_B(y))) = D_A(y)
which again allows you to forge signing for A.

The short answer is yes.

With Public Key cryptography, a message is encrypted with the
recipient's public key (not with anything the sender has). If the
message is signed by the sender then the sender's private key is used
for the signing process. So, for the non-signed situation, Party A
would encrypt the message using party B's public key. Since the B's
public key is public, anyone could have done the same encryption
(including B himself). Encryption alone doesn't provide any
authentication of the sender or guarantee of authenticity of the
message.

That's why people also sign messages. If A were to have signed the
message (with or without encryption), anyone seeing the message would
know that A sent it. No one (even the recipient) could forge that
message (in a computationally feasible way).