2
$\begingroup$

I am searching for a algorithm to verify that a short message (size of about 20-30 bytes) was created by a specific device/user. The device/user can be partially offline.

Signing the data using rsa with 1024 bit is not possible since the content of the message will get to big. The size of the signature should not exceed ~100 bytes. Are there any algorithms or alternatives to create short signatures. The algorithm does not have neccessarily have to rely on public/private key. Both parties are ment to be secure and can use the same key if neccessary.

The purpose is to prevent other devices/users to create messages in the name of some else device/user.

$\endgroup$
  • 1
    $\begingroup$ Elliptic-curve signature schemes such as Ed25519 provide small signatures (e.g., 64 bytes for a 128-bit security target). The "non-public/private key signature" you mention is called a message-authentication code (MAC) and can be as short as the desired security level (e.g., 16 bytes for a 128-bit security target). $\endgroup$ – yyyyyyy Mar 30 '18 at 17:38
6
$\begingroup$

Are there any algorithms or alternatives to create short signatures. The algorithm does not have neccessarily have to rely on public/private key. Both parties are ment to be secure and can use the same key if neccessary.

Absolutely; if you want a public key signature (which, when cryptographers use the term 'signature', that's what they mean), then you can consider ECDSA or EdDSA; those can have signatures of circa 64 bytes for "128 bit security" (that is, we expect that it would take circa $O(2^{128})$ operations to generate a forgery without the private key).

On the other hand, you said that you can have both sides share the same key; that means that you can use a Message Authentication Code (MAC), which are even smaller. There are a number known (HMAC, KMAC, CMAC); those can have very long keys, and can have very short tags (what you call a 'signature'; again, cryptographers don't use that terminology to describe the output of a MAC). The size of the MAC is essentially determined by how unlikely you want it to be that someone can just guess the correct tag for a message; if you are happy with making this probability $2^{-128}$ per attempt, you can use a 128 bit (16 byte) tag

My suggestion: if you are happy with both sides sharing the same key, a MAC makes a lot more sense. It's a lot simpler (easier to get right); I would personally suggest HMAC-SHA256 (although there are a number of quite reasonable alternatives avaiable)

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer! I think, I'm going to stick to the HMAC algorithm. Are there any requirements for generating the key? $\endgroup$ – Florian Mar 31 '18 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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