# Is digital signature without schema possible?

In my application I want to use Rabin crypto system with short keys (like 128 bits) and MD5 for hashing. I found that schema like PKCS1-V1_5 or PPS does not allow you to have such small keys and result signature is like 64 bytes for 512 bit key.

I need to sign small amount of data like 30-50 bytes and having 64 bytes signature is noticeable overhead. I tried BLS (48 bytes for signature) but it is too slow compared to Rabin.

My idea is to use MD5 because it needs only 128 bits and short key with same size to avoid padding. So in this case I don't need schema. Also this should give me 20 bytes for each signature. I realise that this is very weak signature but data (packet) lifetime will be short.

Will such approach work?

New contributor
John Tracid is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• 128 bits for a cryptosystem that depends on the hardness of factorization is obviously not going to cut it. MD5 is also a bad choice because it allows attacks without any noticeable benefit compared to a FDH such as SHAKE128, and you can also simply use the (leftmost bits of) a fast, cryptographically secure hash. I'd rather look at ways around the issue (e.g. ECDH, then derive a MAC key for multiple messages). Sep 14 at 19:07
• Rabin with 64-byte signature (512-bit) is very insecure; it's been publicly broken in 1999 (see this). For 64-byte signature, you might use Ed25519, or ECDSA with curve secp256r1. Signature verification is not as fast as Rabin, and it's more complex, but aside from that I can only think of benefits: smaller public key and signature, faster signature generation. There are 25% smaller (48-byte) variants.
– fgrieu
Sep 15 at 5:59
• Would a Message Authentication Code work in your scenario? It does mean that receiver can generate "signed" messages; in some scenarios, that's not an issue (and in others, it's very much an issue). If you can use a MAC, well, MAC sizes can be quite small without issue (other than the obvious one; an attacker just guessing; with an $n$ bit MAC, he has a $2^{-n}$ probability of being right...) Sep 15 at 21:01
• @poncho Unfortunately no, because this require to have some kind of session key for each pair of participants Sep 15 at 21:05
• Again, I suggest revising the question stating functional goals: message size, maximum message+signature size, need or not for message to be intelligible without public key (if not, a standardized 256-byte Rabin message+signature can embed 222 bytes of message), performance constraints for signature generation and (separately) verification, any security requirement beyond those standard (in particular, is it an issue that knowledge of the private key allows to create pairs of distinct messages with the same signature?).
– fgrieu
Sep 16 at 4:49