EC Signature Size?

Question

I've struggled with this for a while. Here's my scenario. I am trying to generate 25-character software product keys (like Microsoft style FFFFF-EEEEE-DDDDD-BBBBB-77777). I have succesfully generated by nonce (raw product key) - according to this article, my final product key (before encoding in base 24 format) should be exactly 15 bytes (4 bytes for my nonce and 11 bytes for my digital signature).

Now the problem is how do I generate an 11-byte signature? I've tried using the currently shortest signature cryptography (ECC - using a secp128r2 curve - which gives me a 128-bit private key). After signing, the size of my signature is 80 bytes (as printed by the Java statement

System.out.println("length: "+signedProductKeyBytes.length);

My questions are:

1. What exactly is the relationship between an EC key size (in bits) and the length of the resulting EC signature (in bytes)?

2. For instance an EC key of 128-bits is supposed to produce a signature size of how many bytes?

3. How do I generate an 11-byte signature (by the way, I'm sure there was no EC keys in the days of Windows XP - so MS wasnt using EC - is there a better way? Say use an RSA 32-bit key or something?)?

4. Also does the size of the string (in my case it's a stringof just 9 chars e.g "123456789" being signed play a part in the final length of signature?

Have struggled with this for a while, searched everywhere online - answers with a lot of technical talks - but nothing specific to answering my questions (the nearest I got was this article for RSA keys)

I hope I get some quick response - my project is late by weeks already. Thanks guys!

Answer 1

I know of no secure signature scheme that generates that small signatures.

• A raw ECC signature(ECDSA etc.) is four time the security level. If you want an 80 bit security level (using a 160 bit curve), you get 40 byte signatures. You can shave off a few bytes, sacrificing a bit of security, but it becomes trivial to break it somewhere between 20 and 30 bytes.

  A 128 bit curve (64 bit security, can be broken, but it's probably too expensive to be worthwhile) will produce a 32 byte signature.

• Finite field signatures(DSA etc.) have the same size as signatures with ECC at the same security level.

• RSA signatures have the same size as the modulus. With a rather small 768 bit key you get 96 byte signatures.

• BLS signatures come pretty close. The signature size is only twice the security level. 20 bytes at an 80-bit level. 16 bytes at a 64-bit level. You should be able to shave off another two bytes or so by truncation, in exchange for higher signature verification times.