# Digital signatures with one-way function, can messages be longer than the signature?

Ethereum and Bitcoin both use 512 bit signatures, can the message that is being signed be longer than 512 bit?

• Thanks for a great answer, that was what I thought. So, in other words, cryptographically, there is a loss of information and increase in collisions with messages that are longer than the maximum length (and longer messages do get hashes, but there is an increase in collisions because the number base is limited) – lsh Mar 1 '18 at 22:10
• What this answer claims is neither a consequence of the standard definitions of signature schemes, nor even mostly true of the signature schemes out there. The size of the encoding of a public key has no relation whatsoever in general to the size of the messages that can be signed. A putative signature scheme that does not involve hashing a message as an essential part of its definition is almost certainly cryptographically broken, and only exotic schemes, for extremely resource-constrained environments, would use a hash function with a limited input size. – Squeamish Ossifrage Mar 1 '18 at 23:49
• Sometimes in an API for signing, two parts of the computation may be separated—hashing the message, and computing fancy math—but this doesn't apply to all APIs, and doesn't work in all signature schemes, e.g. it breaks down with EdDSA. Even with a split API, the hash and key size are not generally related—counterexamples: in SPHINCS-256, the hash is 256 bits, but the public key is 8448 bits; in EdDSA, one of the hashes is double the size of the public key's encoding. Using a 256-bit hash is a choice for, not a consequence of, the fancy math in ECDSA over secp256k1 in Bitcoin. – Squeamish Ossifrage Mar 2 '18 at 0:04
• Yes, after consideration of what you said I agree I was not right. I tried to up vote your answer, but I no longer have over +15 reputation :) – datKiDfromNY Mar 2 '18 at 0:35

Yes.

Signature length is generally unrelated to the length of the message and the length of the key. Some signature schemes have very short signatures and long public keys, like CFS; some have short keys and very long signatures, like SPHINCS; some are more balanced in size, like Ed25519 or RSA-2048-FDH. Only exotic signature schemes for very special purposes are limited to short messages—the vast majority are designed to handle messages of arbitrary length.

Pretty much every signature scheme is designed with a random function from messages to elements of some mathematical structure for the public-key cryptosystem. This serves to destroy any relations in structured messages. If we didn't do that, e.g. if we used RSA with the stupid verification equation $s^3 \equiv m \pmod n$ for a signature $s$ on a message $m$ under public key $n$, then you could trivially forge the signature $s = 1$ on the message $m = 1$ under any modulus $n$ because $1^3 \equiv 1 \pmod n$. Instead, serious practitioners use a sensible verification equation like $s^3 \equiv H(m) \pmod n$ where $H$ is a random function from messages to $\mathbb Z/n\mathbb Z$ so you have no hope of finding an $m$ such that $H(m) = 1$.

Practical signature schemes are usually instantiated with a fixed hash function $H$ accepting arbitrary bit strings as inputs, like SHAKE256. This is not simply ‘hashing a message, and then signing a hash’—the hash is an integral part of the signature scheme itself, not something you do in addition to signing; the security of the signature scheme relies critically on the hash.

In the signature scheme that Bitcoin uses with the OP_CHECKSIG operation, the message, a transaction, is an arbitrary bit string, mapped with SHA-256d (that is, two iterations of SHA-256, $m \mapsto \operatorname{SHA-256}(\operatorname{SHA-256}(m))$) into a scalar modulo the order of the curve secp256k1.