Подскажите функцию, похожую на хэш, но короче и без коллизий

#алгоритм #хеширование #множества

Требуется генерировать из последовательных целых, уникальные непоследовательные n-значные
коды. Представьте хэши, серийники, или номера купонов. Целочисленному id от 0 до K
соответствует строго один n-значный код. И важно, чтобы последовательно идущие коды
сильно различались, а не одним-двумя символами.

Пример:

0    KXBR6Z
1    8FLWGG
2    PAZT73


Из-за коллизий и краткости требуемых кодов, популярные хэш-функции не подходят. Криптостойкость
не требуется. Если злодеи разгадают алгоритм, пусть хоть все коды распечатают. Делается
для красоты. Хотя, рассмотреть, от чего зависит сложность отгадывания алгоритма по
X имеющимся на руках кодам тоже интересно!

Вопрос: подскажите алгоритм / функцию f(i) = s для соответствия между множествами
0..K и n-значными ABC123XYZ. Обратная функция была бы тоже интересна: f1(s) = i чтобы
из кода получить целое, либо узнать, что код невалиден. 

Наверняка, задача не нова, но не придумал, как искать ответ. Требуется human-трансляция. )

P.S. ищу именно "математику", алгоритм, а не способ забить в БД уникальные значения,
каждый раз при создании нового, проверяя уникальность.
    

Ответы

Ответ 1

С такой задачей хорошо справляются шифры подстановки. Первое, что Вам надо сделать
- это расширить алфавит (перейти от цифр к буквам, где несколько букв будут соответствовать
одной цифре). Если для Вас очень важно скрыть исходные значение, то имеет смысл предварительно
зашифровать данные блочным или асиметричным шифрованием.
накидал пример кода с подстановкой, результат:
input/encoded/decoded - 123 / efg / 123
input/encoded/decoded - 456 / hij / 456
input/encoded/decoded - 789 / abc / 789
input/encoded/decoded - 012 / def / 012
input/encoded/decoded - 1157232188 / eoiafgpybl / 1157232188

сам код:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Substitution {
    private static final int NUMBER_COUNT = 10;
    private static final int LETTER_COUNT = 26;
    private static final int ZERO_ASCII_CODE = 48;
    private static final int A_CHAR_ASCII_CODE = 97;

    // substitution tables
    private static final Map> numToChar = new HashMap>(
            NUMBER_COUNT);
    private static final Map charToNum = new HashMap(
            LETTER_COUNT);

    // init tables
    static {
        // add list containers
        for (int i = 0; i < NUMBER_COUNT; i++) {
            numToChar.put(Character.valueOf((char) (ZERO_ASCII_CODE + i)),
                    new LinkedList());
        }

        // init substitution table
        for (int i = A_CHAR_ASCII_CODE; i < A_CHAR_ASCII_CODE + LETTER_COUNT; i++) {

            // number = (symbol ascii code) mod 9
            Character num = Character
                    .valueOf((char) (i % NUMBER_COUNT + ZERO_ASCII_CODE));
            Character ch = Character.valueOf((char) i);

            numToChar.get(num).add(ch);
            charToNum.put(ch, num);
        }
    }

    public static void main(String[] args) {
        System.out.println("dumping straight substitution table");
        for (Character num : numToChar.keySet()) {
            System.out.println("num to char - " + num + ", replacements = "
                    + numToChar.get(num));
        }
        System.out.println();
        System.out.println("dumping reverse substitution table");
        for (Character ch : charToNum.keySet()) {
            System.out.println("char to num - " + ch + ", replacements = "
                    + charToNum.get(ch));
        }

        // test
        String[] nums = new String[] { "123", "456", "789", "012", "1157232188" };
        String r = null;
        for (int i = 0; i < nums.length; i++) {
            r = decode(nums[i], true);
            System.out.println("input/encoded/decoded - " + nums[i] + " / " + r
                    + " / " + decode(r, false));
        }

    }

    public static String decode(String input, boolean direction) {
        // result buffer
        StringBuilder b = new StringBuilder(input.length());

        // ensure all latters are in lower case
        String data = input.toLowerCase();

        // store indexes (determines which letter to use when coding a number)
        Map indexes = new HashMap();

        // encode string
        for (int i = 0; i < input.length(); i++) {
            b.append(decode(indexes, data.charAt(i), direction));
        }

        return b.toString();
    }

    // straight - number to letter
    // reverse - letter to number
    private static Character decode(Map indexes, char ch,
            boolean direction) {
        // convert character
        Character character = Character.valueOf(ch);
        if (direction) {
            // get list
            List list = numToChar.get(character);

            // get index to use
            Integer index = indexes.get(character);
            if (null == index) {
                index = Integer.valueOf(0);
            }

            // update index map
            int next = index.intValue() + 1;
            if (next == list.size()) {
                next = 0;
            }

            indexes.put(character, Integer.valueOf(next));

            return list.get(index);
        }

        return charToNum.get(character);
    }
}

Данный пример строго "заточен" под цифры и буквы, но, по аналогии, можно сделать
код который будет делать подстановки отдельных символов и/или их последовательностей


Ответ 2

В качестве одного из плохих вариантов, который, тем не менее, решает задачу, могу
предложить следующий подход (плох он из соображений, описанных ниже): 



  
  Кодировать исходный номер купона N в системе кодирования Base36.
  Дописывать недостающие нули в начало для того, чтобы получить желаемую длину кода.
  Совершать какие-либо битовые преобразования, чтобы коды для N и N + 1 не выглядели
похожими, сохраняющие биективность и эффективную вычислимость обратной функции.
  



Сама по себе постановка задачи немного странная - требуется найти биективную функцию,
для которой существует эффективно вычислимая обратная функция ("чтобы из кода получить
целое"). В такой постановка любой купон или серийник, выданный пользователю, автоматически
уязвим для для реверсинга.



  Если выгода, получаемая с такого купона / серийника / ... окажется достаточной,
то наверняка найдется человек, который найдет обратную функцию, а следовательно, сможет
проэксплуатировать систему.



Если же снять ограничение на эффективную вычислимость обратной функции, то практически
задача теряет смысл, поскольку организовать проверку валидности для произвольно взятого
кода купона становится на порядок сложнее.



  Нужно опять каким-то образом сравнивать хэши кодов купонов, исключать коллизии
и т.п. Мне кажется, что для кодов типа KXBR6Z можно доказать, что с приемлемой с практической
точки зрения вероятностью этого не получится. Хотя, возможно, здесь я упускаю что-то
очевидное. [?]



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



  Попробуйте представить, например, как проставить купону, полученному с помощью
некоторой функции, статус revoked или invalid. Или, скажем, разрешить использовать
какой-либо купон дважды.



Из референсов, которые могут быть полезны:



  
  Create a set of “coupon codes” based on an algorithm (см. про Partial Key Verification).
  [CPAN] CouponCode.


Ответ 3

У нас две задачи: сгенерировать для каждого купона уникальное число. Это называется
perfect hash. Вторая задача - сделать так, чтобы каждому купону соответствовало число
от 0 до N-1. Как решить обе эти задачи одним алгоритмом, я не представляю, но по отдельности
- вполне.
Код купона состоит из 6 символов, каждый из которых может иметь одно из 36 значений.
То есть код представляет собой шестизначное число в 36-ричной системе счисления! К
счастью, такое число укладывается в 32 бита. Можешь проверить по калькулятору, что
36^6 < 2^32.
unsigned to_hash(const char* coupon)
{
    unsigned hash = 0;
    char c;
    for( int i = 0; i < 6; ++i ) {
        c = coupon[i];
        if( c < 'A' ) {
            c -= '0';
        } else {
            c -= '7';
        }
        hash *= 36;
        hash += c;
    }
    return hash;
}

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


Ответ 4

Без коллизий нельзя (если хеш постоянной длины), на общем наборе данных. Для последовательности
чисел, чем md5 с солью и выделение части хеша необходимой длинны не подходит?
upd:
Если алгоритм на серверной стороне, возьми простое: серию, если таковая есть, и свою
уникальную соль. Проверку-то, снова будешь на сервере выполнять, в чем тогда отличие
от функции. Пример:
Серия: 101010
Код: e25019

Для них на сервере:
Серия:101010
Соль(приватные данные): Yap!
Md5(101010Yap!) = e2501912913cd181d4199bcea5dd401c
Выделил 6 символов. Проверил. И ты не зависишь от коллизий.

Единственный минус - утечет соль, или будет слишком маленькая по длине(возможность
перебора) - считай, что придется менять алгоритм (менять соль/править настройки безопасности
и т.п.).