Asymmetric algorithm to generate compact unique messages that can be validated I have a cryptographic problem with the following characteristics:


I need to generate a set of relatively short messages; say 20 bytes in length
The contents of the messages themselves is not important to me as long as they are unique within a certain set.
These messages will be sent to a consumer.
The consumer must be able to (with a certain degree of confidence) verify that the message was generated by the producer - again, the contents themselves are actually not important.
An asymmetric algorithm must be used, so that the private key does not have to be shared with the consumer.


I must emphasise that I'm (obviously) not looking for perfection here - the most important thing is for the consumer to get as much confidence as it can in the identity of the producer using a very small footprint of data, and without needing to hold the private key.

I was thinking something like:


generate a unique message [M] (could just be an integer) within a bounded set
generate a digital signature using a private key e.g. RSA and sign the message [S]
"compress" the signature into a smaller space by taking a hash of it using a well known algorithm that has a smaller footprint e.g. something simple like MD5 [CS]
append the "compressed" signature onto the message e.g. M,CS packing these into the number of bytes available as appropriate
the consumer does the opposite to verify


Am I way off the mark? Is there a well known algorithm to do something like this? If it isn't completely ridiculous then is there a good way to evaluate what the actual chances of brute-forcing this would be?

EDIT

Having just re-read my own posting I've noticed a bit of a fatal flaw here :-) how can I use the public key to verify a signature I've "compressed"? I can't see how that could work, but the rest of my question stands.

Is there another more suitable algorithm to do this that is asymmetrical? Is there even a name for what I'm describing?

EDIT 2

I'll try and add some more detail as to WHY its important that this is attempted.

Essentially this is a backup scheme for when the primary method of validating a message is not available. The primary is a request/response over a secure channel back to the producer. This callback would provide meta-data associated with the message. If this is not available then it would be advantageous to us to have a best-effort validation that the message at least came from the producer in the first place - even if we can't get at any of the meta-data we'd like.

We can't trust the consumers with a shared key, and we have a very limited bandwidth/method of transmitting the messages themselves (the primary lookup occurs over a different channel).
It sounds like the main obstacle to using RSA signatures is the size of the signature. If that's the case, consider using Elliptic Curve Digital Signature Algorith (ECDSA).

EC signatures are much shorter than RSA signatures with equivalent strength. For example, an ECDSA signature with a 256-bit key is about 70 bytes long in its standard encoding. This is as strong as an RSA signature with a 3072-bit key, which is 384 bytes long. ECDSA is also a NSA Suite B recommendation, while RSA is not.