1
$\begingroup$

I was wondering what is typically the size of digital signature for every 1-bit data that is signed. I am trying to figure out how size of messages increases if I send only the data in a message or packet versus when I send the signed-data.

N.B. I am new this world of Cryptography, so don't mind if my question sounds too puerile.

$\endgroup$

2 Answers 2

3
$\begingroup$

The size of digital signature (that is the size of the cryptogram output by the signature generation procedure) is in practice independent of the message signed and it's size, because what's signed is a hash of the message. That signature size depends on the signature system, it's parameters, and the decoration of the signature (often signature is preceded by headers, ASN.1 or otherwise, on the tune of this is a signature; and perhaps it is encoded as characters rather than bytes, increasing it's size by a factor like 2 for hexadecimal or 4/3 for base64). In the following I disregard such decoration.

For RSA and signatures schemes based on the difficulty of factorization, the signature is most often the size of the public modulus, with 2048 bits (that is 256 bytes) the current recommended minimum for something like 112 to 128-bit symmetric security.

For DSA, ECDSA, EdDSA… and other mainstream signatures based on the difficulty of the Discrete Logarithm Problem in some cyclic group of $q$ elements, with $q\approx 2^{2b}$ for $b$-bit security, the signature is typically $4b$ (that is 64-byte signature for 128-bit security) . Short Schnorr Signature reduces this to $3b$ but at the expense of a security property: the legitimate key holder can prepare messages with different meaning and the same signature (that's fixable, but not mainstream).

Using the pairing-based scheme BLS in theory allows further reduction of the signature size, down to $2b$ asymtotically; but that's at the expense of speed, is not mainstream, and in the closest thing to a standard the size is $3b$, comparable to Short Schnorr Signature.


The size overhead of digital signature is how much larger a signed message is compared to the non-signed version. Signature schemes giving message recovery allow part of the message to be embedded in the signature, thus overhead lower than the signature size. Overhead is equal to signature size for the other, most common kind of signature: signature schemes with appendix, where the signature is independent of the message, e.g. appended.

For RSA, the ISO/IEC 9796-2 signature schemes allow to reduce the overhead to one hash width plus two bytes, e.g. 34 bytes of overhead for any message at least 222 bytes and a 256-byte signature for 2048-bit public modulus and SHA-256 (the overhead can be further halved, down to near $b$-bit, see Louis Granboulan's OPSSR, but this is not mainstream).

For signatures based on the difficulty of the Discrete Logarithm Problem in some group, the minimum overhead seems to be $3b$-bit. One such system is Abe-Okamoto of ISO/IEC 9796-3 (but it does not improve on overhead compared to Short Schnorr Signature, which may be why it's not much used). Another is ECPVS of ANSI X9.92-1-2009 (which has the same overhead for random messages, but can lower overhead for messages with inherent redundancy, without resorting to compression).

$\endgroup$
2
$\begingroup$

There are 2 types of signature schemes:

  • Signature with Message Recovery - which is becoming increasingly rare, and
  • Signature with Appendix.

The "Appendix" part of Signatures with Appendix usually have constant size, except for the likes of Falcon, which use entropy codings like the Huffman coding to reduce signature size.

And I hope RSA isn't the only signature scheme you'll encounter in your career - RSA is a bijective permutation, it can be used as "signature with message recovery" for small messages. Most signature schemes will first hash the message (in one way or another) - the message can be long or short - then apply a formula using the private key to relate the hash of the message to the public key.

$\endgroup$

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.