Serial numbers generation without user data

This is a followup to this question.

The accepted answer is generally sufficient, but requires user to supply personal information (e.g. name) for generating the key.

I'm wondering if it's possible to generate different keys based on a common seed, in a way that program would be able to validate if those keys belong to particular product, b开发者_StackOverflow中文版ut without making this process obvious to the end user.

I mean it could be a hash of product ID plus some random sequence of characters, but that would allow user to guess potential new keys. There should be some sort of algorithm difficult to guess.

The problem with standard symmetric/asymetric/hash algorithms (MDx, SHAx, RSA, etc.) is they cannot operate on very short strings like a 20/30 characters-long product key strings. If you can give your users ~1000 characters-long strings, then I would go for these algorithms.

If you can't, here is some C# code that is capable of building an "almost-totally-random" short product key, but with a hidden byte in it. You can put anything you want in that "hidden byte" and the key follows some algorithm that is not so easy to guess. You can validate a passed in string & reread the byte using the TryReadKey() like this:

string key = BuildKey(myHiddenByte); // give that to the end user
...
byte hidden;
if (!TryReadKey(key, out hidden))
{
   Console.WriteLine("key is not ok");
}
else
{
   Console.WriteLine("key is ok and hidden byte is " + hidden);
}

The algorithm uses Steganography principles, is certainly not bullet-proof and could be improved, but can be useful. Note key generation can take some time, it's normal. It produces keys like this (note the first word is 6 chars long, the other 5 chars long):

KZGMB0-XYJC2-YRKH3-8LD8G-5FUZG
YKU93K-M34PD-E5PL0-QM91J-QLDZF
DH27H9-NCW8E-EMGPL-YCJXJ-N2PRG
WDAKDE-G56NR-6BA3R-0JE6U-625EB
6D5EJ0-NJDAK-EMGZR-Z6ZDF-JHJGF
....

