Bash Snippet: Luhn Algorithm

I like Bash, but it isn’t well suited for some tasks. For fun I sometimes ignore that. Occasionally people seem to find this useful.

In that spirit, here is my implementation of the popular Luhn / mod10 algorithm used in credit card, IMEI, and other number sequences.

download [luhn.zip]

# Returns Luhn checksum for supplied sequence
luhn_checksum() {
sequence="$1"
sequence="${sequence//[^0-9]}" # numbers only plz
checksum=0
table=(0 2 4 6 8 1 3 5 7 9)

# Quicker to work with even number of digits
# prepend a "0" to sequence if uneven
i=${#sequence}
if [ $(($i % 2)) -ne 0 ]; then
sequence="0$sequence"
((++i))
fi

while [ $i -ne 0 ];
do
# sum up the individual digits, do extra stuff w/every other digit
checksum="$(($checksum + ${sequence:$((i - 1)):1}))" # Last digit
# for every other digit, double the value before adding the digit
# if the doubled value is over 9, subtract 9
checksum="$(($checksum + ${table[${sequence:$((i - 2)):1}]}))" # Second to last digit
i=$((i - 2))

done
checksum="$(($checksum % 10))" # mod 10 the sum to get single digit checksum
echo "$checksum"
}

# Returns Luhn check digit for supplied sequence
luhn_checkdigit() {
check_digit=$(luhn_checksum "${1}0")
if [ $check_digit -ne 0 ]; then
check_digit=$((10 - $check_digit))
fi
echo "$check_digit"
}

# Tests if last digit is the correct Luhn check digit for the sequence
# Returns true if valid, false if not
luhn_test() {
if [ "$(luhn_checksum $1)" == "0" ]; then
return 0
else
return 1
fi
}

To maximize the enjoyment I’ve optimized the script a little bit in two ways:

1) Normally every other digit of the sequence to be computed is multiplied by 2. If that result is greater than 9, then 9 is subtracted. There are only 10 single digits in base-10, so it seemed reasonable to precompute these values. This saves not only the multiplication step, but also the conditional branch (on greater/less than 9), and the occasional subtraction operation (when values were greater than 9).

2) I prepend a 0 to the submitted sequence if there are an uneven number of digits in the sequence. The leading 0 doesn’t affect the end result, but being assured of having pairs of digits available in the while loop of our luhn_checksum() function saves us from needing to keep track of which digits should be added directly and which should be handled as described in optimization #1 above.

If for some reason you are actually using this script, you probably will be most interested in luhn_checkdigit() and luhn_test().

Here is an example of how this can be used:

#!/bin/bash
source luhn.sh

# Example IMEI number from Wikipedia
sample_imei="352152097374972"
if luhn_test "$sample_imei"; then
echo "$sample_imei might be a valid IMEI"
else
echo "$sample_imei is an invalid IMEI"
fi

# Same number with the last two digits transposed
sample_imei="352152097374927"
if luhn_test "$sample_imei"; then
echo "$sample_imei might be a valid IMEI"
else
echo "$sample_imei is an invalid IMEI"
fi

# Creating a check digit for a set of numbers
echo "35215209737497 would be a valid looking IMEI if you added a $(luhn_checkdigit "35215209737497") to the end"

# Many credit card types also use this checksum
sample_mastercard="5105105105105100"
if luhn_test "$sample_mastercard"; then
echo "$sample_mastercard might be a valid card number"
else
echo "$sample_mastercard in an invalid card number"
fi

user@host:~$ ./demo.sh
352152097374972 might be a valid IMEI
352152097374927 is an invalid IMEI
35215209737497 would be a valid looking IMEI if you added a 2 to the end
5105105105105100 might be a valid card number

Categories:Bash