javascript - 创建一个简单的单向哈希

Question

是否有任何标准散列函数/方法可以将任意 9 位整数映射到另一个（唯一）9 位整数，使得映射回来有些困难（不使用蛮力）。

哈希不应该发生冲突，因此每个输出都1 ≤ y < 10^9需要从一个且只有一个输入值映射到1 ≤ x < 10^9.

Answer 1

您描述的问题实际上是格式保留加密旨在解决的问题。

NIST目前正在制定一项标准：用于分组密码的新 FFX 加密模式。

不过，它可能比您预期的要复杂。我在 Javascript 中找不到任何实现，但其他语言中存在一些示例：here (Python) 或here (C++)。

Answer 2

您需要一个只有大约 30 位的非冲突哈希函数。对于任何散列函数来说，这都是一项艰巨的任务。实际上，您需要的不是诸如哈希之类的伪随机函数，而是伪随机排列。

您可以为此使用加密功能，但您显然需要对密钥保密。此外，加密通常使用位作为输入和输出，并且10^9不太可能使用确切数量的位。因此，如果您要选择这样的选项，您可能必须使用格式保留加密。

您还可以使用组 0..10^9-1 中的任何其他 PRP 函数（在将值递减 1 之后），但如果攻击者发现您使用的参数，那么恢复就变得非常简单到原来的。一个例子是与一个与 10^9-1 互质的数字相乘，以 10^9-1 为模。

Answer 3

这是我能想到的：

var used = {};

var hash = function (num) {
    num = md5(num);
    if (used[num] !== undefined) {
        return used[num];
    } else {
        var newNum;
        do {
            newNum = Math.floor(Math.random() * 1000000000) + 1;
        } while (contains(newNum))
        used[num] = newNum;
        return newNum;
    }
};

var contains = function (num) {
    for (var i in used) {
        if (used[i] === num) {
            return true;
        }
    }
    return false;
};

var md5 = function (num) {
    //method that return an md5 (or any other) hash
};

但是我应该注意，当您尝试散列许多不同的数字时会遇到问题，因为这do..while会产生随机数并将它们与已经生成的数字进行比较。如果您已经生成了很多数字，那么您将越来越不可能找到剩余的数字。