The Damm algorithm is a fantastic check digit algorithm that detects all single-digit errors and all adjacent transposition errors. It detects all occurrences of altering one single digit and all occurrences of transposing two adjacent digits, the two most frequent transcription errors. The Damm algorithm also has the benefit that prepending leading base encoding zeros does not affect the check digit so you can use it on fixed size strings. All in all it is a great algorithm for checking if there have been any user errors when entering a number.
The only problem with the Damm algorithm is that all the current implementations are base 10 (0-9) only. I wanted to be able to use it to check alpha-numerical strings (passwords) so I wrote a base32 implementation of the Damm algorithm in C/C++. With the commonly confused characters (0/o and 1/l/i) avoided in the base32 encoding you can make a rather nice password checker. Any desired encoding scheme with 32 characters (or less) can be used.
I use the damn32 program in a bash one-liner to generate 10 (9 + the damn check) character password strings. You can make longer or shorter strings by changing the head -c switch.
# openssl rand -base64 50 | tr -dc '23456789abcdefghjkmnpqrstuvwxyz' | head -c9 | xargs damn32
Here is the code for damn32.c. It can be compiled with gcc using:
# gcc damn32.c -o damn32
I will to port this to javascript and php when I get the chance, but if someone wants to do it now I am happy to link to your code or post it here.
Edit.Thanks Michael for pointing out that due to some stupidity on my behalf the code got called damn.c not damm.c – I have updated the post title, but I will leave the code as is as a reminder to be more careful next time :)
#include/* Base32 implementation of the Damm error detection algorithm in C Copyright (c) 2014, Daniel Tillett All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. BACKGROUND The Damm algorithm is a check digit algorithm that detects all single-digit errors and all adjacent transposition errors. It detects all occurrences of altering one single digit and all occurrences of transposing two adjacent digits, the two most frequent transcription errors. The Damm algorithm has the benefit that it makes do without the dedicatedly constructed permutations and its position specific powers being inherent in the Verhoeff scheme. Prepending leading base encoding zeros does not affect the check digit. https://en.wikipedia.org/wiki/Damm_algorithm */ /* A base32 (or less) encoding. With this example encoding the base 0 is '2' and contains 31 characters that avoids using characters that could be confused with each other (i.e. 0/o or 1/i/l). The encoding can be any scheme with 32 or less characters. To change the encoding update encodeLen and base32 to the desired values. In this example on 31 characters are used */ const int encodeLen = 31; const char base32[encodeLen] = "23456789abcdefghjkmnpqrstuvwxyz"; /* Returns index position of the base32 digit if the digit exists in the base32 string or encodeLen if not. */ int base32Index(char p) { int i; for (i = 0; i < encodeLen; i++) { if (p == base32[i]) { break; } } return i; } /* Damn algorithm base32 check digit calculator. Returns the base32 check digit defined by the base32 string or '-' if the base32 number contains a character that is not defined in the base32 string. Input must be a null terminated C string. */ char damm32Encode(char *code) { int i, interim = 0; char *p; /* WTA quasigroup matrix of order 32 http://stackoverflow.com/questions/23431621/extending-the-damm-algorithm-to-base-32 This was constructed according to Damm Lemma 5.2 by Michael (http://stackoverflow.com/users/3625116/michael) I suspect this Michael is the Michael Damm, but I really don't know :) */ char damm32Matrix[32][32] = { { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 3, 1, 7, 5, 11, 9, 15, 13, 19, 17, 23, 21, 27, 25, 31, 29}, { 2, 0, 6, 4, 10, 8, 14, 12, 18, 16, 22, 20, 26, 24, 30, 28, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31}, { 4, 6, 0, 2, 12, 14, 8, 10, 20, 22, 16, 18, 28, 30, 24, 26, 7, 5, 3, 1, 15, 13, 11, 9, 23, 21, 19, 17, 31, 29, 27, 25}, { 6, 4, 2, 0, 14, 12, 10, 8, 22, 20, 18, 16, 30, 28, 26, 24, 5, 7, 1, 3, 13, 15, 9, 11, 21, 23, 17, 19, 29, 31, 25, 27}, { 8, 10, 12, 14, 0, 2, 4, 6, 24, 26, 28, 30, 16, 18, 20, 22, 11, 9, 15, 13, 3, 1, 7, 5, 27, 25, 31, 29, 19, 17, 23, 21}, {10, 8, 14, 12, 2, 0, 6, 4, 26, 24, 30, 28, 18, 16, 22, 20, 9, 11, 13, 15, 1, 3, 5, 7, 25, 27, 29, 31, 17, 19, 21, 23}, {12, 14, 8, 10, 4, 6, 0, 2, 28, 30, 24, 26, 20, 22, 16, 18, 15, 13, 11, 9, 7, 5, 3, 1, 31, 29, 27, 25, 23, 21, 19, 17}, {14, 12, 10, 8, 6, 4, 2, 0, 30, 28, 26, 24, 22, 20, 18, 16, 13, 15, 9, 11, 5, 7, 1, 3, 29, 31, 25, 27, 21, 23, 17, 19}, {16, 18, 20, 22, 24, 26, 28, 30, 0, 2, 4, 6, 8, 10, 12, 14, 19, 17, 23, 21, 27, 25, 31, 29, 3, 1, 7, 5, 11, 9, 15, 13}, {18, 16, 22, 20, 26, 24, 30, 28, 2, 0, 6, 4, 10, 8, 14, 12, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15}, {20, 22, 16, 18, 28, 30, 24, 26, 4, 6, 0, 2, 12, 14, 8, 10, 23, 21, 19, 17, 31, 29, 27, 25, 7, 5, 3, 1, 15, 13, 11, 9}, {22, 20, 18, 16, 30, 28, 26, 24, 6, 4, 2, 0, 14, 12, 10, 8, 21, 23, 17, 19, 29, 31, 25, 27, 5, 7, 1, 3, 13, 15, 9, 11}, {24, 26, 28, 30, 16, 18, 20, 22, 8, 10, 12, 14, 0, 2, 4, 6, 27, 25, 31, 29, 19, 17, 23, 21, 11, 9, 15, 13, 3, 1, 7, 5}, {26, 24, 30, 28, 18, 16, 22, 20, 10, 8, 14, 12, 2, 0, 6, 4, 25, 27, 29, 31, 17, 19, 21, 23, 9, 11, 13, 15, 1, 3, 5, 7}, {28, 30, 24, 26, 20, 22, 16, 18, 12, 14, 8, 10, 4, 6, 0, 2, 31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1}, {30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0, 29, 31, 25, 27, 21, 23, 17, 19, 13, 15, 9, 11, 5, 7, 1, 3}, { 3, 1, 7, 5, 11, 9, 15, 13, 19, 17, 23, 21, 27, 25, 31, 29, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30}, { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 2, 0, 6, 4, 10, 8, 14, 12, 18, 16, 22, 20, 26, 24, 30, 28}, { 7, 5, 3, 1, 15, 13, 11, 9, 23, 21, 19, 17, 31, 29, 27, 25, 4, 6, 0, 2, 12, 14, 8, 10, 20, 22, 16, 18, 28, 30, 24, 26}, { 5, 7, 1, 3, 13, 15, 9, 11, 21, 23, 17, 19, 29, 31, 25, 27, 6, 4, 2, 0, 14, 12, 10, 8, 22, 20, 18, 16, 30, 28, 26, 24}, {11, 9, 15, 13, 3, 1, 7, 5, 27, 25, 31, 29, 19, 17, 23, 21, 8, 10, 12, 14, 0, 2, 4, 6, 24, 26, 28, 30, 16, 18, 20, 22}, { 9, 11, 13, 15, 1, 3, 5, 7, 25, 27, 29, 31, 17, 19, 21, 23, 10, 8, 14, 12, 2, 0, 6, 4, 26, 24, 30, 28, 18, 16, 22, 20}, {15, 13, 11, 9, 7, 5, 3, 1, 31, 29, 27, 25, 23, 21, 19, 17, 12, 14, 8, 10, 4, 6, 0, 2, 28, 30, 24, 26, 20, 22, 16, 18}, {13, 15, 9, 11, 5, 7, 1, 3, 29, 31, 25, 27, 21, 23, 17, 19, 14, 12, 10, 8, 6, 4, 2, 0, 30, 28, 26, 24, 22, 20, 18, 16}, {19, 17, 23, 21, 27, 25, 31, 29, 3, 1, 7, 5, 11, 9, 15, 13, 16, 18, 20, 22, 24, 26, 28, 30, 0, 2, 4, 6, 8, 10, 12, 14}, {17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 18, 16, 22, 20, 26, 24, 30, 28, 2, 0, 6, 4, 10, 8, 14, 12}, {23, 21, 19, 17, 31, 29, 27, 25, 7, 5, 3, 1, 15, 13, 11, 9, 20, 22, 16, 18, 28, 30, 24, 26, 4, 6, 0, 2, 12, 14, 8, 10}, {21, 23, 17, 19, 29, 31, 25, 27, 5, 7, 1, 3, 13, 15, 9, 11, 22, 20, 18, 16, 30, 28, 26, 24, 6, 4, 2, 0, 14, 12, 10, 8}, {27, 25, 31, 29, 19, 17, 23, 21, 11, 9, 15, 13, 3, 1, 7, 5, 24, 26, 28, 30, 16, 18, 20, 22, 8, 10, 12, 14, 0, 2, 4, 6}, {25, 27, 29, 31, 17, 19, 21, 23, 9, 11, 13, 15, 1, 3, 5, 7, 26, 24, 30, 28, 18, 16, 22, 20, 10, 8, 14, 12, 2, 0, 6, 4}, {31, 29, 27, 25, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, 28, 30, 24, 26, 20, 22, 16, 18, 12, 14, 8, 10, 4, 6, 0, 2}, {29, 31, 25, 27, 21, 23, 17, 19, 13, 15, 9, 11, 5, 7, 1, 3, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0} }; for (p = code; *p != '\0'; ++p) { i = base32Index(*p); if (i == encodeLen) { return '-'; } interim = damm32Matrix[interim][i]; } return base32[interim]; } /* Damm32 Check Returns 1 if the base32 number is error free and 0 if it contains an error or the last digit is not equal to the error check digit. */ int damm32Check(char *code) { return (damm32Encode(code) == base32[0]) ? 1 : 0; } /* Prints to stdout the input base32 number, the base32 check digit, and the damm32 check result. */ int main(int argc, char **argv) { if (argc == 2 && argv[1]) { printf("Input: %s\nCheck Digit: %c\nChecked: %d\n", argv[1], damm32Encode(argv[1]), damm32Check(argv[1])); return 1; } else { printf("Usage: damm32 [base32 number]\n"); return 0; } }