Here is the code:

    // need 32 characters, so we can use a 5-bit base encoding
    //                               0         1         2         3
    //                               01234567890123456789012345678901
    private const string KeyChars = "ABCDEFGHJKLMNPQRTUWXYZ0123456789";
    private const int MinSum = 2000;
    private const int Mask = 0xFFFFF;  // beware, this can have a dramatic influence on performance

    /// <summary>
    /// Builds a key and hides data in it.
    /// Key format is XXXXXX-XXXXX-XXXXX-XXXXX-XXXXX.
    /// </summary>
    /// <param name="hiddenData">The hidden data.</param>
    /// <returns>The build key</returns>
    public static string BuildKey(byte hiddenData)
    {
        int index;
        Guid guid;
        uint[] word = new uint[4];
        byte[] array;
        while (true)
        {
            // we use guid initial randomness characteristics
            guid = Guid.NewGuid();
            array = guid.ToByteArray();

            int sum = array.Aggregate(0, (current, b) => current + b);

            // a simple check to make sure the guid is not filled with too much zeros...
            if (sum < MinSum)
                continue;

            // build a 32-bit word array
            for (int i = 0; i < 4; i++)
            {
                word[i] = BitConverter.ToUInt32(array, i * 4) & Mask;
            }

            // Here we check the guid follows some algorithm. if it doesn't we skip it
            // the algorithm presented here is to check one of the 32-bit word is equal to the sum of the others
            // (modulo a mask otherwise it takes too long!)
            //
            // This algorithm can be changed at your will (and change the TryReadKey as well)

            if ((word[0] + word[1] + word[2]) == word[3])
            {
                index = 3;
                break;
            }

            if ((word[0] + word[1] + word[3]) == word[2])
            {
                index = 2;
                break;
            }

            if ((word[0] + word[3] + word[2]) == word[1])
            {
                index = 1;
                break;
            }

            if ((word[3] + word[1] + word[2]) == word[0])
            {
                index = 0;
                break;
            }
        }

        // hidden info is also xor'd with other words hi order (except the one we masked)
        // so it's not too easy to guess
        hiddenData = (byte)(hiddenData ^ array[0] ^ array[4] ^ array[8] ^ array[12]);

        // rebuild words without mask
        for (int i = 0; i < 4; i++)
        {
            word[i] = BitConverter.ToUInt32(array, i * 4);
        }

        // hidden info is stored in the block that is the sum of other blocks, in hi order byte (outside the mask)
        word[index] &= 0x00FFFFFF;
        word[index] |= ((uint)hiddenData) << 24;

        // rebuild the array back
        for (int i = 0; i < 4; i++)
        {
            byte[] ui = BitConverter.GetBytes(word[i]);
            for (int j = 0; j < 4; j++)
            {
                array[i * 4 + j] = ui[j];
            }
        }

        // now use 5-bits encoding
        int encodingBitIndex = 0;
        StringBuilder key = new StringBuilder();
        while (encodingBitIndex < 128)
        {
            byte encodingByte = Get5Bits(array, encodingBitIndex);
            if ((key.Length > 0) && (key.Length % 6) == 0)
            {
                key.Append('-');
            }
            key.Append(KeyChars[encodingByte]);
            encodingBitIndex += 5;
        }
        return key.ToString();
    }

    /// <summary>
    /// Validates the specified key and reads hidden data from it.
    /// </summary>
    /// <param name="key">The key.</param>
    /// <param name="hiddenData">The hidden data.</param>
    /// <returns>true if the key is valid and hidden data was read; false otherwise.</returns>
    public static bool TryReadKey(string key, out byte hiddenData)
    {
        hiddenData = 0;
        if (key == null)
            return false;

        key = key.Replace("-", string.Empty);
        if (key.Length != 26)
            return false;

        byte[] array = new byte[16];
        int encodingBitIndex = 0;
        foreach (char t in key)
        {
            byte b = 255;
            for (byte k = 0; k < KeyChars.Length; k++)
            {
                if (KeyChars[k] != t) continue;
                b = k;
                break;
            }
            if (b == 255) // char not found
                return false;

            Put5Bits(array, encodingBitIndex, b);
            encodingBitIndex += 5;
        }

        // quick sum check
        int sum = array.Aggregate(0, (current, b) => current + b);

        // add 256 because we changed the hidden byte
        sum += 256;
        if (sum < MinSum)
            return false;

        uint[] word = new uint[4];
        for (int i = 0; i < 4; i++)
        {
            word[i] = BitConverter.ToUInt32(array, i * 4) & Mask;
        }

        // This must match BuildKey algorithm

        int index;
        if ((word[0] + word[1] + word[2]) == word[3])
        {
            index = 3;
        }
        else if ((word[0] + word[1] + word[3]) == word[2])
        {
            index = 2;
        }
        else if ((word[0] + word[3] + word[2]) == word[1])
        {
            index = 1;
        }
        else if ((word[3] + word[1] + word[2]) == word[0])
        {
            index = 0;
        }
        else
            return false;

        // reread word & extract hidden byte back
        word[index] = BitConverter.ToUInt32(array, index * 4);
        hiddenData = (byte)(word[index] >> 24);
        hiddenData = (byte)(hiddenData ^ array[0] ^ array[4] ^ array[8] ^ array[12]);
        return true;
    }

    // get 5 bits from a byte buffer at an arbitrary bit index
    private static byte Get5Bits(byte[] buffer, int bitIndex)
    {
        int r = bitIndex % 8;
        if (r < 4)
            return (byte)(((buffer[bitIndex / 8]) & (0xFF >> r)) >> (3 - r));

        byte b0 = (byte)((buffer[bitIndex / 8] & (0xFF >> r)) << (r - 3));
        if ((1 + (bitIndex / 8)) == buffer.Length) // last
            return (byte)(buffer[buffer.Length - 1] & 0x7);

        if ((bitIndex / 8) < 16)
            return (byte)(b0 | buffer[1 + (bitIndex / 8)] >> (11 - r));

        return b0;
    }

    // put 5 bits into a byte buffer at an arbitrary bit index
    private static void Put5Bits(byte[] buffer, int bitIndex, byte value)
    {
        int r = bitIndex % 8;
        if (r < 4)
        {
            buffer[bitIndex / 8] |= (byte)((value << (3 - r)));
        }
        else
        {
            if ((1 + (bitIndex / 8)) == buffer.Length) // last
            {
                buffer[buffer.Length - 1] |= (byte)(value & 0x7);
            }
            else if ((bitIndex / 8) < 16)
            {
                buffer[bitIndex / 8] |= (byte)((value >> (r - 3)));
                buffer[1 + (bitIndex / 8)] |= (byte)((value << (11 - r)));
            }
        }
    }

You can use digital signature, generated by your key, and with public key inserted into your program.