Extension of the Damm algorithm to base-32

Question

I would like to use the Damm algorithm to generate check digits for codes with a 32-character alphabet. The algorithm itself is easily applied to any database (except 2 or 6). Difficulty is a necessary lookup table, which should be a fully antisymmetric quasigroup with a single character (usually 0) along the main diagonal.

The Wikipedia page gives a table for base 10, and the Python implementation gives a table for base-16 , but I did not find an example of base 32. Does anyone have a suitable table for base 32?

Answer 1

Inspired by David Eisenstat (and the original Damm dissertation he cites), here is a simple Python procedure for calculating / checking the Damm checksum for any 2 ⁿ base for 2 & le; n? 32:

# reduction bitmasks for GF(2^n), 2 <= n <= 32 masks = (3, 3, 3, 5, 3, 3, 27, 3, 9, 5, 9, 27, 33, 3, 43, 9, 9, 39, 9, 5, 3, 33, 27, 9, 27, 39, 3, 5, 3, 9, 141) # calculate Damm checksum for base 2^n def damm2n (digits, n): modulus = (1 << n) mask = modulus | masks[n - 2] checksum = 0 for digit in digits: checksum ^= digit checksum <<= 1 if checksum >= modulus: checksum ^= mask return checksum 

The routine accepts a list (or, more generally, iterable) of digits that are considered integers in the range from 0 to 2 ⁿ & minus; 1 inclusive, and the number n bits per digit (it is assumed that it is in the range from 2 to 32 inclusive).

The completely asymmetric quasigroup used by this implementation of the Damm algorithm is defined by the map (a, b) & mapsto; 2 & otimes; (a? oplus; b) where? denotes adding to the final field GF (2 ⁿ ) (which is just a bitwise XOR), & otimes; denotes multiplication in GF (2 ⁿ ) , and 2 denotes the element represented by the bit string 0 ... 010 ₂ in the normal n-bit representation of GF (2 ⁿ ).

This is equivalent to the map (a, b) & mapsto; ( 2 otimes; a)? b is given by Dam in Example 5.2 of his thesis, except that the input digits b are rearranged (by multiplying them by 2 in GF (2 ⁿ )) to ensure that (a, a) & mapsto; 0 for all a. This is equivalent to rearranging the columns of the quasigroup operation table, so the diagonal is all zeros and allows you to check the checksum simply by adding it to the original input and verifying that the new extended input checksum is zero.

Multiplication of GF (2 ⁿ ) by 2 is performed using the usual left shift trick by one and, if the nth bit of the result is set, XORing with a bit mask corresponding to a monomial irreducible polynomial of order n. The specific bitmasks used are taken from the table of the low-weight table. Irreducible polynomials from Gadiel Seroussi (1998) . If you (for some reason) need checksums for databases larger than 2 ^32, their table reaches as much as 2 ¹⁰⁰⁰⁰ . The Serusi table lists the indicators of nonzero coefficients of each reduction polynomial, excluding the constant term; the bitmasks in the above code are obtained by discarding the highest exponent (which is always n), summing 2 ^k for other exponents k and adding 1. (Thus, for example, writing "8, 4,3,1" for n = 8 gives a mask 2 ⁴ + 2 ³ + 2 ¹ + 1 = 16 + 8 + 2 + 1 = 27.)

In particular, the above code gives, for n = 4, the results corresponding to JoomlaShells in accordance with the 16 Damm checksum base . This is not guaranteed at all, since there are many possible ways to implement the Damm checksum for a given database, but in this case the quasigroups used by these two implementations coincide.

---

Ps. Here's the Python code for printing a lookup table in a format similar to the one used in the Wikipedia article. (Thanks to CJM for the initial version.)

 alphabet = '0123456789ABCDEFGHJKLMNPQRTUVWXY' # avoids easy-to-confuse characters bits = 5 # find out which first single-digit input gives which checksum r = [-1] * 2**bits for i in range(2**bits): r[damm2n([i], bits)] = i # print header print ' |', ' '.join(alphabet) print '--+' + '--' * len(alphabet) # print rest of table for i in range(2**bits): row = (alphabet[damm2n([r[i], j], bits)] for j in range(2**bits)) print alphabet[i], '|', ' '.join(row) 

Answer 2

To summarize the discussion below: we need a table with zeros on the main diagonal. Niklas and I have the impression that instead of being an integral part of the algorithm, this property is to avoid solving the equation x * y = 0 in y for x, where * is a quasigroup operation. With zeros on the main diagonal, we have x = y, but without, we can calculate y through one search in the 32-element table.

The construction that Damm describes is problematic because it has the desired property if and only if a = -1, but in characteristic 2 we have 1 = -1. Z3 constraint resolver did not help.

---

Damme dissertation (in German) here . The corresponding definition is that the Latin square is completely antisymmetric iff [for all x and y, the element (x, y) is equal to the element (y, x) iff x = y]. Damm gives a construction for a prime cardinality n other than 2 (including the case n = 32), considering the element (x, y) to be * x + y, where a is neither 0 nor 1, but * is a multiplication by an n -element Galois field (Beispiel 5.2).

