[Из песочницы] Алгоритм Верхуффа для произвольной чётной системы счисления
Иногда возникает задача защитить строку-идентификатор от случайных ошибок, сделанных человеком. Например, номер платёжной карты. Для этого к строке добавляется вычисленная специальным образом контрольная цифра, и когда человек вводит этот номер, можно сделать первичную проверку на ошибки без обращения к базе данных. Самый простой вариант — добавить остаток от деления суммы всех цифр на 10, в таком случае искажение любой одной цифры (в том числе контрольной) будет легко обнаружить, и такая строка не пройдёт проверку. Но некоторые другие ошибки такая контрольная сумма пропустит, например, перестановку двух цифр местами, а это тоже довольно распространённая ошибка.
Для защиты номеров банковских карт выбран несколько более сложный алгоритм, алгоритм Луна. В нём добавлена одна модификация: цифры, стоящие на чётных местах, перед суммированием умножаются на 2 (а если получается больше девяти, то вычитается 9). Это позволяет словить помимо искажения любой цифры большинство (хотя и не все) перестановок соседних цифр.
Существуют ли алгоритмы, позволяющие обнаружить любые перестановки соседних цифр (помимо искажения любой одиночной цифры)? Да, существуют, хотя они почему-то не очень распространены. Это алгоритм Верхуффа, основанный на диэдральных группах, и алгоритм Дамма, который основан на квазигруппах Дамма. Звучит пугающе, но на самом деле там нет ничего сложного (для тех, кто знаком с понятием «группа»).
Якоб Верхуфф (Jacobus Verhoeff), нидерландский математик и скульптор (на фотографии одна из его скульптур), предложил алгоритм на основании диэдральных групп. Диэдральная группа — это группа симметрий правильного N-угольника, включающая как вращения, так и осевые симметрии. Такая группа не является коммутативной: если правильный многоугольник с перенумерованными вершинами сначала симметрично отобразить, а потом повернуть, то в большинстве случаев получится не то же самое, что если сначала повернуть, а потом отобразить. А поэтому при последовательном «умножении» цифр исходной строки, используя операцию диэдральной группы, т.е. последовательно применяя операции поворота и симметричного отображения над правильным N-угольником, мы получим защиту от большинства перестановок. От большинства, но всё-таки опять не от всех. Верхуфф предложил усовершенствовать этот алгоритм, и перед умножением каждую цифру заменять на другую по специальной таблице, в зависимости от места цифры в строке. Таблица получена из одной перестановки путём последовательного её применения к предыдущему результату, и через 8 таких применений мы приходим к исходному порядку, поэтому можно заранее построить таблицу 8×10 и брать значение оттуда. Некоторые из таких перестановок позволяют определять все 100% возможных ошибок в порядке соседних цифр исходной строки, то есть это является полным и корректным решением задачи нахождения контрольной цифры, защищающей от этих двух типов ошибок. Судя по всему, удачную перестановку Верхуфф нашёл методом случайного подбора, их таких существует довольно много.
Вопрос о том, существуют ли группы, позволяющие находить любые перестановки соседних цифр без дополнительных модификаций, долгое время оставался открытым. И уже в XXI веке, в 2004 году немецкий математик Michael Damm доказал существование таких групп, они называются слабо полностью антисимметричными квазигруппами (weakly totally anti-symmetric quazigroup). Я не полностью разобрался в способе их построения, желающие могут попробовать это сделать самостоятельно по его публикации. И хотя при беглом просмотре она не выглядит такой уж сложной (даже странно, что вопрос оставался открытым так долго), для практической реализации есть более простой способ: воспользоваться готовыми таблицами.
Теперь перейдём к следующему и основному вопросу: что делать, если нужно защитить не строку десятичных цифр, а строку произвольных символов, например, 16-ричных или base64 или base58? То есть, решить задачу не для частного случая десятичной системы счисления, а в общем виде.
Алгоритм Луна расширяется на этот случай без проблем, но это не так интересно, потому что он находит не все перестановки соседних цифр. Способ построения антисимметричной квазигруппы произвольного размера не вполне понятен. Для алгоритма Верхуффа диэдральная группа размера N строится несложно, но ещё нужна таблица перестановок, которую тоже непонятно, где взять (и даже непонятно, существует ли она). Вот исследованием последнего вопроса я и занялся.
Гугление ничего не дало, кроме отдельных попыток и применения «достаточно хороших» решений (т.е. обнаруживающих почти все перестановки) для N=64.
Пожалуй, не буду описывать все испробованные способы поиска нужной перестановки, которые не дали результата. Я пытался решить частную задачу: найти перестановку для base64 и base58, дающую защиту от изменения порядка соседних цифр. Скажу лишь, что попытки найти такую перестановку методом случайного или последовательного перебора с разными вариантами оптимизации ни к чему не привели. Но в итоге я нашёл общее решение для любого чётного n.
Перестановка такая:
0, N-1 .. N/2+1, 1 .. N/2
Например, для N = 10 это будет:
0, 9, 8, 7, 6, 1, 2, 3, 4, 5
Эта перестановка обладает ещё одним замечательным свойством: у неё период всегда (для N >= 8) равен 12, что позволяет заранее построить таблицу 12xN и брать цифру оттуда.
Вот здесь пример реализации предлагаемого расширения алгоритма Верхуффа для base58 (строго говоря, это уже не алгоритм Верхуффа, а его обобщение). Не полноценная либа, а просто утилитка, так сказать, proof of concept.
Доказательство того, что эта перестановка обладает нужным свойством, и что у неё период 12, я предоставлю как-нибудь потом. На полях слишком мало места, чтобы поместить его здесь.
