Хабрахабр

[Из песочницы] Алгоритм Верхуффа для произвольной чётной системы счисления

КДПВ Иногда возникает задача защитить строку-идентификатор от случайных ошибок, сделанных человеком. Например, номер платёжной карты. Для этого к строке добавляется вычисленная специальным образом контрольная цифра, и когда человек вводит этот номер, можно сделать первичную проверку на ошибки без обращения к базе данных. Самый простой вариант — добавить остаток от деления суммы всех цифр на 10, в таком случае искажение любой одной цифры (в том числе контрольной) будет легко обнаружить, и такая строка не пройдёт проверку. Но некоторые другие ошибки такая контрольная сумма пропустит, например, перестановку двух цифр местами, а это тоже довольно распространённая ошибка.
Для защиты номеров банковских карт выбран несколько более сложный алгоритм, алгоритм Луна. В нём добавлена одна модификация: цифры, стоящие на чётных местах, перед суммированием умножаются на 2 (а если получается больше девяти, то вычитается 9). Это позволяет словить помимо искажения любой цифры большинство (хотя и не все) перестановок соседних цифр.

Да, существуют, хотя они почему-то не очень распространены. Существуют ли алгоритмы, позволяющие обнаружить любые перестановки соседних цифр (помимо искажения любой одиночной цифры)? Звучит пугающе, но на самом деле там нет ничего сложного (для тех, кто знаком с понятием «группа»). Это алгоритм Верхуффа, основанный на диэдральных группах, и алгоритм Дамма, который основан на квазигруппах Дамма.

Диэдральная группа — это группа симметрий правильного N-угольника, включающая как вращения, так и осевые симметрии. Якоб Верхуфф (Jacobus Verhoeff), нидерландский математик и скульптор (на фотографии одна из его скульптур), предложил алгоритм на основании диэдральных групп. А поэтому при последовательном «умножении» цифр исходной строки, используя операцию диэдральной группы, т.е. Такая группа не является коммутативной: если правильный многоугольник с перенумерованными вершинами сначала симметрично отобразить, а потом повернуть, то в большинстве случаев получится не то же самое, что если сначала повернуть, а потом отобразить. От большинства, но всё-таки опять не от всех. последовательно применяя операции поворота и симметричного отображения над правильным N-угольником, мы получим защиту от большинства перестановок. Таблица получена из одной перестановки путём последовательного её применения к предыдущему результату, и через 8 таких применений мы приходим к исходному порядку, поэтому можно заранее построить таблицу 8x10 и брать значение оттуда. Верхуфф предложил усовершенствовать этот алгоритм, и перед умножением каждую цифру заменять на другую по специальной таблице, в зависимости от места цифры в строке. Судя по всему, удачную перестановку Верхуфф нашёл методом случайного подбора, их таких существует довольно много. Некоторые из таких перестановок позволяют определять все 100% возможных ошибок в порядке соседних цифр исходной строки, то есть это является полным и корректным решением задачи нахождения контрольной цифры, защищающей от этих двух типов ошибок.

И уже в XXI веке, в 2004 году немецкий математик Michael Damm доказал существование таких групп, они называются слабо полностью антисимметричными квазигруппами (weakly totally anti-symmetric quazigroup). Вопрос о том, существуют ли группы, позволяющие находить любые перестановки соседних цифр без дополнительных модификаций, долгое время оставался открытым. И хотя при беглом просмотре она не выглядит такой уж сложной (даже странно, что вопрос оставался открытым так долго), для практической реализации есть более простой способ: воспользоваться готовыми таблицами. Я не полностью разобрался в способе их построения, желающие могут попробовать это сделать самостоятельно по его публикации.

То есть, решить задачу не для частного случая десятичной системы счисления, а в общем виде. Теперь перейдём к следующему и основному вопросу: что делать, если нужно защитить не строку десятичных цифр, а строку произвольных символов, например, 16-ричных или base64 или base58?

Способ построения антисимметричной квазигруппы произвольного размера не вполне понятен. Алгоритм Луна расширяется на этот случай без проблем, но это не так интересно, потому что он находит не все перестановки соседних цифр. Вот исследованием последнего вопроса я и занялся. Для алгоритма Верхуффа диэдральная группа размера N строится несложно, но ещё нужна таблица перестановок, которую тоже непонятно, где взять (и даже непонятно, существует ли она).

обнаруживающих почти все перестановки) для N=64. Гугление ничего не дало, кроме отдельных попыток и применения «достаточно хороших» решений (т.е.

Я пытался решить частную задачу: найти перестановку для base64 и base58, дающую защиту от изменения порядка соседних цифр. Пожалуй, не буду описывать все испробованные способы поиска нужной перестановки, которые не дали результата. Но в итоге я нашёл общее решение для любого чётного n. Скажу лишь, что попытки найти такую перестановку методом случайного или последовательного перебора с разными вариантами оптимизации ни к чему не привели.

Перестановка такая:

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

Например, для N = 10 это будет:

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

Эта перестановка обладает ещё одним замечательным свойством: у неё период всегда (для N >= 8) равен 12, что позволяет заранее построить таблицу 12xN и брать цифру оттуда.

Не полноценная либа, а просто утилитка, так сказать, proof of concept. Вот здесь пример реализации предлагаемого расширения алгоритма Верхуффа для base58 (строго говоря, это уже не алгоритм Верхуффа, а его обобщение).

На полях слишком мало места, чтобы поместить его здесь. Доказательство того, что эта перестановка обладает нужным свойством, и что у неё период 12, я предоставлю как-нибудь потом.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть