Return to Answer

• 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 that 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).

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$ (a maximum of 64 attempts before concluding that a signature is invalid).

• 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).

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).

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

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$ (a maximum of 64 attempts before concluding that a signature is invalid).

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

So the number of symbols among $n$ required to encode a signature is $\lceil(2m-e-f)/\log_2(n)\rceil$, 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, $n=28$, $e=9.64$, $f=6$ that can be $50$ symbols, like 7RPGE 10VGVH KX7P1 KPMG8 RABKY 25QWX 9DKHM 35J3H D4DM2 M12MF.

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

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

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, $n=28$, that can be $50$ symbols, like 7RPGE 10GVH KX7P1 KPMG8 RABKY 25QWX 9DKHM 35J3H D4DM2 M12MF, with $e=9.64$ (an average of 794 signatures computed for each acceptable one) and $f=6$ (a maximum of 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.