How to generate a verification code/number?

Question

I'm working on an application where users have to make a call and type a verification number with the keypad of their phone.

I would like to be able to detect if the number they type is correct or not. The phone system does not have access to a list of valid numbers, but instead, it will validate the number against an algorithm (like a credit card number).

Here are some of the requirements :

• It must be difficult to type a valid random code
• It must be difficult to have a valid code if I make a typo (transposition of digits, wrong digit)
• I must have a reasonable number of possible combinations (let's say 1M)
• The code must be as short as possible, to avoid errors from the user

Given these requirements, how would you generate such a number?

EDIT :

@Haaked: The code has to be numerical because the user types it with its phone.

@matt b: On the first step, the code is displayed on a Web page, the second step is to call and type in the code. I don't know the user's phone number.

Followup : I've found several algorithms to check the validity of numbers (See this interesting Google Code project : checkDigits).

Answer 1

After some research, I think I'll go with the ISO 7064 Mod 97,10 formula. It seems pretty solid as it is used to validate IBAN (International Bank Account Number).

The formula is very simple:

1. Take a number : 123456
2. Apply the following formula to obtain the 2 digits checksum : mod(98 - mod(number * 100, 97), 97) => 76
3. Concat number and checksum to obtain the code => 12345676
4. To validate a code, verify that mod(code, 97) == 1

Test :

• mod(12345676, 97) = 1 => GOOD
• mod(21345676, 97) = 50 => BAD !
• mod(12345678, 97) = 10 => BAD !

Apparently, this algorithm catches most of the errors.

Another interesting option was the Verhoeff algorithm. It has only one verification digit and is more difficult to implement (compared to the simple formula above).