Re: Can somebody point me in the right direction?

I am very new to encryption and I was tasked to solve a seemingly common
problem. I don't mind doing the research but I need at least some kind of
direction in the beginning.

My problem is very similar to validating serial keys on software packages.
Here is what I need to accomplish:

1. I need to create a black box that is capable of generating a large number
(let's say 1 million) of fix 10 character length pseudo-random strings
2. I need a second black box that is capable validating those strings that
they were generated by black box one. I think this is pretty standard affair
so far although I have no idea how this is accomplished.
3. Here is the twist: When validating a string I need more than just a
passed/failed result. I need to be able to dig out a value between one and
ten from the ten character string. So box number two would either say no,
this was not generated by box number one or it would spit out a number that
was embedded by box number one.
4. Obviously there should be no way of figuring out what number is embedded
in the string or if it is valid or not without using box number two. A
single person would have only access to a small set of the strings so I
don't think this will be difficult to accomplish.
5. There should be little probability of entering a random character string
that would yield a passing result.

For what little I know about encryption I came up with this scheme that is
most likely totally flawed:

Let' say I needed one hundred thousand strings for each digit between zero
and nine so I would end up with one million ten character strings at the
end.

I figured I would pick a random range of sequential numbers for each one
hundred thousand lot so let's say 0 would have a range of
2,005,000-2,105,000 and 1 would have 46,234,125,000-46,234,225,000 etc.

Once I have a range of numbers then I would encrypt them with some kind of
publicly available encryption algorithm using a fixed password. I can use
leading zeros to try to help the encryption to come up with fixed length
results. Is it possible to produce fixed length results or I would have to
discard some of the resulting string?

Many algorithms use a fixed block size and output encrypted values
with the same block size. Note that most of them work in binary,
so after you get an encrypted result, use uuencode or base64 or
some similar algorithm to turn the result into printable characters.
If the encryption algorithm is reversible (that is, you can decrypt),
different plaintext values will result in different ciphertext values
(no collisions).

I don't know. If I do have to discard
some results, I could extend the original range from 100,000 to 200,000 or
more but I still would know what the last number in the range was when I
have my 100,000 ten character strings.

Here's one approach, which may require more memory than you want.
It's the "one-time-pad" approach.

1. Make up 1,000,000 unique random character strings. Preferably
you use true random numbers here, and no form of pseudo-random
number generator. They don't have to be all the same length, but
that might be easier administratively. Assign a number from 0 to
9 to each string. Put these in a database. You don't have to have
equal numbers of strings for each code if some codes are more in
demand than others. The longer the string and the more varied the
character set for the string, the harder it will be to randomly
guess a valid string.

2. Box 1 contains the database of strings, numbers, and a "This
number has been used" flag. It looks for an unused string with the
correct number, marks it used, and outputs it. Eventually Box 1
is going to have to spit out "I'm out of strings for that number".

3. Box 2 contains a database of strings and numbers. It looks up
the string, and returns the corresponding number. If the string is
not found in the database, it is invalid.

4. If someone breaks into Box 1 or Box 2, game over. The entire
list of numbers may be compromised. On the other hand, someone
who manages to collect a lot of these strings can't guess more of
them by figuring out what encryption algorithm was used and a short
password, since there isn't one.

5. You can add more numbers, or invalidate existing ones, by replacing
the database in Box 1 and Box 2.

At the second black box I would simply decrypt a string with the same
password and see if the result falls into any of the ten ranges that I
originally set up. If the resulting number falls into one of the ranges then
I would know which digit it was used for.

This does, perhaps, have a weakness that only about 20 bits of however many
bits are in the block size of the encryption algorithm you chose, and
the rest are fixed for a given code.

I am a web designer not a mathematician. I am certain that this problem has
been solved a long time ago and published somewhere. I would really
appreciate if somebody could point me in the right direction of how to
approach this problem if my thinking is flawed.

A common use for what you describe is activation keys for proprietary
software, with one big exception: For software, Box 2 is running
on a user's machine and it should be considered a hostile environment.
A large database of valid keys would be found. Code that does the
decryption and checks number ranges could be modified to just expand
the number range to include all possible keys.

Activation keys for features on a web site (yours) is easier since
presumably you can secure your web site better than you can secure
software running on a user's machine.

.

Relevant Pages

  • Re: chances
    ... >> Suppose I have an encrypted text, using some block encryption method, IDEA ... >> or DES or some other. ... >> character strings that might be found during an exaustive search? ...
    (sci.crypt)
  • Can somebody point me in the right direction?
    ... of fix 10 character length pseudo-random strings ... There should be little probability of entering a random character string ... For what little I know about encryption I came up with this scheme that is ... At the second black box I would simply decrypt a string with the same ...
    (sci.crypt)
  • Problem with TEA implementation - help needed
    ... standard libraries for encryption. ... // # both take two parameters, a value and a key as strings, ... // # decrypt by 32 loops. ... private static function stringToHex:String { ...
    (sci.crypt)
  • Re: Help Encrypting Connection String
    ... configuration file. ... encrypt and decrypt arbitrary strings, so that will certainly work for what ... connection strings defined in the configuration if you want. ... >> The biggest decision for you here is how you want to store the encryption ...
    (microsoft.public.dotnet.framework.aspnet.security)
  • Urgent: Trouble with CAPICOM and Triple DES Encryption/Decryption
    ... I am using CAPICOM to encrypt/decrypt strings, but not sure why I am ... Here is the sample VB Code which does the Encryption and Decryption. ... Now, I don't understand, in all the three cases, my Password/Key is ...
    (microsoft.public.platformsdk.security)