Creating serial key generator using ECDSA, how to get signature short enough?

Question

I've written some questions in this stackoverflow and got great responses but now I'm trying to wrap it all together.

I have for the last couple of weeks been building a serial key generator project in C# to use in my own software. The goal is to be able to generate serial keys for customers of my software. To stop people from creating key generators I've been looking into elliptical curves and digital signatures using these.

So far I've been able to implement ECDSA using a secp256k1 curve. However one big question remains, how do I keep the signature, which will be made up of two points, short enough to be usable as a serial key? I do not wish to use a license file etc.

Unless I'm doing something wrong I get a signature made up of two points, each point containing a 32 byte BigInteger. This means the total byte count for the signature becomes 128 bytes. Encoding this to hex would yield 256 charactes, way too long to use for a serial key.

Now I've found this sample page: http://kjur.github.io/jsrsasign/sample-ecdsa.html

Using this page for a secp256k1 curve the signature value in hex becomes much shorter than 256 characters. How do they get such a short signature?

I've also found a commercial solution called ellipter (ellipter.com), they get their key length down to 31 characters for a 128 bit "key strength", how is this even possible? What curves are used for 128 bit security?

Thank you!

Answer 1

Restricting to Elliptic Curve Digital Signature Algorithm and curves as in FIPS 186-4 appendix D:

• an $m$-bit curve, that is one over field $GF(2^m)$ with $m$ prime, or over field $GF(p)$ with $\log_2(p)\approx m$ and $p$ prime (and possibly of some special form), allows schemes with $m/2$-bit security (at most, but for well-chosen curves we can largely ignore that as far a we know).
• Challenges at the level $m=109$ have been publicly solved circa 2002. I'm not aware of security authorities ever vetting anything less than $m=163$ for any use, but it is technically sound to use $\log_2(p)\approx128$ as in curve secp128k1 for copy-protection (which can likely be broken by other ways than forging a signature).
• An ECDSA signature normally contains two components $r$ and $s$ of $m$ bits each (ignoring the overheads of ASN.1 formatting).
• It is possible to trim a few bits (say $e=8$) by omitting them from the signature, and compensating for their lack by repeating the signature generation process (with a new random seed) until hitting a signature where these $e$ bits are all zero. That increases the cost of signature generation by a factor of $2^e$ on average, which for small $e$ is often acceptable when a predictable maximum signature generation time is not essential (the distribution of the signature generation time becomes geometric/exponential; the number of attempts to generate a batch of signatures remains quite predictable). There is no loss of security except possibly from side-channel attacks (that we know; for extra confidence we can make the trimmed bits a hash of the others, rather than zero).
• It is possible to trim a few more bits (say $f=8$) again by omitting them from the signature, and compensating for their lack by repeating the signature verification process, enumerating the $2^f$ possible values of the missing bits, until a valid signature is found. That increases the cost of signature verification by a factor of at most $2^f$, which for small $f$ is often acceptable (verification time has predictable maximum, and uniform distribution). There is no practical loss of security (private key recovery from the public key still remains the best known mean to forge a signature).
• If a signature is keyed-in (rather than copy-pasted), one wants to re-encode the corresponding bitstring as symbols chosen to minimize the risk that a keying mistake renders the signature invalid. The problem is different depending on if you have control of the font used to render the string keyed-in, or not. In the later (worst) case, as a courtesy to the user, we should restrict to decimal digits and roman letters without accents, ignoring case, grouping symbols into equivalence classes based on visual similarity, such as $\{\text{0},\text{O},\text{o}\}\;$, $\{\text{1},\text{l},\text{I},\text{i},\text{L}\}\;$, $\{\text{2},\text{Z},\text{z}\}\;$, $\{\text{3}\}\;$, $\{\text{4}\}\;$, $\{\text{5},\text{S},\text{s}\}\;$,... We end up with perhaps $n\approx28$ of these classes, which could be stretched to $n=32=2^5$ with some extras like $\{\text{-},\text{_}\}\;$ and $\{\text{+}\}\;$ (when $n$ is a power of two, the re-encoding is slightly simplified).

Thus $\lceil(2m-e-f)/\log_2(n)\rceil$ symbols among $n$ allow to encode a signature if we are willing to spent the effort to try an average of $2^e$ signatures for generation and a maximum of $2^f$ for verification.

For secp128k1, 7RPGE 10GVH KX7P1 KPMG8 RABKY 25QWX 9DKHM 35J3H D4DM2 M12MF could be a signature coded as $50$ symbols among $n=28$, $e=9.64$ (an average of 794 signatures computed for each acceptable one) and $f=6$ (64 attempts before concluding that a signature is invalid).

An extra complication of the signature generator is that it might be required to avoid signatures containing politically incorrect text, but it will only moderately complicate the generation.

Answer 2

The signature with the 256-bit curve should be 64 bytes, not 128. Was that a typo or are you doing something wrong? If you encode that in Base16 (hex), the efficiency is 50%, you would get 128 characters.

Instead, if you go with Base64, you'd get 75%, so you would be looking at 86 characters.

Since this is not an application that needs a very high level of security, you can use a 128-bit curve, which would give you 43 characters. I don't know whether that's acceptable to you as a serial length.

As for the 31 characters being 128-bit, that's about right. A 128-bit key is 16 bytes, which can be easily represented in 31 characters. (much less if you use Base64)