Luhn algorithm (★★)

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 substract9 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 credit cards 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 (from right to left)
  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) ‘ Generating an integer between 0 and 9 (digit) by using randomize
  Code = digit & Code ‘ Creating the code by concatening the new figure with the previous    code
If i Mod 2 <> 0 Then ‘ When the rank of the generated figure is odd
If digit >= 5 Then    ‘ If the digit is superior or equal to 5
        digit= 2 * digit– 9 ‘ We multiply it by 2 and substract 9 from it
Else: digit = 2 * digit ‘ Otherwise, we simply multiply it by 2
End If
    End If
  Total = Totaldigit ‘ 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)

Interested in this article ? Please feel free to share and comment !

★ Beginner    ★★ Intermediary     ★★★ Advanced

 

 

Advertisements

2 thoughts on “Luhn algorithm (★★)

  1. “Word used by programmers when they don’t want to explain what they did” – ha ha that’s good. Nice article. I use Luhn algorithm using VBA and another version using M to validate ISIN and Sedol. It’s actually tough to write a function in either flavour that is fast. See here for M, and here for VBA.

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s