Checkdigit algorithm Luhn mod N vs simple sum

Question

Do you know why the Luhn mod N algoritm in order to create the check digit performs a sum by doubling the value of each even placed char instead of perfoming a simple sum of all chars?

In pseudo-code words:

given:

var s = "some string i want to create check digit";

do you know why Luhn mod N does basically this:

for(i from s.length-1 to 0)
   if(i is even)
      checkdigit += chr2int(s[i]) * 2;
   else
      checkdigit += chr2int(s[i]);

instead of simply doing a sum

for(i from s.length-1 to 0)
   checkdigit += chr2int(s[i]);

they can still both terminate with a mod operation to make the checkdigit fit into one char

return int2chr( chr2int('a') + (checkdigit mod 25) );

As a side note to this question, to whom it may be interested in a graphic representation of the Luhn algorithm that makes it even more simple to understand:

enter image description here

Actually this one is the original Luhn algorithm that does not even needs to use MOD function.

score 5 · Accepted Answer · edited Feb 19 '20 at 15:55

5

Checkdigit characters are designed to prevent accidental mangling of an input, for example when a clerk enters the number via keyboard.

If just a sum is used both strings "ABCD" and "ABDC" would yield the same checksum ("A" + "B" + "C" + "D"), so simple swap errors could happen unnoticed.

However, taking parity into consideration, "ABCD" and "ABDC" will become (2"A" + "B" + 2"C" + "D") and (2"A" + "B" + 2"D" + "C") respectively, which are (likely) different numbers, so in this way we could detect if two characters were inadvertently swapped.

edited Feb 19 '20 at 15:55

Tur1ng

745
8
22

answered Apr 05 '11 at 16:14

SWeko

30,434
10
71
106

Cool! Therefor can we say that if I need a different type of checksum, one that simply needs to check for missing character and not for swapped characters I can simply use a sum? – Marco Demaio Apr 05 '11 at 18:01
@Marco: Not really because swapping is very cheap! – Micromega Apr 05 '11 at 18:54
@epitaph: it's not for efficiency reason that I want to ignore swapping errors. Let's say I want to checkdigit the query part of an url (i.e. `?usr=joe&curr=euro&amount=34`), key/value pairs could be swapped but the url is still valid, so it might be better to ignore swapping errors. – Marco Demaio Apr 05 '11 at 20:19
@Marko: What are you talking about? If the above example would have been swapped then your formula isn't working anymore! Can you give an example, please? – Micromega Apr 05 '11 at 21:25
@epitaph: `s1 = "?usr=joe&curr=euro&amount=34"` to me is identical to `s2 = "?curr=euro&amount=34&usr=joe"` If I calculate checkdigit over `s1` and `s2` using the Luhn mod N formula I would get 2 different checkdigits, whilest with a simple sum (like my formula) I would get the same checkdigit, do you understand now what I'm talking about! – Marco Demaio Apr 06 '11 at 12:08
@Marco: checkdigits are there to detect *any* mangling in the data. s1 and s2 are clearly not identical, so it's reasonable that they should produce different checkdigits. Checkdigits do not offer or request any insight into the nature of the data they're checking. BTW, if you want to check querystrings, there are better metods (split the string into a hashtable, for example) – SWeko Apr 06 '11 at 12:48
@SWeko: splitting the string into an hashtable would not detect a user copying and pasting by mistake this url `"?curr=euro&amount=1"` instead of this one `"?curr=euro&amount=100"` therefore the amount paied by user would be 1$ instead of 100$. A simple checkdigit would detect this mistake. Your answer is perfect for the question I posted, I was simply considering in comments another idea, just not to post a new question. – Marco Demaio Apr 07 '11 at 12:08
@Marco: for parameter validation, I would recommend some sort of signature parameter (take a look at the Facebook and Twitter API's for an example). – SWeko Apr 07 '11 at 12:53

Checkdigit algorithm Luhn mod N vs simple sum

1 Answers1