Secrets of the LUHN-10 Algorithm - An Error Detection Method
One of the most widely used algorithms for character-based error control is known as the LUHN-10 Algorithm. This simple but effective error detection method is commonly used by companies and organizations when issuing account and membership numbers. The algorithm is specified in the ISO-7812-1 standard defining a common format for credit cards.
Like the ISBN used for book identification, the credit card number shown below is specially constructed to incorporate error detection. In particular, the final digit is included only as an error control mechanism.
This credit card number holds a secret.
Error control codes are often designed for known applications
where certain types of errors are expected to occur.
In this case, the most common errors expected would be those
which humans would typically make when writing or typing the number or
entering it on a web site.
These errors would normally be either "write a single digit incorrectly",
or "switch two adjacent digits". Of course, the ability to detect
errors also provides a simple test to identify invalid numbers which might be
encountered (for example, if someone were to forge a credit card number).
The final digit in the number provides the desired error
detection capability. It is computed when the number is issued
so that the entire value can be checked for errors whenever it is transcribed or transmitted.
4563 9601 2200 1999
The final digit is appended for error control.
One Possible Approach - Checksum "Modulo 10"
Consider a simple scheme in which the first digits are simply added up and the sum (or rather the 'ones' digit
in the sum) is used as the final digit. For example, with 4563 9601 2200 199_ the sum is 57 so the final digit would be '7':
4 5 6 3 9 6 0 1 2 2 0 0 1 9 9 7
4 + 5 + 6 + 3 + 9 + 6 + 0 + 1 + 2 + 2 + 0 + 0 + 1 + 9 + 9 = 57
If any single digit is written incorrectly,
this scheme will detect that error; however, if two digits are
switched with each other, the sum will not be affected and that
error would go undetected. Although this simple 'checksum' does
provide some error detection, it is not good enough for this application.
Modulus Arithmetic
Note that taking only the last digit in a decimal number is
equivalent to dividing the number by 10 and using only the remainder.
This result is also referred to the sum "modulo 10". This is generally written as:
57 ≡ 7 (mod 10)
After division by 10, the remainder is 7.
How the LUHN-10 Algorithm Works
If a 'weighted sum' is constructed by multiplying adjacent digits
by a different constant (in this case, either 1 or 2) the problem of adjacent swapped digits going undetected can be eliminated. A checksum is
constructed from the sum of the resulting digits. If a product
results in two digits (e.g. 2x6=12), the individual digits (1 and 2) are added separately into the checksum.
The final digit is computed so that the weighted sum is an exact multiple of 10.
In other words, the overall sum "modulus 10"
equals zero. In this case, 70 is an exact multiple of ten.
4 5 6 3 9 6 0 1 2 2 0 0 1 9 9 9
x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
8 5 12 3 18 6 0 1 4 2 0 0 2 9 18 9
8 + 5 +1+2+ 3 +1+8+ 6 + 0 + 1 + 4 + 2 + 0 + 0 + 2 + 9 +1+8+ 9 = 70
70 ≡ 0 (mod 10)
The number is correct if a zero result is obtained.
It is important when applying this method to numbers of different
lengths that the rightmost digit (the check digit) is arranged to be multiplied by 1.
It can be observed that the presence or absence of leading zeros in a number to be checked has no effect on the result. (e.g. 8913105 or 08913105 or 00008913105 would all pass the test)
PERFORMANCE ANALYSIS
The contribution of a given digit to the total sum depends on its
position in the number and, specifically, whether it is multipled by 1 or 2.
DIGITS 0 1 2 3 4 5 6 7 8 9
-------------------
Contribution (x1) 0 1 2 3 4 5 6 7 8 9
Contribution (x2) 0 2 4 6 8 1 3 5 7 9
Contribution of LUHN-10 digits to the summation.
1. Single Bad Digit
If a single digit is changed to another, the total sum must change, whether or not that digit is multiplied by 2. A single-digit error is always detected as each possible digit has a unique contribution and the sum cannot change by a multiple of 10.
2. Adjacent Digits Switched (e.g. 34 becomes 43)
The LUHN-10 method is not perfect in detecting swapped digits. Although swapping two adjacent digits will generally result in a checksum failure, there are cases which will not be detected.
From the table above, it can be seen that the contribution of the
digits 9 and 0 do not change with position. If the digits 9 and 0 are side-by-side and get swapped, their contribution to the total sum will be the same.
... 9 0... ... 0 9...
... x1 x2... ... x1 x2...
-- -- -- --
9 0 0 18
9 + 0 = 9 0 +1+8 = 9
It can be argued that for all possible two digit values (00..99) there are 90 cases of two different digits side by side and that the algorithm will fail to detect swapped digits in two of these cases ('09' becomes '90', and '90' becomes '09'). Consequently, swapped digits will be detected 88 times out of 90 (97.8%).
If two non-adjacent digits are swapped, either the change is not detected at
all (if they are both multiplied by 1, or both by 2), or the situation is
identical to swapping adjacent digits.
WORST CASE PERFORMANCE
If a LUHN-10 protected number is totally garbled (or forged!), the use of modulus 10 implies that there is one chance in ten that the (random) number will
nonetheless pass the error detection test. Conversely, there are 9 chances out
of 10 that the error will be detected. Consequently, while single-digit errors are all detected and most swapped adjacent digits can be detected, other types of errors should be detected with 9/10 = 90% reliability.
Applications of LUHN-10
It is interesting to note the number and variety of different
applications which make use of the exact same method of error detection.
Of course, since LUHN-10 is not used for authentication there is no
reason why different credit cards, for example, would not use a standard error control method. Many
software packages use the above test as a preliminary verification on a website or data
terminal before submitting an account number for final authorization.
The following applications use LUHN-10 in their client numbers:
- Virtually all credit card numbers (MasterCard, Visa, American Express)
- Canadian SIN - Social Insurance Numbers (9 digits)
- Canadian GST/HST Registration Numbers (9 digits) - Found on receipts as 'R123456789'
- Province of NB Medicare Numbers (9 digits)
- Mobile Phone IMEI (International Mobile Equipment Identity) number
(15 digits)
Perhaps the most 'public' source of numbers to check in Canada is found in the GST/HST registration number, as every merchant is required to print this nine-digit tax number on all sales receipts.
Try the EE4253 Online LUHN-10 Checking Tool
Conclusions
A systematic approach to error detection can lead to better codes.
Both the simple checksum and the LUHN-10 method involve adding only one
additional digit, yet the latter method is more effective as swapped
adjacent digits can also be detected.