Luhn Algorithm

There are many occasions where we need to check that a number such as a barcode or a credit card number has been recorded correctly. It might be as it has been typed in wrongly, or that some automated system has had a glitch which corrupted data. The validation is done ‘on device’ and does not require some central authority (like a bank). Indeed, the very point is to limit the load on the central authority of processing typos.

If the number is invalid, an automated system quickly scans again, or a person might be asked to retype. Only once a number is found to be valid it can then be passed onto the bank for processing and validation.

With credit cards, a method called the Luhn algorithm is used.

It does not provide protection against a malicious attacker, that is not the intent; what it does do is provide a quick check against error.

If we look at a string of digits, we treat the digits in the even and odd locations separately, and start evaluating right to left.

So, let us imagine a credit card number 123456789012345x, x is known as the ‘checksum’ - and is determined by all the other digits.

We work from the right. Any digit in an ‘odd’ position is left alone. Anything in an ‘even’ position is doubled. If doubling produces a number 10 or above, subtract 9 (this is equivalent to adding the digits of the doubled number).

View fullsize

Diagram of the Luhn Algorithm (Photo Credit: Me)

If we then add all the resulting digits, we get a total of 58. For the overall number to pass the Luhn test as valid, this total should be a multiple of 10. Thus we set x to be equal to 2, and 1234567890123452 is a valid credit card number.

A random error in this number cause it to be rejected. You would need two errors, that cancel out, for it to be passed as valid.

Being valid, however, does not allow it to be used. The card number, if valid, is checked against the issuing bank, verified with chip and pin or with CVV (the three numbers on the back).

I’ve put the code below.

Links

• Source of title image (cropped, used under CC BY-SA 4.0)

• Luhn algorithm (Wikipedia)

• Impuls Imaging on the Luhn algorithm

• Nextbit on Luhn

• Fake credit card numbers used in the code

• Patent US2950048A

• More Cryptography

Recent Cryptography Posts

Extension

Here is some Python 3 code that checks credit card numbers for validity. The code includes some fake but valid credit card numbers, I have added some invalid numbers just for fun, and I have also included the number used above to check that I’d worked through the example correctly.

## This checks to see if a credit card has a valid number
## Luhn encoding does this. Every other digit is multiplied by 2
## then all the digits are added
## When doubling digits, any result 10 or above has digits summed
## this can be done by subtracting 9

## If the result of all this is not a multiple of 10, it is invalid.

def checkLuhn(claimedCC=''):
    sum = 0
    # this is whether we deal with odd or even number of bits
    # as which digit is doubled starts from the right end of
    # the number
    parity = len(claimedCC) % 2
    for i, digit in enumerate([int(x) for x in claimedCC]):
        if i % 2 == parity:
            digit *= 2
            if digit > 9:
                digit -= 9
        sum += digit
    return sum % 10 == 0

def showLuhn(CardToCheck=''):
    i=0
    toprint=''
    for char in CardToCheck:
        i+=1
        toprint+=char
        if i%4 == 0:
            toprint+=' '
    if toprint[-1] != ' ':
        toprint+=' '
    print(toprint,end='')
    if checkLuhn(CardToCheck):
        print('is Valid')
    else:
        print('is INVALID')
    return


# via https://www.darkcoding.net/credit-card-numbers/

# Mastercard
cards=['5576983017214289',
       '5185093691308747',
       '5344110352861547',
       '5409064311100316',
       '5409064611100316',
       '5115674764759414',
       '5233702474653481',
       '5255997912340435',
       '5257058418323588',
       '5490131296307951',
       '5275501660740295',
       '5257058418723588',
# VISA 16 digit
       '4485881658889489',
       '4916789071499530',
       '4929783352485644',
       '4716328163321559',
       '4929874845109193',
       '4929875845109193',
       '4556649514432650',
       '4916222283285299',
       '4556649514432560',
       '4916674801405991',
       '4485043945932537',
       '4539812881394092',
# VISA 13 digit
       '4539043659997',
       '4532800548214',
       '4929910384939',
       '4929810384939',
       '4240663728317',
       '4916092865883',
# American Express
       '343630787633627',
       '349633586383455',
       '378988730624038',
       '378988730624058',
       '375495456031243',
       '370197962392193',
# Discover
       '6011434921721697',
       '6011982509270321',
       '6011084672406905',
# Diners Club
       '30005500544864',
       '30131784916550',
       '30115599761293',
# enRoute
       '214991936421108',
       '214941552100080',
       '214960375164701',
# JCB
       '3521762753010114',
       '3589167184187615',
       '3589163184187615',
       '3581040372683968',
# Voyager
       '869923035562373',
       '869938341879873',
       '869971069458307',
# Example
       '1234567890123452'
       ]

for card in cards:
    showLuhn(card)