1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Semantical security prevents this. $\endgroup$ – kelalaka Feb 18 '20 at 15:46
  • $\begingroup$ @kelalaka Thanks for the answer. So this means, that it is safe to use HMAC for example? $\endgroup$ – AquilaRapax Feb 18 '20 at 15:53
  • $\begingroup$ When I say Semantical security prevents this I mean the output space must be larger than the input. Note that in signing you sign the hash of the message not the message. Therefore, you don't have the size problem. $\endgroup$ – kelalaka Feb 18 '20 at 16:16
  • 2
    $\begingroup$ "Encrypting it via a private rsa key" is wrong terminology. You want to sign your 16-byte message with a private key. In public-key cryptography, encryption is always with a public key. $\endgroup$ – fgrieu♦ Feb 18 '20 at 17:00
  • $\begingroup$ @fgrieu Yeah, you're right. I should have quoted the term ;-) Thanks for the clarification. $\endgroup$ – AquilaRapax Feb 19 '20 at 8:55
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Hmmmm, as for BLS, I was under the impression that pairing friendly curves were somewhat derated (by revised estimates on the difficulty of performing DLog in the extension fields). Are there known 256 bit pairing friendly curves that are still believed to have circa 128 bit security? $\endgroup$ – poncho Feb 18 '20 at 16:49
  • $\begingroup$ @poncho The RFC linked to in this answer points to another RFC about a 381 bit pairing friendly curve, which finally points to Kim & Barbulescu's paper, which gives a 384 bit key size to reach 128 bits of security (381 is close enough). Beware that it grows to an unwieldy 27K curve size for 256 bits of security. You can still use 256 bits for 100 bit security, if you want to live dangerously, but then again RSA 2048 is still used a lot and doesn't fare all that much better. Thanks, adjusted answer. $\endgroup$ – Maarten Bodewes♦ Feb 18 '20 at 17:21

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.