一对一整数映射函数

Question

我们正在使用MySQL并开发一个应用程序,我们希望ID序列不被公开显示...... ID几乎不是绝密的,如果有人确实能够对它们进行解码,则没有重大问题.

因此,哈希当然是显而易见的解决方案,我们目前正在使用MD5 ... 32位整数进入,我们将MD5修剪为64位然后存储它.但是,我们不知道当你这样修剪时碰撞的可能性(特别是因为所有数字都来自自动增量或当前时间).我们目前检查是否存在冲突,但由于我们可能会同时插入100,000行,因此性能非常糟糕(无法批量插入).

但最后,我们真的不需要哈希提供的安全性,它们会消耗不必要的空间,还需要一个额外的索引...所以,有没有任何简单而且足够好的函数/算法可以保证一个任何数字的一个映射,没有明显的序列号视觉模式？

编辑:我使用的PHP默认情况下不支持整数运算,但在环顾四周后我发现它可以通过按位运算符进行廉价复制.32位整数乘法的代码可以在这里找到:http://pastebin.com/np28xhQF

Answer 1

你可以简单地用0xDEADBEEF进行XOR,如果这还不错的话.

或者乘以奇数mod 2 ^ 32.对于逆映射,只需乘以乘法逆

示例:n = 2345678901; multiplicative inverse(mod 2 ^ 32):2313902621对于映射,只需乘以2345678901(mod 2 ^ 32):

1 - > 2345678901 2 - > 396390506

对于逆映射,乘以2313902621.

Answer 2

如果您想确保 1:1 映射，则使用加密（即排列），而不是散列。加密必须是 1:1，因为它可以被解密。

如果你想要 32 位数字，那么使用Hasty Pudding Cypher或只写一个简单的四轮 Feistel 密码。

这是我之前准备的一个：

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