Luhn algorithm (★★)

Today, I am going to talk about Luhn algorithm, the algorithm running behind credit cards numbers, IMEI (US), INSEE, SIRET codes.

Algorithm: Word used by programmers when they don't want to explain what they did

Don't worry, I'll try to explain as clearly as I can how this algorithm works and why it has been invented !

A bit of history...

Luhn algorithm is a checksum formula used to validate a variety of identification numbers in the world such as credit card numbers or companies codes. It was invented in 1954 by the German IBM researcher Hans Peter Luhn.

Its main purpose was to protect against accidental errors (mystiped or reversed figures for example), not malicious attacks.

How does the algorithm actually work ?

An example with credit card numbers

Classic credit cards have 16 digits. Here are the steps applied by the algorithm to check the 16 digits credit card :

1. Drop the last digit from the card number. The last digit (16th position) is called Luhn key.
2. Evaluate each digit from right to left. When the digit is in odd positions, we multiply it by 2. If, in addition, the digit is superior or equal to 5, we simply substract 9 from the previous multiplication (only applicable for odd ranks).
3. Add all the numbers together
4. Compute the Luhn Key. This (last) digit is the amount that you would need to add to the previous total (computed above in step 3) to get a multiple of 10 (Modulo 10). This Luhn key has to be equal to the last digit which has been removed in step 1.

Important note : I have chosen this example because it is probably the easiest and most universal. My goal is not to teach you how to hack credit cards... You would need much more information anyway (cryptogram, expiration date for example) ! I just try sometimes on this blog to make a link between real life and programming/data.

A solution in VBA

So now, we are going to program this algorithm in VBA in order to generate fake credit card numbers (16 digits). Considering the logic above we will :

1. Randomly generate the first 15 digits of the credit card number
2. Apply the "multiply and substract" rule (step 2 above)
3. Calculate the relevant sum
4. Compute the correct Luhn key

You will find below a suggestion I wrote in VBA. The code is commented :

Sub Luhn_Generator() 

Dim digit As Integer, i As Integer, Luhn_Key As Integer, Total As Integer
Dim Code As String

' Clearing the previous code
ActiveSheet.Cells(1, 1).ClearContents

' Initializing VBA random
Randomize

' Generating the first 15 digits of the credit card number (code) - from right to left
For i = 1 To 15
 digit = Int(Rnd * 10) ' by using randomize
 Code = digit & Code ' Creating the code by concatening the new figure with    previous code
 If i Mod 2 <> 0 Then
  If digit >= 5 Then
   digit = 2 * digit - 9 ' when the rank of the generated figure is odd and superior or equal to 5, then we multiply the figure by 2 and substract 9
   Else: digit = 2 * digit ' If it is just odd, we simply multiply it by 2
  End If
End If
Total = Total + digit ' Calculating the total by following Luhn's logic

Next i

' Computing Luhn key (check digit, 16th and last figure of the code) by making sure Total + Luhn_Key can be divided by 10
Luhn_Key = Application.WorksheetFunction.RoundUp(Total, -1) - Total

' Concatening the credit card number with its Luhn key. I am using "'" to get rid of format issues since the code now has 16 characters !
Code = "'" & Code & Luhn_Key

' Displaying the credit card number
ActiveSheet.Cells(1, 1).Value = Code

End Sub

Good to know

- The first 4 digits of your credit card actually depend on your bank and the number of digits (n) may vary with your type of card (Visa, American Express, Mastercard...). Another proof that I am not trying to teach you how to hack credit cards :)

- the French Serge Humpish was sent to jail in 2000 for proving the weaknesses of the application of Luhn Algorithm for credit cards. He wrote a book "Le Cerveau Bleu" (Blue Brain) in 2001 to explain how he discovered the flaw in the credit cards system.

Going further

Now you have this VBA code above, maybe you could try to write a code in order to :

1. Check if a given 16-digit number follows Luhn algorithm
2. Apply the same logic to generate other codes such as INSEE, IMEI, SIRET, etc.
3. A bit harder : List all the possible combinations for a given Luhn key and bank.

I would also be interested to see your solutions in other programming languages such as R, Python, C# ...

Final question : why the hell did I choose a moon as a featured image for this article ?  (Hint : I am French)

This article was originally posted on my blog. The variables in the code and the comments are easier to read and identify thanks to the use of colours / better indentation.

Feel free to share & comment !

★ Beginner    ★★ Intermediary     ★★★ Advanced