A problem I hadn’t thought of before is: how do you distinguish signatures from random strings?

I hadn’t thought of this because I figured it would be obvious. If you have a public key and know the message being signed, signatures can be verified using the scheme’s Verify algorithm, whereas random strings won’t pass. But what if you don’t know the public key or the messages?

It turns out this can reasonably done for signature schemes like EdDSA and ECSDA over most curves, if you have a few examples to look at.

First off, if the signature (here: ECDSA) is encoded using DER encoding, then there will be strong DER structure you can recognize. I won’t go into that because it’s not our setting. Here we’ll assume these are raw byte strings that possibly consist of a curve point encoding R and a scalar S, formatted as R || S or S || R.

For EdDSA, a nice fact is that these signatures are recognizable, at least if you have a few. They consist of two concatenated 32-byte values R || S (or the other way around) where S is a scalar. The scalar S is drawn from a relatively “small” field of size 2^{252} + 27742317777372353535851937790883648493, which is much smaller than the 256-bit slot it occupies. So it’s relatively easy to look at a few signatures and quickly distinguish them from random, just by testing whether one of the two halves is consistently less than this field size.

Unfortunately, ECDSA over fields like P-256 and the Bitcoin curve secp256k1, the field size is very close to 2²⁵⁶. This means that you simply can’t rely on the scalar test. Instead you need to look at the curve points. The real test is to look at the element that might be the x-coordinate of an EC point, and see if it could possibly solve the curve equation. This will happen about half the time, so a small collection of signatures will let you distinguish with high confidence.

If you don’t have very many signatures, then your options are more limited.

If you have a signature verification oracle, sometimes you can check for signature malleability in ECDSA signatures. Concretely: if you have an oracle that will verify the signatures (against the unknown public key and message) you can replace the S term with n-S (where n is the field size) and see if the signature is still accepted. This works for some implementations of ECDSA because in these implementations there are two scalars that satisfy the verification equation: essentially S and -S.

If this doesn’t work, your options are more limited. You can try to guess the message. Given knowledge of the exact message (and hash function used, including any domain separators), it’s generally possible to recover the public key used in a signature scheme. This public key is basically a random group element, so it doesn’t tell you much by itself. But if you have two or three signatures all made by the same public key, then you can repeat this process on all of them and see if they consistently produce the same public key.