2

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

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

4

3 回答 3

3

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

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

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

于 2013-05-25T16:08:40.553 回答
1

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

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

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

于 2013-05-23T22:23:31.557 回答
0

是我能想到的:

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会产生随机数并将它们与已经生成的数字进行比较。如果您已经生成了很多数字,那么您将越来越不可能找到剩余的数字。

于 2013-05-23T22:29:41.147 回答