Verkhuffa algorithm for an arbitrary even number system

Sometimes there is a task to protect the identifier string from accidental mistakes made by a person. For example, the number of the payment card. For this purpose, a specially calculated check digit is added to the line, and when a person enters this number, you can do an initial check for errors without accessing the database. The simplest option is to add the remainder of dividing the sum of all digits by 10, in which case the distortion of any single digit (including the control) will be easy to detect, and such a line will not pass the test. But some other errors such checksum will miss, for example, rearrangement of two digits in places, and this is also a fairly common mistake.

To protect bank card numbers, a slightly more complicated algorithm, the Moon algorithm, was chosen . One modification has been added to it: the numbers standing in even places are multiplied by 2 before summing (and if more than nine is obtained, then 9 is subtracted). This makes it possible to catch, in addition to the distortion of any digit, the majority (although not all) of the permutations of neighboring digits.

Are there any algorithms that can detect any permutation of neighboring digits (in addition to the distortion of any single digit)? Yes, there are, although for some reason they are not very common. These are the Verhuff algorithm based on dihedral groups, and Damm's algorithm , which is based on Damm quasigroups. It sounds scary, but in fact there is nothing complicated (for those who are familiar with the concept of "group").

Jacobus Verhoeff, a Dutch mathematician and sculptor (one of his sculptures in the photo), proposed an algorithm based on dihedral groups. A dihedral group is a symmetry group of a regular N-gon, including both rotations and axial symmetries. Such a group is not commutative: if a regular polygon with renumbered vertices is first symmetrically displayed, and then rotated, then in most cases it will not be the same as if you first rotate and then display. Therefore, when sequentially “multiplying” the digits of the original string, using the operation of the dihedral group, i.e. consistently applying the rotation and symmetric mapping operations on the correct N-gon, we get protection against most permutations. From the majority, but still not from everyone. Verkhuff proposed to improve this algorithm, and before multiplying, replace each digit with another in a special table, depending on the location of the digit in the row. The table is obtained from one permutation by applying it consistently to the previous result, and after 8 such applications we come to the original order, so you can build an 8x10 table in advance and take the value from there. Some of these permutations allow you to determine all 100% of possible errors in the order of the adjacent digits of the source line, that is, this is a complete and correct solution to the problem of finding a check digit that protects against these two types of errors. Apparently, Verhuffff found a successful permutation by random selection, there are quite a few of them. Some of these permutations allow you to determine all 100% of possible errors in the order of the adjacent digits of the source line, that is, this is a complete and correct solution to the problem of finding a check digit that protects against these two types of errors. Apparently, Verhuffff found a successful permutation by random selection, there are quite a few of them. Some of these permutations allow you to determine all 100% of possible errors in the order of the adjacent digits of the source line, that is, this is a complete and correct solution to the problem of finding a check digit that protects against these two types of errors. Apparently, Verhuffff found a successful permutation by random selection, there are quite a few of them.

The question of whether there are groups that allow one to find any permutations of neighboring numbers without additional modifications has remained open for a long time. And already in the 21st century, in 2004, the German mathematician Michael Damm proved the existence of such groups, they are called weakly totally anti-symmetric quazigroup. I have not fully understood the way of their construction, anyone can try to do it yourself by publishing it . And although at a cursory review it doesn’t look so complicated (it’s even strange that the question remained open for so long), for practical implementation there is an easier way: use ready-made tables .

We now turn to the following and the main question: what to do if you want to protect not a string of decimal digits, but a string of arbitrary characters, for example, hexadecimal or base64 or base58? That is, to solve the problem not for the particular case of the decimal number system, but in general.

The Moon algorithm expands to this case without problems, but it is not so interesting, because it does not find all permutations of neighboring numbers. The method of constructing an antisymmetric quasigroup of arbitrary size is not quite clear. For the Verhuff algorithm, the dihedral group of size N is not difficult to construct, but we still need a permutation table, which is also not clear where to take (and even it is not clear whether it exists). Here is the study of the last question I took up.

Googling did nothing, except for individual attempts and the use of “sufficiently good” solutions (that is, those that reveal almost all permutations) for N = 64.

Perhaps, I will not describe all the tried and tested methods of searching for the desired permutation, which did not produce a result. I tried to solve a particular problem: to find a permutation for base64 and base58, which gives protection against changing the order of neighboring digits. Let me just say that attempts to find such a permutation using the method of random or sequential search with different optimization options did not lead to anything. But in the end I found a common solution for any even n.

Permutation is this: For example, for N = 10 it will be:

0, N-1 .. N/2+1, 1 .. N/2



0, 9, 8, 7, 6, 1, 2, 3, 4, 5

This permutation has another remarkable property: it always has a period (for N> = 8) equal to 12, which allows you to build a table 12xN in advance and take a figure from there.

Here is an example of the implementation of the proposed extension of the Verhuff algorithm for base58 (strictly speaking, this is no longer Verkhuff’s algorithm, but its generalization). Not a full-fledged lib, but just a utility, so to speak, proof of concept.

The proof that this permutation possesses the necessary property, and that it has a period of 12, I will provide somehow later. There is too little space on the margin to place it here.