# Activation keys and asymmetric encryption

To me it seems that a quite safe way of creating activation keys is by using asymmetric encryption, so that the end-user could only reverse-engineer the validation method. This way the company keeps the generation algorithm (and key) safe.

Assume one uses RSA encryption with 1024 bit keys. They sign some data with the private key and the result is 128 bytes long.

How can he fit this into an activation key that is much shorter than that? e. g. 16 or 20 chars or so.

The validation algorithm must now decrypt with the public key and see if the message is really coming from the company. How is it done when the full cryptographic message is unknown?

Is there an error in my assumptions above or is it in fact done like this?

You can not compress an RSA signature much below the private modulus size. All methods that I know double the cost of either signing or verifying for each extra bit trimmed, after the first one or two which comes nearly for free.

The higher-order bit of an RSA signature can be trimmed: just use a padding scheme such that the padded message $R$ verifies $2R<N$ (the two padding schemes of PKCS#1 have this property); normally the signature would be $S=R^d\bmod N$, but rather use $\tilde S=\min(S,N-S)$, which is at least one bit less than $N$ is. On the verifier side, after computing $\tilde R=\tilde S^e\bmod N$, get back the original $R=\min(\tilde R,N-\tilde R)$.

At the expense of more work, the signer can trim more bits by using a randomized signature scheme (that is, one such that multiple signatures of the same message using the same key are different, because there is randomness in the message representative; an example is RSASSA-PSS of PKCS#1), and signing multiples times until the signature happens to be suitably small (say 16-bit less than $N$ is).

At the expense of more work for the verifier, we can trim still more bits, that the verifier can find by trial and error (says the low-order 24 bits).

So pulling every of these tricks together, the signer will need to make in the order order of $2^{13}$ signatures (I'm assuming the public modulus is chosen on the low side of the interval defined by the modulus size), and the verifiers $2^{23}$ checks (which will remains bearable, especially with $e=3$. Problem is we saved less than 4% (for 1024-bit modulus).

One thing to consider is a RSA signature scheme with message recovery, which squeezes a message in the signature. An example is ISO/IEC 9796-2 which allows about $n-h-16$ bits of message in a signature with $n$-bit public modulus $N$, and a $h$-bit hash; for 1024-bit RSA and SHA-256 that's 94 bytes of message (some of which must be scarified to remains compatible with the tricks above). If there is a message to convey that is near or above that recoverable size, and it does not matter that the message is unintelligible until after the signature has been verified, nothing beats RSA (or Rabin) with message recovery when it comes to compactness.

However, for a really short signature when message recovery won't apply (including when the message to sign needs not be transferred with signature, including e.g. a customer identifier known by the verifier), we need to move away from cryptography based on Integer Factorization

For a long time, the systems giving the shorter signatures have been the Schnorr signature scheme (description and references here), based on the Discrete Logaritm problem, which has $3b$-bit (resp. $4b$-bit) signature for conjectured (resp. proven) $b$-bit security. e.g., for 80-bit conjectured security (sometime compared to 1024-bit RSA), a signature can be 30 bytes.

There are message-recovery variants (references here) which allow to embed a $b$-bit message in a $4b$-bit signature with provable security.

And we can trim some few bits by the same tricks as for RSA, and the same curse that each bit trimmed doubles the effort of one of the signer or verifier.

There's even better, notably Boneh–Lynn–Shacham signature, which approach $2b$-bit signature for $b$-bit security. However, the parameters to use are not easy to find (hence this question), and my understanding is that computational requirements are non-trivial.