Is there an asymetric encryption whos output size is quite equal to the input size I want to send a verifiable chunk of data (around 16 bytes) by simply encrypting it with a private RSA key, providing the public key in the source code for the verification. This was my initial thought. (I now know that this is not the same as signing the data, but this does not matter now.)
I tried RSA and ECC to determine that the length of the output data relies on the length of the keys. For this small amount of data, even the much smaller ECC keys produce a heavy amount of data overhead. So the question is: Are there any asymmetric encodings that don't have so much overhead, or is this per se impossible with asymmetric encryption/signing?
I found the possible solution of using message authentication codes. Still, I don't like that I have to provide the security with the software, which is (if I understand correctly) the case for every symmetric encryption. But maybe I'm wrong, and this is not such a big issue?
For ECC you are probably better off just using ECDSA or, if you're adventurous, the BLS signature scheme. ECDSA has a signature size / overhead of 4x the security strength (say 128 bit), or two times the key size (a 256 bit curve). BLS has a signature size / overhead of about three times the security strength (say 128 bit) or once the key size - it requires a larger key size of 381 bits to reach 128 bit security. So that's about 64 bytes for ECDSA (for a flat encoding without ASN.1 / DER overhead) and 48 bytes for BLS (currently the minimum recommended).

For RSA, see signatures giving (partial) message recovery. For message recovery schemes you will get at least 34 bytes of overhead (assuming SHA-256) - but that doesn't matter much because the minimal signature size is at least the same size as the RSA key size. A rather small key size of 2048 bits will therefore already give you 256 bytes for a signature that contains all the data.

Using a HMAC is only OK if you trust the other systems that get the key to keep the key secure &amp; play fair (and there is of course the issue of establishing the key in the first place).



For many common runtimes / generic cryptography libs I'd only expect to find ECDSA and HMAC implementations.