Целочисленная функция однозначного отображения

Question

Мы используем MySQL и разрабатываем приложение, в котором мы хотели бы, чтобы последовательность идентификаторов не была общедоступной ... идентификаторы вряд ли являются совершенно секретными, и нет существенной проблемы, если кто-то действительно сможет их декодировать.

Итак, хеш - это, конечно, очевидное решение, мы в настоящее время используем целые числа MD5 ... 32-битные, и мы обрезаем MD5 до 64-бит и затем сохраняем его. Тем не менее, мы не знаем, насколько вероятны столкновения при подобной обрезке (особенно если учесть, что все числа взяты из автоинкремента или текущего времени). В настоящее время мы проверяем наличие коллизий, но поскольку мы можем вставлять 100 000 строк одновременно, производительность ужасна (невозможно массовое добавление).

Но, в конце концов, нам действительно не нужна безопасность, обеспечиваемая хешами, и они занимают ненужное пространство, а также требуют дополнительного индекса ... Итак, есть ли какая-нибудь простая и достаточно хорошая функция / алгоритм, которая гарантирует однозначное сопоставление для любого числа без очевидных визуальных шаблонов для последовательных чисел?

РЕДАКТИРОВАТЬ: я использую PHP, который не поддерживает целочисленную арифметику по умолчанию, но после осмотра я обнаружил, что это может быть дешево реплицировано с побитовыми операторами. Код для умножения 32-битного целого числа можно найти здесь: http://pastebin.com/np28xhQF

Answer 1

Вы можете просто выполнить XOR с 0xDEADBEEF, если этого достаточно.

В качестве альтернативы умножьте на нечетное число mod 2 ^ 32.Для обратного отображения просто умножьте на мультипликативное обратное

Пример: n = 2345678901;мультипликативный обратный (мод 2 ^ 32): 2313902621 Для отображения просто умножьте на 2345678901 (мод 2 ^ 32):

1 -> 2345678901 2 -> 396390506

для обратного отображенияумножьте на 2313902621.

Answer 2

Если вы хотите обеспечить отображение 1: 1, используйте шифрование (то есть перестановку), а не хеш.Шифрование должно быть 1: 1, потому что оно может быть расшифровано.

Если вы хотите 32-битные числа, используйте Hasty Pudding Cypher или просто напишите простой четырехугольный шифр Фейстеля.

Вот тот, который я подготовил ранее:

import java.util.Random;

/**
 * IntegerPerm is a reversible keyed permutation of the integers.
 * This class is not cryptographically secure as the F function
 * is too simple and there are not enough rounds.
 *
 * @author Martin Ross
 */
public final class IntegerPerm {
    //////////////////
    // Private Data //
    //////////////////

    /** Non-zero default key, from www.random.org */
    private final static int DEFAULT_KEY = 0x6CFB18E2;

    private final static int LOW_16_MASK = 0xFFFF;
    private final static int HALF_SHIFT = 16;
    private final static int NUM_ROUNDS = 4;

    /** Permutation key */
    private int mKey;

    /** Round key schedule */
    private int[] mRoundKeys = new int[NUM_ROUNDS];

    //////////////////
    // Constructors //
    //////////////////

    public IntegerPerm() { this(DEFAULT_KEY); }

    public IntegerPerm(int key) { setKey(key); }

    ////////////////////
    // Public Methods //
    ////////////////////

    /** Sets a new value for the key and key schedule. */
    public void setKey(int newKey) {
        assert (NUM_ROUNDS == 4) : "NUM_ROUNDS is not 4";
        mKey = newKey;

        mRoundKeys[0] = mKey & LOW_16_MASK;
        mRoundKeys[1] = ~(mKey & LOW_16_MASK);
        mRoundKeys[2] = mKey >>> HALF_SHIFT;
        mRoundKeys[3] = ~(mKey >>> HALF_SHIFT);
    } // end setKey()

    /** Returns the current value of the key. */
    public int getKey() { return mKey; }

    /**
     * Calculates the enciphered (i.e. permuted) value of the given integer
     * under the current key.
     *
     * @param plain the integer to encipher.
     *
     * @return the enciphered (permuted) value.
     */
    public int encipher(int plain) {
        // 1 Split into two halves.
        int rhs = plain & LOW_16_MASK;
        int lhs = plain >>> HALF_SHIFT;

        // 2 Do NUM_ROUNDS simple Feistel rounds.
        for (int i = 0; i < NUM_ROUNDS; ++i) {
            if (i > 0) {
                // Swap lhs <-> rhs
                final int temp = lhs;
                lhs = rhs;
                rhs = temp;
            } // end if
            // Apply Feistel round function F().
            rhs ^= F(lhs, i);
        } // end for

        // 3 Recombine the two halves and return.
        return (lhs << HALF_SHIFT) + (rhs & LOW_16_MASK);
    } // end encipher()

    /**
     * Calculates the deciphered (i.e. inverse permuted) value of the given
     * integer under the current key.
     *
     * @param cypher the integer to decipher.
     *
     * @return the deciphered (inverse permuted) value.
     */
    public int decipher(int cypher) {
        // 1 Split into two halves.
        int rhs = cypher & LOW_16_MASK;
        int lhs = cypher >>> HALF_SHIFT;

        // 2 Do NUM_ROUNDS simple Feistel rounds.
        for (int i = 0; i < NUM_ROUNDS; ++i) {
            if (i > 0) {
                // Swap lhs <-> rhs
                final int temp = lhs;
                lhs = rhs;
                rhs = temp;
            } // end if
            // Apply Feistel round function F().
            rhs ^= F(lhs, NUM_ROUNDS - 1 - i);
        } // end for

        // 4 Recombine the two halves and return.
        return (lhs << HALF_SHIFT) + (rhs & LOW_16_MASK);
    } // end decipher()

    /////////////////////
    // Private Methods //
    /////////////////////

    // The F function for the Feistel rounds.
    private int F(int num, int round) {
        // XOR with round key.
        num ^= mRoundKeys[round];
        // Square, then XOR the high and low parts.
        num *= num;
        return (num >>> HALF_SHIFT) ^ (num & LOW_16_MASK);
    } // end F()

} // end class IntegerPerm

Answer 3

Сделайте то, что сказал Хенрик в своем втором предложении. Но так как эти значения, похоже, используются людьми (иначе вы не захотите их рандомизировать). Сделай еще один шаг. Умножьте порядковый номер на большое простое число и уменьшите mod N, где N - степень 2. Но выберите N на 2 бита меньше, чем вы можете сохранить. Затем умножьте результат на 11 и используйте его. Итак имеем:

Hash = ((count * large_prime)% 536870912) * 11

Умножение на 11 защищает от большинства ошибок ввода данных - если какая-либо цифра будет введена неправильно, результат не будет кратен 11. Если какие-либо 2 цифры будут транспонированы, результат не будет кратен 11. Так что Предварительная проверка любого введенного значения, вы проверяете, делится ли оно на 11, прежде чем даже искать в базе данных.

Answer 4

Вы можете использовать мод операции для большого простого числа.

ваш номер * большое простое число 1 / большое простое число 2.

Простое число 1 должно быть больше второго. Секунды должны быть близки к 2 ^ 32, но меньше его. Чем это будет трудно заменить.

Prime 1 и Prime 2 должны быть константами.