How can I prevent a message replay with RSA? I am using RSA to encrypt some data but I would like to eliminate the possibility of message replay. By message replay I mean sending a valid message multiple times to the original recipient. It is obvious that an attacker can capture a valid message without knowing its contents and replaying it.

Is there any efficient way for the recipient to determine if a given message has been replayed or avoid the problem altogether?

The only things I can think from the top of my head are: including an expiration time in the message (rather insecure) or hashing the message, storing it and checking if future messages have the same hash value (can consume a lot of memory).
You could use some combination of:


an expiration timeout (i.e. if the message does not arrive until the timeout, we don't accept it)
storing previous values of a nonce.


You only have to store those nonce values whose timeout didn't yet expire.

If the messages arrive all in order, you can instead use a simple counter (which always goes up) and reject every message which has a counter value smaller or equal than the last received one.