How does Luhn algorithim actually work?

Question

I learned about the luhn algorithim from this source: https://en.wikipedia.org/wiki/Luhn_algorithm

I understand the formula. If my understanding is correct, credit card companies will add a checksum number such that it satisfies the mod 10 formula. I have a few questions though and it might have one answer.

Why does this work? Seems pretty random to me to be multiplying each second number and adding it up with the checksum just satisfies this mod 10.

Also, the wiki page says it works for SSN numbers as well. How does that happen? Is there a checksum number for SSN as well?

Does everyone (banks, SSN providers, etc) compose their numbers such that it just has to pass Luhn algorithim?

Answer 1

Does everyone (banks, SSN providers, etc) compose their numbers such that it just has to pass Luhn algorithm?

Yes, exactly. (Well, not everyone - but that's how institutions that use the algorithm do it.) The algorithm works only for numbers chosen so that it works.

In other words, banks and other institutions that use it generate a partial identification number (in whichever way they like), use Luhn's algorithm to compute a check digit, and then append that to the partial number to get the full identification number.

Then the identification number can be verified by using Luhn's algorithm again to see if the check digit is correct.

The US social security numbers do not include a check digit (chosen by Luhn's algorithm or in any other way) but the Social Insurance Numbers issued by Canada do, as well as several others listed in the article.

Seems pretty random to me to be multiplying each second number and adding it up with the checksum just satisfies this mod 10.

In some ways this algorithm is very arbitrary, but the goal of all checksum algorithms is to make sure that when common errors are made in writing down the number, the checksum will become invalid.

The Wikipedia algorithm mentions that single-digit errors, and almost all transpositions of adjacent digits, are detected by Luhn's algorithm.

Answer 2

The reasoning behind this way to create check digits is that "multiply the digit by 2 and add the digits of the result" corresponds to permuting the ten possible digits:

$$ \begin{array}{l|c} \text{Original digit }d & 0 & 1 & 2& 3& 4 & 5& 6& 7 & 8 & 9 \\ \hline \text{Doubled to }2d & 0 & 2 & 4& 6& 8& 10 & 12& 14& 16 & 18 \\ \hline \text{Contribution to final sum} & 0 & 2& 4& 6& 8 & 1 & 3 & 5 & 7 & 9 \\\hline \text{Difference modulo 10} & 0 & 1 & 2 & 3 & 4 & 6 & 7 & 8 & 9 & 0 \end{array} $$

This means that if you mistype a single digit, the Luhn checksum will come out differently, and if you accidentally interchange two neighboring digits (thereby switching which of them gets subjected to the multiply-by-2 permutation) the checksum will be different too -- except if the digits being switched are $0$ and $9$, because each of those has the same difference (namely zero) between permuted and non-permuted.

The inability to catch $09\leftrightarrow 90$ interchanges is a weakness of the algorithm, and new applications outside the "card number" universe generally pick a check-digit principle that gives better guarantees.