Bash Snippet: Luhn Algorithm

27 Feb 2018

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 this value. This saves not only the multiplication step, but also the conditional jump (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
Original post by Chris - check out the source