Yesterday, i was testing some ordering processes at work and needed a Credit Card to continue. I filled out all the fields with random characters to see if i could get with that, but no.. I went through the code to check out the validation and there are 3 things that must be true in order for a Credit Card to be valid before it even considers processing. One of these things was just that it wasn't expired, but the other 2 dealt with the number itself.
Since i was inputting a VISA card, the number had to follow a few conventions. It had to be either 13 or 16 digits long, and had to start with a 4. Our processing software has a bunch of other card types as well, each with their own conventions specifying the length of the number, and the first couple digits prefixing the number.
The real interesting requirement was the number had to follow the Luhn Formula, which i later looked up on wikipedia. The Luhn Formula states that when you double every other number starting from the end up the digit sequence and then add all the digits together, their sum is divisible by 10.
So...
If you have a some random number sequence: a1 a2 a3 a4 a5 a6
Double every other digit starting from the back: 2(a1) a2 2(a3) a4 2(a5) a6
Add them all together: 2(a1) + a2 + 2(a3) + a4 + 2(a5) + a6
They should be divisble by 10: (2(a1) + a2 + 2(a3) + a4 + 2(a5) + a6) % 10 = 0 (formula 1)
Moving some things around we'd get this formula if the number of digits are even: ( 2(a(1..n odd)) + a(2..n even) ) % 10 = 0
So.... this is how i needed to derive my fake Visa number to continue along the ordering process. I began using the conventions defined with the card type, so that gave me this template: 4xxx xxxx xxxx xxxx.
Since we take every other digits, let's split up the variables a little bit: 4xyx yxyx yxyx yxyx.
Plugging this number into our formula, gives us ( 2(4 + 7y) + 8x ) % 10 = 0 or ( 8 + 14y + 8x ) % 10 = 0 or ( 4 + 7y + 4x ) % 5 = 0 (formula 2)
That 7 is rather annoying, but we've already hit prime with the 5, so you can't really reduce it much further. Luckily it's in a cute little formula that we could just plug in numbers to find something simple.. This is, of course, if we wanted all x to be the same and all y to be the same. Otherwise formula 2 would be formula 1.
Anywho.. looking at formula 2 for a few seconds may give you an answer. if y = 1 and x = 1, it succeeds. I've got my fake Visa number 4111 1111 1111 1111, but you could go the easy route and have y = 0 and find x = 4, or x = 0 and find y = 3.
I suppose it would've been easily if i kept my number as 4xxx xxxx xxxx xxxx. Then i would've found ( 4 + 11x ) % 5 = 0, and found x = 1 very quickly.. or that i could use x = 6 too.
After looking into this stuff, i've realized just how insecure this whole system is. It's pretty easy to make up a fake Visa number, but taking a look at that wikipedia article, the Luhn Formula is not meant for encryption, just validation. Just a little housekeeping, so someone doesn't screw up and type a 5 rather than a 6 and still get a valid number. This is used for all credit card numbers too, so if you're bored why not double check your Visa number to see if its valid.
Math is everywhere ^_^