I 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 signatures.

First off, if the signature (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 R and a scalar S, either 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, but by testing whether one of the two values is 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.

If you don’t have a small collection of signatures, then your options are more limited. You can check for signature malleability. 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, you can try to guess the message. Given a message, it’s generally possible to recover the public key used in a signature scheme. This 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.