I'm looking for a cryptographic construction that allows a client to decode a message but not encode it

Question

Let's say A and B are two people that want to exchange a message yada yada...

I want to build something that would allow A to send an encrypted message to B; with B able to decode the message but not being able to encode another valid message.

Kind of the opposite of how assymetrical schemes work.

Does a construction like that exists?

Answer 1

NOTE: I'm making some simplifications here, and that's dangerous in cryptography. What I'm saying about RSA is correct, but you really must do some study before you use any cryptographic system, and especially before designing any novel way of using one. Very small misuses can lead to completely insecure systems. As @almosnow notes, using ElGamal this way would be broken. As @CodesInChaos notes, signatures are not exactly "encrypting with the private key" (that's their heart, but there are other important pieces). RSA is very likely the right tool for this specific job but you must use it correctly, and unfortunately I don't know any short "here's what you need to know to implement it correctly" short of the Stanford Crypto Course, which is quite good, but neither short nor easy.

That's exactly how RSA works.

• A has a key that can encrypt messages. We call it the private key
• B (and possibly everyone else) has a key that can decrypt messages encrypted with A. We call it the public key.

It is true that the key B has can be used to generate a message that can only be decrypted by A, but for a given protocol it should be easy to declare that "not a message" if that's what you need. B cannot encrypt a message that B can decrypt in any case, and since only A has the private key, this should be exactly what you described.