Generate a random code that can be validated later

I need to generate a verification code and send it to a customer, so that the开发者_JAVA技巧 customer can then provide the code later and I validate it. I want to be able to do this without storing the verification codes in a database, i.e., the codes should be self-containted.

How can I generate the code and prevent the customer from just guessing what a valid code is? Obviously, I can't completely rule out a lucky guess, but I want the probability of such an event to be reasonably small, while keeping the code length small. A code may contain digits and letters.

For example, a very basic verification code would be like this: randomly generate the number 1122. Now, compute the verification code 11226 ( 1122 and append its checksum 6=1+1+2+2). So, if the customer sends back 11226 back I would be able to validate it, but of course this is too easy to tamper with. Is there a method to generate such codes?

EDIT: The problem is that the system which sends the verification code and the system where the verification code is validated are separated, no information is shared between these two systems. There is no way that even the randomly generated number (1122 in the example) is known to the validation system. Let me give you another example: in my country, there is a thing called "Orange Wednesday". You can get 2 movie tickets for the price of one if you have a code received by SMS (you send a SMS and receive a code by SMS if you are Orange customer). However, this code is not tied to anything (phone number or similar): I can give the code to someone else and it is still valid. I would need this kind of verification code.

What you are looking for can be implemented using Message Authentication Codes (MAC):

The key observations to make are:

1. The secret key (which only you know) is required to generate and validate MAC codes.
2. The MAC code produced is tinkering-proof, i.e. an attacker is not able to tell what impact a given modification to the (message, MAC) tuple may have.
3. No information needs to be stored outside of the message flow, except for the secret key.

In your scenario, you can use any arbitrary message since your only requirement is to verify that the input you receive from a customer was originally generated by you. You can do this by

• settling for some kind of pattern, e.g. generate only codes that start with 012345679xxxxxxx, or simply take the date encoded as "dd.mm.yyyy hh:mm:ss" for your 'arbitrary message'.
• use random numbers that are long enough and store which codes have actually been generated by you. However, you seemed to be looking for a solution that does not depend on databases.

What you are suggesting is the use of a check digit. The problem is that the system can be "figured out" and new working codes produced fairly easily. Having a database would allow you to keep track of which codes have been sent out and to make sure that the codes coming back to you have actually been sent out. Check out also Luhn's algorithm, from the links section of the above Wikipedia article.

You could digitally sign the customer's name (for example) using public key cryptography. On your server, you'd store a private signing key, which the customer would send to you for registration. Once there, you could sign it and send it back to customer. Validating the code would boil down to checking a signature against your public key. Of course this would do nothing to deter stuff like spoofing another customer's information but at least it would certify that for any given customer name, whether you did authorize them -- and you wouldn't need to store a huge database of all your customers (though why you don't want to store a database is beyond me, since you'd probably need all that data for legal/financial record keeping purposes at least.)