Re: reversible whole number license key

From: Mark Wooding (mdw_at_nsict.org)
Date: 08/05/03 

Date: 5 Aug 2003 12:59:18 GMT

Thor Russell <thor.russell@paradise.net.nz> wrote:

> I tried using a matrix multiply for each digit, making a vector out of
> them, but the inverse matrix is ugly, not consisting of whole numbers.
> Any ideas?

Going with the matrix for a bit: you could do the matrix arithmetic mod
10, instead of over real numbers. Invertable matrices mod 10 shouldn't
be hard to find. The only trick is that you need to use the extended
Euclidean algorithm to compute the multiplicative inverses of the
individual elements. If that sounds baffling, maybe
<http://www.wikipedia.org/wiki/Extended_Euclidean_algorithm> will
explain things.

Gathering 9 different (linearly-independent) codes will be enough to
allow someone to compute the matrix. I suspect that this isn't of
concern -- after all, the matrix will be in the code anyway, and it's
not that hard to just turn of the check.

Alternatively, you can use some real cryptography. Note that 32-bit
numbers fit in 10 digits. Stash the seat count (and maybe other stuff)
in the bottom l bits. Add t random bits. Now, pad that with zeros and
psuh it through your favourite block cipher (e.g., AES, DES, whatever
you think is easy to get hold of or implement) with some `secret'[1]
key. Glue the answer on to the seat count and random data, and grab the
first 32 bits (so we have (32 - t - l) bits of block cipher output, t
bits of random stuff, and l bits of seat count and other information).
Checking is basically the same process. Assuming that the block cipher
is a pseudorandom function, guessing a correct code without knowing the
key happens with probability at most 2^{32 - t - l}. (The random string
is to make copies of the same thing look different.)

[1] Not that secret. Your program will know it.

-- [mdw]