math - propiedades - Función de mapeo entero uno a uno

propiedades de los hash

Question

Estamos utilizando MySQL y desarrollando una aplicación en la que deseamos que la secuencia de ID no sea públicamente visible ... las ID no son muy secretas y no hay un problema significativo si alguien realmente pudo decodificarlas.

Entonces, un hash es, por supuesto, la solución obvia, actualmente estamos usando MD5 ... entran enteros de 32 bits, y recortamos el MD5 a 64bits y luego lo almacenamos. Sin embargo, no tenemos idea de cuán probables son las colisiones cuando se recorta así (especialmente dado que todos los números provienen del autoincrement o de la hora actual). Actualmente verificamos si hay colisiones, pero dado que podemos estar insertando 100.000 filas a la vez, el rendimiento es terrible (no se puede insertar a granel).

Pero al final, realmente no necesitamos la seguridad ofrecida por los hashes y consumen espacio innecesario y también requieren un índice adicional ... entonces, ¿hay alguna función / algoritmo lo suficientemente simple y suficiente que garantice uno-a ¿un mapeo para cualquier número sin patrones visuales obvios para los números secuenciales?

EDITAR: Estoy usando PHP que no admite la aritmética de enteros por defecto, pero después de mirar alrededor descubrí que podría ser replicado de forma económica con operadores bit a bit. El código para la multiplicación de enteros de 32 bits se puede encontrar aquí: http://pastebin.com/np28xhQF

Answer 1

Haz lo que Henrik dijo en su segunda sugerencia. Pero dado que estos valores parecen ser utilizados por personas (de lo contrario, no le conviene aleatorizarlos). Toma un paso adicional. Multiplique el número secuencial por un primo grande y reduzca el mod N, donde N es una potencia de 2. Pero elija N para que sea 2 bits más pequeño que el que puede almacenar. Luego, multiplica el resultado por 11 y úsalo. Entonces tenemos:

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

La multiplicación por 11 protege contra la mayoría de los errores de ingreso de datos: si cualquier dígito se escribe incorrectamente, el resultado no será un múltiplo de 11. Si se transponen 2 dígitos, el resultado no será un múltiplo de 11. Entonces, como verificación preliminar de cualquier valor ingresado, se verifica si es divisible entre 11 antes de siquiera buscar en la base de datos.

Answer 2

Puede usar la operación de modificación para el número principal grande.

su número * gran número primo 1 / gran número primo 2.

El primer número 1 debería ser más grande que el segundo. Los segundos deberían estar cerca de 2 ^ 32 pero menos que eso. Que será difícil de sustituir.

Prime 1 y Prime 2 deben ser constantes.

Answer 3

Si desea garantizar una asignación de 1: 1, utilice una encriptación (es decir, una permutación), no un hash. La encriptación tiene que ser 1: 1 porque se puede descifrar.

Si quieres números de 32 bits, utiliza Hasty Pudding Cypher o simplemente escribe una simple cifra de cuatro letras Feistel.

Aquí hay uno que preparé antes:

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 4

Simplemente podría XOR con 0xDEADBEEF, si eso es suficiente.

Alternativamente, multiplique por un número impar mod 2 ^ 32. Para el mapeo inverso solo multiplique por el inverso multiplicativo

Ejemplo: n = 2345678901; inversión multiplicativa (mod 2 ^ 32): 2313902621 Para el mapeo simplemente multiplique por 2345678901 (mod 2 ^ 32):

1 -> 2345678901 2 -> 396390506

Para el mapeo inverso, multiplica por 2313902621.