I have a cryptographic problem with the following characteristics:

  1. I need to generate a set of relatively short messages; say 20 bytes in length
  2. The contents of the messages themselves is not important to me as long as they are unique within a certain set.
  3. These messages will be sent to a consumer.
  4. 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.
  5. 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?


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?


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).

  • 1
    $\begingroup$ Perhaps a bit more background about the problem you're trying to solve may help? Create an algorithm given some arbitrary synthetic constraints is harder than providing a problem that needs solving in a non-abstract domain, and even if a produced algorithm is technically correct it may not solve your problem. Why is the message unimportant? Is the fact that it must be unique needs to be taken into consideration somehow? Are you just trying to verifiably communicate identifiers of members of a set? $\endgroup$
    – Allon Guralnek
    Jun 26, 2012 at 17:20
  • $\begingroup$ Two questions: 1) Should the consumer be able to prove to third parties that the message came from the producer? 2) What about replay attacks and MiTM? | You should start in the very beginning, and describe the goals of your protocol. $\endgroup$ Jun 27, 2012 at 9:30
  • 1
    $\begingroup$ Short signatures are an active topic, with a breakthrough in 2001 allowing 20-byte signatures with decent security. See also this thesis (incidentally, anyone gets the title?) $\endgroup$
    – fgrieu
    Jun 28, 2012 at 12:24
  • 1
    $\begingroup$ @KieranBenton: The strangely-titled thesis Collected Papers where Every Theorem Is Filled with Grief describes pretty much the state of the art by 2005 in matters of short signature, which is what you want. Section 3.1 is a readable summary, then heavy math follows. Beware some schemes are patented in the US, e.g. this practical one $\endgroup$
    – fgrieu
    Jun 28, 2012 at 13:30
  • 1
    $\begingroup$ I found the home page for the thesis. That is full of fascinating articles. $\endgroup$
    – fgrieu
    Jun 28, 2012 at 21:09

4 Answers 4


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.

  • $\begingroup$ Thanks - I'll definitely look into this. Do you know if shorter keys can be used (obviously sacrificing the strength)? $\endgroup$ Jun 27, 2012 at 11:30
  • 1
    $\begingroup$ There are smaller elliptic curves. You'll get reasonable strength for 160 bit curves, with 40 byte signatures. But a signature by itself is useless, you need a message you want to sign. To make that message unique, you might want to use a 16 byte nonce. $\endgroup$ Jun 27, 2012 at 11:43
  • $\begingroup$ Well that certainly makes sense :) Do any of you know if C# and the BCL can be coaxed into using smaller keys? I've got a snippet here gist.github.com/d81c2ae5141250b72874 but 256 is the smallest key it seems to allow. $\endgroup$ Jun 27, 2012 at 14:57
  • 1
    $\begingroup$ @CodeInChaos have you got an example of how to generate a key for a curve smaller than 256? I've not been able to find any information on how to do that (on any platform). $\endgroup$ Jun 28, 2012 at 13:12

Here's the signature process:

  • Create a message

  • Take a hash of the message and encrypt it with the private key. The result is called a signature

  • Send the message and the signature together

  • The recipient verifies the signature by taking a hash of the message, decrypting the signature with the public key, and comparing the hash and decrypted signature. They should match. If the verification succeeds, the recipient knows that the message came from a holder of the private key.

If you send a random message, then this process merely proves that the sender holds the private key.

As you noticed, you can't compress the signature with a hash function. Also, since the signature is computed from a hash, it will be larger than 20 bytes, even if the message is that small. Otherwise, your process is fine.

Any asymmetric algorithm should be able to do this, but I don't think there's anything wrong with RSA.

  • $\begingroup$ Your steps 2 and 4 are badly written. "encrypt with private key" is the case for RSA, but not most other signature algorithms. You also neglected to mention padding, which is essential for RSA signatures. $\endgroup$ Jun 27, 2012 at 9:26
  • $\begingroup$ Yes, afraid this won't work for me for the reasons stated in the question - this is not a general case problem, the data size I have to work with is pretty much a hard limit :( $\endgroup$ Jun 27, 2012 at 11:31

Would something like password hash verification work for this application?

  • Assume you know long ahead of time the possible plaintext messages -- perhaps a selected set of FourCC codes or integers from 0000 to 9999.
  • Assume you have enough storage in each consumer device to store ~20 bytes for each possible message that particular device needs to recognize. (For 1000 possible messages, that's ~20 KBytes. Possibly each consumer device responds to a different set of 10 messages, requiring ~200 bytes on each consumer device).
  • Long ahead of time, for each possible plaintext message, on some secure machine, generate a fresh "verifiable message" for each possible plaintext message: the plaintext message in the 1st four bytes; followed by 16 bytes freshly pulled from /dev/random . (Alternately, would it be better to use /dev/random for all 20 bytes of each "verifiable message" ?)
  • Store each "verifiable message" in some secure location accessible by the producer.
  • Long ahead of time, run all 20 bytes of each "verifiable message" through some (slow) password hash to generate the corresponding message digest -- perhaps scrypt or the winner of the Password Hashing Competition. Truncate each message digest to some reasonable length (~20 bytes?) (With 16 or 20 bytes of entropy, pretty much any one-way cryptographic hash function such as a single iteration of sha3 or even MD5 may be adequate).
  • Long ahead of time, store each truncated message digest in the consumer device, where it sits and collects dust until the appropriate time.

Later, when the appropriate time comes:

  • Pull the appropriate "verifiable message" from its secure location.
  • Transmit that verifiable message to the consumer.
  • The consumer runs all 20 bytes of the allegedly "verifiable message" through the same hash function, and truncates it the same way, to get a freshly-calculated message digest.
  • The consumer uses the 1st two bytes of the message as an index to pull out the message digest corresponding to that message.
  • (Alternately, the consumer device compares the the freshly-calculated digest to every digest in its storage. If it matches the 9th item in storage, it does what it's supposed to do in response to plaintext message "9").
  • If that old, dusty message digest exactly matches the freshly-calculated message digest, then the message must have come from the generator -- otherwise, it came from an imposter or somehow got corrupted in transit.

The consumer device does not require a private key. Even if an attacker knew everything that the consumer device knows -- in particular, every message digest stored in every device -- it doesn't help the attacker much. 16 random bytes of data is more secure than a 16-letter passphrase.

It would take an attacker thousands of years to recover a 20 byte "verifiable message" from a stored message digest, assuming he used something like the the COPACOBANA RIVYERA which can brute-force a 56 bit DES key in a single day. That's even if this algorithm uses a technically "broken" cryptographic function and a technically "broken" random number generator that results in "only" 2^(8*10) operations -- rather than the full 2^(8*16) operations required to brute force an unbroken single-cycle 16-byte hash, and significantly more operations required for (slow) password hashes.


If both sides have a keypair, and they know each other's public key, you could run a key-exchange algorithm to get a shared symmetric secret between these two parties. Then use that to calculate a MAC of a nonce. Assuming a 16 byte nonce and a 16 byte MAC, you get 32 bytes total.

But in its plain form this will be open to replay or MitM attacks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.