The following is an instance of this method for n = 32.

 [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31], [2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13, 18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 24, 25, 30, 31, 28, 29], [4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11, 20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27], [6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9, 22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25], [8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23], [10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5, 26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21], [12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3, 28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19], [14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1, 30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17], [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], [18, 19, 16, 17, 22, 23, 20, 21, 26, 27, 24, 25, 30, 31, 28, 29, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13], [20, 21, 22, 23, 16, 17, 18, 19, 28, 29, 30, 31, 24, 25, 26, 27, 4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11], [22, 23, 20, 21, 18, 19, 16, 17, 30, 31, 28, 29, 26, 27, 24, 25, 6, 7, 4, 5, 2, 3, 0, 1, 14, 15, 12, 13, 10, 11, 8, 9], [24, 25, 26, 27, 28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7], [26, 27, 24, 25, 30, 31, 28, 29, 18, 19, 16, 17, 22, 23, 20, 21, 10, 11, 8, 9, 14, 15, 12, 13, 2, 3, 0, 1, 6, 7, 4, 5], [28, 29, 30, 31, 24, 25, 26, 27, 20, 21, 22, 23, 16, 17, 18, 19, 12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3], [30, 31, 28, 29, 26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0, 1], [5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10, 21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26], [7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 23, 22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24], [1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14, 17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30], [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12, 19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28], [13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2, 29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18], [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16], [9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6, 25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22], [11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4, 27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 20], [21, 20, 23, 22, 17, 16, 19, 18, 29, 28, 31, 30, 25, 24, 27, 26, 5, 4, 7, 6, 1, 0, 3, 2, 13, 12, 15, 14, 9, 8, 11, 10], [23, 22, 21, 20, 19, 18, 17, 16, 31, 30, 29, 28, 27, 26, 25, 24, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8], [17, 16, 19, 18, 21, 20, 23, 22, 25, 24, 27, 26, 29, 28, 31, 30, 1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14], [19, 18, 17, 16, 23, 22, 21, 20, 27, 26, 25, 24, 31, 30, 29, 28, 3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12], [29, 28, 31, 30, 25, 24, 27, 26, 21, 20, 23, 22, 17, 16, 19, 18, 13, 12, 15, 14, 9, 8, 11, 10, 5, 4, 7, 6, 1, 0, 3, 2], [31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0], [25, 24, 27, 26, 29, 28, 31, 30, 17, 16, 19, 18, 21, 20, 23, 22, 9, 8, 11, 10, 13, 12, 15, 14, 1, 0, 3, 2, 5, 4, 7, 6], [27, 26, 25, 24, 31, 30, 29, 28, 19, 18, 17, 16, 23, 22, 21, 20, 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 1, 0, 7, 6, 5, 4]] 

Below is the very harsh Haskell code that did this. This may work for the other two forces. Argument 5 is mainly for 2 ^ 5.

 module Main where import Data.Char import Data.List xs +. ys = simplify (xs ++ ys) xs *. ys = simplify $ do x <- xs y <- ys return (x + y) simplify xs = (reverse . map head . filter (odd . length) . group . sort) xs subseqs [] = [[]] subseqs (x : xs) = let xss = subseqs xs in xss ++ map (x :) xss polys n = subseqs [n, n - 1 .. 0] reduce [] ys = ys reduce xs [] = [] reduce xs@ (x : _) ys@ (y : _) = if x > y then ys else reduce xs (map ((y - x) +) xs +. ys) irred [] = False irred ys@ (y : _) = let xss = polys (y `div` 2) \\ [[0]] in (not . any null . map (flip reduce ys)) xss irreds n = filter irred (polys n) ip n = (head . filter irred . map (n :)) (polys (n - 1)) eval xs = (sum . map (2 ^)) xs timesTable n = let ms = ip n zs = polys (n - 1) !! 2 in do xs <- polys (n - 1) return $ do ys <- polys (n - 1) return (reduce ms ((zs *. xs) +. ys)) verify t = all ((1 ==) . length . filter id) $ zipWith (zipWith (==)) t (transpose t) main = print $ map (map eval) $ timesTable 5 

Answer 3

If you have a TA quasigroup, you can simply rearrange the columns so that 0 are on the main diagonal. Then the quasigroup (in general) is a WTA quasigroup and can be used for the Damm algorithm. I did this for order 32, see the Result below, and it is possible for every order except 2 and 6.

I think that a quasigroup of order 10, which can be found on Wikipedia, is constructed according to Lemma 5.2 of Damm's theses. This is due to the fact that it must still detect phonetic errors after rearranging the columns, so the elements must be renamed, and the rows must be rebuilt accordingly.

Finally, here is the WTA quasigroup of order 32 for the Damm algorithm:

 00 02 04 06 08 10 12 14 16 18 20 22 24 26 28 30 03 01 07 05 11 09 15 13 19 17 23 21 27 25 31 29 02 00 06 04 10 08 14 12 18 16 22 20 26 24 30 28 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 04 06 00 02 12 14 08 10 20 22 16 18 28 30 24 26 07 05 03 01 15 13 11 09 23 21 19 17 31 29 27 25 06 04 02 00 14 12 10 08 22 20 18 16 30 28 26 24 05 07 01 03 13 15 09 11 21 23 17 19 29 31 25 27 08 10 12 14 00 02 04 06 24 26 28 30 16 18 20 22 11 09 15 13 03 01 07 05 27 25 31 29 19 17 23 21 10 08 14 12 02 00 06 04 26 24 30 28 18 16 22 20 09 11 13 15 01 03 05 07 25 27 29 31 17 19 21 23 12 14 08 10 04 06 00 02 28 30 24 26 20 22 16 18 15 13 11 09 07 05 03 01 31 29 27 25 23 21 19 17 14 12 10 08 06 04 02 00 30 28 26 24 22 20 18 16 13 15 09 11 05 07 01 03 29 31 25 27 21 23 17 19 16 18 20 22 24 26 28 30 00 02 04 06 08 10 12 14 19 17 23 21 27 25 31 29 03 01 07 05 11 09 15 13 18 16 22 20 26 24 30 28 02 00 06 04 10 08 14 12 17 19 21 23 25 27 29 31 01 03 05 07 09 11 13 15 20 22 16 18 28 30 24 26 04 06 00 02 12 14 08 10 23 21 19 17 31 29 27 25 07 05 03 01 15 13 11 09 22 20 18 16 30 28 26 24 06 04 02 00 14 12 10 08 21 23 17 19 29 31 25 27 05 07 01 03 13 15 09 11 24 26 28 30 16 18 20 22 08 10 12 14 00 02 04 06 27 25 31 29 19 17 23 21 11 09 15 13 03 01 07 05 26 24 30 28 18 16 22 20 10 08 14 12 02 00 06 04 25 27 29 31 17 19 21 23 09 11 13 15 01 03 05 07 28 30 24 26 20 22 16 18 12 14 08 10 04 06 00 02 31 29 27 25 23 21 19 17 15 13 11 09 07 05 03 01 30 28 26 24 22 20 18 16 14 12 10 08 06 04 02 00 29 31 25 27 21 23 17 19 13 15 09 11 05 07 01 03 03 01 07 05 11 09 15 13 19 17 23 21 27 25 31 29 00 02 04 06 08 10 12 14 16 18 20 22 24 26 28 30 01 03 05 07 09 11 13 15 17 19 21 23 25 27 29 31 02 00 06 04 10 08 14 12 18 16 22 20 26 24 30 28 07 05 03 01 15 13 11 09 23 21 19 17 31 29 27 25 04 06 00 02 12 14 08 10 20 22 16 18 28 30 24 26 05 07 01 03 13 15 09 11 21 23 17 19 29 31 25 27 06 04 02 00 14 12 10 08 22 20 18 16 30 28 26 24 11 09 15 13 03 01 07 05 27 25 31 29 19 17 23 21 08 10 12 14 00 02 04 06 24 26 28 30 16 18 20 22 09 11 13 15 01 03 05 07 25 27 29 31 17 19 21 23 10 08 14 12 02 00 06 04 26 24 30 28 18 16 22 20 15 13 11 09 07 05 03 01 31 29 27 25 23 21 19 17 12 14 08 10 04 06 00 02 28 30 24 26 20 22 16 18 13 15 09 11 05 07 01 03 29 31 25 27 21 23 17 19 14 12 10 08 06 04 02 00 30 28 26 24 22 20 18 16 19 17 23 21 27 25 31 29 03 01 07 05 11 09 15 13 16 18 20 22 24 26 28 30 00 02 04 06 08 10 12 14 17 19 21 23 25 27 29 31 01 03 05 07 09 11 13 15 18 16 22 20 26 24 30 28 02 00 06 04 10 08 14 12 23 21 19 17 31 29 27 25 07 05 03 01 15 13 11 09 20 22 16 18 28 30 24 26 04 06 00 02 12 14 08 10 21 23 17 19 29 31 25 27 05 07 01 03 13 15 09 11 22 20 18 16 30 28 26 24 06 04 02 00 14 12 10 08 27 25 31 29 19 17 23 21 11 09 15 13 03 01 07 05 24 26 28 30 16 18 20 22 08 10 12 14 00 02 04 06 25 27 29 31 17 19 21 23 09 11 13 15 01 03 05 07 26 24 30 28 18 16 22 20 10 08 14 12 02 00 06 04 31 29 27 25 23 21 19 17 15 13 11 09 07 05 03 01 28 30 24 26 20 22 16 18 12 14 08 10 04 06 00 02 29 31 25 27 21 23 17 19 13 15 09 11 05 07 01 03 30 28 26 24 22 20 18 16 14 12 10 08 06 04 02 00